Quantum Phase Estimation Algorithm

Many of the most famous quantum algorithms are, in the end, trying to learn an eigenvalue. Shor's algorithm factors an integer by finding the eigenvalue of a modular-multiplication operator. Quantum chemistry calculates the ground-state energy of a molecule by finding the smallest eigenvalue of a Hamiltonian. HHL solves a linear system Ax = b by inverting the eigenvalues of A. In every one of these, the quantum computer's job reduces to: take a unitary U and an eigenstate |u\rangle, then tell me the phase \varphi such that U|u\rangle = e^{2\pi i \varphi}|u\rangle.

Phase estimation is the universal subroutine that does exactly that.

The picture, in one breath. You have a unitary U on some number of qubits. You have a state |u\rangle that happens to be an eigenstate of U — meaning U does not rotate |u\rangle, it only multiplies it by a phase e^{2\pi i \varphi}. That phase encodes the information you want. The problem is that in isolation, e^{2\pi i \varphi} on |u\rangle is a global phase — invisible to any measurement. You cannot distinguish |u\rangle from e^{2\pi i \varphi}|u\rangle by doing anything to |u\rangle alone.

QPE gets around the invisibility problem by kicking the phase back onto a register of ancilla qubits, and then using the inverse QFT to turn that phase register into a binary number you can just read out. One controlled gate, and the phase is out of hiding. A ladder of them, and the phase becomes a t-bit binary expansion. An inverse QFT, and the binary expansion lands in the computational basis where a measurement reveals it as bits.

This chapter builds the algorithm from those three ingredients — phase kickback (ch. 60), the inverse QFT (ch. 67-68), and controlled-U^{2^k} gates — and shows in full, with worked examples, how they combine into the single most important subroutine in quantum algorithms.

The setup — input, output, ingredients

Input. A unitary U on n_u qubits, and an eigenstate |u\rangle with eigenvalue e^{2\pi i \varphi}. Here \varphi is an unknown real number in [0, 1) — the "phase fraction." (The convention of writing the eigenvalue as e^{2\pi i \varphi} rather than e^{i\theta} is chosen so that \varphi represents a fraction of a full turn, which makes the binary expansion natural.)

Output. A t-bit binary approximation \widetilde\varphi = 0.\varphi_1\varphi_2\ldots\varphi_t of \varphi, obtained as the measurement outcome on a t-qubit ancilla register. Here 0.\varphi_1\varphi_2\ldots\varphi_t is binary-fraction notation: 0.\varphi_1\varphi_2\ldots\varphi_t = \varphi_1/2 + \varphi_2/4 + \cdots + \varphi_t/2^t, where each \varphi_k \in \{0, 1\}.

Ingredients.

• t ancilla qubits, all initialised to |0\rangle. They will hold the phase register. Larger t gives higher precision.
• A target register of n_u qubits holding |u\rangle. For QPE to work, you need to be able to prepare |u\rangle — or at least a state that is approximately an eigenstate.
• The ability to implement controlled-U^{2^k} for k = 0, 1, \ldots, t-1. The powers grow doubly: U, U^2, U^4, \ldots, U^{2^{t-1}}.
• An inverse QFT circuit on the t-qubit ancilla register.

Why doubling powers: to extract the k-th bit of \varphi's binary expansion, you need to multiply the phase by 2^k so that the relevant bit is shifted into the "ones" place where a controlled-U can read it. Doubling powers is exactly the binary-bit-extraction trick — and it is why QPE uses an exponential number of U applications to get polynomial precision.

Step one — Hadamards make the ancilla superposition

The ancillas begin in |0\rangle^{\otimes t}, a plain product state with no interesting phase structure. Apply a Hadamard to each:

Why this move: H|0\rangle = \tfrac{1}{\sqrt 2}(|0\rangle + |1\rangle), so on t qubits the Hadamard tower produces a uniform superposition over all 2^t basis states. Every t-bit integer x between 0 and 2^t - 1 appears with amplitude 1/\sqrt{2^t}. This is the canonical "first move" of a huge class of quantum algorithms: put the register into a uniform superposition so the subsequent gates can act on every input in parallel.

The full state (ancilla ⊗ target) after the Hadamards is

The target is still |u\rangle, unchanged. The ancillas hold a uniform spread of "labels" |x\rangle, each tagged with the same target eigenstate.

