Iterative phase estimation

Kitaev's iterative phase estimation (IPE) estimates the eigenphase $\varphi$ of $U|\psi\rangle = e^{2\pi i\varphi}|\psi\rangle$ using a single ancilla qubit reused across $t$ sequential rounds, instead of the $t$ ancilla qubits plus inverse-QFT used by textbook phase estimation.

Per-round structure. Round $k$ (starting from the most significant bit) prepares the ancilla in $|+\rangle$, applies a controlled $U^{2^{t-1-k}}$, applies a phase correction $e^{-i\omega}$ built from the bits already measured in earlier rounds (the "semiclassical" feedback), applies $H$, and measures. The measured bit is the $k$-th bit of the binary expansion of $\varphi$. Because the ancilla is reset and reused, only one physical qubit is needed beyond the eigenstate register, at the cost of $t$ sequential circuit executions instead of one wide circuit.

Small worked instance. Take $U=S$ (the phase gate) acting on its eigenstate $|1\rangle$: $S|1\rangle = e^{i\pi/2}|1\rangle = e^{2\pi i (1/4)}|1\rangle$, so $\varphi=1/4$. In binary, $1/4 = 0.01_2$ — an exact 2-bit fraction with no truncation error. Running 2-bit IPE: round 0 (most significant bit) applies controlled-$U^{2}=S^2=Z$ and recovers bit $b_1=0$; round 1 applies controlled-$U^1=S$ with the feedback phase set from $b_1$, recovering bit $b_0=1$. The two measured bits reconstruct $\varphi=0.01_2=1/4$ exactly, since this particular phase happens to terminate at 2 bits.

Complexity. Both textbook QPE and IPE use $O(2^t)$ total controlled-$U$ applications to resolve $t$ bits of $\varphi$; IPE's advantage is $O(1)$ coherent ancilla qubits rather than $O(t)$, which matters on hardware where qubit count, not gate count, is the binding constraint.