Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 53 / 2 / 5 / Solution

Each independent run uses one oracle call and gives a uniformly sampled equation $z\cdot s=0$. Collect $n-1$ linearly independent equations and use Gaussian elimination over ${\mathbb{F}}_2$. Their solution space has dimension one and consists of $\{0,s\}$, so the promised nonzero solution identifies $s$ uniquely.

To quantify the expected query count for Simon sampling, write $d=n-1$. If the existing equations have rank $k<d$, their span contains $2^k$ of the $2^d$ possible samples. A fresh equation raises the rank with probability $1-2^{k-d}$. The mean waiting time is the corresponding geometric distribution mean, givingThe last sum is less than $2$: its first term is $1$ and its remaining terms are bounded by ${\sum }_{j=2}^{\infty }{2}^{1-j}=1$. Hence the expected number of quantum queries is $O(n)$. For a fixed high-confidence budget, use $m=d+c$ samples. Failure to span means that a nonzero linear functional on the $d$-dimensional sampling space annihilates every sample. Each such functional has probability $2^{-m}$, so the union bound gives failure probability at most $(2^d-1)2^{-m}<2^{-c}$. Thus $O(n+\log (1/\delta ))$ queries suffice for failure probability at most $\delta$. For $n=1$, the nonzero string is known already and no samples are needed.

Classically, a collision between distinct queried arguments immediately yields $s=x+y$. Random queries produce this collision after order $2^{n/2}$ calls, by the birthday problem. Conversely, choose the nonzero period uniformly and label the fibres randomly. Before a collision, $q$ queries can exclude at most $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ periods, their pairwise argument differences; every remaining period has the same no-collision transcript distribution. When $q=o(2^{n/2})$, those exclusions occupy a vanishing fraction of the candidate periods, and neither collision discovery nor guessing a remaining period has a constant success probability. More quantitatively, conditioned on no previous collision, the next query tests at most $q$ of at least $2^n-1-\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ remaining periods; summing these conditional probabilities proves the same square-root lower bound. Therefore the optimal bounded-error classical query count is $\Theta (2^{n/2})$, exponentially larger in $n$ than the quantum count.

This comparison presumes a hidden nonzero period. Under a literal interpretation asking merely for some $s$ satisfying the printed identity, returning $s=0$ requires no queries at all, quantum or classical. Nonzero $s$ is the necessary intended promise, not a consequence of two-to-one behavior alone.