Quantum Phase Estimation

Quantum Phase Estimation

Quantum Phase Estimation (QPE) is the engine behind many of quantum computing's most celebrated algorithms, including Shor's factoring algorithm and quantum simulation of chemistry.

The core problem: Given a unitary operator U and one of its eigenstates |ψ⟩, find the phase φ such that:

The phase φ is a real number between 0 and 1. QPE encodes it as a binary fraction to n bits of precision using n ancilla qubits.

Circuit structure:

The algorithm applies controlled-$U^{2^j}$ for each counting qubit $j$. Because |ψ⟩ is an eigenstate, each application picks up a phase: the $j$-th ancilla accumulates $e^{2\pi i\cdot 2^j\cdot \phi }$. After all controlled operations, inverse QFT on the counting register extracts φ as a binary integer.

Phase kickback:

When a controlled-U gate is applied to an eigenstate, the control qubit picks up the eigenvalue's phase:

$CU(|1⟩\otimes |\psi ⟩)=|1⟩\otimes e^{2\pi i\phi }|\psi ⟩=e^{2\pi i\phi }|1⟩\otimes |\psi ⟩$

The eigenstate |ψ⟩ is unchanged. The phase ends up on the control qubit. This is phase kickback: the mechanism that makes QPE work.

Precision and resources:

When the phase is exactly representable in n bits (as in the T-gate example, φ=1/8 with n=3), the success probability is essentially 100%; the ~81% figure is the worst-case bound for general, non-representable phases. Adding extra qubits beyond the required precision boosts that bound toward 100%. The gate count scales as $O(n^2)$ for the QFT and $O(n\cdot T_U)$ for the controlled-U applications, where $T_U$ is the cost of one U application.