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.
Instead of starting from physical quantum weirdness and spooky action at a distance, Aaronson starts form a generalisation of probability theory.
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.
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).