Success Probability

When the phase $\varphi$ is exactly representable in $n$ bits — meaning $2^n \varphi$ is an integer — the inverse QFT collapses the counting register onto the single correct state and measurement succeeds with probability 1. Real-world phases are rarely so cooperative. This lesson analyses what happens when $\varphi$ falls between two consecutive $n$-bit grid points.

The general amplitude formula

Write the true phase as $\varphi$. After phase kickback and before the inverse QFT, the counting register holds

$\frac{1}{2^n} \sum_{k=0}^{2^n - 1} e^{2\pi i k \varphi} |k\rangle.$

Let $b$ be any candidate integer in $\{0, 1, \ldots, 2^n - 1\}$. The inverse QFT maps this state to one whose amplitude on $|b\rangle$ is

$\alpha_b = \frac{1}{2^n} \sum_{k=0}^{2^n - 1} e^{2\pi i k(\varphi - b/2^n)}.$

Setting $\delta = \varphi - b/2^n$ (the mismatch between $\varphi$ and the grid point $b/2^n$), the geometric sum evaluates to

$\alpha_b = \frac{1}{2^n} \cdot \frac{1 - e^{2\pi i \cdot 2^n \delta}}{1 - e^{2\pi i \delta}} \qquad (\delta \ne 0).$

The measurement probability is $|\alpha_b|^2$. Using $|1 - e^{i\theta}| = 2|\sin(\theta/2)|$:

$P(b) = \left|\frac{\sin(\pi \cdot 2^n \delta)}{2^n \sin(\pi \delta)}\right|^2.$

The best estimate

The best estimate is the integer $m$ such that $|m/2^n - \varphi|$ is smallest, i.e. $|\delta| \le 1/2^{n+1}$. For that estimate the mismatch satisfies $|\delta| \le 1/(2 \cdot 2^n)$, and it can be shown that

$P(m) \ge \frac{4}{\pi^2} \approx 0.405.$

This bound is tight: it is achieved in the worst case $|\delta| = 1/(2 \cdot 2^n)$ and follows from the inequality $\sin\theta \le \theta$ (for $\theta \ge 0$) combined with the bound $\sin\theta \ge 2\theta/\pi$ for $\theta \in [0,\pi/2]$. Concretely,

$P(m) = \left|\frac{\sin(\pi \cdot 2^n \delta)}{2^n \sin(\pi \delta)}\right|^2 \ge \left|\frac{\sin(\pi \cdot 2^n \delta)}{2^n \cdot \pi |\delta|}\right|^2.$

At $|\delta| = 1/(2 \cdot 2^n)$ the numerator is $|\sin(\pi/2)| = 1$ and the denominator is $\pi/2$, giving $(2/\pi)^2 = 4/\pi^2$.

Amplifying the success probability

Several strategies push the success probability above $4/\pi^2$:

1. Use more counting qubits. Each additional qubit doubles the grid resolution, making a worst-case tie less likely and increasing the typical probability.
2. Repeat and take the median. Running QPE $O(\log(1/\delta))$ times and taking the median estimate reduces the failure probability to $\delta$ exponentially fast.
3. Phase amplification. Quantum amplitude amplification can be used to boost the success probability of any QPE run from $4/\pi^2$ to near 1 with a modest circuit overhead.

Numerical check

For the $T$ gate, $\varphi = 1/8$. With $n = 3$ counting qubits, $2^3 \varphi = 1$ is exactly an integer, so $P = 1$ and QPE is deterministic. To see the non-trivial bound you need a phase like $\varphi = 1/3$, where no power of 2 makes $2^n \varphi$ an integer. For $n = 3$ and $\varphi = 1/3$, the best estimate is $m = 3$ (since $3/8 = 0.375$ is closest to $1/3 \approx 0.333$), giving $|\delta| = 1/24$, and the exact probability is

$P(3) = \left|\frac{\sin(\pi/3)}{8 \sin(\pi/24)}\right|^2 \approx 0.688,$

comfortably above $4/\pi^2 \approx 0.405$ as the bound guarantees.

Try it

QPE's worst-case success probability for the best estimate is $4/\pi^2$. Return that value as a number.

Sign in on the full site to ask questions and join the discussion.