QFT and phase estimation

The Fourier transform on amplitudes, and the routine that reads eigenphases: the engine inside Shor.

You will learn to

Read a QFT circuit: Hadamards and controlled phases in a triangle, then swaps.
Explain what phase estimation outputs for an eigenstate.
Relate precision to the number of counting qubits.

QFT ∣ x ⟩ = \frac{1}{N} k = 0 \sum N - 1 e^{2 π i x k / N} ∣ k ⟩, N = 2^{n}

The same transform as classical DFT, but on amplitudes: n qubits need only O(n²) gates instead of O(N log N) operations. The catch is that you cannot read the amplitudes out directly.

Try it

QFT of |101⟩

Open the State tab: all eight basis states have equal probability but phases that advance in steps; the Line view shows the phase ramp. Then open Compile → Levels to see how many CPhase gates survive on hardware.

OPENQASM 3.0;
include "stdgates.inc";
qubit[3] q;
x q[0];
x q[2];
barrier q;
h q[2];
cp(pi/2) q[1], q[2];
cp(pi/4) q[0], q[2];
h q[1];
cp(pi/2) q[0], q[1];
h q[0];
swap q[0], q[2];

Open in the IDE Open in the Playground

Phase estimation

Given a unitary U and an eigenstate |u⟩ with U|u⟩ = e^{2πiφ}|u⟩, phase estimation writes φ into a register of t counting qubits: controlled-U^{2^j} gates kick the phase back onto the counting qubits, and an inverse QFT turns the phase ramp into a binary number. With t qubits you read φ to t bits of precision with high probability.

Try it

Estimate φ = 1/4 with two counting qubits

U = P(π/2) on q2 (eigenstate |1⟩, φ = 1/4). Simulate: the counting register reads 01 = 1/4 in binary every time. Change the phase to π/3 and the answer spreads: 1/6 is not representable in two bits.

OPENQASM 3.0;
include "stdgates.inc";
qubit[3] q;
bit[2] c;
x q[2];
h q[0];
h q[1];
cp(pi/2) q[0], q[2];
cp(pi) q[1], q[2];
barrier q;
swap q[0], q[1];
h q[0];
cp(-pi/2) q[0], q[1];
h q[1];
c[0] = measure q[0];
c[1] = measure q[1];

Open in the IDE Open in the Playground

Quiz 1 · 10 XP

Doubling the number of counting qubits in phase estimation…

Quiz 2 · 10 XP

Why is the QFT not simply a faster FFT?

Key takeaway

The QFT is cheap on amplitudes but unreadable on its own; phase estimation uses it to turn an eigenphase into bits, one counting qubit per bit of precision.

Docs: QFT, QPE and IQPE benchmarks

Up next: Shor's algorithm: the overview

OPENQASM 3.0; include "stdgates.inc"; qubit[3] q; bit[2] c; x q[2]; h q[0]; h q[1]; cp(pi/2) q[0], q[2]; cp(pi) q[1], q[2]; barrier q; swap q[0], q[1]; h q[0]; cp(-pi/2) q[0], q[1]; h q[1]; c[0] = measure q[0]; c[1] = measure q[1];