Gwern's Reviews > Quantum Computing Since Democritus

Quantum Computing Since Democritus by Scott Aaronson
Rate this book
Clear rating

's review

really liked it

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 & 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.


- 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


- 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 & 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 & practical by the useless & bizarre? If ever there was a moment that the saying 'one man's modus tollens is another man's modus ponens' was appropriate...

I made excerpts of the book as I read it:

- Preface
- chapters 1-3
- 4-5
- 9-11
- 15-16
- 22
45 likes · flag

Sign into Goodreads to see if any of your friends have read Quantum Computing Since Democritus.
Sign In »

Reading Progress

April 7, 2013 – Shelved
May 31, 2013 – Started Reading
June 17, 2013 – Finished Reading

Comments Showing 1-4 of 4 (4 new)

dateDown arrow    newest »

message 1: by Ur (new)

Ur Salem What do you think of his paper "refuting" Wolfram's thesis?

Gwern Which one?

message 3: by Ur (last edited Dec 11, 2014 09:45AM) (new)

Ur Salem Gwern wrote: "Which one?"

he mentioned it in this book of his. He is under the illusion that he actually "refuted" Wolfram's book, New Kind of Science, in the field of Quantum Entanglement.

message 4: by Raghu (new)

Raghu Aaronson's review of Wolfram's book -

back to top