Quantum Phase Estimation
Quantum phase estimation (QPE) is an algorithm that reads out the hidden phase of a quantum operation as a binary number. It puts a set of counting qubits in superposition, and then applies the operation 1, 2, 4, … times so each counting qubit picks up a multiple of the unknown phase. Finally an inverse QFT turns those phases into bits you can measure. It is the engine inside Shor's algorithm and most proposed chemistry algorithms, and at useful precision it needs circuits so deep that only an error-corrected machine could run them.
| Task | Best classical | Quantum |
|---|---|---|
| Ground-state energy of an m-qubit Hamiltonian (worst case) | Exponential in m — the matrix has 2^m rows | Polynomial-size circuits per run, if you can prepare a state close to the eigenstate (theory; that preparation can itself be hard) |
| One extra bit of precision | n/a | One more counting qubit — and double the controlled-U applications |
What problem does phase estimation solve?
Some special states are left almost unchanged by a quantum operation U. The only change is a turn of phase. We write this as U|ψ⟩ = e^(2πiφ)|ψ⟩. Such a state |ψ⟩ is called an eigenstate of U. The turn, φ (phi), is its phase. (It is linked to U's eigenvalue.) Phase estimation finds φ as a binary fraction. You get as many bits as you have counting qubits.
Think of a clock hand that moves the same unknown amount each time you press a button. You can't see the hand directly. Phase estimation is a clever way to read off how far it moves per press.
Why care about a phase you can't see? Because important answers hide there. The energy levels of a molecule are hidden in the phases of the operation that moves the molecule forward in time. (The math object for a molecule's energy is called its Hamiltonian.) The period that Shor's algorithm needs is hidden in the phases of multiplying by a number, over and over. Phase estimation is the all-purpose tool that turns "hidden phase of a quantum process" into "a number on a screen."
How would a normal computer do it?
For a grid of numbers (a matrix) you can write down, finding its eigenvalues is routine math. The trouble is size. A system of m qubits has a matrix with 2^m rows. For 40 qubits that is about a trillion rows. Exact methods hit a wall at about 50 qubits' worth of state.
Being honest means giving the other side too. Normal computers have excellent shortcut methods. They have names like Lanczos, DMRG, tensor networks, and quantum Monte Carlo. They work well for many real physical systems, and they keep getting better. Phase estimation's advantage is only proven against exact normal methods on general systems. It is not proven against the best shortcuts on the systems chemists really care about.
How does phase estimation work?
It takes three moves:
- Spread out the counting qubits. Hadamard gates put n counting qubits into an equal superposition of all 2ⁿ values.
- Apply U 1, 2, 4, … times. Counting qubit k controls U applied 2^k times (written U^(2^k)) to the eigenstate. Through phase kickback, the phase lands on the counting qubit instead of the eigenstate. So that qubit's phase becomes 2^k·φ. Now the counting qubits hold φ, 2φ, 4φ, and so on, in their phases.
- Inverse QFT. This phase pattern is exactly what a QFT makes from a binary number. So the inverse QFT turns it back into bits, which you measure.
Here are the honest warnings. First, you must be able to prepare the eigenstate, or a state very close to it. If not, you get a random mix of different phases. Second, you must be able to run "controlled U^(2^k)" efficiently. For n bits of precision, the last step applies U 2ⁿ⁻¹ times. For 10 bits that is 512 times. So the depth doubles with each extra bit of precision.
Run it: what is the phase of a P(π/4) gate?
What happens when the phase doesn't fit?
The same circuit, now estimating P(1.0). Its phase is φ = 1 ÷ 2π ≈ 0.159, which is not a multiple of 1/8. Now only about 78% of shots read the nearest value (counting value 1). The rest spill into nearby values, mostly 2 (about 11%). Three bits give three bits of precision, no more. Each extra bit costs one qubit and doubles the controlled-U work.
What are its limits?
- Preparing the eigenstate. The answer is only as good as how close your starting state is to the eigenstate you want. Making good starting states for hard molecules is an open research problem. It is not a solved step.
- Depth doubles with each bit. n bits of phase needs about 2ⁿ controlled uses of U. Chemistry needs a precision of about 1.6 milli-Hartree (a tiny unit of energy, equal to 1 kcal/mol). That points to circuits with millions to billions of steps. See why depth is the real limit.
- Controlled time steps are costly. In chemistry, U is itself a big circuit that simulates the molecule. Making it controlled, and repeating it 2ⁿ times, multiplies a cost that was already large.
- Doesn't fit today's noisy machines. Today's era is called NISQ, for noisy intermediate-scale quantum. These depths are exactly why near-term work moved to VQE. VQE gives up phase estimation's guarantees to get short circuits.
How does phase estimation do on hardware today?
Phase estimation has been shown exactly the way you see it here. A few counting qubits estimated the phase of one hand-picked gate, on superconducting, trapped-ion, and photonic devices. That shows the circuit works. It doesn't show a useful ability. The answer was known in advance, and the whole run fits in a few dozen gates.
No hardware has run phase estimation on a problem whose answer wasn't already easy for a normal computer. On every serious roadmap, chemistry-grade phase estimation is an algorithm for the error-corrected era. Run the 4-qubit demo in the lab, and compare it with today's device specs at hardware/qpus.