Quantum Computing Since Democritus: Scott Aaronson's Lecture Notes

Scott Aaronson’s “Quantum Computing Since Democritus” began as a lecture course at the University of Waterloo and later became a book published by Cambridge University Press. The original lecture notes remain freely available on Aaronson’s website, and they constitute one of the most intellectually stimulating free resources in quantum computing. The material starts from ancient philosophy and mathematics (sets, logic, probability, computational complexity) and builds upward to quantum mechanics and quantum computing as the logical culmination of a long argument about the nature of physical computation.

The complexity theory coverage is the heart of the course. Aaronson treats P vs NP, the polynomial hierarchy, randomized complexity, and interactive proofs as prerequisites to understanding what is genuinely hard for quantum computers versus what merely seems hard for classical ones. The treatment of BQP (the class of problems efficiently solvable by a quantum computer) is exceptionally clear about what is and is not known. The QMA lectures (quantum Merlin-Arthur, the quantum analog of NP) cover quantum proof systems, the local Hamiltonian problem, and connections to condensed matter physics that rarely appear in introductory materials. The quantum cryptography section covers not just quantum key distribution but also quantum money, quantum copy-protection, and the limits of what quantum mechanics can and cannot guarantee.

Throughout the notes, Aaronson engages directly with philosophical questions (free will, the interpretation of quantum mechanics, the anthropic principle) that most quantum computing courses avoid. This makes the material unusual and, depending on your tastes, either distracting or essential context. The notes are best suited to readers who already have solid classical complexity theory background and want to understand where quantum complexity fits within the broader theory of computation.

What you’ll learn

• Computational complexity foundations: P, NP, the polynomial hierarchy, IP, and randomized complexity reviewed from scratch
• The complexity class BQP: what problems are known to be in BQP, what separations are known, and the limits of current knowledge
• QMA and quantum proof systems: the local Hamiltonian problem, quantum Cook-Levin theorem, and connections to quantum chemistry
• Quantum cryptography: QKD, quantum money, copy-protection, and the information-theoretic arguments underlying these constructions
• Quantum lower bounds: polynomial method, adversary method, and limitations on quantum speedups
• Philosophy of physics and computation: interpretations of quantum mechanics and their relevance (or lack thereof) to computing

Who is this for?

• Theoretical computer scientists who want the most rigorous complexity-theoretic treatment of quantum computing available for free
• Researchers who have read introductory quantum computing materials and want to understand where quantum complexity sits within computational complexity theory
• Anyone who has read the published book and wants to compare it against the original lecture notes
• Advanced students who enjoy conceptually demanding material that does not shy away from open problems and philosophical asides