= Nearest-integer stopping for amplitude amplification
{title2=$r=\lfloor\pi/(4\theta)\rfloor,\quad \sin^2\theta=p$}
For known initial success probability $p\in(0,1)$, this choice of iteration count ensures $|(2r+1)\theta-\pi/2|\leq\theta$. Hence the success probability after <amplitude amplification> is at least $\cos^2\theta=1-p$. Counting initial state preparation and the forward and inverse preparation in each iterate gives $2r+1$ preparation-unitary applications, asymptotic to $\pi/(2\sqrt p)$ as $p\to0$.
Back to article page
