Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 10C (Quantum Information and Computation)

Write $x=x_1{x}_2$. Since the marked word is $11$, the required oracle is a single Toffoli gate with $x_1$ and $x_2$ as its two controls and the answer qubit $y$ as its target:The target flips exactly when both controls are one, which is exactly when $x=11$.

Let $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Applying the oracle with this answer qubit produces phase kickback:Inside $A$, the $X$ gates on both search qubits conjugate the phase oracle for $11$. Hencewhere $I_0=I-2|00⟩⟨00|$.

The first oracle similarly acts on the search register as $I_{x_0}=I-2|x_0⟩⟨x_0|$. Reading the remaining gates from right to left, the search-register operation after its initial Hadamards is thereforewhile the answer qubit remains in $|-⟩$.

After the initial Hadamards the search register isThe marked-state phase oracle changes only the last sign:Now $H^{\otimes 2}{I}_0{H}^{\otimes 2}=I-2|s⟩⟨s|$. Since the overlap of the last displayed state with $|s⟩$ is $1/2$, its image is $-|11⟩$. Thus the complete output isThe minus sign is a physically irrelevant global phase.

Measurement of the two search qubits in the computational basis returns $11$ with probability one. The answer qubit is unentangled from them and remains in $|-⟩$.

Only one Grover iteration is required. For one marked item among four, the initial marked amplitude corresponds to an angle $\theta$ with $\sin \theta =1/2$, so $\theta =\pi /6$; one iteration changes this to $3\theta =\pi /2$, giving unit success amplitude. Further iterations are neither needed nor beneficial.