Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 10D / d / 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⟩$, after $r$ iterations the success probability isby the Grover rotation angle. Choose an integerThen $(2r+1)\theta$ differs from $\pi /2$ by at most $\theta$, soFor every sufficiently large $N$ this is greater than $1/2$, whileThus measuring the search register determines the faulty input with the required constant success probability using $O(\sqrt{N})$ oracle queries.