Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 15D (Quantum Information and Computation)

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.

Let $a=\Vert {\Pi }_A\xi \Vert$ and $b=\Vert {\Pi }_{A^{\perp }}\xi \Vert$. Since $a^2+b^2=1$, choose $\theta \in [0,\pi /2]$ with $a=\sin \theta$, $b=\cos \theta$. Normalizing the two nonzero projections givesAt an endpoint, the unused normalized vector may be chosen arbitrarily in its subspace.

Since $I_A|\alpha ⟩=-|\alpha ⟩$,Substituting the decomposition of $|\xi ⟩$ and using the double-angle identities gives

The two stated formulas show that $Q$ rotates the $(|\beta ⟩,|\alpha ⟩)$ plane by $2\theta$. Starting from $|\xi ⟩$, whose angle from $|\beta ⟩$ is $\theta$, two iterations give angleHence $Q^2|\xi ⟩=|\alpha ⟩$. The reflection about $|\xi ⟩$ is implementable asThus apply $U$ to $|0\cdots 0⟩$, followed by two applications of $-I_{\xi }{I}_A$. This prepares $|\alpha ⟩$ exactly and deterministically.