Past exam of the laser science and quantum information processing course of the University of Oxford / 2022 / 4 / b / Solution

Let $x\in \{00,01,10,11\}$ and let $f(x)$ be one only at the marked input. A three-qubit implementation of Grover's algorithm starts with $|00⟩|1⟩$, applies a Hadamard gate to each qubit, queries the reversible quantum oracle $U_f:|x,y⟩\mapsto |x,y\oplus f(x)⟩$, applies the Grover diffusion operator $D=2|s⟩⟨s|-I$ to the first two qubits, and measures those two qubits in the computational basis. Here $|s⟩=\frac{1}{2}{\sum }_x|x⟩$. The full three-wire quantum circuit is the composition

Here $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since $X|-⟩=-|-⟩$, phase kickback gives $U_f(|x⟩|-⟩)=(-1{)}^{f(x)}|x⟩|-⟩$. The third qubit remains separable and unchanged. A direct marked-state phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ therefore replaces the three-qubit query using only two qubits:For the explicit choice $f(x)=1$ only at $x=11$, $O_f$ is a Controlled-Z gate. Immediately after it,The mean of these four probability amplitudes is $\overline{a}=1/4$. The Grover diffusion operator maps each probability amplitude $a_x$ to $2\overline{a}-a_x$. The three unmarked probability amplitudes become zero and the marked one becomes one. A single query consequently finds $11$ with probability one.

A gate-level implementation of $D$ is $H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$. Up to an irrelevant global phase, it is $H^{\otimes 2}{X}^{\otimes 2}\mathrm{CZ}{X}^{\otimes 2}{H}^{\otimes 2}$. For any other chosen marked word, conjugate the Controlled-Z gate by Pauli X gates on precisely the positions where the marked word has a zero.