= Solution
If some integer $k$ obeys $(2k+1)\theta=\pi/2$, ordinary <amplitude amplification> already gives $|g\rangle$ exactly. For a general known $\theta$, use <exact amplitude amplification>. Choose $k$ so that
$$
\theta'=\frac{\pi}{4k+2}\leq\theta
$$
and put $c=\sin\theta'/\sin\theta\leq1$. Append an ancilla and coherently arrange that its designated good value has amplitude $c$ conditional on the original register being good. With the enlarged good subspace defined by
$$
f(x)=1\quad\text{and}\quad\text{ancilla}=0,
$$
the starting state's total good amplitude is $c\sin\theta=\sin\theta'$.
Apply the <amplitude amplification theorem> $k$ times to this enlarged problem. Its final good amplitude is
$$
\sin((2k+1)\theta')=\sin\frac\pi2=1.
$$
The <Boolean quantum oracle> implements the reflection $I_G$ by phase kickback, and the known state-preparation circuit implements the reflection about the starting state by prepare--reflect--unprepare. A final computational-basis measurement therefore yields an $x$ with $f(x)=1$ with certainty.
Back to article page
