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.

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.