Grover rotation angle

If $M$ of $N$ items are marked and $\sin \theta =\sqrt{M/N}$, each Grover iteration rotates the state by $2\theta$ in the marked--unmarked plane, so after $r$ iterations the marked amplitude is $\sin ((2r+1)\theta )$.

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\le 1/2$, its first value at least $1/2$ occurs atBefore 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\ge 1/2$, no iteration is needed. For small $p$, $n_{\min }$ is asymptotic to $\pi /(8\sqrt{p})$.

For one marked element among $N\ge 2$ 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\ge \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.

For $N=4$ and one marked item, $\theta =\pi /6$. One Grover iteration gives marked amplitude $\sin (3\theta )=1$, so measurement returns the target with certainty.