Hidden subgroup problem

The hidden subgroup problem asks for a subgroup $H\le G$ given an oracle $f:G\to X$ that is constant on each left coset of $H$ and takes different values on different cosets. Abelian instances are solved by preparing coset states and applying a group quantum Fourier transform.

For a generator of a group $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^a{x}^{-b}$ hides the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$ of ${\mathbb{Z}}_M^2$. Each fiber is an affine coset $\{(yb+k,b):b\in {\mathbb{Z}}_M\}$. Measuring the function register gives its normalized coset state. Applying the positive-exponent quantum Fourier transform to both input registers gives amplitudeThe finite geometric series vanishes off $c_2=-y{c}_1$ and equals $M$ on that line. Thus each allowed output pair has probability $1/M$, independently of the coset offset. If $\gcd (c_1,M)=1$, a modular inverse recovers $y=-c_2{c}_1^{-1}$.

Let $d=\gcd (c_1,M)$. A supported sample guarantees $d\mid c_2$. Dividing its linear congruence by $d$ gives an invertible coefficient modulo $M/d$ and a unique residue $y_0$ there. The $d$ compatible discrete logarithms modulo $M$ are $y_0+jM/d$ for $0\le j<d$. Only $d=1$ determines the discrete logarithm from the sample alone; $(c_1,c_2)=(0,0)$ conveys no information for $M>1$.

For a finite group $G$, subgroup $H$, and $g\in G$, the coset state is the uniform superposition

For $r\mid N$, a periodic coset state in the computational basis of ${\mathbb{Z}}_N$ isIt is the coset state of the subgroup $r{\mathbb{Z}}_N$ translated by $x_0$.

For a finite abelian group $G$, $U(h)|g⟩=|g+h⟩$ defines the regular representation on the basis labelled by $G$. The linear characters give the common eigenbasisCharacter orthogonality proves orthonormality, and changing variables by the translation in a group proves the eigenvalue formula.

Measuring the coset state $|g_0+K⟩$ in the group shift operator eigenbasis samples uniformly from the annihilator of a subgroup of a finite abelian group $K^{\perp }$. Indeed,so the character-sum cancellation lemma gives probability $|K|/|G|$ on $K^{\perp }$ and zero elsewhere. The modulus of $\chi (g_0)$ is one, so the offset has no effect on the distribution.

Simon's problem asks for the hidden string $p\in \{0,1{\}}^n$ promised by $f(x)=f(y)$ exactly when $x\oplus y\in \{0^n,p\}$. It is the hidden subgroup problem on $({\mathbb{Z}}_2{)}^n$ with hidden subgroup $\{0^n,p\}$.

For an unknown nonzero period, a collision $f(x)=f(y)$ reveals the period $x\oplus y$. Birthday problem sampling finds one using $O(2^{n/2})$ queries with bounded error. A matching lower bound follows by choosing the period and output labels randomly: without a collision, $q$ queries rule out at most $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ candidate periods. For $q=o(2^{n/2})$, almost all periods remain consistent with the transcript. The exponential separation is in query complexity, compared with Simon's algorithm's linear quantum query count.

Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$, and samples vectors $y$ satisfying $y\cdot p=0$ over ${\mathbb{F}}_2$. Repeated samples and Gaussian elimination recover $p$ with $O(n)$ oracle queries and polynomial computation.

With a nonzero hidden period, Simon's algorithm samples uniformly from its $(n-1)$-dimensional orthogonal complement over the binary field. At rank $k$, a new sample raises the rank with probability $1-2^{k-(n-1)}$. Summing the geometric waiting times gives an expected $n-1+{\sum }_{j=1}^{n-1}(2^j-1{)}^{-1}<n+1$ queries. After $n-1+c$ samples, the probability of insufficient rank is less than $2^{-c}$, by a union bound over the nonzero linear functionals that could annihilate all samples.

If the hidden string is zero, one oracle-Hadamard run samples every $y\in {\mathbb{F}}_2^n$ with probability $2^{-n}$. If the hidden string is nonzero, it samples every $y$ satisfying $y\cdot p=0$ with probability $2^{-(n-1)}$ and every other string with probability zero. Pairing $x$ with $x\oplus p$ makes the forbidden amplitudes cancel.

For a subspace $W\le {\mathbb{F}}_2^n$, its orthogonal complement is $W^{\perp }=\{y:x\cdot y=0\text{ for every }x\in W\}$, where the dot product is evaluated modulo two.

For a group action $F:G\times X\to X$ and fixed $x$, the orbit map $f_x(g)=F(g,x)$ hides the stabilizer subgroup $G_x$: $f_x(g)=f_x(h)$ exactly when $h^{-1}g\in G_x$, equivalently when $g$ and $h$ lie in the same left coset of $G_x$.