Further Reading: The First Quantum Algorithms

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

The original papers

These are unusually readable, and worth going to directly rather than through summaries.

• Deutsch, "Quantum theory, the Church–Turing principle and the universal quantum computer" (1985), Proceedings of the Royal Society A 400, 97. The one-qubit version, and the paper that framed quantum computation as a question about physics rather than about engineering. Tier 1.
• Deutsch and Jozsa, "Rapid solution of problems by quantum computation" (1992), Proceedings of the Royal Society A 439, 553. The $n$-qubit generalization. Short. Note how carefully the promise is stated — §20.5's whole subject is a precondition these authors were explicit about and later retellings often soften. Tier 1.
• Bernstein and Vazirani, "Quantum Complexity Theory" (1993 STOC; 1997 SIAM Journal on Computing 26, 1411). The paper the one-query parity trick is a residue of. The important result is the recursive construction's super-polynomial separation, not the flat version everyone teaches — read it to see what §20.3's Honest Assessment is pointing at. Tier 1.
• Simon, "On the power of quantum computation" (1994 FOCS; 1997 SIAM Journal on Computing 26, 1474). The first exponential separation, and the paper Shor has said directly inspired his own. Structurally the most important item on this list. Tier 1.

On the hidden subgroup problem

The unifying frame. All four algorithms in this chapter, plus Shor's, are instances.

• Any survey of the hidden subgroup problem. All of Chapter 20's algorithms hide a subgroup of $(\mathbb{Z}_2)^n$; Shor's hides one of $\mathbb{Z}_N$. The abelian case is solved and the non-abelian case is largely open — and graph isomorphism sits in the non-abelian case, which is why it has resisted a quantum algorithm despite decades of attention. Exercise 20.26's subject. Tier 2.
• Kaye, Laflamme, and Mosca, An Introduction to Quantum Computing, Chapter 7. The clearest textbook treatment of the HSP framing, and the best route from this chapter to Chapter 23. Tier 1.
• Nielsen and Chuang, §5.4.3. The hidden subgroup problem as a generalization of phase estimation, which connects §20.1's pattern to Chapter 22's. Tier 1.

On query complexity

• Ronald de Wolf, "Quantum Computing: Lecture Notes" (arXiv, regularly updated). The chapters on Deutsch–Jozsa, Bernstein–Vazirani, and Simon are the best free treatment available, by someone who proves these theorems. Read alongside Chapter 19 §19.7's caveats. Tier 1.
• Ambainis, "Quantum lower bounds by quantum arguments" (2002), Journal of Computer and System Sciences 64, 750. The adversary method — how lower bounds on quantum query complexity are actually proved. Necessary if you want to know how solid "provably faster" is. Tier 1.
• Aaronson and Ambainis, "The need for structure in quantum speedups" (2014). Directly relevant to §20.6: the argument that exponential quantum speedups require promise problems, and that for total functions the gap is at most polynomial. This is the theoretical justification for why every algorithm in this chapter needed a promise, and it is the single most useful thing to read after this chapter. Tier 1.

On the classical half

• Any treatment of linear algebra over $\mathbb{F}_2$. Gaussian elimination over the two-element field, rank, and null spaces — Case Study 2's subject, and the half of Simon's algorithm that gets skipped. Coding-theory texts cover it best. Tier 2.
• The probability that random $\mathbb{F}_2$ vectors are independent. The product $\prod_{k}(1-2^{-k}) \to 0.2888$ is a classical result worth knowing, because the same "collect until rank" pattern appears in coding theory, randomized linear algebra, and Shor's post-processing. Tier 2.

Forward references

• Chapter 21 — Grover, which drops the promise entirely and pays for it with a quadratic rather than exponential speedup.
• Chapter 22 — the QFT and phase estimation: §20.1's Hadamard layer is the QFT over $(\mathbb{Z}_2)^n$, which is the connection that makes Chapter 23 possible.
• Chapter 23 — Simon's algorithm over $\mathbb{Z}_N$ instead of $(\mathbb{Z}_2)^n$, with continued fractions in place of Gaussian elimination.
• Chapter 27 — where Case Study 1's "check the promise in the harness" becomes a testing discipline.

Where to go next. If one thing: Simon's 1994 paper. It is short, it is the first exponential separation, and Shor has credited it as the direct inspiration for factoring — so it is the rare toy result whose importance is documented rather than asserted.

If two: add Aaronson and Ambainis on the need for structure, because it turns §20.6's observation that "these problems were constructed to exhibit their separations" from a complaint into a theorem.

Then Chapter 21 — Grover, and what happens when you give up the promise.