Skip to content

Lesson 19: Quantum Phase Estimation

19.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the phase estimation problem and its input requirements.
  2. Derive the QPE circuit and show why the inverse QFT extracts the phase.
  3. Prove the exact case (\(\theta\) an \(n\)-bit binary fraction) gives the answer with probability 1.
  4. Apply the precision–probability theorem to choose the number of counting qubits.
  5. Recognise QPE as the central subroutine of Shor's algorithm, HHL and quantum chemistry.

19.2 The Problem

Given:

  • A unitary \(U\) (as a circuit, so that controlled-\(U^{2^k}\) can be applied).
  • An eigenstate \(|u\rangle\) with \(U|u\rangle = e^{2\pi i\theta}|u\rangle\), \(\theta\in[0,1)\).

Find: an estimate of \(\theta\) to \(n\) bits of precision.

Why \([0,1)\)? Every eigenvalue of a unitary has modulus 1, so it can be written \(e^{2\pi i\theta}\) with \(\theta \in [0,1)\). The problem is to extract that real number.

QPE is the most important subroutine in quantum computing. Shor's order finding is QPE applied to the modular-multiplication operator. HHL is QPE applied to \(e^{iAt}\). Quantum chemistry algorithms are QPE applied to \(e^{-iHt}\) to find ground-state energies. Learn it once, use it everywhere.

19.3 The Circuit

Two registers:

  • Counting register: \(t\) qubits, initialised to \(|0\rangle^{\otimes t}\). Larger \(t\) ⟶ more precision.
  • Eigenstate register: holds \(|u\rangle\).
              t counting qubits
  |0> --[H]--------------------*----------------.
  |0> --[H]-----------------*--|--- [ QFT^-1 ] --[M]--> estimate of theta
  |0> --[H]--------------*--|--|----------------'
                         |  |  |
  |u> -----------------[U^1][U^2][U^4]--- ... ---------  (unchanged)

The \(j\)-th counting qubit (from the bottom) controls \(U^{2^{j}}\).

19.4 Derivation

Step 1 — superpose the counting register.

\[ |\psi_1\rangle = \frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}|k\rangle\ \otimes|u\rangle \]

Step 2 — controlled powers of \(U\). The stack of controlled-\(U^{2^j}\) gates applies \(U^k\) to the eigenstate register when the counting register holds \(|k\rangle\). Because \(|u\rangle\) is an eigenstate,

\[ U^{k}|u\rangle = e^{2\pi i k\theta}|u\rangle , \]

so by generalised phase kick-back (L11 §3.2) the phase lands on the counting register:

\[ |\psi_2\rangle = \frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}e^{2\pi i k\theta}|k\rangle\ \otimes|u\rangle \]

The eigenstate register is unchanged and unentangled. All the information is now in the phase ramp of the counting register.

Step 3 — recognise the state. Compare with the QFT definition (L18):

\[ \mathrm{QFT}|j\rangle = \frac{1}{\sqrt{2^t}}\sum_k e^{2\pi ijk/2^t}|k\rangle . \]

If \(\theta\) happens to equal \(j/2^t\) exactly for some integer \(j\), then \(|\psi_2\rangle\) is exactly \(\mathrm{QFT}|j\rangle\).

Step 4 — apply the inverse QFT.

\[ |\psi_3\rangle = \mathrm{QFT}^{-1}|\psi_2\rangle \]

Step 5 — measure the counting register, obtaining an integer \(m\). Output

\[ \tilde\theta = \frac{m}{2^t} . \]

19.5 The Exact Case

Theorem. If \(\theta = j/2^t\) for an integer \(0\le j < 2^t\) — equivalently, \(\theta\) has an exact \(t\)-bit binary expansion — then QPE returns \(m = j\) with probability 1.

Proof. By Step 3, \(|\psi_2\rangle = \mathrm{QFT}|j\rangle\) exactly. Applying the inverse:

\[ |\psi_3\rangle = \mathrm{QFT}^{-1}\mathrm{QFT}|j\rangle = |j\rangle . \]

Measurement returns \(j\) deterministically. \(\blacksquare\)

Interpretation. Writing \(\theta = 0.\theta_1\theta_2\cdots\theta_t\) in binary, the counting register ends up holding exactly those \(t\) bits.

19.6 The General Case and the Precision Theorem

When \(\theta\) is not an exact \(t\)-bit fraction, the output spreads around the nearest fraction. Let \(b\) be the integer such that \(b/2^t\) is the best \(t\)-bit approximation, and let \(\delta = \theta - b/2^t\) with \(|\delta| \le 2^{-(t+1)}\).

