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

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.