Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 58 / 2 / c / Solution

For the normalized vector defining the orthogonal projection $P=|\varphi ⟩⟨\varphi |$, $P^k=P$ for every $k\ge 1$. Thuswhich proves the projector phase rotation identity in this case:It changes the sign of the component along $\varphi$ and fixes the orthogonal complement, so it is a reflection operator.

For a marked computational basis vector $w$, $U_{P_w}=I-2|w⟩⟨w|$ is the marked-state phase oracle. With $|\psi ⟩=H^{\otimes N}|0^N⟩$, the other reflection isThe Hadamard gates thus implement its change of basis from the known all-zero state. The usual Grover diffusion operator is $D=2|\psi ⟩⟨\psi |-I=-U_{P_{\psi }}$. Consequently a Grover search algorithm iteration isThe minus sign is an irrelevant global phase. These two reflections rotate the search state in the span of the marked vector and the unmarked uniform vector, with the Grover rotation angle controlled by the initial marked amplitude. Iterating them approximately $\pi \sqrt{2^N}/4$ times gives high-probability search. The same pair of projectors appears additively in the continuous-time Hamiltonian, but the product of full reflections and evolution under their sum are distinct dynamics.