Verified Grover promise test ($k=\lfloor \pi /(4\theta )\rfloor ,\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|\le \theta$, the marked-entry success probability is at least ${\cos }^2\theta =1-1/N$. For $N\ge 4$ 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 \ge 1/\sqrt{N}$. Measuring a candidate without verification would not determine whether a marked entry exists.