Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 324 / 2

Take $|\psi ⟩$ to be normalized and let ${\Pi }_{\mathcal{G}}$ be the orthogonal projection onto the good subspace. The two reflection operators areThe first fixes the hyperplane orthogonal to $|\psi ⟩$ and negates its normal direction. The second fixes ${\mathcal{G}}^{\perp }$ and negates $\mathcal{G}$. Both are Hermitian operators and unitary operators, since their defining projectors square to themselves. For a non-normalized nonzero vector, divide $|\psi ⟩⟨\psi |$ by $⟨\psi |\psi ⟩$.

Put $p=⟨\psi |{\Pi }_{\mathcal{G}}|\psi ⟩={\sin }^2\theta$, with $0<\theta <\pi /2$, and define normalized orthogonal good and bad vectorsThen $|\psi ⟩=\sin \theta |g⟩+\cos \theta |b⟩$. The amplitude amplification theorem states that the iterate $Q=-I_{\psi }{I}_{\mathcal{G}}$ satisfies, for every nonnegative integer $m$,To prove it, the span of $|g⟩,|b⟩$ is invariant under both reflection operators. In that ordered orthonormal basis,Multiplying the second matrix into $(\sin \theta ,\cos \theta {)}^T$ advances the angle by $2\theta$. Induction proves the formula, and projecting onto $\mathcal{G}$ gives $p_m$. The minus sign in $Q$ is just a global phase choice, but it makes the displayed state formula exact.

If $p$ is known, choose $m$ nearest to $\pi /(4\theta )-1/2$, with $m\ge 0$. The final angle is within $\theta$ of $\pi /2$, so $p_m\ge {\cos }^2\theta =1-p$. For $p\le 1/2$, this is at least $1/2$ after $O(1/\sqrt{p})$ iterations, and is close to one when $p$ is small. For $p>1/2$, measuring the initial state already has success above $1/2$. Repeated independent attempts with a success test give any fixed desired success probability. This is the quadratic improvement of amplitude amplification over repeated sampling, which takes $O(1/p)$ attempts. At $p=0$ there is no good component to amplify, and at $p=1$ the initial state is already entirely good; these endpoint cases do not require the undefined normalized component vectors.

Prepare an ancillary qubit inIt can be prepared from $|0⟩$ by an $X$ operation followed by a Hadamard gate, independently of $g$. One call to the Boolean quantum oracle then gives quantum phase kickback:The data state receives a minus sign precisely on the basis vectors spanning $\mathcal{G}$, while the ancilla remains unchanged and unentangled. One oracle call realizes the reflection. By linearity it is the marked-state phase oraclewith one oracle call. The ancillary preparation and its optional inverse use only fixed operations, so no additional knowledge of $g$ is needed.

Follow the printed examples by counting positive squares, so zero is not marked. For $N\ge 2$, the marked output set isA one-to-one map from the finite set $[N]$ to itself is a permutation, so exactly $K$ inputs have outputs in $S$. In the uniform quantum superposition $|s⟩=N^{-1/2}{\sum }_x|x⟩$, the initial good probability is therefore $p=K/N$. For permutation-preimage quantum search, this known marked density under a permutation is $\Theta (N^{-1/2})$.

Define the efficiently computable predicate $h(y)$ to be one if and only if $y$ is a positive square. The assumed Boolean quantum oracle for $h$, acting on $y$ and a $|-⟩$ ancilla, implements its diagonal sign operation $D_h|y⟩=(-1{)}^{h(y)}|y⟩$. Compute the modular-addition quantum oracle into a zero output register, apply this sign operation, and uncompute:This implements $I_{\mathcal{G}}$ for $\mathcal{G}=\mathrm{span}\{|x⟩:f(x)\in S\}$, with the work registers clean. Only forward calls to $U_f$ were promised, but its inverse costs one such call: if $J|y⟩=|-y\mathrm{mod}N⟩$ on the second register, thenIndeed the output addition is changed into subtraction. Thus each marked reflection costs exactly two queries to $U_f$; all other operations used here are independent of the unknown $f$.

Use the amplitude amplification theorem with $|\psi ⟩=|s⟩$, whose reflection is allowed by the assumptions. With $\theta =\arcsin \sqrt{K/N}$, choose $m$ nearest to $\pi /(4\theta )-1/2$. Here $p\le 1/2$ for every $N\ge 2$, so a trial succeeds with probability at least $1/2$. AlsoMeasure $x$ and use one additional $U_f$ query to evaluate and check $f(x)$. On failure, restart with fresh registers. Four independent trials have failure probability at most $2^{-4}$, so the required confidence and query bound areThis is an upper bound on quantum query complexity, not a claim that arbitrary reflections or every classical gate have constant cost. Including zero as a square would change $K$ to $K+1$ without changing the asymptotic bound. With the printed positive-square interpretation, $N=1$ has no valid output and no algorithm can satisfy the success requirement; the intended asymptotic task necessarily has $N\ge 2$.