= Solution
{c}
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\rangle|1\rangle$, applies a <Hadamard gate> to each <qubit>, queries the reversible <quantum oracle> $U_f:|x,y\rangle\mapsto|x,y\mathbin\oplus f(x)\rangle$, applies the <Grover diffusion operator> $D=2|s\rangle\langle s|-I$ to the first two <qubits>, and measures those two <qubits> in the <computational basis>. Here $|s\rangle=\tfrac12\sum_x|x\rangle$. The full three-wire <quantum circuit> is the composition
$$
\boxed{|00\rangle|1\rangle
\xrightarrow{H^{\otimes3}}|s\rangle|-\rangle
\xrightarrow{U_f}(O_f|s\rangle)|-\rangle
\xrightarrow{D\otimes I}|x_*\rangle|-\rangle
\xrightarrow{\text{measure first two}}x_*.}
$$
\Image[/past-exam-of-the-laser-science-and-quantum-information-processing-course-of-the-university-of-oxford/2022-grover-search-circuits.png]
{title=Three- and two-qubit implementations of <Grover's algorithm> for four inputs}
Here $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$. Since $X|-\rangle=-|-\rangle$, <phase kickback> gives $U_f(|x\rangle|-\rangle)=(-1)^{f(x)}|x\rangle|-\rangle$. The third <qubit> remains separable and unchanged. A direct <marked-state phase oracle> $O_f|x\rangle=(-1)^{f(x)}|x\rangle$ therefore replaces the three-<qubit> query using only two <qubits>:
$$
\boxed{|00\rangle\xrightarrow{H\otimes H}|s\rangle
\xrightarrow{O_f}O_f|s\rangle\xrightarrow{D}|x_*\rangle
\xrightarrow{\text{measure}}x_*.}
$$
For the explicit choice $f(x)=1$ only at $x=11$, $O_f$ is a <Controlled-Z gate>. Immediately after it,
$$
O_f|s\rangle=\tfrac12(|00\rangle+|01\rangle+|10\rangle-|11\rangle).
$$
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^{\otimes2}(2|00\rangle\langle00|-I)H^{\otimes2}$. Up to an irrelevant <global phase>, it is $H^{\otimes2}X^{\otimes2}\,\mathrm{CZ}\,X^{\otimes2}H^{\otimes2}$. 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.
Back to article page
