58-page review: Quantum Computing Since Democritus by Scott Aaronson [2/5]

I intend to write book reviews here sometimes, and perhaps it’s appropriate that I start small, with a book that I have only read 58 pages into: Quantum Computing Since Democritus. It goes without saying that all general statements about the book should be taken with a grain of salt the size of Scott Aaronson’s ego.

Quantum Computing Since Democritus is a remarkable book in part for feeling even more undisciplined than its title suggests. Aaronson tries very hard, and sometimes succeeds, at being entertaining. As a hilarious way of setting the tone, the preface begins as follows:

by Scott Aaronson

To give another example of his stylistic flavor, Aaronson writes in the opening paragraph of the actual book, “[Democritus] was a disciple of Leucippus, according to my source, which is Wikipedia.” I enjoy this kind of banter, and Aaronson is pretty good at it, but it doesn’t make my time feel well spent when reading his book or help to teach me anything. At best, the conversational tone allows him to get in some good, quick jokes; at worst, it obscures the distinction between throwaway asides and the deeper points made in the book. On the whole, the balance of this trade-off is negative.

To be sure, if the book falls short, it’s not because it isn’t trying to make deep points. In the few chapters I read, Aaronson covers the following topics:

  • Logic and set theory, even writing out the rules of first-order logic and the Zermelo-Fraenkel axioms
  • Gödel’s completeness and incompleteness theorems
  • Turing machines, the Church-Turing thesis, and the halting problem
  • Turing’s imitation game and the possibility of machine consciousness
  • Why the solvability of problems is essentially unimportant compared to the reasonably fast solvability of problems.
  • Different complexity classes, meaning groups of problems that can be solved at different levels of efficiency, and how they are related to each other

All of these topics are discussed with a strange mixture of formality and what I might call “conceptual gist.” To take a line arguably out of context, Aaronson admits “…I don’t expect you to understand everything.” However, this raises the unanswered question of what exactly we are not expected to understand, as well as why he would write about something that we aren’t expected to understand anyway. I’m not even sure which arguments are solid proofs and which are just the outlines of proofs. Many of the arguments required several passes for me to understand at all, and others were difficult enough that I just gave up and moved on; yet when I did manage to follow the arguments, I was rarely sure what was important about them.

For example, after presenting the Zermelo-Fraenkel axioms, Aaronson writes, “These axioms—called the Zermelo-Fraenkel axioms—are the foundation for basically all of math. So I thought you should see them at least once in your life.” This justification doesn’t cut it for me, and that’s coming from someone who’s read a symbolic logic textbook just for fun. Why did Zermelo and Fraekel choose these particular axioms and not others? Which axioms did they toy with and find were already contained in the others? Which axioms did they try to include but found out were inconsistent with the others? Are there any axioms here that are in some sense questionable, like Euclid’s parallel postulate? How can we understand the fact that these axioms are strong enough to ground mathematics, but weak enough to leave open interesting problems (as opposed, say, to a weaker system identical to ZF aside from the omission of a single axiom, or a stronger and uninteresting system like “there exists a unique set and nothing else”)? Aaronson gives us no guidance. In the end, I can’t figure out why on earth it should be interesting to me to see the axioms listed, only to immediately move on.

I fear that this pattern makes up most of the sections I read, and probably the remainder of the book: arguments too informal for the reader to thoroughly understand, but formal enough to be difficult to follow even conceptually, and with insufficient attention drawn throughout to the separation of details from essential features.

There are things I appreciated about the book. The chapter on sets gave me some intuitive understanding of ordinal numbers (though I’m not sure why I should want it). The discussion of the halting problem was one area where the importance of both the problem and the proof of its resolution was made clear. As one extension of this, Aaronson gives a straightforward proof of Godel’s Incompleteness theorem bootstrapped off the nonexistence of a halt-checking program. A direct request in the text got me to read Turing’s original paper about the imitation game, which is quite approachable and much more interesting than I would have expected. The book provides a very digestible introduction to what complexity classes are and why they’re important.

That’s an extraordinarily admirable list of virtues for the first 58 pages to have, and I have no doubt that I would get some fuzzy, big picture insights from finishing the book. So perhaps it is partly from pride and partly from stubbornness that I don’t plan to keep reading.

After all, it’s not even like page 58 is the end of a particularly well-resolved chapter. It’s in fact right in the middle of a chapter. The reason I chose to stop there is that 58 pages is exactly how long it took for me to completely lose my trust that Aaronson is respectful of or fair to his readers. This is what’s at the bottom of the page:

…As a first question, is it obvious that NP-complete problems even exist?

I claim that it is obvious. Why?

Well, consider the following problem, called DUH: we’re given a polynomial-time Turing machine M, and we want to know if there exists an n^{k}-bit input string that causes M to accept. I claim that any instance of any NP problem can be converted, in polynomial time, into a DUH instance having the same answer. Why? Well, DUH! Because that’s what it means for a problem to be in NP!

I read this several times and I have no idea what he’s saying. I don’t think he ever specified what it means for a Turing machine to “accept,” or what he means by an “instance” of a problem. In fact, what is a polynomial-time Turing machine? Isn’t it the algorithm that’s polynomial time or not?

I take heart in two facts: first, there have already been other things in the book that Aaronson non-explicitly assumes the reader knows about, but which I understood because I already knew what he was talking about. (For example, he casually references algorithms to multiply n x n matrices without saying what matrices are or warning you that you’re supposed to already know linear algebra before starting the book.) That makes me more confident that he’s presupposing knowledge without saying so, and that I shouldn’t actually be able to sort this passage out from within the text.

The second fact I’ll let Paul Graham explain:

The greatest advantage of a PhD (besides being the union card of academia, of course) may be that it gives you some baseline confidence. For example, the Honeywell thermostats in my house have the most atrocious UI. My mother, who has the same model, diligently spent a day reading the user’s manual to learn how to operate hers. She assumed the problem was with her. But I can think to myself “If someone with a PhD in computer science can’t understand this thermostat, it must be badly designed.”

Aaronson is trying to reduce something to a “DUH!” level of epistemic status that I can’t parse after several passes. But I can think to myself “If someone getting a PhD in physics can’t understand this discussion allegedly for non-specialists, it must be badly written.”

Leave a Reply

Your email address will not be published.

To write LaTeX output, type $latex [input]$ with [input] replaced by LaTeX input.