Part IV. Protocols and Algorithms · Chapter 31
Quantum Fourier Transform
The quantum Fourier transform never appears in a headline and appears inside nearly every serious algorithm: it is the basis change that turns hidden periodicity into bits you can measure.
In this chapter 9 sections
Reader question. What transformation does the quantum Fourier transform perform, and what information can its circuit make observable?
The QFT maps computational-basis amplitudes to discrete Fourier components with phase-encoded output, implemented by Hadamards, controlled rotations, and bit reversal; it is valuable as a subroutine when structured phases are later sampled, not as a way to read an exponentially long Fourier vector.
- This chapter does not claim the QFT alone solves a problem or outputs all transform coefficients.
- It does not hide approximation error, qubit-order reversal, or controlled-rotation cost.
The DFT written as a unitary
Define the matrix, normalization, and basis action.
The quantum Fourier transform maps computational-basis states to Fourier-basis states; superpositions whose amplitudes step through regular phase progressions. Applied to a state with no periodic structure, it gives you nothing you wanted. Applied to a state whose phases encode a period, the inverse QFT concentrates that information into measurement outcomes you can read.
That is why the QFT appears inside phase estimation and period finding rather than on its own poster. Those algorithms arrange for the answer to live in phases; the QFT is the reader. Understanding it as a basis change; the same conceptual move as the Hadamard, one chapter-sized step further; keeps both halves of that sentence in view.
Evidence boundary. The QFT is the unitary discrete Fourier transform over computational basis states. [Michael A. Nielsen] [John Watrous]
Binary fractions factor the output state
Derive the product form for a basis input.
For an n-bit input x, QFT|x> can be written as a tensor product of single-qubit phase states whose angles are binary fractions 0.x_j x_{j+1}... . Circuit order reverses those factors, which is why diagrams either end with SWAPs or declare reversed output order. A two-qubit hand trace should reconcile matrix indices, wire order, and that swap convention.
Evidence boundary. Its circuit decomposes into Hadamards, controlled phase rotations, and output-order reversal. [John Preskill] [Don Coppersmith]
Two qubits expose every phase
Calculate the four-by-four transform and circuit.
On an -qubit register with , the definition is:
Each input basis state spreads over all output basis states with equal magnitude, distinguished only by phase. For two qubits, , and the phases step through the fourth roots of unity:
Different inputs produce different phase progressions, and those progressions are mutually orthogonal; which is why the transform is unitary, reversible, and implementable as a circuit of one Hadamard per qubit plus controlled phase gates. The circuit is a corollary of the definition, not the definition.
Evidence boundary. Approximate QFT can omit small rotations with a quantifiable accuracy/cost tradeoff. [Don Coppersmith] [Peter W. Shor]
Notation contract: ; ; bit order and sign convention declared; R_k angle defined.
Resource account: controlled rotations build precision
Map phase angles to gate sequence.
| Resource | Exact n-qubit QFT | Truncated account |
|---|---|---|
| Hadamards | n | n |
| Controlled rotations | n(n-1)/2 | Keep only angles above the declared cutoff; report the retained count. |
| Output swaps | floor(n/2) or zero under reversed output convention | Same convention must be used by the verifier. |
| Depth and synthesis | Architecture-dependent after routing and gate synthesis | Report depth together with the approximation metric; omission count alone is insufficient. |
Hadamards create each output phase reference; controlled R_k rotations add successively smaller binary-fraction contributions. The exact circuit uses n Hadamards and n(n-1)/2 controlled rotations, plus optional output swaps. This O(n^2) gate account describes preparing Fourier amplitudes, not reading all Fourier coefficients, which measurement cannot do.
Swaps reconcile mathematical and wire order
Make bit reversal explicit.
The QFT is the quantum cousin of the discrete Fourier transform from signal processing, with one decisive difference: you cannot read the coefficients. A classical DFT hands you the whole spectrum; the QFT holds it in amplitudes, and measurement returns samples. Algorithm design is the art of arranging for the coefficient you want to carry most of the probability before you measure.
The implementation checklist for any QFT-based workflow:
- choose the register size; it sets both resolution and circuit depth;
- prepare the phase-structured input state;
- apply the QFT or its inverse;
- measure;
- interpret the sampled bit string classically.
Precision and sample distributions matter even for clean, noise-free algorithms. A QFT on paper is exact; a QFT in a workflow is a statistical component.
Approximate QFT drops small angles
State an error/cost trade rather than a slogan.
Omitting rotations below an angle threshold shortens depth while perturbing the output state. The approximation must be tied to a norm or downstream success bound and the hardware's native precision; saying a rotation is small is not an error analysis. On noisy devices, an omitted gate can improve observed performance even as ideal algorithmic error rises, so report both contributions.
QFT conformance suite
| Field | Reader-visible record |
|---|---|
| Format | Parameterized circuit generator, dense-matrix oracle, and approximation comparison |
| Verification | Tests n≤6 circuit/matrix equivalence up to declared bit order, inverse round-trip, and approximation error versus omitted rotations. |
| Availability | Source-embedded acceptance record; no separate download is claimed |
{
"artifact": "QFT conformance suite",
"format": "Parameterized circuit generator, dense-matrix oracle, and approximation comparison",
"acceptance_test": "Tests n≤6 circuit/matrix equivalence up to declared bit order, inverse round-trip, and approximation error versus omitted rotations.",
"publication_state": "source-embedded contract and worked fixture"
}Executable reference fixture
Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.
import cmath
def qft_matrix(size, normalized=True):
if type(size) is not int or size < 2 or size & (size - 1):
raise ValueError("QFT fixture requires a power-of-two size")
scale = size ** 0.5 if normalized else 1.0
return [[cmath.exp(2j * cmath.pi * row * column / size) / scale
for column in range(size)] for row in range(size)]
def unitarity_error(matrix):
size = len(matrix)
return max(abs(sum(matrix[row][a].conjugate() * matrix[row][b] for row in range(size))
- (1.0 if a == b else 0.0))
for a in range(size) for b in range(size))
four_point = qft_matrix(4)
eight_point = qft_matrix(8)
unnormalized = qft_matrix(4, False)
four_error = unitarity_error(four_point)
eight_error = unitarity_error(eight_point)
mutant_error = unitarity_error(unnormalized)
invalid_rejected = False
try:
qft_matrix(6)
except ValueError:
invalid_rejected = True
assert four_error < 1e-12 and eight_error < 1e-12
assert mutant_error > 1.0 and invalid_rejected
print(f"PASS: 31 QFT unitary_error_N4={four_error:.3g} N8={eight_error:.3g} unnormalized_error={mutant_error:.1f}")Scope boundary
- This chapter does not claim the QFT alone solves a problem or outputs all transform coefficients.
- It does not hide approximation error, qubit-order reversal, or controlled-rotation cost.
Depth commitment. One unitary definition, one product factorization, one two-qubit trace, and one approximation test.
Practice problem
Compute QFT|01> for two qubits by matrix and circuit, including the final swap convention, then apply inverse QFT.
- Deliverable
- Two derivations, phase-labeled output vector, ordering statement, and round-trip result.
- Pass condition
- The conformance suite compares matrix/circuit states up to global phase and recovers |01>.
Verification record
Expected solution form. Dense-matrix calculation beside a gate trace and automated diff.
Model answer. With basis order 00,01,10,11, QFT|01>=(|00>+i|01>-|10>-i|11>)/2. The standard two-qubit circuit produces the same labeled amplitudes once its final swap convention is applied; inverse QFT returns |01>.
Model result and check. CI executes both conventions and verifies the student's declared one.
Acceptance test. The conformance suite compares matrix/circuit states up to global phase and recovers |01>.
Companion work
Artifacts for this chapter
These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.
Reproduce or test
python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts
Provenance
Sources and review
- Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2010textbook
- John Watrous. The Theory of Quantum Information. Cambridge University Press / University of Waterloo. 2018textbook
- John Preskill. Lecture Notes for Physics 219: Quantum Computation. California Institute of Technology. 2018graduate lecture notes
- Don Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research report / arXiv. 2002primary paper
- Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing. 1997primary paper
The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.