With this book, Scott Aaronson has produced a wonderful, personal exploration of topics in theory of computation, complexity theory, physics, and philosophy. His witty, informal writing style makes the material approachable as he weaves together threads of complexity theory, computing theory, mathematical logic, and the math and physics of quantum mechanics (QM) and quantum computing to show how these topics interrelate to each other, what that says about the universe, and something about us.
Beginning with chapter 1, “Atoms and the Void,” the book proceeds through overviews of set theory, Turing machines and computing theory, Gödel’s theorems, complexity theory, and QM, to a review of the latest significant findings in complexity theory and computability. It then relates these to the research on what quantum computers are and what they might be able to do. Along the way it delves into randomness, cryptology, learning, the anthropic principle, free will, philosophy, cosmology, time travel, and Roger Penrose’s speculation about QM and the brain.
The author comes at QM from an information theoretic view, one that has evolved over the past three or four decades among practitioners in the field. His view of the mathematics of QM as a generalization of probability theory and that QM exists in a layer between math and physics is intriguing. Yet as one grounded in physics before computer science, I am not ready to concede (yet) that math and information underlie the physical world. Nevertheless, the alternatives are interesting to contemplate.
However, even as the author treats all these topics clearly and enthusiastically, the reader can come away with the impression that he is immersed in the story of the blind men and an elephant. This is by no means a criticism of the book. No matter how many ways one approaches these topics, at the end, the discussion is about questions that approach the limits of what we can observe, what we can compute, and thus what we can know. The author asks and discusses questions that for now have no answers: Does P equal NP? Can a nontrivial quantum computer be built? Do humans have free will? Many important and desired solutions remain elusive despite the best efforts of many talented practitioners over hundreds of years. The author highlights what we do and don’t yet know, and shows how theoreticians have been inching their way forward from various directions. Furthermore, he does it engagingly.
One might ask who the intended audience for this book is. It could be used as a textbook, as it has exercises and a set of worthwhile references. It would likely be welcomed by students used to typical mundane college texts, which it most certainly is not. One argument against it being used in such a manner is that it covers a tremendous number and diversity of topics without the depth typical of textbooks; the instructor would need to fill in a lot of the background. Given the book’s rather heavy math and physics content, I’m not sure it could be classified as a popular science book. On the other hand, the breadth of topics could potentially resonate with readers who have many different interests. That said, someone unfamiliar with complexity theory may find the topic, its alphabet soup of classes, and its math puzzling. The same is true of someone unfamiliar with QM and its underlying physics. For those with the background or who are willing to learn as needed, this book is a treat.
More reviews about this item: Amazon, Goodreads
