Quantum Computing Since Democritus
Scott Aaronson
Free lecture notes connecting quantum computing to complexity theory, cryptography, free will and the anthropic principle. Funny, opinionated, and the best correction to hype you will find.
Advanced · 5 resources
Quantum complexity theory
The study of what quantum computers can and cannot do efficiently: the class BQP, its relationship to P, NP and PSPACE, the quantum analogue QMA, and the oracle separations that justify the field.
Learn first:Grover's algorithm
Why it matters
It tells you which speedups are provable, which are conjectural, and which are impossible — the antidote to hype, delivered as theorems.
After this you will be able to
- Define BQP and QMA and place them among classical classes
- Explain why BQP is not believed to contain NP
- Read complexity-theoretic quantum advantage arguments
Start here
3 best places to start
Hand-picked and ordered. If you only have time for one, take the first.
Complexity Zoo
Scott Aaronson and contributors
Definitions and known relationships for hundreds of complexity classes, BQP and QMA among them. The place to check what is actually proven versus merely believed.
The Theory of Quantum Information
John Watrous (University of Waterloo)
The mathematically complete treatment of channels, entropies, distance measures and semidefinite programming duality. Free PDF, and the reference when you need a theorem stated exactly right.
Also covering this
2 more resources
Ph219 Quantum Computation lecture notes
John Preskill (Caltech)
Preskill's notes have taught much of the field. Chapter 10 on quantum error correction is, for many researchers, the definitive introduction to the subject.
Shtetl-Optimized
Scott Aaronson
The field’s most reliable hype filter. When a quantum computing claim makes the news, this is where a leading complexity theorist explains what it does and does not mean.
Next
This unlocks
Topics that list Quantum complexity theory as a prerequisite.