Chapter 22 — Key Takeaways (The Quantum Fourier Transform)
§22.3's readout problem is the most important idea here; §22.4's phase estimation is what the QFT is actually for.
The transform
$$\text{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\,|k\rangle$$
Verified: the QFTGate unitary IS the DFT matrix, to $10^{-10}$, at $n = 2, 3, 4$.
3-qubit QFT: {'h': 3, 'cp': 3, 'swap': 1}
$n$ Hadamards, $n(n-1)/2$ controlled phases, a swap layer. Angles halve at each step: $\pi/2, \pi/4, \pi/8, \dots$ — which §22.5 exploits.
⚠️ The convention trap
ascending + swaps fidelity vs QFTGate = 0.264679
DESCENDING + SWAPS fidelity vs QFTGate = 1.000000 <- the right one
descending, no swaps fidelity = 0.250000
ascending, no swaps fidelity = 0.250000
Three of four give a wrong answer with no error message, and 0.25 looks like a subtle problem rather than a wrong one. Verify against the DFT matrix — the definition has no convention.
Exponentially fewer operations
n N = 2ⁿ QFT gates classical FFT ops
8 256 36 2,048
16 65,536 136 1,048,576
32 4.3 × 10⁹ 528 1.4 × 10¹¹
$$\mathcal{O}(n^2) = \mathcal{O}\big((\log N)^2\big) \quad\text{vs}\quad \mathcal{O}(N\log N)$$
136 gates against a million operations at $n = 16$.
★★★ And that is not a speedup — you cannot read the output
QFT output amplitudes: [0, 0, 0, 0, 0, 1, 0, 0]
one measurement gives: outcome 5, and nothing else
n QFT gates tomography ~ 4ⁿ
4 10 256
8 36 65,536
16 136 4,294,967,296
$$\underbrace{\mathcal{O}(2^n)}_{\text{load}} + \underbrace{\mathcal{O}(n^2)}_{\text{transform}} + \underbrace{\mathcal{O}(4^n)}_{\text{read out}}$$
Sandwiched between an exponential load and an exponential readout. Loading arbitrary classical data is $\mathcal{O}(2^n)$; extracting $2^n$ amplitudes needs tomography.
🔬 You cannot use the QFT to speed up signal processing, image compression, or spectral analysis. Same shape as Ch. 21 §21.7's database argument, and the most common way quantum speedup claims go wrong: an exponentially fast subroutine wrapped in exponential I/O. It recurs in Ch. 32's QML.
The criterion:
$$\text{advantage survives when } |\text{answer}| = \mathcal{O}(\text{poly}(n)), \text{ not } \mathcal{O}(2^n)$$
Ask: do I want a number, or an array?
★ Phase estimation — what the QFT is for
$$U|\psi\rangle = e^{2\pi i\varphi}|\psi\rangle \quad\Longrightarrow\quad \text{estimate } \varphi$$
1. SUPERPOSE H on t counting qubits
2. KICK BACK controlled-U^(2^j) from counting qubit j
3. INTERFERE INVERSE QFT on the counting register
Chapter 20 §20.1's three-step pattern with the QFT replacing the final Hadamard layer — because the Hadamard layer is the QFT over $(\mathbb{Z}_2)^n$.
Exact for dyadic phases
true phase bits measured estimate error P(best)
0.500000 3 100 0.500000 0.000000 1.0000
0.250000 3 010 0.250000 0.000000 1.0000
0.125000 3 001 0.125000 0.000000 1.0000
Otherwise error falls as $2^{-t}$
φ = 1/3 bits measured estimate error
3 011 0.375000 0.041667
4 0101 0.312500 0.020833
5 01011 0.343750 0.010417
6 010101 0.328125 0.005208
8 01010101 0.332031 0.001302
10 0101010101 0.333008 0.000326
Each additional counting qubit halves the error. (Note the bits spell out $1/3 = 0.0101\ldots_2$.)
$$t = m + \left\lceil \log_2\!\left(2 + \tfrac{1}{2\epsilon}\right) \right\rceil$$
📐 The extra qubits buy CONFIDENCE, not precision — about 6 for 99%, independent of $m$.
Used by: Ch. 21's quantum counting (phase estimation on the Grover operator — the principled answer to "how many solutions?"), Ch. 23's period finding, and chemistry's energy estimation.
★ The approximate QFT
Angles decay to $2\pi/2^n$ — at $n=16$ the smallest is $2\pi/65536$, below any hardware's resolution and below the noise floor. Drop them.
n = 8 cutoff cp gates fidelity gate saving
1 7 0.458548 75.0%
2 13 0.852517 53.6%
3 18 0.970902 35.7%
4 22 0.995137 21.4%
7 28 1.000000 0.0%
Cutoff 3 → 97% fidelity for 36% fewer gates. Cutoff 4 → 99.5% for 21% fewer.
The $c = \mathcal{O}(\log n)$ rule, and the saving GROWS:
n full cp cutoff AQFT cp saved
8 28 3 18 35.7%
16 120 4 54 55.0%
64 2,016 6 363 82.0%
128 8,128 7 868 89.3%
At $n=64$ the AQFT uses 18% of the gates. For Shor at cryptographic sizes it is what makes the circuit expressible at all.
Cost: rotations, not T gates
Every controlled phase is an arbitrary rotation, and Ch. 19 §19.5 measured that rotations are not primitives under error correction — each must be synthesized into Clifford+T.
n = 16, rotations sequential
full QFT 120 rotations -> 190,970 physical qubits, 10,067 μs
AQFT c=4 54 rotations -> 121,690 physical qubits, 4,576 μs
36% fewer qubits, 55% less runtime, for 99.5% fidelity.
🗝️
rotationDepthis not optional. Left at 0:text rotations physical qubits runtime μs 90 4,060,890 466.4 120 1,299,610 1,284.4 <- FEWER qubits than 90Non-monotonic — the estimator silently switches space–time tradeoff points (Ch. 15 §15.8's T-factory saturation again). A QFT's rotations are sequential, sorotationDepth ≈ rotationCount.
Common pitfalls
- Reconstructing the QFT in one of the three wrong conventions.
- Verifying against an implementation instead of the DFT definition.
- Believing $\mathcal{O}(n^2)$ vs $\mathcal{O}(N\log N)$ is a usable speedup.
- Forgetting the input load is $\mathcal{O}(2^n)$ for arbitrary data.
- Wanting an array out of a QFT.
- Assuming phase estimation is always approximate (it is exact for dyadic phases).
- Leaving
rotationDepthat 0.
Project piece added this chapter
vqelab/qft.py — qft_circuit(n, cutoff) in the correct convention (with the three wrong ones
recorded in the docstring), verify_against_dft, aqft_fidelity, phase_estimation_circuit,
estimate_phase returning a PhaseEstimate that knows whether the phase was dyadic,
counting_qubits_for, and qft_cost with rotationDepth set. 15 tests pass, including
test_the_three_WRONG_conventions_are_detectably_wrong,
test_dyadic_phases_are_estimated_EXACTLY, and test_cost_is_monotonic_in_rotation_count.