= Solution
When $k=N/4$,
$$
\sin\theta=\frac12,
\qquad \theta=\frac\pi6.
$$
One <Grover search algorithm> iteration therefore gives
$$
Q|\psi_0\rangle
=\sin(3\theta)|\psi_G\rangle+\cos(3\theta)|\psi_B\rangle
=|\psi_G\rangle.
$$
The selective sign change $I_G$ is implemented with one application of the <Boolean quantum oracle>: prepare its answer qubit in $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$ and use <quantum phase kickback>, obtaining $(-1)^{f(x)}$ on each $|x\rangle$. The remaining operations $H_n$, $I_0$, and the final computational-basis measurement are independent of $f$. Measurement of $|\psi_G\rangle$ returns some $x\in G$ with probability one, so exactly one query to $U_f$ suffices.
Back to article page
