Quantum Phase Estimation

An algorithm to estimate the eigenvalue (phase) of a unitary operator. A key subroutine in many quantum algorithms.

Quantum Phase Estimation (QPE) determines the phase $\theta$ when a unitary $U$ acts on its eigenstate: $U|u⟩=e^{2\pi i\theta }|u⟩$.

The Problem

Given:

• A unitary operator $U$
• An eigenstate $|u⟩$ (or superposition of eigenstates)

Find: The phase $\theta$ such that $U|u⟩=e^{2\pi i\theta }|u⟩$

The Circuit

|0⟩ ──H────────●────────────────────QFT†── Measure (θ₀)
               │
|0⟩ ──H────────┼────●──────────────QFT†── Measure (θ₁)
               │    │
|0⟩ ──H────────┼────┼────●────────QFT†── Measure (θ₂)
               │    │    │
|u⟩ ──────────U¹───U²───U⁴────────────── (unchanged)

Key components:

1. Counting register: $n$ qubits initialized to $|0⟩$, determines precision
2. Target register: Holds the eigenstate $|u⟩$
3. Controlled-U operations: Apply $U^{2^k}$ controlled by qubit $k$
4. Inverse QFT: Extracts the phase as a binary number

How It Works

1. Hadamards create superposition in counting register
2. Controlled-$U$ operations encode phase information
3. The counting register ends up in state encoding $\theta$
4. Inverse QFT converts phase to binary representation
5. Measurement reads out $\theta$ (approximately)

Precision

With $n$ counting qubits:

• Precision: $2^{-n}$ (can distinguish $\theta$ values differing by $1/2^n$)
• Success probability: High for $\theta$ that’s exactly representable
• For general $\theta$: Concentration around true value

Applications

Shor’s Algorithm

QPE finds the period of modular exponentiation.

Quantum Chemistry (VQE-related)

Estimate eigenvalues of molecular Hamiltonians → ground state energies.

HHL Algorithm

Estimate eigenvalues for matrix inversion.

Quantum Counting

Count Grover solutions by estimating phase related to solution count.

Variants

Iterative Phase Estimation

Uses single counting qubit, repeated measurements. More noise-resilient, useful for NISQ.

Robust Phase Estimation

Handles noise and imperfect eigenstates better.

Quantum Eigenvalue Estimation

Generalizations for non-eigenstate inputs (get superposition of phases).

Resource Requirements

For $n$-bit precision:

• Counting qubits: $n$
• Controlled-$U$ calls: $2^n-1$ (can be expensive!)
• QFT on $n$ qubits

The cost of implementing controlled-$U^{2^k}$ is often the bottleneck.

See also: Quantum Fourier Transform, Shor’s Algorithm, VQE