= Verified Grover promise test
{title2=$k=\lfloor\pi/(4\theta)\rfloor,\quad\sin\theta=N^{-1/2}$}
Under the promise of either no marked entry or one marked entry in an $N$-element <Boolean quantum oracle> search space, run the <Grover search algorithm> for the displayed number of iterations, measure a candidate, and make one additional oracle query to check it. Since $|(2k+1)\theta-\pi/2|\leq\theta$, the marked-entry success probability is at least $\cos^2\theta=1-1/N$. For $N\geq4$ this is at least $3/4$. If no entry is marked the verification never accepts, so there is no false positive. The query count is $k+1=O(\sqrt N)$ because $\theta\geq1/\sqrt N$. Measuring a candidate without verification would not determine whether a marked entry exists.
Back to article page
