Quantum Computing since Democritus | |

Aaronson (Scott) | |

This Page provides (where held) the Abstract of the above Book and those of all the Papers contained in it. | |

Text Colour-Conventions | Notes Citing this Book |

**BOOK ABSTRACT: **__Amazon Book Description__

- Written by noted quantum computing theorist Scott Aaronson, this book takes readers on a tour through some of the deepest ideas of maths, 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 students and researchers working in physics, computer science, mathematics and philosophy.

- If you're a computational complexity theorist, then everything looks like .. well, a problem in computational complexity. Scott Aaronson is astonishingly bright, on top of his subject and genuinely droll: this book gives you a fly-on-the-wall view of how he engaged with his students at the University of Waterloo.
- We start with a tour of prerequisites. Chapter 2 covers axiomatic set theory (ZF); chapter 3 Gödel's Completeness and Incompleteness Theorems, and Turing Machines. In chapter 4 we apply some of these ideas to artificial intelligence, discuss Turing's Imitation Game and the state of the art in chatbots, and also Searle's Chinese Room puzzle. Aaronson invariably provides a fresh perspective on these familiar topics although already we see the `lecture note' character of this book, where details are hand-waved over (because the students already know this stuff, or they can go away and look it up).
- Chapters 5 and 6 introduce us to the elementary computation complexity classes and explain the famous P not = NP conjecture. This is not a first introduction - you are assumed to already understand formal logic and concepts such as clauses, validity and unsatisfiability. Chapters 7 and 8 introduce, by way of a discussion on randomness and probabilistic computation, a slew of new complexity classes and the hypothesised relations between them, applying some of these ideas to cryptanalysis.
- Chapter 9 brings us to quantum theory. Six pages in we're talking about qubits, norms and unitary matrices so a first course on quantum mechanics under your belt would help here. The author's computer science take on all this does bring in some refreshing new insights. We're now equipped, in chapter 10, to talk about quantum computing. Typically this is not architecture or engineering discussion; Aaronson is a theorist, and for his community, quantum computing means a new set of complexity classes with conjectural relationships to those of classical computation.
- We now go off at a tangent as the author critiques Sir Roger Penrose's views on consciousness as a quantum gravity phenomenon. I think it's fair to say that no-one in AI takes this idea seriously, but the author has the intellectual resources to engage Penrose on his own ground here.
- In chapter 12 we crank up the technical level to talk about decoherence and hidden variable theories. This is one of the most interesting chapters but is too discursive - really important concepts are touched on and then abandoned; for example the discussion of decoherence and the 2nd Law of Thermodynamics is set against a model of the multiverse, but it's never quite clear whether Aaronson is assuming the reality of the Everett Interpretation or whether he has some other, more purely mathematical model in mind.
- Chapter 12 reminds us that a computational complexity theorist's idea of proof is a long way from that of a logician. We plunge into stochastic proofs, zero-knowledge proofs and probabilistically checkable proofs, all framed by a complexity analysis.
- The next few chapters cover a series of topics in similar vein: quantum proofs (and their complexity classes), rebuttals of sceptical arguments against quantum computing (interesting and convincing), some technically demanding material on learning algorithms, and concepts of interactive proof.
- The final few chapters are more philosophical: Aaronson applies his toolkit to topics such as the Anthropic Principle (via Bayesian reasoning); free will (he's in favour but has a highly-idiosyncratic view of what free will is); time travel (how closed timelike curves impact on classical and quantum computation); and cosmology (black holes, the information paradox, with firewalls bringing us up-to-date).
- I have to say that I did finish this book - it didn't just sit on my coffee table, abandoned after the first few chapters, as the author rather fears in his preface. However, it has to be said that despite the author's undeniable enthusiasm, complexity theory remains a minority taste. There are plenty of insights and novel observations even for those of us less enthralled but I hope it's clear what kind of background the reader needs to get anything out of this volume.
- To be fair, the book is already 362 pages long and to make the material less a write-up of post-graduate lecture notes and more a self-contained and smoothly-developed presentation of Aaronson's many original insights would seem to require an inordinate amount of time and effort, without substantially increasing the likely readership. I enjoyed it, but not without a degree of frustration.

- Lecture 1 (Link): Atoms and the Void
- Lecture 2 (Link): Sets
- Lecture 3 (Link): Gödel, Turing, and Friends
- Lecture 4 (Link): Minds and Machines
- Lecture 5 (Link): Paleocomplexity
- Lecture 6 (Link): P, NP, and Friends
- Lecture 7 (Link): Randomness
- Lecture 8 (Link): Crypto
- Lecture 9 (Link): Quantum
- Lecture 10 (Link): Quantum Computing
- Lecture 10.5 (Link): Penrose
- Lecture 11 (Link): Decoherence and Hidden Variables
- Lecture 12 (Link): Proof
- Lecture 13 (Link): How Big Are Quantum States?
- Lecture 14 (Link): Skepticism of Quantum Computing
- Lecture 15 (Link): Learning
- Lecture 16 (Link): Interactive Proofs
- Lecture 17 (Link): Fun With The Anthropic Principle
- Lecture 18 (Link): Free Will
- Lecture 19 (Link): Time Travel
- Lecture 20 (Link): Cosmology and Complexity
- Lecture 21 (Link): Ask Me Anything

- The ACR above suggests that the book is a collection of lecture notes – no doubt tidied up a bit – though not a lot from what I can see on Amazon.
- Aaronson’s course introduction is:-
- “This course tries to connect quantum computing to the wider intellectual world.
- We'll start out with various scientific, mathematical, or philosophical problems that predate quantum computing: for example, the measurement problem, P versus NP, the existence of secure cryptography, the Humean problem of induction, or the possibility of closed timelike curves.
- We'll then examine in what ways, if any, quantum computing affects how we should think about the problem.
- To keep things grounded, each session will end with a concrete puzzle that students will be expected to have thought about (if not solved) by the next session. The class format will strongly encourage participation, discussion, and debate.”

- I have not actually purchased this book since it is available on-line as lecture-notes.
- See Link

- Blue: Text by me; © Theo Todman, 2018
- Mauve: Text by correspondent(s) or other author(s); © the author(s)

© Theo Todman, June 2007 - May 2018. | Please address any comments on this page to theo@theotodman.com. | File output: Website Maintenance Dashboard |

Return to Top of this Page | Return to Theo Todman's Philosophy Page | Return to Theo Todman's Home Page |