Step two — the controlled-U ladder builds the phase

Now the central move. For each ancilla qubit k = 0, 1, \ldots, t-1, apply a controlled-U^{2^k} gate with ancilla k as the control and the target register as the target.

Take it one qubit at a time first. Suppose k = 0: the gate is just controlled-U. On the branch where ancilla 0 is in |0\rangle, nothing happens. On the branch where ancilla 0 is in |1\rangle, the target is hit with U. Because the target is an eigenstate with eigenvalue e^{2\pi i \varphi}, the result is

Exactly as in phase kickback, the phase e^{2\pi i \varphi} jumps off the target and sticks onto the control — because on the |1\rangle branch the phase is present and on the |0\rangle branch it isn't, which makes it a relative phase rather than a global one. The effect on ancilla 0 is

Now do the same reasoning for ancilla k, which controls U^{2^k}. The eigenvalue of U^{2^k} on |u\rangle is (e^{2\pi i \varphi})^{2^k} = e^{2\pi i \cdot 2^k \varphi}. So ancilla k picks up the relative phase e^{2\pi i \cdot 2^k \varphi}:

Why U^{2^k}'s eigenvalue is e^{2\pi i \cdot 2^k \varphi}: applying U multiplies the eigenstate by e^{2\pi i \varphi}; applying U again multiplies by e^{2\pi i \varphi} a second time, giving e^{4\pi i \varphi}; applying it 2^k times multiplies by e^{2\pi i \cdot 2^k \varphi}. Raising U to the 2^k-th power doubles the phase k times, which is exactly the binary shift \varphi \mapsto 2^k \varphi.

Put all t ancillas together. The joint state of the ancilla register is the tensor product

Expand this product. Each factor contributes either |0\rangle (amplitude 1/\sqrt 2, no phase) or |1\rangle (amplitude 1/\sqrt 2, phase e^{2\pi i \cdot 2^k \varphi}). A basis state |x\rangle = |x_{t-1} x_{t-2} \ldots x_0\rangle picks up a phase e^{2\pi i \cdot 2^k \varphi} for each position k where x_k = 1, and nothing for positions where x_k = 0. Adding the exponents:

because \sum_k x_k 2^k is exactly the integer x written in binary. So the ancilla register after the controlled-U ladder is

Written out, one line at a time, the ancillas have become a state whose amplitudes are uniform in magnitude but whose phases march through e^{2\pi i \cdot 0 \cdot \varphi}, e^{2\pi i \cdot 1 \cdot \varphi}, e^{2\pi i \cdot 2 \cdot \varphi}, \ldots — a linear ramp of phases indexed by x. This is exactly a Fourier-basis state: the QFT of the computational-basis state |2^t \varphi\rangle.

The target register, through all of this, remains |u\rangle. The eigenstate is untouched. The phase has migrated from target to ancillas in one pass.

Step three — inverse QFT converts phase into bits

The ancilla register currently sits in a Fourier-basis state. Read the QFT definition from the previous chapters:

Compare this with what you just built on the ancillas:

The two are identical under the substitution y/2^t = \varphi, i.e. y = 2^t \varphi. In other words, the ancilla state is exactly \text{QFT}|2^t \varphi\rangle — the QFT image of the integer 2^t \varphi.

Why this substitution works cleanly when \varphi = k/2^t: if \varphi is a t-bit binary fraction, 2^t\varphi is an integer, and the ancilla state is the exact QFT image of a computational-basis state. If \varphi is not expressible as k/2^t, 2^t\varphi is not an integer and the ancilla state is a "rounded" Fourier-basis state — it will concentrate amplitude near the nearest integer but not perfectly. This is the source of the finite-precision error discussed in the next chapter.

Now apply the inverse QFT (\text{QFT}^\dagger) to the ancillas. By definition of the inverse,

If 2^t \varphi is an integer, the ancilla register collapses into the computational-basis state |2^t \varphi\rangle — exactly. If it isn't, the inverse QFT concentrates amplitude on the integer closest to 2^t \varphi, with smaller amplitudes spreading to nearby integers.

Step four — measurement reveals the bits

Measure the t ancilla qubits in the computational basis. The outcome is a t-bit string y_{t-1} y_{t-2} \ldots y_0 interpreted as an integer y = \sum_k y_k 2^k.

