Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 324 / 4 / b

In the hidden subgroup problem, an oracle gives a function $f:G\to X$ that is constant on every left coset of an unknown subgroup $H\le G$ and takes distinct values on distinct cosets. The task is to determine $H$.

Regard bit strings as the elementary abelian group $G=({\mathbb{Z}}_2{)}^n$ under bitwise exclusive or. The promise saysThus $f$ is constant exactly on the cosets of $H$ and distinct between them. Determining the hidden subgroup determines its nonzero element $p$, so this is Simon's problem as an instance of the hidden subgroup problem.

Prepare $2^{-n/2}{\sum }_x|x⟩|0^n⟩$, query the oracle, and measure or discard the output register. For $p\ne 0$, the input register becomes the coset stateApply $H^{\otimes n}$, the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$. The two amplitudes interfere destructively unless the binary inner product satisfiesand every vector in this orthogonal subspace is sampled uniformly. Repeat until $n-1$ independent equations have been collected, then use Gaussian elimination over ${\mathbb{F}}_2$ to find their one-dimensional null space; its nonzero vector is $p$. This is Simon's algorithm. It uses $O(n)$ oracle queries with high probability and polynomial classical work. When $p=0^n$, the function is injective and the samples eventually span all of $({\mathbb{F}}_2{)}^n$, which distinguishes that case with arbitrarily high probability.