= Solution
\b[One Grover iteration returns a marked label with certainty.] Prepare $|s\rangle=N^{-1/2}\sum_x|x\rangle$; apply the supplied <phase oracle> to negate amplitudes on the $N/4$ marked inputs; apply the <Grover diffusion operator> $D=2|s\rangle\langle s|-I$; and measure in the <computational basis>. If F prepares $|s\rangle$ from $|0\rangle$, the reflection is $D=F(2|0\rangle\langle0|-I)F^\dagger$, 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 is
$$
\mu=\frac1N\left(\frac{3N}{4\sqrt N}-\frac{N}{4\sqrt N}\right)=\frac1{2\sqrt N}.
$$
The reflection performs <inversion about the mean>, $a_x\mapsto2\mu-a_x$. It therefore sends every unmarked amplitude to zero and every marked amplitude to $2/\sqrt N$. The resulting normalized state is
$$
\boxed{\frac2{\sqrt N}\sum_{f(x)=1}|x\rangle.}
$$
Each 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.
Back to article page
