= Solution
Take $|\psi\rangle$ to be normalized and let $\Pi_{\mathcal G}$ be the <orthogonal projection> onto the good subspace. The two <reflection operators> are
$$
\boxed{I_\psi=I-2|\psi\rangle\langle\psi|,\qquad I_{\mathcal G}=I-2\Pi_{\mathcal G}.}
$$
The first fixes the hyperplane orthogonal to $|\psi\rangle$ and negates its normal direction. The second fixes $\mathcal G^\perp$ and negates $\mathcal G$. Both are <Hermitian operators> and <unitary operators>, since their defining projectors square to themselves. For a non-normalized nonzero vector, divide $|\psi\rangle\langle\psi|$ by $\langle\psi|\psi\rangle$.
Put $p=\langle\psi|\Pi_{\mathcal G}|\psi\rangle=\sin^2\theta$, with $0<\theta<\pi/2$, and define normalized orthogonal good and bad vectors
$$
|g\rangle=\frac{\Pi_{\mathcal G}|\psi\rangle}{\sqrt p},\qquad
|b\rangle=\frac{(I-\Pi_{\mathcal G})|\psi\rangle}{\sqrt{1-p}}.
$$
Then $|\psi\rangle=\sin\theta|g\rangle+\cos\theta|b\rangle$. \b[The <amplitude amplification theorem> states] that the iterate $Q=-I_\psi I_{\mathcal G}$ satisfies, for every nonnegative integer $m$,
$$
\boxed{Q^m|\psi\rangle=\sin((2m+1)\theta)|g\rangle+\cos((2m+1)\theta)|b\rangle,\qquad
p_m=\sin^2((2m+1)\theta).}
$$
To prove it, the span of $|g\rangle,|b\rangle$ is invariant under both <reflection operators>. In that ordered orthonormal basis,
$$
I_{\mathcal G}=\begin{pmatrix}-1&0\\0&1\end{pmatrix},\qquad
Q=\begin{pmatrix}\cos2\theta&\sin2\theta\\-\sin2\theta&\cos2\theta\end{pmatrix}.
$$
Multiplying the second matrix into $(\sin\theta,\cos\theta)^T$ advances the angle by $2\theta$. Induction proves the formula, and projecting onto $\mathcal G$ gives $p_m$. The minus sign in $Q$ is just a global phase choice, but it makes the displayed state formula exact.
If $p$ is known, choose $m$ nearest to $\pi/(4\theta)-1/2$, with $m\geq0$. The final angle is within $\theta$ of $\pi/2$, so $p_m\geq\cos^2\theta=1-p$. For $p\leq1/2$, this is at least $1/2$ after $O(1/\sqrt p)$ iterations, and is close to one when $p$ is small. For $p>1/2$, measuring the initial state already has success above $1/2$. Repeated independent attempts with a success test give any fixed desired success probability. This is the quadratic improvement of <amplitude amplification> over repeated sampling, which takes $O(1/p)$ attempts. At $p=0$ there is no good component to amplify, and at $p=1$ the initial state is already entirely good; these endpoint cases do not require the undefined normalized component vectors.
Back to article page
