Algorithms · Kitaev iterative phase estimation
Iterative phase estimation
Estimates the eigenphase of a unitary using a single reused ancilla qubit instead of a full phase-estimation register.
Strong empiricalUpdated
Open on the mapView frozen graph
A small worked example, computed in your browser. It is not a result from this record's papers.
Phase estimation of P(3*pi/4)
3 counting qubits estimating the phase of P(3π/4), which is 2π·3/8 exactly: a phase 3-bit QPE can represent exactly.
Step 1 of 4 · X
Probability of each outcome after this step
- 1000100%
Puts the target qubit into |1⟩, which is an eigenstate of P(3*pi/4): applying the gate to it multiplies it by a phase and changes nothing else. That is the whole requirement QPE places on its input.
The whole state moves from 0000 to 1000 — one certain outcome before, one certain outcome after, no superposition either side.
Spreads the 3 counting qubits over all 8 values they can hold at once. Each one will later ask about a different power of the phase.
Probability spreads from 1 outcome to 8. All 8 are equally likely.
Counting qubit k applies P(3*pi/4) to the target 2^k times, controlled on itself. The target never changes — it is an eigenstate — so the phase it would have picked up is kicked back onto the control instead. This is the step that writes the answer into the register.
The outcome probabilities do not move at all. What this step changes is phase — 8 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
The inverse Fourier transform reads that phase pattern back out as a binary number. Phase in, bits out.
Probability gathers from 8 outcomes onto 1. 1011 goes from 12.5% to 100.0%.
Readout The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
Open in Studio- Steps3
- Wires2
- Ancilla qubits1 (reused across rounds)
- Rounds (bits of precision)t = 2 (toy instance)
- Toy phaseφ = 1/4 (U = S gate)
- Papers2
Kitaev's iterative (semiclassical) phase estimation trades the O(t) ancilla qubits of textbook QPE for O(1) ancilla and classical feedback between t sequential rounds.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Kitaev's iterative phase estimation (IPE) estimates the eigenphase of using a single ancilla qubit reused across sequential rounds, instead of the ancilla qubits plus inverse-QFT used by textbook phase estimation.
Per-round structure. Round (starting from the most significant bit) prepares the ancilla in , applies a controlled , applies a phase correction built from the bits already measured in earlier rounds (the "semiclassical" feedback), applies , and measures. The measured bit is the -th bit of the binary expansion of . Because the ancilla is reset and reused, only one physical qubit is needed beyond the eigenstate register, at the cost of sequential circuit executions instead of one wide circuit.
Small worked instance. Take (the phase gate) acting on its eigenstate : , so . In binary, — an exact 2-bit fraction with no truncation error. Running 2-bit IPE: round 0 (most significant bit) applies controlled- and recovers bit ; round 1 applies controlled- with the feedback phase set from , recovering bit . The two measured bits reconstruct exactly, since this particular phase happens to terminate at 2 bits.
Complexity. Both textbook QPE and IPE use total controlled- applications to resolve bits of ; IPE's advantage is coherent ancilla qubits rather than , which matters on hardware where qubit count, not gate count, is the binding constraint.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Ancilla qubits
- 1 (reused across rounds)
- Rounds (bits of precision)
- t = 2 (toy instance)
- Toy phase
- φ = 1/4 (U = S gate)
- Controlled-U calls
- O(2^t) total
- Qubit overhead
- O(1) vs O(t) for textbook QPE
- Feedback
- Classical, between rounds
H (ancilla)on ancillaControlled-Uᵏon ancilla, eigenstateFeedback phase + Hon ancilla
Quantum vs classical
Classical baseline
Classical eigenvalue decomposition of a unitary requires the explicit matrix and costs exponentially in the number of qubits it acts on.
Quantum claim
IPE extracts binary digits of the phase using only black-box controlled-U access, with O(2^t) total queries for t bits of precision and O(1) coherent ancilla qubits.
How to compare
Compare total controlled-U calls and ancilla-qubit count against textbook QPE, and against classical diagonalization when the unitary's matrix is actually available.
Nobody has reviewed this record for gaps yet.
from qiskit import QuantumCircuit
import numpy as np
def ipe_round(k, total_bits, omega):
"""One semiclassical IPE round for U = S-gate, eigenstate |1>."""
qc = QuantumCircuit(2, 1)
qc.x(1) # eigenstate |1> of S
qc.h(0) # ancilla in |+>
reps = 2 ** (total_bits - 1 - k)
for _ in range(reps):
qc.cp(np.pi / 2, 0, 1) # controlled-S^reps
qc.p(-omega, 0) # feedback from previously measured bits
qc.h(0)
qc.measure(0, 0)
return qc
# phi = 1/4 for U = S acting on |1>; recovered exactly in 2 rounds
round0 = ipe_round(0, 2, omega=0.0) # expect bit b1 = 0
round1 = ipe_round(1, 2, omega=0.0) # feedback uses b1; expect bit b0 = 1
FINAL_CIRCUIT = round1Where this sits
This record is named by the layer graph at:
- Iterative phase estimation on one ancilla Method
Takes A circuit for U that can be applied as controlled U^(2^j), a preparation routine for a state whose overlap with the target eigenvector is not negligible, the number of bits of the phase wanted, and the failure probability that may be tolerated. Returns An estimate of the eigenphase to the requested number of bits, with the failure probability it was obtained at, plus the two costs that actually differ between routes: how many ancillas were held at once, and how many sequential rounds were run.
Related entries
- Quantum phase estimation
Algorithms
- Quantum Fourier Transform
Algorithms
- Transverse-field Ising simulation
Algorithms
References
- Quantum measurements and the Abelian Stabilizer Problem
A. Yu. Kitaev · 1995
Original iterative phase-estimation scheme using a single ancilla qubit and classical post-processing.
- Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
M. Dobsicek, G. Johansson, V. S. Shumeiko, G. Wendin · 2006
Formalizes the semiclassical feedback rounds used in this entry's circuit.