= First successful Grover iterate
{title2=$k_{\min}=\lceil\pi/(4\theta)\rceil-1$}
For one marked element among $N\geq2$ candidates, set $\theta=\arcsin(N^{-1/2})$. The first nonnegative <Grover search algorithm> iteration count attaining marked probability at least $\cos^2\theta$ is the displayed integer. Before the first success interval, the angle $(2k+1)\theta$ is below $\pi/2-\theta$; entering that interval requires $k\geq\pi/(4\theta)-1$. Rounding up gives an angle less than $\pi/2+\theta$, so it cannot skip the interval. Moreover $k_{\min}<\pi/(4\theta)<\pi\sqrt N/4$. For $N=1$, the known candidate is already the answer and no iteration is needed; the two-dimensional marked--unmarked plane degenerates.
Back to article page
