= First half-probability Grover iterate
{title2=$n_{\min}=\max\!\left\{0,\left\lceil\frac{\pi}{8\arcsin\sqrt p}-\frac12\right\rceil\right\}$}
If the marked fraction is $p$ and $\theta=\arcsin\sqrt p$, the success probability after $n$ <Grover search algorithm> iterations is $\sin^2((2n+1)\theta)$. For $0<p\leq1/2$, its first value at least $1/2$ occurs at
$$
n_{\min}=\left\lceil\frac{\pi}{8\theta}-\frac12\right\rceil.
$$
Before this integer the angle is below $\pi/4$, so success is below $1/2$. At this integer, the angle lies in $[\pi/4,\pi/4+2\theta)$, contained in $[\pi/4,3\pi/4)$, where squared sine is at least $1/2$. If $p\geq1/2$, no iteration is needed. For small $p$, $n_{\min}$ is asymptotic to $\pi/(8\sqrt p)$.
Back to article page
