= Solution
The <amplitude amplification theorem> concerns a known preparation <quantum circuit> $A$ and a good-subspace projector $\Pi$. Write $A|0\rangle=\sin\theta|g\rangle+\cos\theta|b\rangle$, with $\sin^2\theta=p=\|\Pi A|0\rangle\|^2$. Let $S_0=I-2|0\rangle\langle0|$ and $S_\chi=I-2\Pi$. Then
$$
Q=-A S_0A^\dagger S_\chi,\qquad\boxed{\|\Pi Q^jA|0\rangle\|^2=\sin^2((2j+1)\theta).}
$$
The <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^\dagger$, together with a known reflection. \b[<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.
Back to article page
