Quantum Computing Since Democritus

The book's spine is computation, and here Aaronson is on home ground. In 1936 Alan Turing described an imaginary machine — a strip of tape, a head that reads and writes symbols, a short list of rules — and argued that this stripped-down gadget could carry out any procedure a human calculator could follow step by step. That claim is the reason we can talk about computers in general rather than particular contraptions. It also handed us a sharp knife: some things this universal machine can never do.

The famous casualty is the halting problem. There is no program that can take any other program plus its input and reliably decide whether it will eventually stop or run forever. Turing proved it with a self-referential twist that rhymes with Russell's paradox — feed the deciding program a version of itself and it contradicts its own answer. Aaronson likes that the limits of computation were mapped before the first real computer was built. We knew what machines couldn't do before we finished building one that could do anything.

The pivot of the book is a claim that sounds like a category error until you sit with it: what a computer can efficiently do depends on the laws of physics. For most of the twentieth century, computer scientists could ignore this, because every reasonable machine seemed to have the same rough powers. Quantum mechanics broke that comfort. A machine that stores information in quantum states is not just a faster classical computer; it works by different rules, and Aaronson's whole trade is figuring out exactly how much that buys you.

He is careful, almost pedagogically stern, about what those rules are. A quantum bit isn't simply 'a zero and a one at the same time,' the phrase that launched a thousand bad headlines. It's described by amplitudes — numbers that can be negative, even complex, and that combine so that some possibilities cancel each other out. Interference, not mere parallelism, is the point. A quantum algorithm is choreography: you arrange for the amplitudes of wrong answers to destroy one another and right answers to reinforce. Aaronson frames quantum computing as, in effect, probability theory done with numbers that can go negative.

Step back from the individual results and a method comes into focus. Aaronson keeps converting questions about physics into questions about information and computation, and finds that the translation loses almost nothing. What is a measurement? What does it mean for two events to be causally connected? Can the universe secretly solve hard problems for free? Each time, he reaches for the toolkit of complexity and computability rather than metaphysical intuition, and each time the reformulated question turns out to be sharper than the original.

The interpretations of quantum mechanics are his best example of this attitude. The Copenhagen view, the many-worlds picture, the various flavors of hidden variables — Aaronson refuses to treat these as a menu to pick from on taste. He asks instead what, if anything, would compute differently under each, and is candid when the honest answer is 'not much that we can test.' He has his leanings, but the discipline he insists on is the same he credited Democritus with: don't accept a story just because it's comforting or dramatic; ask what it actually commits you to.

The book ends more or less where it began, with the sense that these are all one conversation. Democritus argued his way to atoms; Cantor argued his way to bigger infinities; Turing drew a line around the computable; Shor found a crack in it that only a quantum machine can slip through. Aaronson's achievement is to make those feel like moves in a single game rather than trophies from different fields, without smoothing away the parts nobody has solved.