Book Review

Quantum Computing Since the Age of Democritus by Scott Aaronson review by: Jash Desai May 2022

Scott Aaronson, a computational theorist at UT Austin wrote Quantum Computing Since the Age of Democritus in order to introduce the idea of quan- tum computation to a liberal arts class. If we take Aaronson’s initial idea as a goal for this book, it succeeds in wild fashion. Be warned, this is not a textbook in quantum computing teaching about circuit representations or qiskit syntax. Rather, this is a holistic overview of the importance of computing theory in relation to quantum computing. In fact, Aaronson begins with a diatribe about the history of physics and computation from Greek origins. Thus we have a title and a preferential frame of reference for how this book will proceed. Aaronson begins with computation theory, specifcally the mathematical origins of com- puting theory and Turing machines. This book requires a somewhat heavy prerequisite of linear algebra and discrete math as Aaronson will introduce and the walk you through proofs of important theorems relevant to computing and large number primes. For example, the proof for countable versus uncountable infinities. He then introduces higher infinities such as א0 before reminding the reader of the importance of abstraction to real world concepts in computation and theoretical computer science. Aaronson will often do this, where he begins very low level and technical before connecting that technical, abstract concept to the next section. The next few sections go into computing theory and, eventually, as Aaronson calls it, the most important theory to have been developed in the past 4 decades, computational complexity theory.

Aaronson begins complexity theory with talking about complexity classes, or ways in which computers can group types of problems to solve by type of difficulty with respect to what variable they may optimize with respect to. Complexity classes include time and space as the most common but Aaronson introduces the idea of several other classes including polynomial or exponen- tial based complexity. After explaning classes Aaronson breaks down several important computing problems and terminology including oracles, the halting problem, and classical Turing machines. He introduces these concepts via formal mathematical structures and does not relent in imposing formalism on all the problems. However, Aaronson does not shy away from removing the abstraction at the end of the chapter to realte to more grounded, applicable problems. After the introduction of computing theory concepts we get the famous P = NP conjecture which Aaronson explains in great detail, to the point where a lay person could feasible pick up a textbook on complexity and continue from there. It should be noted that Aaronson is an excellent and funny writer, though he does pack a lot of density into his writing and does not relent on precise mathematical description of proofs and their solutions. Given that these are compiled lecture notes, he actually adopts a rather casual tone making this very readable. He continues to expand on complexity theory and how polynomial time algorithms can be fit inside exponential frameworks and how an oracle can transcribe most unsolved complexity problems back into P = NP, thus reinstating its impor- tance and value to the field. We then get a short segway in cryptography and algorithms for polynomials over finite fields being a great way to secure mes- sages. He then raises this argument for all larger polynomial security algorithms being in the field of Z mod n. From here we transition into quantum mechanics.

Aaronson introduces quantum theory solely in the language of linear algebra (a la Sakurai and Napoliotano). This helps the reader to have the same basis for understanding computing theory and quantum theory in the same book, we also get a light introduction to standard bra-ket notation. By introducing the wave function Ψ, unitary matrices U, and the Bloch sphere we get a quick bridge to actual quantum computing. Throughout the book he also has a philosoph- ical discussion between the role and the ”fundamentalness” of math,physics, and computer science. He doesn’t really come to a conclusion as to what is more important or the base of all models but he does make incredible exam- ples that links the three of them together in ways that I don’t think any other author is able to. For example, when talking about Feynman path integration, Aaronson shows that path integration is really just the same as multiple finite fields with random matrices embeded in an exponential one, thus also showing that bounded quantum polynomial algorithms are equivalent to BQP can exist within an exponential space, therefore showing that Feynman path integration is really just showing that BQP = P.

We end the book with a broader descriptions of the type of problems quan- tum computers can crack and addressing common misconceptions about quan- tum computing. Everything from quantum computers not being simple parallel processors on steroids to talking about quantum and post-quantum cryptogra- phy.This section is a little rushed but it ends with some incredible theoretical questions such as a thought experiment about a simple computing machine on the edge of a black hole as well as a quantum machine learning applied to a AGI with near unlimited compute power. Aaronson also talks about hardware advances and topological qubit stability helping to create room temperature quantum computers. He ultimately says quantum computing will help us re- solve many problems in both quantum and computing theory despite its over hyped status. He also says theory will be enhanced as a result of experiments made on optical quantum computers and large N circuits. This books is simply incredible as an introduction to many subjects in theory surrounding quantum computing, I could not more highly recommend it for those purposes.