Quantum Phase Estimation (QPE)

Also known as: Eigenvalue estimation

First described: Kitaev, 1995

Status: Proven Maturity: Production primitive Speedup: Polynomial-to-exponential (depending on alternative)

The problem

Given a unitary U and an eigenvector |ψ⟩ with U|ψ⟩ = e^{2πiφ}|ψ⟩, estimate φ to t bits of precision.

Apply controlled-U^{2^k} for k = 0..t-1 to a t-qubit ancilla register prepared in |+⟩^t, then inverse-QFT the ancilla. Measure in the computational basis to read φ.

Best classical

O(N) for the underlying eigenvalue problem (e.g. Lanczos); QPE wins in the structured-Hamiltonian regime.

Quantum complexity

Õ(1/ε) calls to controlled-U for ε precision (Heisenberg-limited).

Our verdict

The eigenvalue oracle for FTQC. Most applications you'd want — chemistry ground states, material spectra, eigenvalue counting — flow through QPE. Iterative variants (Kitaev's phase estimation, Bayesian QPE) are NISQ-friendlier but still demand deeper circuits than today's hardware delivers reliably.

When to use it

Eigenvalue extraction once FTQC is available — chemistry energies, condensed-matter spectra.
Inside Shor (factoring is QPE on modular-exponentiation unitary).
When you need precision and can afford the depth.

When not to use it

NISQ — depth O(1/ε) is too deep for current hardware. Use iterative-QPE or variational methods.
When you don't already have an eigenstate to feed in (state preparation is the bottleneck).

Classical baseline

For sparse, structured Hamiltonians, Krylov methods (Lanczos, Arnoldi) are very strong. QPE's win is on Hamiltonians whose dimension is exponential in particle count — fermionic systems, lattice gauge theory.

Hardware cost

t-qubit ancilla register + system qubits. Total controlled-U^{2^k} applications: O(2^t) — that's the cost of high-precision estimation.

Key papers

Quantum measurements and the Abelian Stabilizer Problem ↗
Kitaev · 1995 · ECCC

Deep-dive tutorials

Last verified: 2026-05-24