Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 324 / 3

Let ${\Pi }_G$ be the orthogonal projection onto $G$. The two reflection operators areThe first fixes the hyperplane $|\psi {⟩}^{\perp }$ and changes the sign of $|\psi ⟩$; the second fixes $G^{\perp }$ and changes the sign of $G$.

Write the normalized projections of $|\psi ⟩$ asThe amplitude amplification theorem states that forone has, up to the irrelevant global sign $(-1{)}^k$,Thus every iteration increases the angle toward the good axis by $2\theta$ until the first overshoot.

For the proof, the plane $\mathrm{span}\{|g⟩,|b⟩\}$ is invariant. In its ordered basis,Their product is a planar rotation through $2\theta$ together with an overall sign. Applying that matrix $k$ times proves the formula, while components orthogonal to this plane never enter the initial state.

If some integer $k$ obeys $(2k+1)\theta =\pi /2$, ordinary amplitude amplification already gives $|g⟩$ exactly. For a general known $\theta$, use exact amplitude amplification. Choose $k$ so thatand put $c=\sin {\theta }^{\prime }/\sin \theta \le 1$. Append an ancilla and coherently arrange that its designated good value has amplitude $c$ conditional on the original register being good. With the enlarged good subspace defined bythe starting state's total good amplitude is $c\sin \theta =\sin {\theta }^{\prime }$.

Apply the amplitude amplification theorem $k$ times to this enlarged problem. Its final good amplitude isThe Boolean quantum oracle implements the reflection $I_G$ by phase kickback, and the known state-preparation circuit implements the reflection about the starting state by prepare--reflect--unprepare. A final computational-basis measurement therefore yields an $x$ with $f(x)=1$ with certainty.

At trial $k$, the amplitude amplification theorem gives success probabilityBecause the state is prepared afresh, the probability that the first success occurs at $k$ isIf one application of $R$ uses a constant number of oracle calls, reaching and performing trial $k$ costs a total of order $1+2+\cdots +k=\Theta (k^2)$ calls. Equivalently,For $k\theta \ll 1$, use $\log {\cos }^{2}x=-x^2+O(x^4)$ andto obtainThe first successful index is therefore typically $k^{\ast }=\Theta ({\theta }^{-2/3})$, andwhere $n^{\ast }=\Theta (1/\theta )$ is the first near-optimal Grover iteration count.

The last requested assertion in the official paper is false as printed. In fact, for small $\theta$, at least a constant fraction of the indices $j<n^{\ast }$ have $(2j+1)\theta \ge \pi /4$, and hence failure probability at most $1/2$. Consequentlyfor some constant $c>0$, rather than being bounded below by a positive constant. The reversed event $\mathrm{Pr}(k^{\ast }<n^{\ast })$ does have a positive lower bound and in fact tends to one.

Now try only $k_i=2^i$. Since $n^{\ast }=2^N=\Theta (1/\theta )$, the total work through trial $N$ is the geometric seriesFor $i<N$, the success probabilities scale asTheir sum is $O(1)$, so the product of their failure probabilities stays bounded away from zero: there is a constant probability of reaching the scale $k_N=n^{\ast }$. At that trial, the defining property of $n^{\ast }$ givesso almost all surviving runs stop there. ThereforeThe geometric amplitude-amplification schedule is asymptotically better than the sequential schedule's $\Theta ((n^{\ast }{)}^{4/3})$ calls and matches the usual Grover scaling up to a constant factor.