Past exam of the introduction to quantum information course of the University of Oxford / 2015 / 1 / e

Each run of Simon's algorithm uses 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 givesAlternatively, $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}$. ConsequentlyThe 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^{\prime }$. 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 $\left(\genfrac{}{}{0ex}{}{q}{2}\right)/(2^n-1)$. The usual randomized classical query complexity of Simon's problem is therefore exponential in $n$, on the scaleA 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.