= Nearest-integer success bound for quantum phase estimation
{title2=$\Pr(\text{nearest phase label})\geq4/\pi^2$}
For a <unitary operator> <eigenphase> $\phi$, an $n$-qubit <quantum phase estimation> register of size $L=2^n$ has output <probability amplitude>
$$
a_m(\phi)=\frac1L\sum_{x=0}^{L-1}e^{ix(\phi-2\pi m/L)}.
$$
Choose the nearest integer label $m$ to $L\phi/(2\pi)$, with labels understood modulo $L$, and put $d=L\phi/(2\pi)-m$, taking the representative $|d|\leq1/2$. The <finite geometric series> gives $|a_m|=|\sin(\pi d)|/[L|\sin(\pi d/L)|]$. For $0<|d|\leq1/2$, <concavity> of sine gives $|\sin(\pi d)|\geq2|d|$, while $|\sin(\pi d/L)|\leq\pi|d|/L$. Thus the <probability> of the nearest label is at least $4/\pi^2$. At $d=0$ it is exactly one. If two labels tie for nearest, each satisfies the bound.
Back to article page
