Simon's algorithm
= Simon's algorithm
{c}
= Simon algorithm
{c}
{synonym}
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.