Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 10E (Quantum Information and Computation)

The reflection is $I_{|\psi ⟩}=I-2|\psi ⟩⟨\psi |$. Hence $I_{|x_0⟩}|x⟩=-|x_0⟩$ for $x=x_0$ and equals $|x⟩$ otherwise.

The marked-subspace reflection is $I_G=I-2{\sum }_{j=1}^M|g_j⟩⟨g_j|$.

Write $|G⟩=M^{-1/2}{\sum }_g|g⟩$ and $|B⟩=(N-M{)}^{-1/2}{\sum }_{x\notin G}|x⟩$. Then $|{\psi }_0⟩=\sin \alpha |G⟩+\cos \alpha |B⟩$. Both reflections preserve $\mathrm{span}\{|G⟩,|B⟩\}$, hence so does their product.

In the orthonormal basis $(|G⟩,|B⟩)$, direct multiplication gives(up to the equivalent opposite orientation convention).

The displayed orthogonal matrix is a rotation through $2\alpha$, where ${\sin }^2\alpha =M/N$.

After $r$ iterations the marked amplitude is $\sin ((2r+1)\alpha )$. Choose $r$ nearest to $\pi /(4\alpha )-1/2$; for $M\ll N$, this is about $(\pi /4)\sqrt{N/M}$ oracle iterations.