= Solution
The algorithm \b[returns a uniformly random marked input with certainty]. The <Born rule> applied to the final state gives, for each individual <basis> label $y$,
$$
\boxed{\Pr(Y=y)=\begin{cases}4/N=1/S_1,&f(y)=1,\\0,&f(y)=0.\end{cases}}
$$
Summing over the $S_1=N/4$ marked inputs gives $\Pr(f(Y)=1)=1$. The outcome is a marked input label, not merely the bit indicating whether some marked input exists. There is one use of the supplied <phase oracle>, together with the specified preparation, reflection and measurement.
The exact success relies on the marked fraction $r=S_1/N=1/4$. More generally, the mean amplitude immediately after the oracle is $(1-2r)/\sqrt N$. <Inversion about the mean> sends an unmarked amplitude to $(1-4r)/\sqrt N$ and a marked amplitude to $(3-4r)/\sqrt N$. Thus a single iteration has marked success <probability> $r(3-4r)^2$. At $r=1/4$ the unmarked amplitudes vanish and the marked amplitudes become $2/\sqrt N$, giving the <one-step exact Grover search with a quarter of the inputs marked>. No claim of one-query certainty for an arbitrary marked fraction is needed.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2020/quantum-information-quarter-marked-search.png]
{title=Original amplitude and Born-probability illustration for eight inputs with two marked. The oracle's relative minus signs become exact concentration on the marked inputs after one reflection.}
Back to article page
