= Solution
Use the construction in part (c) for the marked-state phase reflection in each <Grover search algorithm> iteration. Every such reflection costs one query to $U_f$; the identity-oracle circuit, Hadamard gates, and $I_0$ are independent of $f$.
Starting from $|s\rangle$, after $r$ iterations the success probability is
$$
\sin^2((2r+1)\theta),
\qquad
\sin\theta=N^{-1/2},
$$
by the <Grover rotation angle>. Choose an integer
$$
r=\left\lfloor\frac{\pi}{4\theta}-\frac12\right\rceil.
$$
Then $(2r+1)\theta$ differs from $\pi/2$ by at most $\theta$, so
$$
\Pr(\text{measure }x_0)
\geq\cos^2\theta
=1-\frac1N.
$$
For every sufficiently large $N$ this is greater than $1/2$, while
$$
r=O(\theta^{-1})=O(\sqrt N).
$$
\b[Thus measuring the search register determines the faulty input with the required constant success probability using $O(\sqrt N)$ oracle queries.]
Back to article page
