= Solution
{c}
Each run of <Simon's algorithm> uses \b[one oracle call] and returns one uniform sample from $s^\perp$. Collect samples as rows of a <matrix> $Z$ and solve $Zs=0$ over the two-element <field> using <Gaussian elimination>. Once the rows have <matrix rank> $n-1$, the <kernel> is $\{0,s\}$, so the promised nonzero vector is uniquely determined. Dependent samples, including $z=0$, must be allowed for; exactly $n-1$ runs need not suffice.
For a rough quantitative estimate, put $d=n-1$. When the existing samples span an $r$-dimensional <vector subspace> of $s^\perp$, the next sample increases the <matrix rank> with <probability> $1-2^{r-d}$. The <random spanning of a binary vector space> estimate gives
$$
\mathbb E Q=\sum_{r=0}^{d-1}\frac1{1-2^{r-d}}
=d+\sum_{j=1}^d\frac1{2^j-1}<d+2=n+1.
$$
Alternatively, $m=d+t$ samples fail to span with <probability> less than $2^{-t}$: failure means some nonzero <linear functional> on the $d$-dimensional space vanishes on every sample, and a <union bound> gives $(2^d-1)2^{-m}$. Consequently
$$
\boxed{Q_{\rm quantum}=O(n)\text{ for fixed error},\qquad
Q_{\rm quantum}=O\bigl(n+\log(1/\varepsilon)\bigr)\text{ for error }\varepsilon.}
$$
The <Gaussian elimination> requires only a polynomial amount of classical work, for example $O(n^3)$ bit operations for $O(n)$ samples. The degenerate case $n=1$ needs no calls because the promise already specifies $s=1$.
Classically, distinct inputs with equal function values reveal $s=x\oplus x'$. Uniformly sampling distinct inputs finds such a <function collision> after roughly $\sqrt{2^n}$ calls, by the <birthday square-root scale>. For $q$ sampled inputs, the expected number of colliding pairs is $\binom q2/(2^n-1)$. The usual randomized classical <query complexity> of <Simon's problem> is therefore exponential in $n$, on the scale
$$
\boxed{Q_{\rm classical}=\Theta(2^{n/2})\text{ for bounded error},\qquad
Q_{\rm quantum}=O(n).}
$$
A straightforward exhaustive classical search instead uses $O(2^n)$ calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised <quantum oracle>, rather than an explicit table of all function values.
Back to article page
