= Solution
Normalization gives $p^2+q^2=1$. Write $p=\sin\theta$, $q=\cos\theta$ with $0<\theta<\pi/2$, and set $|u\rangle=U|b\rangle$. Define the two <Householder reflections>
$$
R_u=2|u\rangle\langle u|-I
=U(2|b\rangle\langle b|-I)U^\dagger,
\qquad
R_\xi=I-2|\xi\rangle\langle\xi|.
$$
The <amplitude amplification> iterate $G=R_uR_\xi$ preserves $\operatorname{span}\{|\xi\rangle,|\phi\rangle\}$ and rotates that plane through $2\theta$. Consequently
$$
\boxed{
G^kU|b\rangle
=\sin((2k+1)\theta)|\xi\rangle
+\cos((2k+1)\theta)|\phi\rangle}.
$$
In particular, $O(1/p)$ iterations raise the success probability to a constant close to one.
Back to article page