Divide by 2^t to get the phase estimate:

If \varphi = k/2^t for some integer k, this measurement gives \widetilde\varphi = \varphi with probability 1.

If \varphi is not a t-bit fraction, this measurement gives the nearest t-bit approximation with probability at least 4/\pi^2 \approx 0.405 — and if you want higher confidence, the next chapter shows how to boost it.

And that is the entire algorithm. Four steps: Hadamard the ancillas, fire the controlled-U ladder, inverse QFT, measure. The target register is untouched throughout (it is a "work eigenstate," used catalytically) and the answer lands in the ancillas.

Worked examples

Why phase kickback is doing all the work

Pause for a moment to name the magic. The target register was in an eigenstate, so applying U to it did nothing — just multiplied by a phase. A phase on a lone state is invisible. But a phase on one branch of a superposition, with the other branch untouched, is a relative phase — and relative phases are visible.

The controlled-U^{2^k} gate manufactures exactly that situation. On the |1\rangle branch of ancilla k, U^{2^k} fires and the target picks up a phase. On the |0\rangle branch, nothing. The phase that was hidden on the target now appears as a relative phase on the ancilla — one ancilla per power, with the phase scaling as 2^k \varphi.

The Fourier basis is precisely the basis adapted to reading phases-as-integers. A state of the form \sum_x e^{2\pi i x \varphi}|x\rangle is the Fourier image of |2^t \varphi\rangle, and the inverse QFT is the tool that converts it back into a computational-basis state whose bit-pattern is the binary expansion of 2^t \varphi.

Take away either ingredient and the trick fails. Without an eigenstate, there is no clean phase to kick back — U|u\rangle would be a different state, and you would not be able to factor |u\rangle out. Without the QFT, the phases on the ancillas would remain encoded in relative phases rather than in bit values, invisible to a computational-basis measurement. Combining them is the trick. It is no accident that the QFT sits at the end of Shor's algorithm as well — the QFT's job is to turn phase information into basis-state information, which is what every measurement ultimately reads.

The target register — work eigenstate, not consumed

A crucial property of QPE: the target register is unchanged at the end. You input |u\rangle, you output |u\rangle. The eigenstate is catalytic; it is used to stamp phases onto the ancillas but is not consumed or destroyed.

This matters for two reasons.

First, if preparing |u\rangle is expensive, you only need to do it once. The same |u\rangle can be fed through QPE again (with a fresh set of ancillas) to get another phase sample, useful for majority-vote boosting (next chapter).

Second, QPE is part of a longer quantum subroutine in many algorithms. In HHL, for instance, the target register holds the input vector |b\rangle, which is written as a superposition over eigenstates of A: |b\rangle = \sum_j \beta_j |u_j\rangle. QPE acting on each component |u_j\rangle leaves it intact and attaches the corresponding eigenvalue estimate \widetilde\lambda_j to an ancilla — so after QPE, the state is \sum_j \beta_j |u_j\rangle |\widetilde\lambda_j\rangle, ready for conditional rotations based on \widetilde\lambda_j. None of that would work if QPE collapsed the eigenstate.

Common confusions

• "QPE needs an exact eigenstate." Not exactly. If the input is a superposition |\psi\rangle = \sum_j \beta_j |u_j\rangle of several eigenstates with different eigenvalues, QPE outputs the phase \widetilde\varphi_j corresponding to eigenvalue e^{2\pi i \varphi_j} with probability |\beta_j|^2. The output is a random sample from the spectrum, weighted by the input's overlap with each eigenstate. This is actually used deliberately — if you can prepare a rough approximation to a ground state, QPE will sometimes project you onto an exact eigenstate and simultaneously tell you its eigenvalue.

• "The controlled-U^{2^k} gates are cheap." They are not. Each successive gate doubles the number of U-applications: the last gate applies U a total of 2^{t-1} times. Total count across the ladder is 1 + 2 + 4 + \cdots + 2^{t-1} = 2^t - 1 applications of U. That is exponential in t. For t = 20 bits of precision, that is about a million U-applications — doable only if U itself has an efficient (polynomial-size) quantum circuit. The reason QPE works in Shor's algorithm is precisely that the modular-multiplication unitary has an O(n^3)-gate implementation, so U^{2^k} is polynomial-size for every k.

