Simon's algorithm

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.

To solve Simon's problem, prepare a uniform quantum superposition, evaluate the function coherently into a second quantum register, and perform Simon Fourier sampling on the first. Each run produces a uniform binary string $z$ with $z\cdot s=0$ over the two-element field. Once the observed rows have matrix rank $n-1$, Gaussian elimination recovers $s$ as the unique nonzero element of their kernel. The random spanning of a binary vector space bounds the required number of runs.

Apply the Hadamard transform to a Simon coset state. The probability amplitude of $|z⟩$ is $2^{-(n+1)/2}(-1{)}^{x\cdot z}[1+(-1{)}^{s\cdot z}]$. Destructive quantum interference eliminates exactly those $z$ with $z\cdot s=1$. A computational-basis measurement therefore samples the kernel $s^{\perp }$ uniformly, independently of the representative $x$.

In Simon's algorithm, conditioning on a function value leaves the first quantum register in an equal coherent sum of its two preimages. This is a pure state, even though discarding the second quantum register without retaining its outcome generally leaves a mixed state. The label $x$ depends on the measured value; the period $s$ does not.

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.