= Quantum phase estimation tail bound
{title2=$\Pr(\operatorname{dist}_{\mathbb Z/L\mathbb Z}(J,j_0)\geq m)\leq[2(m-1)]^{-1}$}
Let $L=2^t$, let $j_0$ be the nearest label to $L\phi$, and let $m\geq2$. The exact <quantum phase estimation> amplitude is $L^{-1}\sum_{a=0}^{L-1}e^{2\pi ia(\phi-j/L)}$. The sine bound on circular distances gives probability at most $1/(4d_j^2)$, where $d_j$ is the centered distance from $j$ to $L\phi$. At label distance $\ell$ from $j_0$, $|d_j|\geq\ell-1/2$, with at most two labels for each $\ell$. Since $(\ell-1/2)^{-2}\leq[(\ell-1)\ell]^{-1}$, the tail telescopes to the displayed bound. Adding $u$ control <qubits> beyond $b$ desired phase bits gives circular accuracy below $2^{-b}$ with failure probability at most $[2(2^u-1)]^{-1}$.
Back to article page