Amplitude of outcome \(m\).

\[ A_m = \frac{1}{2^t}\sum_{k=0}^{2^t-1}e^{2\pi ik(\theta - m/2^t)} = \frac{1}{2^t}\cdot\frac{1 - e^{2\pi i 2^t(\theta - m/2^t)}}{1 - e^{2\pi i(\theta - m/2^t)}} \]

(a finite geometric series), giving

\[ \Pr[m] = |A_m|^2 = \frac{1}{2^{2t}}\left|\frac{\sin\big(\pi 2^t(\theta - m/2^t)\big)} {\sin\big(\pi(\theta-m/2^t)\big)}\right|^2 . \]

This is the Fejér / Dirichlet kernel — a sharply peaked function centred at \(m = 2^t\theta\).

Theorem (Standard bound). \(\Pr[m = b] \ge \dfrac{4}{\pi^2} \approx 0.405\).

Theorem (Precision–probability). To obtain \(\theta\) accurate to \(n\) bits with success probability at least \(1-\epsilon\), use

\[ \boxed{\ t = n + \left\lceil \log_2\!\left(2 + \frac{1}{2\epsilon}\right)\right\rceil \ \text{counting qubits}\ } \]

Worked values.

Desired precision \(n\) Failure \(\epsilon\) Extra qubits Total \(t\)
4 0.25 2 6
8 0.10 3 11
10 0.01 6 16
20 0.01 6 26

Cost. The controlled-\(U^{2^j}\) gates require \(1 + 2 + 4 + \cdots + 2^{t-1} = 2^t - 1\) applications of \(U\), so the cost is \(O(2^t)\) applications — exponential in the number of bits of precision. This is why QPE gives high precision only when \(U\) itself can be exponentiated cheaply (as modular exponentiation can, by repeated squaring).

19.7 What If You Do Not Have the Eigenstate?

Usually you cannot prepare \(|u\rangle\) — that would often require knowing the answer. QPE handles this gracefully. Expand an arbitrary input in the eigenbasis:

\[ |\psi\rangle = \sum_u c_u |u\rangle . \]

By linearity, QPE produces

\[ \sum_u c_u\,|\tilde\theta_u\rangle\otimes|u\rangle . \]

Measuring the counting register returns \(\tilde\theta_u\) with probability \(|c_u|^2\), and collapses the eigenstate register to the corresponding \(|u\rangle\). You get a random eigenphase, sampled according to the overlap.

In Shor's algorithm the input \(|1\rangle\) is an equal superposition of all \(r\) relevant eigenstates of the modular-multiplication operator, so the measurement returns \(\approx s/r\) for a uniformly random \(s\in\{0,\dots,r-1\}\). That is precisely the output the continued-fractions step (L20) is designed to consume.

19.8 Solved Problems

Problem 1 — Exact phase estimation

\(U = \begin{pmatrix}1&0\\0&e^{2\pi i\cdot0.375}\end{pmatrix}\) with eigenstate \(|u\rangle = |1\rangle\). Use \(t=3\) counting qubits. What is measured?

Solution. \(\theta = 0.375 = \frac{3}{8}\). In binary:

\[ 0.375 = \frac{0}{2} + \frac{1}{4} + \frac{1}{8} = 0.011_2 . \]

Since \(\theta = 3/2^3\) is an exact 3-bit fraction, the exact case applies:

\[ m = 3 = 011_2, \qquad \Pr[m=3] = 1 . \]

Output: \(\tilde\theta = 3/8 = 0.375\) ✓, exactly, in one run.

Check the state before the inverse QFT:

\[ \frac{1}{\sqrt8}\sum_{k=0}^{7}e^{2\pi ik\cdot3/8}|k\rangle = \mathrm{QFT}_8|3\rangle \ \checkmark \]

Problem 2 — Inexact phase, distribution of outcomes

Now \(\theta = 0.4\) with \(t = 3\). Compute \(\Pr[m]\) for all \(m\) and identify the most likely outcome.

Solution. \(2^t\theta = 8\times0.4 = 3.2\). The nearest integer is \(b = 3\), so \(\tilde\theta = 3/8 = 0.375\) with error \(0.025\).

Using \(\Pr[m] = \frac{1}{64}\left|\frac{\sin(8\pi(0.4 - m/8))}{\sin(\pi(0.4-m/8))}\right|^2\):

