Quantum Computing Since Democritus
Aaronson’s book is based off his online lecture notes which I hadn’t read before though I’ve read his blog for years. I was really excited when the book was announced, since I hoped for expanded better version of his incredibly interesting paper/monograph “Why Philosophers Should Care About Computational Complexity” (abstract: “…In particular, I argue that computational complexity theory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.”), and see also his more recent “The Ghost in the Quantum Turing Machine”.
The book turns out to be excellent, but not the 5-star universally-compelling, suitable for the layman and professional alike, complete coverage of all that is interesting about computational complexity and quantum I was hoping for. I’d say probably that one could get 80% of the value from reading “Why Philosophers Should Care About Computational Complexity”, and even more if one is not particularly interested in computational complexity or quantum computing for their own sakes.
Pros:
best book I’ve ever read on computational complexity
repeatedly throws out fascinating observations
learned a lot of new things even after years reading Aaronson’s blog
PAC learning, Blum’s speedup theorem, Tarski’s decision algorithm
humor better than expected
Cons:
some key arguments are sketched out briefly or badly (eg. I don’t know how anyone would understand Aaronson’s version of Cantor’s diagonal proof, compared to longer better-illustrated versions like Hofstadter’s in Gödel, Escher, Bach)
the complex-probability version of quantum mechanics didn’t seem much more transparent to me than other versions; maybe if I had a physics degree? (Not that I really understood the ‘Quantish’ universe in Drescher’s equally excellent book Good and Real, either.)
overuse of complexity zoo abbreviations
no discernible connection to Democritus or the Democritus quote
some later chapters highly technical and specialized and uninteresting (eg. the size of quantum states), not always meaningfully connected
Aaronson randomly inserts bizarre and sloppy anti-Bayesian digs—like at the end of his chapter on anthropics, he seems to think it refutes the ‘religion’ of Bayesianism. Dude, WTF? No one understands or agrees on anyone in anthropics, that’s the whole point of half the field (constructing paradoxes and unpleasant implications of the most sensible principles), and you want to use anthropics as an argument against Bayesianism‽ You want to disprove the eminently successful and practical by the useless and bizarre? If ever there was a moment that the saying ‘one man’s modus tollens is another man’s modus ponens’ was appropriate…