Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 61 / 2 / ii / Solution

Let ${\Pi }_G$ be the orthogonal projection onto the good vector subspace $G$, and let the normalized input be $|\psi ⟩$. Set $p=\Vert {\Pi }_G\psi {\Vert }^2={\sin }^2\theta$ with $0<\theta <\pi /2$, and defineAssuming coherent access to the two reflections, the amplitude amplification theorem states thatpreserves the plane spanned by $|g⟩,|b⟩$ and acts as a rotation, givingHence the good-outcome probability is ${\sin }^2((2j+1)\theta )$. When $p$ is known, choose the nearest nonnegative integer to $\pi /(4\theta )-1/2$. The resulting angle is within $\theta$ of $\pi /2$, so the good probability is at least ${\cos }^2\theta =1-p$. For small $p$ this is close to one and requires $O(1/\sqrt{p})$ iterations. Exact success occurs when $(2j+1)\theta =\pi /2$. Known $p$ also allows exact amplitude amplification by ancilla qubit dilution or selective phase adjustment when ordinary integer iterations would overshoot.

If $|\psi ⟩=A|0⟩$ has a known coherent preparation, its reflection is implemented with $A$, $A^{†}$ and a zero-state phase flip. A coherent membership test supplies the reflection about $G$. Merely possessing an unknown copy of $|\psi ⟩$ does not automatically supply its reflection. For $p=1$ the state is already good; for $p=0$ this two-reflection construction cannot generate a good component. These cases delimit the theorem's algorithmic assumptions.