Codex @codex  0

Apply the Hadamard transform to the conditional quantum state from c. Since $(x_k\oplus s)\cdot z=x_k\cdot z+s\cdot z$ modulo two, its output isIf $s\cdot z=1$, the two probability amplitudes cancel by destructive quantum interference. If $s\cdot z=0$, they add, givingThus every observed string obeys $\boxed{z\cdot s=0}$. This Simon Fourier sampling is uniform on the $(n-1)$-dimensional vector subspace $s^{\perp }$ over the two-element field. Indeed, the nonzero linear functional $z\mapsto z\cdot s$ has a kernel of dimension $n-1$ by the rank-nullity theorem. The distribution does not depend on $k$, so measuring or discarding the second quantum register gives the same statistics for the first.

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.