= One-step exact Grover search with a quarter of the inputs marked
{title2=$r=\tfrac14\Rightarrow P_{\rm marked}=1$}
= Quarter-marked exact Grover search
{synonym}
Start from $|s\rangle=N^{-1/2}\sum_x|x\rangle$, negate amplitudes at marked indices, and apply $2|s\rangle\langle s|-I$. If the marked fraction is $r$, the oracle-state mean amplitude is $(1-2r)/\sqrt N$. <Inversion about the mean> therefore gives amplitudes $(1-4r)/\sqrt N$ on unmarked indices and $(3-4r)/\sqrt N$ on marked ones. The marked success <probability> is $r(3-4r)^2$. At $r=1/4$ it is exactly one: unmarked amplitudes vanish and each marked amplitude is $2/\sqrt N$. The output is uniform among the $N/4$ marked indices. This is an exact special case of <Grover's algorithm>, using one <phase oracle> call under the stated promise.
Back to article page
