Quantum Phase Estimation

Let $U$ be a unitary operator acting on some Hilbert space, and let $|\psi\rangle$ be one of its eigenvectors, so that

The number $\varphi$ is called the eigenphase of $U$ relative to $|\psi\rangle$. Because global phases are unobservable and $U$ is unitary, its eigenvalues always lie on the unit circle, so writing them as $e^{2\pi i \varphi}$ loses no generality. Quantum Phase Estimation is the algorithm that takes as input a copy of $|\psi\rangle$, together with the ability to apply $U$ (or more precisely, controlled versions of $U$ and its powers), and outputs a classical estimate $\tilde\varphi$ of $\varphi$, correct to $n$ bits with high probability. The problem is nontrivial because $\varphi$ is a continuous, generally irrational, real number, while quantum measurement produces only discrete classical outcomes. QPE resolves this tension using a two-register architecture. A counting register of $t$ qubits, initialized to $|0\rangle^{\otimes t}$ and then put into uniform superposition, will hold the phase estimate. A target register, holding $|\psi\rangle$, is used only to control the application of $U^{2^j}$ for various $j$, and it returns to $|\psi\rangle$ unchanged at the end (this is the defining property of an eigenstate). The counting register accumulates phase kicks proportional to $2^j\varphi$ for each qubit $j$, producing exactly the state that the inverse Quantum Fourier Transform is designed to decode. It is essential to be precise about what "controlled-$U$" access means: the algorithm assumes a black-box unitary $C\text{-}U$ that applies $U$ to the target register exactly when a control qubit is $|1\rangle$, and does nothing otherwise. Building $C\text{-}U^{2^j}$ efficiently (e.g., by repeated squaring, $j$ applications of $C\text{-}U$ composed, or a native fast-forwarding circuit) is a separate engineering problem whose cost is not included in the abstract "one query" cost of QPE — this distinction matters when comparing QPE's efficiency to classical alternatives.

The circuit uses $t$ counting qubits (initialized to $|0\rangle$) and however many qubits are needed to hold $|\psi\rangle$.

Step 1 — Superposition. Apply Hadamard gates to all $t$ counting qubits:

Step 2 — Controlled phase kicks. For $j = 0, 1, \dots, t-1$, apply $C\text{-}U^{2^j}$ controlled by qubit $j$ of the counting register, acting on the target register. Because $|\psi\rangle$ is an eigenstate of $U$ with eigenvalue $e^{2\pi i\varphi}$, it is also an eigenstate of $U^{2^j}$ with eigenvalue $e^{2\pi i \, 2^j\varphi}$. Each controlled application therefore imprints a phase onto the corresponding qubit of the counting register without disturbing $|\psi\rangle$ at all — this is the phase kickback trick. After all $t$ controlled operations, the state factors as

Step 3 — Inverse QFT. Apply $\mathrm{QFT}^{-1}$ to the counting register. Recall that the (forward) QFT maps $|j\rangle \mapsto \frac{1}{\sqrt{2^t}}\sum_k e^{2\pi i jk/2^t}|k\rangle$; its inverse is the natural decoder for a state of the form $\sum_k e^{2\pi i \varphi k}|k\rangle$, which is exactly a QFT-encoded basis state $|2^t\varphi\rangle$ when $2^t\varphi$ is an integer.

Step 4 — Measurement. Measure the counting register in the computational basis, obtaining an integer $m \in \{0,\dots,2^t-1\}$. Output the estimate $\tilde\varphi = m / 2^t$. ``` Algorithm QuantumPhaseEstimation(U, |psi>, t): Input: black-box controlled-U access; eigenstate |psi> of U with U|psi> = e^{2 pi i * phi} |psi>; t = number of counting qubits (precision/confidence parameter) Output: integer m in [0, 2^t - 1]; estimate phi_hat = m / 2^t

# Registers: counting register C (t qubits, init |0...0>),

# target register T (init |psi>) for j in 0 .. t-1: apply H to C[j] # uniform superposition for j in 0 .. t-1: apply Controlled-U^(2^j) # control = C[j], target = T

# equivalently: apply Controlled-U, 2^j times in sequence,

# or use a precomputed fast-exponentiation circuit for U^(2^j) apply Inverse-QFT to register C m <- measure(C) # standard basis measurement phi_hat <- m / 2^t return phi_hat ``` The qubit ordering convention matters: qubit $j$ of the counting register controls $U^{2^j}$, and after the inverse QFT the most significant bit of $m$ comes from the qubit that controlled the largest power $U^{2^{t-1}}$. Implementations must match this convention to the specific QFT circuit's bit-reversal behavior, or the output will be scrambled.

Gate complexity. The Hadamard layer costs $t$ gates. The inverse QFT on $t$ qubits costs $O(t^2)$ elementary gates (each of the $t$ controlled-phase-rotation layers touches at most $t$ qubits), or $O(t \log t)$ with approximate/fast variants. The controlled-$U^{2^j}$ layer requires $t$ applications of controlled powers of $U$; if each $C\text{-}U^{2^j}$ is built by repeating $C\text{-}U$ sequentially $2^j$ times, the total number of elementary $C\text{-}U$ calls is

which is exponential in $t$ unless a fast-forwarding circuit for $U^{2^j}$ (cost $\mathrm{poly}(j)$ instead of $2^j$ repetitions) is available. In algorithms like Shor's, modular exponentiation gives exactly such a fast-forwarding circuit, so the total circuit is polynomial in the input size. In the fully black-box query model, complexity is instead measured in queries to $C\text{-}U$: QPE with $t$ counting qubits uses $O(2^t)$ such queries in the naive construction, or exactly $t$ queries if controlled-$U^{2^j}$ is furnished directly as a primitive (which is the standard convention in most textbook analyses, since squaring a unitary classically-described circuit is itself efficient).