\(m\) \(0.4 - m/8\) \(\Pr[m]\)
0 \(0.400\) 0.006
1 \(0.275\) 0.009
2 \(0.150\) 0.026
3 \(0.025\) 0.877
4 \(-0.100\) 0.057
5 \(-0.225\) 0.013
6 \(-0.350\) 0.007
7 \(-0.475\) 0.005

Sum \(= 1.000\) ✓.

Most likely outcome: \(m = 3\) with probability 0.877, far above the guaranteed bound \(4/\pi^2 = 0.405\). Note the asymmetry: \(m=4\) (0.057) is more likely than \(m=2\) (0.026), because \(\theta = 0.4\) lies between \(3/8 = 0.375\) and \(4/8 = 0.5\) but nearer the former. The distribution is sharply concentrated, not spread out.

Practical procedure. Run QPE several times and take the mode. Two runs already give the correct answer with probability \(1 - (0.123)^2 \approx 98.5\%\).

Problem 3 — Choosing the number of counting qubits

You need \(\theta\) to 10 binary digits with failure probability at most 5 %. How many counting qubits, and how many applications of \(U\)?

Solution. Apply the formula with \(n = 10\), \(\epsilon = 0.05\):

\[ t = n + \left\lceil\log_2\!\left(2 + \frac{1}{2\times0.05}\right)\right\rceil = 10 + \lceil\log_2(2 + 10)\rceil = 10 + \lceil\log_2 12\rceil = 10 + \lceil3.585\rceil = 10 + 4 \]
\[ \boxed{t = 14 \ \text{counting qubits}} \]

Applications of \(U\):

\[ 2^{14} - 1 = 16{,}383 . \]

Total qubits: 14 counting + however many \(|u\rangle\) requires.

Observation. Doubling the precision from 10 to 20 bits would need \(t = 24\) and \(2^{24}\approx1.7\times10^7\) applications of \(U\) — the exponential cost in precision. QPE buys precision at exponential cost in circuit depth, which is why NISQ devices cannot run it and why iterative QPE (one counting qubit reused \(t\) times, with classical feed-forward) was invented.

Problem 4 — QPE applied to a Pauli

Apply QPE with \(t=2\) to \(U = Z\) with eigenstate \(|1\rangle\). Verify the output.

Solution. \(Z|1\rangle = -|1\rangle = e^{i\pi}|1\rangle = e^{2\pi i(1/2)}|1\rangle\), so \(\theta = \frac12\).

\(\theta = 1/2 = 2/4 = 2/2^t\) — exact for \(t=2\), with \(j = 2 = 10_2\).

Trace it. After Step 1: \(\frac12\sum_{k=0}^3|k\rangle|1\rangle\).

After Step 2 (phase \(e^{2\pi ik/2} = (-1)^k\)):

\[ \frac12\big(|0\rangle - |1\rangle + |2\rangle - |3\rangle\big)\otimes|1\rangle \]

This is \(\mathrm{QFT}_4|2\rangle\) (computed in L18, Problem 1) ✓.

After \(\mathrm{QFT}_4^{-1}\): \(|2\rangle = |10\rangle\).

Measurement gives \(m=2\), so \(\tilde\theta = 2/4 = 0.5\) ✓, and the eigenvalue is \(e^{2\pi i(0.5)} = -1\) ✓.

Note. With \(t = 1\) this reduces to the Hadamard test of L11 Problem 4: one \(H\), one controlled-\(Z\), one \(H\), measure — giving 1 with certainty.

Problem 5 — QPE for order finding (previewing Shor)

Let \(N=15\), \(a=7\). Define \(U_a|y\rangle = |ay \bmod 15\rangle\). Show that its eigenvalues have phases \(s/r\), and state what QPE would return.

Solution.

From L17, \(r = \mathrm{ord}_{15}(7) = 4\): the cycle is \(1 \to 7 \to 4 \to 13 \to 1\).

Eigenstates. For \(s = 0,1,\dots,r-1\) define

\[ |u_s\rangle = \frac{1}{\sqrt r}\sum_{k=0}^{r-1} e^{-2\pi i sk/r}\,\big|a^k \bmod N\big\rangle . \]

Verify the eigenvalue equation.

\[ U_a|u_s\rangle = \frac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi isk/r}|a^{k+1}\rangle \]

