Iterative Quantum Phase Estimation

Overview

Iterative quantum phase estimation measures the eigenvalue of a unitary operation one bit at a time using a single extra qubit. The standard version of phase estimation uses a register of t ancilla qubits to get t bits of precision at once, and it needs a quantum Fourier transform. The iterative version reuses a single ancilla, measures it, and feeds the result forward as a classical correction for the next round.

The goal is to save qubits and circuit width rather than to gain speed. The total number of applications of the unitary is the same as in the standard algorithm, but the machine needs only one control qubit, which is why this form is the one most often used on early quantum computers and in resource estimates for chemistry.

The problem it solves

Estimating the phase associated with a quantum operation's eigenstate (as in standard phase estimation), but using significantly fewer physical qubits.

History and background

Kitaev's 1995 paper on the abelian stabilizer problem described a phase estimation procedure based on repeated single-qubit measurements, and it is the conceptual origin of the iterative approach. Griffiths and Niu showed in 1996 that the quantum Fourier transform in Shor's algorithm can be replaced by a semiclassical version in which one qubit is measured at a time and later rotations are conditioned on earlier results, which is the key to the single-ancilla trick.

Dobšíček, Johansson, Shumeiko, and Wendin published an arbitrary-accuracy iterative phase estimation algorithm in 2007, with a two-qubit benchmark, and Higgins and coauthors reported an experiment in Nature the same year showing Heisenberg-limited phase estimation without entanglement. Later work introduced robust and Bayesian variants, including the robust phase estimation of Kimmel, Low, and Yoder in 2015 and the Bayesian methods of Wiebe and Granade in 2016, and these are the versions used in modern experiments and in estimates for fault-tolerant chemistry.

How it works

Repeats a single-qubit measurement-and-feedback procedure multiple times, extracting one bit of phase information per round instead of using a large register of qubits simultaneously.

Recall that phase estimation extracts the phase phi in the eigenvalue e to the 2 pi i phi of an operator U. The bits of phi are determined from least significant to most significant by using controlled powers of U. Kickback of a controlled U to the power 2 to the k writes the k-th bit of phi in the phase of the control qubit.

Suppose you first use the largest power of U, 2 to the m minus 1. A single control qubit then tells you the last bit of the m-bit binary expansion of phi. Having learned that bit, you can undo its effect by applying a known rotation, and move on to the next-largest power, which tells you the next bit, and so on until all bits are found.

The rotation that undoes the known bits is what replaces the inverse quantum Fourier transform. It is applied to the same single qubit, and the angle depends on the earlier measurement outcomes, which are classical data held by the controller. So the quantum hardware needs only one ancilla and the classical computer does the bookkeeping.

Step by step

1. Prepare the target register in an eigenstate of the unitary U, or a state with high overlap, and a single ancilla qubit in the state 0.
2. Apply a Hadamard gate to the ancilla.
3. Apply controlled U raised to the power 2 to the k, with the ancilla as the control, starting with k equal to m minus 1 for an m-bit estimate.
4. Apply a phase rotation to the ancilla by an angle determined by the bits already measured, then another Hadamard gate.
5. Measure the ancilla to obtain the next bit of the phase, and reset it to the state 0 for the next round.
6. Repeat with the next smaller power until all m bits are obtained, then assemble them into the estimate of phi.

A worked example

Suppose the true phase is phi equal to 5 over 8, which is 0.101 in binary. With m equal to 3 rounds, the first round uses U to the 4th power, and the ancilla measurement returns the last bit, 1. The second round uses U squared and applies a correction rotation of minus pi over 2 for the known bit, and the measurement returns the middle bit, 0. The third round uses U, applies corrections for both bits, and returns the first bit, 1.

Assembling gives 0.101, which equals 5 over 8 exactly. When the phase is not an exact binary fraction, the measurement outcomes are random with the correct statistics, and the procedure is repeated several times per bit and combined by majority vote or by Bayesian inference to reach the target confidence.

Complexity and resources

What hardware it needs

• Mid-circuit measurement and reset of the ancilla, and classically conditioned rotations with low latency.
• Controlled powers of U, which dominate the circuit depth.
• For useful chemistry, fault-tolerant hardware to run the long controlled evolutions.

Applications

• Computing molecular ground-state energies in quantum chemistry resource estimates, where saving qubits matters.
• Order finding in Shor's algorithm with a reduced qubit count, as in the 2n plus 3 qubit constructions.
• Calibrating quantum gates by estimating small rotation errors.
• Metrology and sensing tasks that measure a phase near the Heisenberg limit.

Limitations and caveats

• It needs fast classical feedback, which is a hardware challenge for some platforms.
• The total circuit depth is the same as for standard phase estimation, so it does not reduce the demand for coherence.
• It requires a good initial state, as with all phase estimation methods.
• Noise in mid-circuit measurement and reset affects the result, so robust versions use more repetitions.

Common misconceptions

• Iterative phase estimation is not faster than the standard version. It uses fewer qubits, not fewer gates.
• It does not remove the need for an eigenstate or a good approximation of one.

How it compares

• Standard phase estimation uses many ancillas and an inverse quantum Fourier transform, and runs in a single coherent pass.
• Kitaev's original method and Bayesian phase estimation trade more repetitions for simpler circuits.
• Variational eigensolvers avoid long controlled evolutions but lack accuracy guarantees.

Real-world impact

Makes phase estimation — a key subroutine in Shor's Algorithm and quantum chemistry simulation — more practical on today's qubit-limited NISQ hardware.

Why it matters

Because qubits are expensive, the ability to trade width for classical bookkeeping is valuable. Iterative phase estimation is the form of the algorithm most likely to be used on early fault-tolerant machines, and it underlies many chemistry resource estimates.

It also illustrates a general principle in quantum algorithm engineering: use mid-circuit measurement and classical feedback to reduce the quantum resources.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Phase Estimation (QPE)
• Related algorithm: Quantum Fourier Transform (QFT)
• Related algorithm: Shor's Algorithm
• Related algorithm: Variational Quantum Eigensolver (VQE)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database