The Quantum Fourier Transform & Phase Estimation
An exponentially fast Fourier transform, and how to use it.
A classical computer needs about operations to Fourier-transform a list of numbers, even with the fast Fourier transform. A quantum computer applies the same transform to the amplitudes of qubits with about gates. The catch: you cannot read those amplitudes, only sample from them. This lesson shows exactly when that is enough, and builds phase estimation, the engine inside Shor's algorithm.
What you’ll learn
- Define the quantum Fourier transform on qubits and prove that it is unitary.
- Show that a periodic state is mapped to sharp peaks at multiples of , with the offset hidden in the phases.
- Derive the product formula and build the QFT from Hadamards and controlled phase rotations with gates.
- Analyze phase estimation: the role of controlled-, the exact case, and the output distribution for a general phase.
- Explain why the QFT does not speed up the Fourier transform of classical data.
The Fourier transform as a unitary
Let and . The quantum Fourier transform is the linear map defined on the computational basis by
where the integer is written in binary on qubits, qubit 0 (the top wire) holding the most significant bit. On a general state it is the discrete Fourier transform of the amplitude vector: with .
The columns of are the vectors ; compute their inner products.
For this is a geometric series whose ratio is an -th root of unity, so it sums to zero.
For every term is , giving . The columns are orthonormal, so is unitary.
Think first What is , the QFT on a single qubit? And what is ?
, the Hadamard gate, because . And , the uniform superposition. Every basis state becomes a "plane wave" of equal magnitudes: all of its information sits in the phases.
Periodic states make sharp peaks
The QFT shines on periodic states. Suppose the period divides and the state is a uniform superposition over one residue class:
In Shor's algorithm a state like this appears with an offset that is random and unknown to you.
Insert the definition and split .
The same geometric-series argument as for unitarity, now with terms.
Only survives. Each of the peaks has probability , and the offset appears only in the phases.
Five qubits (), input with period and some offset. What is the probability of measuring after the QFT?
Show the answer
12.5 %
The peaks sit at multiples of , namely , and is one of them. Each of the peaks has probability , whatever the offset.
Think first What happens when does not divide ?
The peaks no longer sit on integers. Probability concentrates on the integers nearest to , with tails that fall off like the inverse square of the distance; the nearest integer to each is still hit with probability roughly or more. You get an approximation of , and Shor's algorithm turns it into the exact fraction with continued fractions.
The product formula
Write in binary, , and use binary fractions . The QFT of a basis state then factorizes into single-qubit states, which is the key to building it from small gates.
Expand , with the most significant output bit.
The exponential of a sum is a product, and each factor involves only one : the sum over bit strings factorizes into a tensor product.
Only the fractional part of matters, and it consists of the last bits of .
The product formula. Output qubit 1 depends only on ; output qubit depends on every input bit.
In (so ), what is the state of the last output qubit, the least significant bit ?
Show the answer
D.
The last factor has phase , giving . Equivalently, the coefficient of in is .
Building the circuit
Let , so , and . A controlled- multiplies by and leaves the other basis states alone, so it is symmetric in its two qubits. In the composer below it is a control dot and a phase gate in the same column.
Because .
Controlled on , the rotation adds to the binary fraction.
After controlled rotations, wire 1 holds the last factor of the product formula. The control wires are untouched and still in basis states.
Repeat for each wire in turn. Wire needs controls only from the wires below it, which have not been touched yet.
The wires now hold the factors in reverse order. Final swaps (or simply relabeling the wires) put them in place.
| Gate | Number in | For |
|---|---|---|
| Hadamard | 3 | |
| Controlled- | 3 | |
| SWAP | 1 | |
| Total | 7 |
from math import pi
from qiskit import QuantumCircuit
def qft(n: int) -> QuantumCircuit:
"""QFT with qubit 0 as the most significant bit (this course's convention)."""
qc = QuantumCircuit(n)
for j in range(n):
qc.h(j)
for k in range(2, n - j + 1):
qc.cp(2 * pi / 2**k, j + k - 1, j) # controlled-R_k: control j+k-1, target j
for j in range(n // 2):
qc.swap(j, n - 1 - j)
return qcQiskit numbers qubits little-endian (qubit 0 is the least significant bit), so compare this with its library QFT only after accounting for the wire order.
Phase estimation
Here is the most important use of the QFT. A unitary has an eigenstate with , and you want the phase . You are given and may apply controlled-. Recall phase kickback: a controlled- acting on leaves alone and writes the eigenvalue onto the control, .
Put the -qubit counting register into uniform superposition.
Counting qubit (top ) controls . Together they apply with , and the eigenvalue kicks back the phase .
If has an exact -bit binary expansion, the counting register is exactly the Fourier transform of .
The inverse QFT returns with certainty.
In general the output is spread over , sharply peaked at the -bit values nearest to .
You run phase estimation on the input , where are eigenstates with distinct phases that are exact -bit numbers. What does the counting register read?
- An estimate of the average
- or , each with probability
- Always , the phase of the first term
- Nothing useful: phase estimation requires an exact eigenstate
Show the answer
B. or , each with probability
By linearity the final state is . The work-register states are orthogonal, so measuring the counting register gives or with probability each, and the work register collapses to the matching eigenstate. Shor's algorithm relies on exactly this.
What the QFT buys you
| Problem | Unitary | The eigenphase reveals |
|---|---|---|
| Order finding (Shor) | , and from it the order of modulo | |
| Quantum counting | the Grover iterate | an angle with , the fraction of marked items |
| Energy estimation | an eigenvalue of the Hamiltonian, via | |
| Discrete logarithms (Shor) | multiplication by and on two registers | the exponent in |
Next, Shor's Factoring Algorithm applies phase estimation to modular multiplication and uses continued fractions to turn the estimate of into the exact period.
Key takeaways
- is unitary. A state with period becomes equal peaks at multiples of ; the offset survives only as phases.
- The product formula gives a circuit of Hadamards, controlled rotations and swaps: gates versus for the FFT, but acting on amplitudes.
- Phase estimation: , controlled-, then . An exact -bit phase is read with certainty; otherwise the nearest -bit value has probability at least .
- A superposition of eigenstates yields one eigenphase at random, with probability equal to its squared amplitude: the engine of Shor's algorithm.
- The QFT does not speed up Fourier transforms of classical data; input loading and readout dominate.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
How many controlled phase rotations does the textbook QFT circuit on qubits contain?
- 10
- 45
- 90
- 1024
Show the answer
B. 45
Wire receives controlled rotations, so the total is .
. The input is the uniform superposition over all . Which outcomes can a measurement after the QFT return?
- Only
- Multiples of 16
- Multiples of 4
Show the answer
D. Multiples of 4
The period is , so the peaks sit at multiples of , each with probability . The offset 5 changes only the phases.
You run phase estimation with counting qubits on and its eigenstate . What does the counting register read?
- with certainty
- with certainty
- with probability about
- A uniformly random 3-bit string
Show the answer
A. with certainty
, so . A phase with an exact 3-bit expansion is returned with certainty: .
Why does the QFT not give an exponential speedup for the discrete Fourier transform of a classical list of numbers?
- The QFT circuit needs gates, like the FFT
- The QFT computes a different transform from the DFT
- Loading arbitrary numbers into amplitudes and reading out amplitudes each cost operations or samples in general
- Quantum gates are slower than classical operations
Show the answer
C. Loading arbitrary numbers into amplitudes and reading out amplitudes each cost operations or samples in general
The transform itself is cheap, gates. Input and output are the bottleneck: amplitudes are not directly readable, and preparing a generic -dimensional state is costly.
In phase estimation with a generic phase , what does one extra counting qubit do?
- Doubles the probability of the most likely outcome
- Halves the grid spacing , and doubles the total number of controlled- applications
- Nothing, unless has an exact binary expansion
- Adds a second eigenphase to the output
Show the answer
B. Halves the grid spacing , and doubles the total number of controlled- applications
The estimate lives on a grid of spacing , so precision doubles. The new top qubit controls , so the total count of applications, , roughly doubles too.
Go deeper
- Deriving the QFT Circuit · The product formula, O(n²) gates and the approximate QFT.
- Phase Estimation: Error Analysis · How many qubits, how much precision, what success probability.
- The Hidden Subgroup Problem · The framework unifying Simon, Shor and their limits.
Further reading
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, ch. 5 (Cambridge, 10th anniv. ed., 2010).
- R. Cleve, A. Ekert, C. Macchiavello & M. Mosca, "Quantum algorithms revisited", Proc. R. Soc. Lond. A 454, 339 (1998).
- A. Yu. Kitaev, "Quantum measurements and the Abelian stabilizer problem", arXiv:quant-ph/9511026 (1995).
- D. Coppersmith, "An approximate Fourier transform useful in quantum factoring", IBM Research Report RC19642 (1994); arXiv:quant-ph/0201067.