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.
Beginner · 5 resources
What quantum computers can’t do
Quantum computers give large speedups on a narrow, structured set of problems. They are not faster at general computing, they do not "solve NP-complete problems instantly", and they will not run your spreadsheet.
Learn first:What is quantum computing?
Why it matters
The field is drowning in hype. A learner who can distinguish a real quantum advantage claim from a press release is more useful than one who can recite gate matrices.
After this you will be able to
- Explain why quantum computers are not believed to solve NP-complete problems efficiently
- Critique a typical quantum computing news headline
- Name where the credible near-term value actually is
Read it here first
The plain-language version
The credible list is short: simulating quantum systems (chemistry, materials), factoring and discrete logarithms via Shor, quadratic speedups for search-like problems via Grover, and some structured linear algebra with heavy caveats.
Analogy
Less like a faster engine, more like a specialised instrument. A telescope does not make you a better runner — it does one thing that no amount of running can substitute for.
Common misconception
Quantum computers will solve NP-complete problems instantly.
What is actually true
BQP is not believed to contain NP. Grover gives a quadratic speedup on brute-force search — turning 2^128 into 2^64 steps, which is still completely infeasible.
The thing to remember
Quantum chemistry is the application with the clearest theoretical case. Cryptography is the one driving the funding. Almost everything else is currently speculative.
Start here
3 best places to start
Hand-picked and ordered. If you only have time for one, take the first.
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.
Quantum Computing in the NISQ era and beyond
John Preskill (2018)
The essay that named the NISQ era. Almost no equations, and it frames what near-term hardware can and cannot do more honestly than anything else you will read.
Also covering this
2 more resources
Quanta Magazine — quantum computing coverage
Quanta Magazine
Science journalism that researchers actually respect. The best way to follow real results without either the arXiv firehose or press-release hyperbole.
Quantum Computing: Progress and Prospects
US National Academies
A sober expert assessment of feasibility and timelines, free to read online. Written for policymakers, which means it is unusually clear about uncertainty and risk.