Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 15D / a

Writewhere $|\beta ⟩$ is the normalized component orthogonal to $|x_0⟩$. On this real plane, $I_{x_0}$ is reflection in the line perpendicular to $|x_0⟩$, whileis reflection in the line spanned by $|{\psi }_0⟩$. Their product $Q=-J{I}_{x_0}$ is a rotation through $2\theta =\pi /3$ toward $|x_0⟩$. This is the geometric core of Grover search.

Prepare $|{\psi }_0⟩=H^{\otimes 2}|00⟩$. One query to $U_f$, with phase kickback, implements $I_{x_0}$. The reflection $-J$ is independent of $f$ and can be implemented by conjugating the phase flip of $|00⟩$ with $H^{\otimes 2}$. Since $|{\psi }_0⟩$ begins at angle $\theta =\pi /6$ from the unmarked direction, one Grover iterate rotates it by $2\theta$ and givesA computational-basis measurement therefore determines $x_0$ with certainty after one oracle query.