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