• "QPE has a classical analogue." It does not. Classical methods for finding eigenvalues of a unitary (matrix diagonalisation, power iteration) work on the matrix directly, not on eigenstates. QPE works by embedding the eigenvalue into a superposition phase and using the QFT to read it — an intrinsically quantum mechanism built on phase kickback, which has no classical cousin.

• "QPE gives the exact phase." Only when \varphi is exactly k/2^t for some integer k. Otherwise it gives the nearest t-bit fraction with probability \ge 4/\pi^2 \approx 40\%, and the runner-up outcomes take up the rest of the probability. The next chapter (phase estimation accuracy) unpacks the full distribution and shows how to boost the success rate.

• "The inverse QFT is the `QPE^{-1}' somehow." The inverse QFT is a subroutine within QPE, not the inverse of QPE as a whole. QPE's circuit is: Hadamards, controlled-U^{2^k} ladder, \text{QFT}^\dagger, measurement. Reversing that (dropping the measurement, reversing every gate) would give a circuit that, run on |\widetilde\varphi\rangle|u\rangle, would prepare a uniform ancilla superposition — the time-reversal of QPE. That is occasionally used as a subroutine itself but is not what "\text{QFT}^\dagger inside QPE" means.

Going deeper

Superposition of eigenstates — QPE samples the spectrum

When the input is |\psi\rangle = \sum_j \beta_j |u_j\rangle with different eigenvalues e^{2\pi i \varphi_j}, run the QPE circuit. Linearity means QPE acts independently on each eigenstate component: after the full circuit (but before measurement), the joint state is

where |\widetilde\varphi_j\rangle is the ancilla state peaked at 2^t \varphi_j.

Measure the ancillas. With probability |\beta_j|^2, you get \widetilde\varphi_j. Simultaneously — and this is the subtle, powerful part — the target register collapses to |u_j\rangle. You have simultaneously (i) estimated an eigenvalue and (ii) prepared its corresponding eigenstate. This is how VQE and QPE-based chemistry algorithms bootstrap: start from a rough trial state, run QPE, and read out both the eigenvalue and the clean eigenstate in one go.

The downside: you get only one eigenvalue per run, sampled with probability |\beta_j|^2. If you want the lowest eigenvalue (the ground-state energy), you need the trial state to have significant overlap with the true ground state. Algorithmic work has gone into adiabatic preparation of good trial states as an upstream step to QPE.

Kitaev's original 1995 construction

Alexei Kitaev introduced phase estimation in 1995 (arXiv:quant-ph/9511026) in a slightly different form than the QFT-based version shown above. Kitaev's original algorithm uses O(\log(1/\varepsilon)) controlled-U gates but not a QFT — instead, it does bit-by-bit estimation using separate Hadamard tests on individual ancillas.

The idea: to estimate the k-th bit \varphi_k of the binary expansion, prepare a single ancilla in |+\rangle, apply controlled-U^{2^{k-1}}, then H, then measure. The outcome is \varphi_k with a probability that depends on whether the higher bits have already been corrected for. Kitaev showed that with O(\log n \cdot \log(1/\delta)) repetitions per bit (for confidence 1 - \delta), you can extract all n bits sequentially with high probability.

Kitaev's construction uses fewer qubits — just one ancilla at a time — but more runs and classical postprocessing. It is a precursor of the iterative phase estimation algorithms used on current NISQ hardware, where qubit counts are precious and circuit depth is forgiving.

Iterative phase estimation

A modern NISQ-friendly variant: use a single ancilla qubit and extract one bit of \varphi per repetition of the circuit, re-using the same ancilla and the same target after classical feedforward. The procedure, roughly:

1. Estimate the lowest bit \varphi_t first by running controlled-U^{2^{t-1}} and measuring the ancilla in the X basis.
2. Update the next round of controlled-U with a classically-controlled phase correction that "subtracts off" the bit you just found.
3. Repeat for \varphi_{t-1}, \varphi_{t-2}, \ldots, \varphi_1.

Total ancilla count: 1. Total U-applications: still 2^t - 1. Total classical processing: O(t) conditional feedforward steps.

Iterative QPE is implemented on every major NISQ hardware vendor (IBM, IonQ, Rigetti) as a benchmark algorithm, because its low qubit count makes it accessible on current devices. Dobšíček et al. (2007) formalised the variant most commonly used today (arXiv:quant-ph/0610214).

