= First half-success time in Grover search
{title2=$r_{1/2}=\left\lceil\frac{\pi}{8\chi}-\frac12\right\rceil$}
For both oracle phases equal to $\pi$, the good/bad matrix is $\begin{pmatrix}\cos2\chi&\sin2\chi\\-\sin2\chi&\cos2\chi\end{pmatrix}$. Acting $r$ times on the initial vector $(\sin\chi,\cos\chi)$ yields success $\sin^2((2r+1)\chi)$. For $0<\chi\le\pi/4$, the first crossing of one half is the displayed integer, since the rounded angle stays between $\pi/4$ and $3\pi/4$. With $\sin^2\chi=m/N\ll1$ this is asymptotic to $(\pi/8)\sqrt{N/m}$. Iterating indefinitely is incorrect: the success oscillates after its first maximum.
Back to article page
