home > book reviews > Scott Aaronson
Google > Scott Aaronson


Books

Short works

Books : reviews

Scott Aaronson.
Quantum Computing Since Democritus.
CUP. 2013

rating : 2.5 : great stuff
review : 13 November 2013

Written by noted quantum computing theorist Scott Aaronson, this book takes readers on a tour through some of the deepest ideas of math, computer science, and physics.

Full of insights, arguments, and philosophical perspectives, the book covers an amazing array of topics. Beginning in antiquity with Democritus, it progresses through logic and set theory, computability and complexity theory, quantum computing, cryptography, the information content of quantum states, and the interpretation of quantum mechanics. There are also extended discussions about time travel, Newcomb’s Paradox, the Anthropic Principle, and the views of Roger Penrose. Aaronson’s informal style makes this fascinating book accessible to readers with scientific backgrounds, as well as to students and researchers working in physics, computer science, mathematics, and philosophy.

Most books about quantum computation are heavy on the quantum physics, and somewhat lighter on the computation, covering mainly the circuit model and the major algorithms. This book is not like those other books. It is heavy on the computational complexity theory, with a quantum flavour. But even that flavour is not physics, but maths. Aaronson admits that this is not the standard treatment.

p.xv. Even in 2013, the view of quantum mechanics as a theory of information and probabilities remains very much a minority one.

Instead of starting from physical quantum weirdness and spooky action at a distance, Aaronson starts form a generalisation of probability theory.

p.xvii. Quantum mechanics is a beautiful generalization of the laws of probability: a generalization based on the 2-norm rather than the 1-norm, and on complex numbers rather than nonnegative real numbers. It can be studied completely separately from its applications to physics (and indeed, doing so provides a good starting point for learning the physical applications later). This generalized probability theory leads naturally to a new model of computation – the quantum computing model – that challenges ideas about computation once considered a priori, and that theoretical computer scientists might have been driven to invent for their own purposes, even if there were no relation to physics. In short, while quantum mechanics was invented a century ago to solve technical problems in physics, today it can be fruitfully explained from an extremely different perspective: as part of the history of ideas, in math, logic, computation, and philosophy, about the limits of the knowable.

Of course, it is possible to invent a multitude of new models of computation, with greater or lesser degrees of relationship to the real world. Despite Aaronson’s discomfort with physics, however, what is important about this particular model is that there is in fact a physical realisation of it: quantum mechanics.

p.xviii. In Chapters 2 and 3, I move on to discuss the deepest knowledge we have that intentionally doesn’t depend on “brute facts” about the physical world: namely, mathematics. Even there, something inside me (and, I suspect, inside many other computer scientists!) is suspicious of those parts of mathematics that bear the obvious imprint of physics, such as partial differential equations, differential geometry, Lie groups, or anything else that’s “too continuous.” So instead, I start with some of the most “physics-free” parts of math yet discovered: set theory, logic, and computability.

So there’s very little in this book on quantum physics. Contrariwise, there’s a lot here that you might not expect to find in a book on quantum computing: a dissection of Roger Penrose’s ideas on intelligence and quantum gravity, computational learning, the anthropic principle, free will, and time travel, to name a few. He shows how these are all related to computational complexity.

This grew out of notes for a lecture course that Aaronson gave. I would not class it as a textbook, however. It feels closer to a transcript of those lectures, with a chatty, breezy style. The conversational style is readable and entertaining (although I could have done with fewer “dude”s). But at those times where it gets too breezy, students will need to consult another volume to get the details they require.

Despite this caveat, I definitely recommend this book. It puts the computation into quantum computation, it gives novel and marvellous insights into aspects of computational complexity theory, and it covers much material probably not available anywhere else. I learned a lot (dude).