Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 58 / 2

A good item must exist, so assume $1\le k<N$; if $k=0$, the requested search is impossible, while $k=N$ makes every output good. Put $p=k/N$ and $\theta =\arcsin \sqrt{p}$. Normalize the good and bad components of the uniform superposition state asThe Boolean phase oracle negates $|g⟩$ and fixes $|b⟩$. The Grover diffusion operator is $-I_{{\psi }_0}=2|{\psi }_0⟩⟨{\psi }_0|-I$. Its implementation is independent of $f$: conjugate the reflection about $|0^n⟩$ by Hadamard gates. One Grover search algorithm iteration isHence, by the Grover rotation angle formula,Choose the nonnegative integer $j$ nearest to $\pi /(4\theta )-1/2$. Its final angle differs from $\pi /2$ by at most $\theta$, so a computational-basis measurement succeeds with probability at least ${\cos }^2\theta =1-p$. The allowed small-density regime includes $p\le 1/3$, giving the requested $2/3$ bound. Each iteration uses one Boolean phase oracle query, and $j=O(1/\sqrt{p})=O(\sqrt{N/k})$.

For $k=N/4$, $\theta =\pi /6$ and one iteration reaches $3\theta =\pi /2$ exactly. Thus one query gives a good outcome with certainty:This is exact Grover search on four entries applied to a marked fraction of one quarter, not only to a four-element register.

The amplitude amplification theorem concerns a known preparation quantum circuit $A$ and a good-subspace projector $\Pi$. Write $A|0⟩=\sin \theta |g⟩+\cos \theta |b⟩$, with ${\sin }^2\theta =p=\Vert \Pi A|0⟩{\Vert }^2$. Let $S_0=I-2|0⟩⟨0|$ and $S_{\chi }=I-2\Pi$. ThenThe reflection operators preserve the two-dimensional good-bad plane and rotate it by $2\theta$, so $O(1/\sqrt{p})$ iterations amplify a small known success probability to a constant close to one. Each iteration uses one good-subspace phase test and one use each of $A,A^{†}$, together with a known reflection. Amplitude amplification provides a quadratic improvement in the number of repetitions of a successful preparation. The query cost of the preparation and its inverse must be included when they themselves use the input oracle. Exact amplitude amplification uses additional known-overlap preparation or phase matching to avoid integer-iteration overshoot.

Under the usual reversible-circuit interpretation, there is a genuine obstruction to uniform probability lowering by a unitary in the printed premise. The universal assertion cannot hold for arbitrary $p$: it fails already at the search density $p=k/N$.

An explicit counterexample uses $N=4$, one good basis state $|0⟩$, $p=1/4$ and $p^{\prime }=1/8$. The six pure statesall have good probability $1/4$. Their equally weighted density operator is $I_4/4$, a maximally mixed state. Every unitary operator $C$ leaves this mixture unchanged, so its average output good probability remains $1/4$. The printed assertion would instead make all six output probabilities $1/8$, a contradiction. More generally, averaging states $\sqrt{k/N}|g⟩+e^{i\alpha }\sqrt{1-k/N}|b⟩$ uniformly over good and bad basis vectors and two opposite phases gives $I_N/N$, proving the same obstruction at the actual search density $p=k/N$.

The intended conditional construction needs only a supplied reversible preparation that lowers the success probability of the particular starting state, not of every state. Here is the complete argument under that weaker resource assumption. Count $C$ and $C^{†}$ as supplied, query-free operations, as required for the claimed input-oracle bound. Let $\theta =\arcsin \sqrt{k/N}$ and chooseIf equality holds, use the original preparation. Otherwise use the stipulated preparation on $|{\psi }_0⟩$ to obtain $|{\psi }_{\ast }⟩=C|{\psi }_0⟩$ with good probability $p_{\ast }$. Its reflection operator is implementable byThe good and bad components may be nonuniform, but amplitude amplification applies to this same two-dimensional decomposition. After $j$ iterations of $-I_{{\psi }_{\ast }}{I}_f$, its good probability isThus the stated exact-query conclusion follows from accessible preparation of one known-overlap state and its inverse. If the supplied preparation uses oracle queries, those costs cannot be omitted.

A physically realizable known-state success dilution for exact amplitude amplification is available in the standard enlarged marking-oracle model. Append a flag in $\sqrt{1-q}|0⟩+\sqrt{q}|1⟩$, where $q=p_{\ast }/p$, and call a joint state good only when $f(x)=1$ and the flag is one. This prepared state's success probability is exactly $pq=p_{\ast }$. Reflect about this known product preparation and mark the joint good subspace; $j$ ordinary iterations then succeed with certainty. A supplied controlled phase oracle gives one marking query per iteration, or a Boolean bit oracle computes $f$, applies the joint phase and uncomputes $f$ in two queries. Measuring the data therefore returns a good $x$ with certainty in $O(\sqrt{N/k})$ queries. This changes the state space and marking test, and does not assert the impossible universal $n$-qubit circuit. Controlled access is an additional resource in a bare phase-oracle model, so it is made explicit rather than silently assumed.