Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 10D (Quantum Information and Computation)

Letwhere $H$ is the Hadamard gate. For a computational-basis string $z$, define the phase reflectionThus $I_0$ changes the sign of $|0^n⟩$, while $I_{x_0}$ changes the sign of the marked state.

Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s⟩$, sois the Grover diffusion operator, the reflection about $|s⟩$. The Grover iteration operatoris the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0⟩$ and the normalized uniform superposition of unmarked states, whereIt is the identity up to sign on the orthogonal complement of that plane.

Use $n$ controlled-NOT gates in parallel. For each $j=1,\dots ,n$, the $j$th input qubit is the control and the $j$th output-register qubit is the target. Their combined action iswhich is exactly

The known circuit from part (b) lets us apply $U_{\mathcal{I}}$ without querying the faulty oracle. Their composition satisfiesBecause $a=00\cdots 01$, only the last answer qubit is flipped in the exceptional case.

Prepare the answer register asSince $X|-⟩=-|-⟩$, quantum phase kickback gives, for an arbitrary search-register state,The answer register is unchanged and factors out. The induced operation on the first register is thereforeThis is the marked-state phase oracle from a single faulty identity-oracle query.

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.