Further Reading: The Quantum Fourier Transform

Tagged Tier 1 (confident it exists and recommended) and Tier 2 (real and worth seeking, but verify the current version or URL).

The primary sources

• Nielsen and Chuang, Chapter 5. The standard treatment of the QFT and phase estimation, including the derivation of the counting-qubit formula §22.4 quotes. §5.2's development of phase estimation from the QFT is the clearest short account there is. Read §5.1 with a pencil and the four conventions from §22.1 in mind — the book's presentation is correct and does not belabour which ordering it is using. Tier 1.
• Coppersmith, "An approximate Fourier transform useful in quantum factoring" (1994), IBM Research Report RC19642. The approximate QFT, at the source, and it is worth reading for the framing: the AQFT was introduced because Shor's algorithm at cryptographic sizes is otherwise not expressible. §22.5 measures what the paper proposes. Tier 1.
• Kitaev, "Quantum measurements and the Abelian Stabilizer Problem" (1995), arXiv:quant-ph/9511026. Phase estimation's other origin, and the source of the semiclassical QFT — replacing controlled rotations with mid-circuit measurement and classically-conditioned single-qubit rotations. Exercise 22.34's subject, and directly relevant given Chapter 9's dynamic circuits. Tier 1.
• The Qiskit documentation for QFTGate and qiskit.circuit.library. Specifically the do_swaps and approximation_degree parameters, which are the library's answers to §22.1's convention question and §22.5's cutoff. Tier 1.

On the readout problem

This is the most important section to read beyond the chapter, because the misconception is widespread and the correction is not.

• Aaronson, "Read the fine print" (2015), Nature Physics 11, 291. Four caveats that apply to nearly every claimed quantum speedup on classical data — state preparation, readout, and the classical competition. Case Study 1's argument in two pages, by the person who made it best. If you read one thing after this chapter, read this. Tier 1.
• Any careful treatment of quantum state tomography's scaling. The $\mathcal{O}(4^n)$ that makes §22.3's argument quantitative. Chapter 26 §26.8 returns to it. Tier 1.
• The literature on efficient quantum state preparation. What can be loaded cheaply — states with closed-form amplitudes, sparse states, states produced by a known circuit — which is the honest answer to "when can the loading objection be dodged." Exercise 22.15's subject. Tier 2.
• Tang's "quantum-inspired" classical algorithms (2018 onward). A sequence of results showing that several claimed exponential quantum speedups on classical data can be matched classically given the same sampling access assumptions. The sharpest available demonstration that the I/O model is where the advantage lives or dies. Tier 1.

On phase estimation and its uses

• Cleve, Ekert, Macchiavello, and Mosca, "Quantum algorithms revisited" (1998), Proceedings of the Royal Society A 454, 339. Unifies Deutsch–Jozsa, Simon, Grover, and Shor under phase estimation and the hidden subgroup problem. This is the paper that makes Chapter 20 §20.1's three-step pattern into a theory rather than a coincidence. Tier 1.
• Brassard, Høyer, Mosca, and Tapp on amplitude estimation (also cited in Chapter 21). Quantum counting as phase estimation on the Grover operator — Exercise 22.22's subject, and the principled answer to Chapter 21 Case Study 1. Tier 1.
• Any current work on phase estimation variants with reduced circuit depth — iterative phase estimation, Bayesian phase estimation, and robust variants. These matter because textbook QPE needs coherence across all $2^t$ controlled operations, which near-term hardware does not have. Tier 2.

On the cost

• Chapter 19's rotation-count discussion and the Ross–Selinger synthesis result cited there. A QFT contains no T gates at all and is nonetheless expensive, because every controlled phase must be synthesized. This is the clearest example in the book of why rotationCount is a separate estimator input. Tier 1.
• Nam, Su, and Maslov, or similar work on QFT and arithmetic circuit optimization. Concrete reductions in the resource counts §22.6 reports, and a reminder that those numbers improve. Tier 2.

Forward references

• Chapter 23 — where phase estimation becomes period finding and period finding becomes factoring. The payoff for this entire chapter.
• Chapter 21 §21.5 — quantum counting, which this chapter's machinery finally makes principled.
• Chapter 32 — where §22.3's I/O argument recurs, and where "assume efficient state preparation" does a great deal of unacknowledged work.
• Chapter 36 — energy estimation as eigenvalue phase estimation, and why VQE is used instead on near-term hardware.

Where to go next. If one thing: Aaronson's "Read the fine print." It is short, it is written for exactly the audience that finds the $\mathcal{O}(n^2)$-versus-$\mathcal{O}(N\log N)$ comparison compelling, and it will inoculate you against the most common failure mode in this field.

If two: add Cleve, Ekert, Macchiavello, and Mosca, because seeing Deutsch–Jozsa, Simon, Grover, and Shor as one algorithm is the moment Part IV stops being a list.

Then Chapter 23 — Shor's algorithm, where an exponential speedup, a useful problem, and a satisfiable set of conditions finally coincide.