Measurement-based phase estimation

A conceptual variant: instead of the full QFT ladder, interleave controlled-U gates with single-qubit measurements, using the measurement results to adaptively choose the next gate's parameters. This achieves the same information output as QPE with a circuit whose ancilla count is 1 but whose classical processing is more sophisticated.

Measurement-based QPE is one member of the broader "adaptive quantum algorithms" family, where measurement outcomes mid-circuit drive the gate choices for subsequent rounds.

Applications — a tour

Shor's algorithm. The unitary U_a is modular multiplication by a on a register of n bits: U_a|x\rangle = |ax \bmod N\rangle. Its eigenvalues are e^{2\pi i k/r} where r is the multiplicative order of a mod N and k runs over \{0, 1, \ldots, r-1\}. QPE extracts k/r, from which r can be classically recovered via continued fractions, from which non-trivial factors of N can be recovered by standard reduction.

Quantum chemistry. The Hamiltonian H of a molecule determines its energy levels via H|E_j\rangle = E_j|E_j\rangle. Exponentiate to get U = e^{-iH\tau} for some time step \tau; then the eigenvalues of U are e^{-iE_j\tau}, phases equal to -E_j\tau / (2\pi). QPE on U with a trial ground state extracts the ground-state energy, the central quantity in predicting molecular behaviour. This is why quantum computers are expected to outperform classical ones for electronic-structure calculation.

HHL (linear systems). Given A and b, solve Ax = b. HHL writes |b\rangle = \sum_j \beta_j |u_j\rangle in the eigenbasis of A, applies QPE to tag each component with its eigenvalue \widetilde\lambda_j, does a conditional rotation to build 1/\widetilde\lambda_j amplitudes, and un-computes the QPE. Runtime is O(\log N) in the matrix size under strong assumptions — an exponential speedup when the assumptions hold.

Grover / amplitude amplification via QPE. The Grover operator G is a unitary whose eigenvalues are e^{\pm 2i\theta} where \sin^2\theta = M/N (marked items / total). Running QPE on G gives \theta directly, from which M can be extracted — this is the "quantum counting" algorithm.

VQE bootstrapping. In variational quantum eigensolvers (VQE), a classical optimiser steers a parameterised quantum circuit toward an approximate ground state. QPE can be run at the end of VQE as a validation and refinement step: it both certifies the energy and projects onto the nearest exact eigenstate.

Indian context — TIFR, IISc, and the National Quantum Mission

Quantum phase estimation is on the curriculum of every Indian quantum computing research group. TIFR Mumbai runs courses on quantum algorithms that derive QPE in exactly the form shown here, often followed by Shor's algorithm as the first real use case. IISc Bangalore and IIT Madras have postgraduate programmes that cover QPE as part of their quantum information theory courses, with hands-on implementations on IBM Quantum cloud hardware.

India's National Quantum Mission (2023, ₹6000 crore over 8 years) funds research that includes QPE-based algorithms for chemistry and materials science — a natural fit since India's semiconductor and pharmaceutical industries have material-science problems that classical simulation has hit scaling walls on.

Where this leads next

• Phase estimation accuracy — how many ancillas for a given precision, the 4/\pi^2 success probability, and boosting by majority vote.
• Applications of phase estimation — a survey of the algorithms built on top of QPE, beyond the brief tour here.
• Shor's algorithm — the flagship QPE application: integer factoring via period-finding.
• HHL algorithm — solving linear systems with QPE as the eigenvalue-inversion step.
• Variational quantum eigensolver — the NISQ-era cousin of QPE that sidesteps the exponential gate count.

References

1. Alexei Kitaev, Quantum measurements and the Abelian stabilizer problem (1995) — arXiv:quant-ph/9511026. The original phase estimation paper.
2. Wikipedia, Quantum phase estimation algorithm.
3. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §5.2 — phase estimation derivation and accuracy analysis — Cambridge University Press.
4. John Preskill, Lecture Notes on Quantum Computation, Chapter 7 — phase estimation and its applications — theory.caltech.edu/~preskill/ph229.
5. Qiskit Textbook, Quantum Phase Estimation — hands-on implementation with Qiskit.
6. Stephen Jordan, Quantum Algorithm Zoo — curated catalogue of quantum algorithms, with QPE listed as a fundamental subroutine.