Day: November 9, 2025

Quantum Phase Estimation

A key application of the quantum Fourier transform (see this post) is the Quantum Phase Estimation algorithm. This algorithm allows one to estimate the phase (or eigenvalue) of a unitary operator and serves as a central component of many quantum algorithms, including Shor’s factoring algorithm and quantum simulation.

Consider a unitary matrix U. Since U^\dagger U = I, all eigenvalues of U have the form e^{2\pi i \theta} with 0 \leq \theta < 1. Expressing \theta in binary gives

\theta = 0.\theta_1 \theta_2 \theta_3 \cdots = \sum_{k=1}^\infty \theta_k \, 2^{-k},

where each \theta_k \in {0,1}. The task is to estimate \theta to n binary digits of precision.

More precisely, the quantum phase estimation algorithm aims to determine the phase \theta in the eigenvalue equation

U |\psi\rangle = e^{2\pi i \theta} |\psi\rangle,

where U is the given unitary operator, |\psi\rangle is an eigenstate of U that can be prepared as an input state, and \theta is the phase to be determined. We further assume that controlled-U^{2^l} operations can be implemented for arbitrary non-negative integer l. The goal is to estimate \theta to the desired number of digits with high probability.

Now suppose that we express \theta in n binary digits,

\theta = 0.\theta_1\theta_2\cdots \theta_n.

Then, we have

U^{2^l} \lvert \psi \rangle = e^{2 \pi i 0.\theta_1\theta_2\cdots\theta_n 2^l} \lvert \psi \rangle = e^{2 \pi i \theta_1\cdots\theta_l.\theta_{l+1}\cdots\theta_n} \lvert \psi \rangle

where the integer part of \theta_1\cdots \theta_l.\theta_{l+1}\cdots \theta_n can be omitted, as it contributes only a trivial phase factor of 1.

For the controlled unitary C(U^{2^l}), its action on |+\rangle|\psi\rangle (with |+\rangle the control qubit) is:

C(U^{2^l}) \frac{1}{\sqrt{2}} ( \lvert 0 \rangle + \lvert 1 \rangle ) \lvert \psi \rangle = \frac{1}{\sqrt{2}} \lvert 0 \rangle \otimes \lvert \psi \rangle + e^{2 \pi i 0.\theta_{l+1}\cdots \theta_n} \lvert 1 \rangle \otimes \lvert \psi \rangle

= \frac{1}{\sqrt{2}} (|0\rangle + e^{2\pi i 0.\theta_{l+1}\cdots \theta_n} |1\rangle) \otimes |\psi\rangle

It is convenient to view this control qubit as representing the $(l+1)$-th digit of a binary number k = k_1 k_2 \cdots k_n = k_1 \times 2^0 + k_2 \times 2^1 + \cdots + k_n \times 2^{n-1}.

With this notation, the above expression can be rewritten as

C(U^{2^l}) \frac{1}{\sqrt{2}} (\lvert0\rangle + \lvert1\rangle)\lvert\psi\rangle = \frac{1}{\sqrt{2}} \sum_{k_{l+1}=0}^1 e^{2 \pi i \theta k_{l+1} 2^l} \lvert k_{l+1}\rangle \lvert\psi\rangle

This expression for the first qubit is familiar from our earlier discussion of the quantum Fourier transform, and it naturally suggests that the quantum Fourier transform should be applied here. The eigenstate \lvert \psi \rangle therefore remains unchanged and can be reused in subsequent steps.

Fig 1: quantum circuit for quantum phase estimation algorithm.

The quantum phase estimation algorithm uses two quantum registers as shown in Figure 1:

  • First register (phase record): Contains n qubits, which will store the estimated phase.
  • Second register (eigenstate): Contains the eigenstate \lvert \psi \rangle, which is an eigenstate of the unitary operator U.

The quantum phase estimation algorithm consists of the following steps:

  1. Prepare Initial State

The system starts with two registers:

  • The first register is initialized in the state \lvert 0 \rangle^{\otimes n}.
  • The second register is initialized in the eigenstate \lvert \psi \rangle of U.

The initial state is: \lvert 0 \rangle^{\otimes n} \otimes \lvert \psi \rangle.

  1. Apply Hadamard Gates

Apply Hadamard gates to each qubit in the first register, thereby creating a uniform superposition over all possible computational basis states:

\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \lvert k \rangle \otimes \lvert \psi \rangle

Here, k = k_1 k_2 \cdots k_n denotes the binary representation of the integer k, with the bits encoded from the bottom to the top qubit in the first register.

  1. Apply Controlled-U^{2^l} Operations

For each qubit k_l in the first register, apply the controlled-U^{2^l} operation.
This step entangles the first and second registers, yielding the state:

\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \lvert k \rangle \otimes U^k \lvert \psi \rangle

Since U \lvert \psi \rangle = e^{2 \pi i \theta} \lvert \psi \rangle, this becomes:

\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2 \pi i k \theta} \lvert k \rangle \otimes \lvert \psi \rangle

At this stage, the second register is no longer needed, as all phase information is now encoded in the first register.

  1. Apply the Inverse Quantum Fourier Transform

Apply the inverse quantum Fourier transform (U_{\rm QFT}^\dagger) on the first register to extract the phase information:

\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2 \pi i k \theta} \lvert k \rangle

  1. Measure the First Register

Finally, measure the qubits in the first register. The measurement will yield the binary representation of the phase \theta with an n-bit approximation.
The output will be an n-bit approximation of the phase \theta, such that:

\theta \approx 0.\theta_1 \theta_2 \dots \theta_n

where \theta_1, \theta_2, \dots, \theta_n are the binary digits of \theta.