Space complexity. $t$ counting qubits plus $\dim(|\psi\rangle)$ qubits for the target register; no additional workspace is required beyond what the inverse QFT and controlled-$U$ implementations use internally.

Correctness, exact case. Suppose $\varphi = m/2^t$ exactly for some integer $0 \le m < 2^t$. After step 2 the counting register is in the state

which is precisely $\mathrm{QFT}|m\rangle$ by the definition of the QFT. Applying $\mathrm{QFT}^{-1}$ therefore returns exactly $|m\rangle$, and measurement yields $m$ with probability 1. This is the clean base case: when $\varphi$ has an exact $t$-bit binary expansion, QPE is deterministic and exact.

Correctness, general case — the amplitude calculation. In general $\varphi$ is not exactly $m^*/2^t$ for any integer $m^*$. Let $m^*$ be the integer closest to $2^t \varphi$ and write $\delta = \varphi - m^*/2^t$, so $|\delta| \le 1/2^{t+1}$. After the inverse QFT, the amplitude on outcome $m^*$ is

This is a geometric sum whose modulus can be bounded to show the distribution concentrates near $m^*$: the standard bound (proved via the geometric series estimate above) shows that the probability the measured outcome $m$ satisfies $|m - m^*| \le 2^{t-n}$ (i.e., $\tilde\varphi = m/2^t$ agrees with $\varphi$ to $n$ bits) is at least

Setting $t = n + \lceil \log_2(2 + 1/(2\varepsilon))\rceil$ makes this probability at least $1-\varepsilon$. This is the precise, checkable statement behind the informal slogan "add a few extra qubits for high confidence": each additional counting qubit beyond the $n$ bits of desired precision roughly halves the failure probability.

Correctness intuition without the algebra. The inverse QFT is a discrete Fourier analyzer: it takes a signal of the form $e^{2\pi i \varphi k}$ (as a function of $k$) and reports which frequency $\varphi$ dominates. If $\varphi$ sits exactly on a frequency bin $m^*/2^t$, the analyzer reports it with certainty. If $\varphi$ falls between bins, energy leaks into neighboring bins — exactly the "spectral leakage" phenomenon familiar from classical discrete Fourier analysis — but the leaked energy decays quickly away from the true bin, which is why nearby outcomes remain overwhelmingly likely.

Tradeoffs. QPE's precision (number of correct bits $n$) and its confidence ($1-\varepsilon$) both cost extra counting qubits, and the query cost to $C\text{-}U^{2^j}$ scales with $t$ in the worst case. If $U$ cannot be fast-forwarded, achieving many bits of precision becomes exponentially expensive in queries — the algorithm's efficiency claims are conditional on efficient controlled-power circuits, not free of assumptions.

Take $t=3$ counting qubits and suppose the true phase is $\varphi = 0.1011\ldots_2$ in binary — concretely, let

which does not have an exact 3-bit expansion ($5/8 = 0.101_2$ exactly, but the extra $1/32$ term pushes it off-grid). This exercises the non-exact case honestly rather than hiding behind a phase that lands perfectly on a grid point. We have $2^t\varphi = 8 \times 0.65625 = 5.25$. The nearest integer is $m^* = 5$, and $\delta = \varphi - 5/8 = 0.03125 = 1/32$.

The measured outcome $5$ gives estimate $0.625$, which is the best 3-bit approximation to the true $0.65625$ — the algorithm is not "wrong" here, it has correctly found the closest representable value, and the residual error is bounded exactly by the half-bin-width guarantee derived above ($|\delta|\le 2^{-(t+1)} = 1/16$ in the worst case for the nearest target, matching the observed $0.03125$). If a second run is performed, there is a small but nonzero chance of measuring $4$ or $6$ instead — this is the spectral leakage predicted by the amplitude formula, not a bug. Using $t=6$ counting qubits instead would shrink this residual error by roughly a factor of 8, at the cost of twice as many controlled-$U^{2^j}$ layers.

Phase estimation crystallized out of the broader development of quantum algorithms built on the Quantum Fourier Transform, following Shor's 1994 discovery that factoring reduces to period-finding. The phase-estimation formulation — separating "find the eigenphase" from "find the order" — was made explicit shortly after, and it was quickly recognized as a reusable primitive rather than a Shor-specific trick.

Quantum Phase Estimation is the load-bearing subroutine of Shor's algorithm, where it drives the Order-Finding Subroutine that finds the multiplicative order of an integer modulo $N$ — the step that ultimately breaks RSA-style cryptography on a sufficiently large fault-tolerant quantum computer. It is equally central to Quantum Counting, which uses phase estimation on the Grover diffusion operator to count marked items without measuring them directly, generalizing Grover's search to a counting problem. In quantum simulation and chemistry, QPE applied to a Hamiltonian's time-evolution unitary $U = e^{-iHt}$ extracts energy eigenvalues directly, making it the textbook approach to computing molecular ground-state energies on a quantum computer — a target application frequently cited by companies and research labs pursuing quantum advantage in materials and drug design. In numerical linear algebra, the HHL Algorithm uses QPE to extract eigenvalues of a matrix encoded as a unitary, invert them, and reconstruct a solution vector to a linear system exponentially faster than classical methods under certain sparsity and conditioning assumptions. Understanding QPE's exact-vs-approximate behavior, and its dependence on efficient controlled-$U$ powers, is therefore prerequisite knowledge for essentially every advanced quantum algorithm built after 1994.

Ask the tutor: How does the choice of $t$ in QPE translate into the continued-fractions post-processing used in Shor's order-finding algorithm?