The Exercise

A map $f$ from a finite group $G$ to a finite set $X$ hides a subgroup $K$ of $G$ when it is constant on each left coset of $K$ and takes different values on different cosets: $f(g_1) = f(g_2)$ exactly when $g_1 K = g_2 K$. The hidden subgroup problem asks for $K$, given $f$ as an oracle.

A quantum algorithm learns about $K$ by querying $f$ on a uniform superposition of group elements, $m$ of them side by side, and then discarding the answers. What is left is a mixed state of the register that holds the $m$ group elements. The exercise asks how many samples it takes before the states left by two different hidden subgroups are nearly orthogonal.

A Quantum System

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The composite system $S \otimes T$ of two quantum systems $S$ and $T$ is the quantum system whose state space is the tensor product of the state spaces of $S$ and $T$.^✦

A state $\rho$ of $S$, also called a density operator of $S$, is a positive operator of unit trace on the state space of $S$.^✦ A pure state $\psi$ of $S$ is a unit vector $|\psi\rangle$ in the state space of $S$, and it determines the state $|\psi\rangle\langle\psi|$ of $S$, the projector onto $|\psi\rangle$. Two states $\rho$ and $\sigma$ of the same system have as their overlap the real number $\operatorname{Re}\operatorname{tr}(\rho\sigma)$.^✦

The partial trace $\operatorname{Tr}_T(\rho)$ of a state $\rho$ of $S \otimes T$ is the state of $S$ obtained by tracing out $T$ against an orthonormal basis $\{|j\rangle\}$ of the state space of $T$, with $I$ the identity on the state space of $S$, $$\operatorname{Tr}_T(\rho) = \sum_j \bigl(I \otimes \langle j|\bigr)\, \rho\, \bigl(I \otimes |j\rangle\bigr).$$(1)^✦

The Query State

For a finite set $Y$, the system $\mathbb{C}[Y]$ is the quantum system whose state space is the Hilbert space $\mathbb{C}^Y$ itself, the complex functions on $Y$ with the standard inner product; its orthonormal basis vectors $|y\rangle$ are labelled by the elements $y$ of $Y$.^✦

For a map $h$ from a finite set $Y$ to a finite set $Z$, the query vector $|\psi_h\rangle$ is the vector $$|\psi_h\rangle = \frac{1}{\sqrt{|Y|}} \sum_{y \in Y} |y\rangle \otimes |h(y)\rangle$$(2)^✦ of the composite system $\mathbb{C}[Y] \otimes \mathbb{C}[Z]$. The query state $\psi_h$ is the pure state of $\mathbb{C}[Y] \otimes \mathbb{C}[Z]$ with unit vector $|\psi_h\rangle$.^✦

Sampling $m$ group elements at once is a single query of this kind. Write $G^m$ for the set of tuples $(g_1, \dots, g_m)$ of elements of $G$, one entry for each sample, and $f^m \colon G^m \to X^m$ for the map that applies $f$ to every entry, $f^m(g_1, \dots, g_m) = (f(g_1), \dots, f(g_m))$. Tracing the answer register $\mathbb{C}[X^m]$ out of the query state of $f^m$ leaves the state $$\rho_f = \operatorname{Tr}_{X^m}\bigl(|\psi_{f^m}\rangle\langle\psi_{f^m}|\bigr)$$(3) of $\mathbb{C}[G^m]$.

The Claim

What Is Checked

The claim is stated over the reduced states $\rho_f$ and $\rho_{f'}$ of (3), partial traces of the query states of $f^m$ and $f'^{m}$ on $\mathbb{C}[G^m] \otimes \mathbb{C}[X^m]$, and over their overlap.

The library proves that the query vector (2) is a unit vector, so that the query state is a pure state. It proves that the projector onto a unit vector is a density operator and that the partial trace of a density operator is again one, so that $\rho_f$ and $\rho_{f'}$ are states of $\mathbb{C}[G^m]$.