Quantum Phase Estimation (QPE)

Prerequisites: Quantum Fourier Transform -- QPE uses the inverse QFT as its core readout mechanism. Make sure you are comfortable with QFT before diving in.

The Idea

Imagine you have a vibrating tuning fork, but you cannot see it -- you can only listen. Your job is to figure out the exact frequency of the vibration. Classically, you would sample the sound wave many times and run a Fourier analysis. Quantum Phase Estimation does the same thing, except the "vibrating fork" is a quantum unitary operator, and the "frequency" is the phase of its eigenvalue.

Given a unitary U and one of its eigenstates |psi>, where

U |psi> = e^(2*pi*i*phi) |psi>

QPE estimates the phase phi (a number between 0 and 1) using a bank of counting qubits that act like a quantum frequency detector. More counting qubits means finer resolution, just as a longer recording of the tuning fork lets you pin down its pitch more precisely.

How It Works

The algorithm uses three stages:

1. Controlled kicks -- probe the eigenvalue

Each counting qubit j controls the operation U^(2^j) on the eigenstate register. Because |psi> is an eigenstate, the controlled operation imprints a phase on counting qubit j:

|0> + e^(2*pi*i * 2^j * phi) |1>

After all controlled operations, the counting register encodes phi in its relative phases -- like a set of clock hands spinning at different speeds.

2. Inverse QFT -- decode the phases

The inverse Quantum Fourier Transform converts those relative phases into a computational-basis state. It is the quantum equivalent of a discrete Fourier analysis that extracts the dominant frequency.

3. Measurement -- read the answer

Measuring the counting register collapses it to a bitstring whose integer value, divided by 2^n, gives the estimated phase.

CODECopy
Counting:  |0> ──H──────■─────────────────┐
           |0> ──H──────┼────■─────────────┤ QFT^-1 ──M
           |0> ──H──────┼────┼────■────────┘          M
                         │    │    │                   M
Eigenstate:|1> ────────U^1──U^2──U^4──────────────────

The Math

The eigenvalue equation is:

U |psi> = e^(2*pi*i*phi) |psi>,   phi in [0, 1)

Write phi as a binary fraction:

CODECopy
phi = 0.phi_1 phi_2 ... phi_n  (base 2)
    = phi_1/2 + phi_2/4 + ... + phi_n/2^n

After the controlled-U gates, the state of the counting register is:

1/sqrt(2^n) * sum_{k=0}^{2^n - 1} e^(2*pi*i*phi*k) |k>

This is exactly the QFT of the state |2^n * phi>. Applying the inverse QFT yields |2^n * phi> with probability 1 when phi is an exact n-bit binary fraction. For non-exact fractions, the result concentrates around the nearest representable value with probability >= 4/pi^2 ~ 0.405 (worst case, one additional bit gives >= 1 - epsilon with high probability via Kitaev's analysis).

Precision

For phases that are exact binary fractions (k/2^n), QPE returns the correct answer deterministically. For other phases, the closest binary fraction dominates the output distribution.

Expected Output

Running with the default phase=0.25 and n_counting=3:

CODECopy
Quantum Phase Estimation:
  Counts: {'010': 1024}
  Estimated phase: 0.25
  True phase:      0.25
  Error:           0.000000

The bitstring 010 encodes the binary fraction 0.010_2 = 2/8 = 0.25. Because 0.25 is an exact 3-bit binary fraction, all shots land on 010.

Qiskit bit ordering note: Qiskit uses little-endian convention where the rightmost character in a bitstring is qubit 0. For our circuit, counting qubits 0, 1, 2 map to classical bits 0, 1, 2, so the Qiskit bitstring reads as q2 q1 q0. For phase=0.25 (binary 0.010): qubit 0=0, qubit 1=1, qubit 2=0, giving bitstring "010".

Running the Circuit

PYTHONCopy
from circuit import run_circuit, estimate_phase, verify_phase_estimation

# Basic usage
counts = run_circuit(phase=0.25, shots=1024)
estimated = estimate_phase(counts, n_counting=3)
print(f"Estimated phase: {estimated}")   # 0.25

# Higher precision
counts = run_circuit(phase=0.3, n_counting=5, shots=4096)
estimated = estimate_phase(counts, n_counting=5)
print(f"Estimated phase: {estimated}")   # ~0.3125

# Verify against known test cases
result = verify_phase_estimation(shots=4096)
for check in result["checks"]:
    status = "PASS" if check["passed"] else "FAIL"
    print(f"[{status}] {check['name']}: {check['detail']}")

Try It Yourself

1. Non-exact phase: Run QPE with phase=1/3 and n_counting=3. What bitstrings appear? Increase n_counting to 5 and 8 -- how does the distribution sharpen?

2. Precision experiment: For phase=0.1, plot the estimation error as a function of n_counting from 2 to 10. Does the error decrease as 1/2^n as theory predicts?

3. Different unitary: Modify create_phase_estimation to use a T-gate (phase = 1/8) instead of a general CP gate. Verify that QPE recovers phase = 0.125 exactly with 3 counting qubits.

4. Build your own: Implement iterative QPE (Kitaev's single-ancilla version) that uses only 1 counting qubit with classical feedback. Compare the circuit depth to standard QPE for the same precision.

What's Next

• Quantum Fourier Transform -- the building block that makes QPE's readout possible.
• Grover's Search -- another foundational algorithm that achieves quadratic speedup for unstructured search.
• Deutsch-Jozsa -- a simpler algorithm that demonstrates quantum advantage through phase kickback (the same mechanism QPE exploits).

References

1. Kitaev, A. Yu. (1995). Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026
2. Nielsen, M. A. & Chuang, I. L. (2010). Quantum Computation and Quantum Information (10th anniversary ed.), Section 5.2: The quantum Fourier transform and its application -- Phase estimation.