Substitute \(k' = k+1\) (indices mod \(r\), using \(a^r \equiv 1\)):

\[ = \frac{1}{\sqrt r}\sum_{k'}e^{-2\pi is(k'-1)/r}|a^{k'}\rangle = e^{2\pi is/r}\cdot\frac{1}{\sqrt r}\sum_{k'}e^{-2\pi isk'/r}|a^{k'}\rangle = e^{2\pi is/r}|u_s\rangle \ \checkmark \]
\[ \boxed{\ \theta_s = \frac{s}{r} = \frac{s}{4} \in \left\{0,\ \tfrac14,\ \tfrac12,\ \tfrac34\right\}\ } \]

The problem of preparing \(|u_s\rangle\). Building \(|u_s\rangle\) requires knowing \(r\) — which is what we are trying to find. The resolution is the key identity

\[ \frac{1}{\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle = |1\rangle . \]

Proof: the coefficient of \(|a^k\rangle\) in the sum is \(\frac{1}{r}\sum_s e^{-2\pi isk/r}\), which is 1 if \(k\equiv0\) and 0 otherwise — leaving only \(|a^0\rangle = |1\rangle\) ✓.

So we simply prepare \(|1\rangle\) — trivially easy — which is an equal superposition of all \(r\) eigenstates. By §6, QPE then returns \(\tilde\theta \approx s/4\) for a uniformly random \(s\in\{0,1,2,3\}\):

Measured \(\tilde\theta\) \(s\) Probability
\(0.00\) 0 1/4
\(0.25\) 1 1/4
\(0.50\) 2 1/4
\(0.75\) 3 1/4

Recovering \(r\). From \(\tilde\theta = 0.25 = \frac14\) we read \(r = 4\) directly. From \(\tilde\theta = 0.5 = \frac12\) we get the reduced fraction \(\frac12\), giving \(r = 2\) — wrong, because \(s=2\) and \(r=4\) share the factor 2. From \(\tilde\theta = 0\) we learn nothing.

This is why Shor's algorithm needs continued fractions and a verification step \(a^r\stackrel{?}{\equiv}1\), and why it may need to be repeated. Useful outcomes here are \(s\in\{1,3\}\) (those coprime to \(r\)), occurring with probability \(\phi(r)/r = 2/4 = 1/2\).

19.9 Practice Problems

  1. \(\theta = 0.625\) with \(t=3\): what is measured? [Ans: \(m=5\), exact]
  2. \(\theta = 1/3\) with \(t=4\): find \(b\) and the error. [Ans: \(b=5\), \(\tilde\theta = 5/16 = 0.3125\)]
  3. How many counting qubits for 6-bit precision with 1 % failure? [Ans: \(t=12\)]
  4. Apply QPE with \(t=2\) to \(U=S\) with eigenstate \(|1\rangle\). [Ans: \(\theta = 1/4\), \(m=1\), exact]
  5. Prove that the phases of \(U_a\) are exactly \(\{s/r\}\) for \(s = 0,\dots,r-1\).
  6. Show \(\Pr[b]\ge 4/\pi^2\) using \(|\sin x| \ge 2|x|/\pi\) for \(|x|\le\pi/2\).
  7. Why does the eigenstate register end up unentangled from the counting register in the exact case?

19.10 Summary

  • QPE estimates \(\theta\) where \(U|u\rangle = e^{2\pi i\theta}|u\rangle\), using \(t\) counting qubits.
  • Circuit: Hadamards → controlled-\(U^{2^j}\) (phase kick-back writes the ramp \(e^{2\pi ik\theta}\)) → \(\mathrm{QFT}^{-1}\) → measure.
  • Exact case: if \(\theta\) has a \(t\)-bit binary expansion, the answer is deterministic.
  • General case: the outcome distribution is a Fejér kernel peaked at \(b\approx2^t\theta\), with \(\Pr[b]\ge 4/\pi^2\); use \(t = n + \lceil\log_2(2+\frac{1}{2\epsilon})\rceil\) qubits.
  • Cost is \(2^t-1\) applications of \(U\) — exponential in precision, so \(U\) must be cheaply exponentiable.
  • If you cannot prepare \(|u\rangle\), feed in any state: QPE returns a random eigenphase with probability \(|c_u|^2\). In Shor, the easily-prepared \(|1\rangle\) is an equal superposition of all \(r\) eigenstates.
  • QPE is the engine of Shor, HHL and quantum chemistry.

Next lesson: L20 — Shor's algorithm for integer factorization, assembled in full.

Practise now: unit2-algorithms-lab.html → Phase Estimation tab: set \(\theta\) and \(t\), and see the Fejér-kernel probability distribution and the effect of adding counting qubits.