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

Apply one Hadamard gate independently to each qubit. These gates act in parallel, so the quantum circuit implements $H^{\otimes n}$ with $n$ gates and depth one.

For a computational basis state, factorization givesThe exponent is the dot product over the finite field ${\mathbb{F}}_2$, because multiplying the separate signs adds their exponents modulo two. This is the Walsh-Hadamard transform, equivalently the quantum Fourier transform on the finite Abelian group $({\mathbb{Z}}_2{)}^n$.

In particular, the all-zero input becomes the uniform coherent superposition $2^{-n/2}{\sum }_y|y⟩$. It is a useful initial operation because an oracle can then act on all amplitudes in one call, and subsequent interference can reveal a global property. Measurement alone does not read all function values: the later interference step is what turns the preparation into an algorithmic advantage.

The first Hadamard transform prepares a uniform superposition in the first register while the second stays zero. The Boolean quantum oracle, now with an $n$-bit output register and bitwise addition, therefore givesThis state is normalized because distinct $x$ labels are orthogonal, even when their oracle outputs coincide. Addition in the oracle is bitwise exclusive-or, making the oracle reversible; replacing the first register by $f(x)$ would not define a unitary gate for a two-to-one function.

For the later recovery steps we use the intended nonzero hidden-period promise $s\ne 0$. Then two-to-one behavior and $f(x+s)=f(x)$ force each fibre to be exactly $\{x,x+s\}$. The printed allowance $s\in \{0,1{\}}^n$ does not explicitly exclude zero. If zero were allowed without a nonzero-period promise, the displayed identity would hold trivially for every function and would not specify Simon's problem. That distinction is addressed again in the query count.

Only strings $k$ in the image of $f$ can be observed. Choose one preimage $x_k$ of an observed string. Under the nonzero-period promise its two preimages are $x_k$ and $x_k+s$. The Born rule gives probability $2/2^n$ to this second-register outcome, and conditional normalization leaves the first-register coset stateThe relative plus sign is retained: measuring the output register reveals which fibre was sampled but does not reveal which member of the fibre was present. Measuring its bits successively gives the same projection onto the observed full string as measuring the whole register at once.

Apply the Hadamard transform to the conditional coset state. The amplitude of a first-register output $z$ isWhen $s\cdot z=1$ over ${\mathbb{F}}_2$, the two terms cancel exactly. When $s\cdot z=0$, their squared modulus is $2^{-(n-1)}$. ThusThere are $2^{n-1}$ orthogonal outputs, so these probabilities sum to one. The distribution is independent of the particular observed fibre. It is the Single-sample distribution in Simon's algorithm: each run gives a uniform random equation restricting the hidden period to the orthogonal complement over the binary field.

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.