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

Because $H_n|0^n⟩=|{\psi }_0⟩$,which is the reflection operator in the line spanned by $|{\psi }_0⟩$. Meanwhile $I_G$ changes the sign of every good basis state and fixes every bad basis state; onit is the reflection in the $|{\psi }_B⟩$ axis. Both reflections preserve $\mathcal{P}$, so their product $Q$ does too.

WriteIn Euclidean geometry, the composition of reflections in two lines through the origin has a rotation matrix through twice the oriented angle between the lines. Hence $Q$ rotates the good-bad plane by $2\theta$ from $|{\psi }_B⟩$ toward $|{\psi }_G⟩$. In particular, the Grover rotation angle formula is

When $k=N/4$,One Grover search algorithm iteration therefore givesThe selective sign change $I_G$ is implemented with one application of the Boolean quantum oracle: prepare its answer qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ and use quantum phase kickback, obtaining $(-1{)}^{f(x)}$ on each $|x⟩$. The remaining operations $H_n$, $I_0$, and the final computational-basis measurement are independent of $f$. Measurement of $|{\psi }_G⟩$ returns some $x\in G$ with probability one, so exactly one query to $U_f$ suffices.