Past exam of the computer science course of the University of Oxford / 2019 / Quantum information / 3 / e / Solution

One Grover iteration returns a marked label with certainty. Prepare $|s⟩=N^{-1/2}{\sum }_x|x⟩$; apply the supplied phase oracle to negate amplitudes on the $N/4$ marked inputs; apply the Grover diffusion operator $D=2|s⟩⟨s|-I$; and measure in the computational basis. If F prepares $|s⟩$ from $|0⟩$, the reflection is $D=F(2|0⟩⟨0|-I)F^{†}$, requiring no further oracle query.

After the oracle the amplitudes are $1/\sqrt{N}$ on the $3N/4$ unmarked labels and $-1/\sqrt{N}$ on the marked labels. Their average isThe reflection performs inversion about the mean, $a_x\mapsto 2\mu -a_x$. It therefore sends every unmarked amplitude to zero and every marked amplitude to $2/\sqrt{N}$. The resulting normalized state isEach marked label has Born rule probability $4/N$, every unmarked label has probability zero, and the marked probabilities sum to $(N/4)(4/N)=1$. This is one-step exact Grover search with a quarter of the inputs marked, using one reduced-oracle query. The positive integer N must be divisible by four; a qubit implementation may take $N=2^m$, but the stated reflection proof does not assume that register convention.