### Quantum Computing Since Democritus: New Foreword!

Saturday, June 20th, 2020Time for a non-depressing post. Quantum Computing Since Democritus, which is already available in English and Russian, is about to be published in both Chinese and Japanese. (So if you read this blog, but have avoided tackling QCSD because your Chinese or Japanese is better than your English, today’s your day!) To go along with the new editions, Cambridge University Press asked me to write a new foreword, reflecting on what happened in the seven years since the book was published. The editor, Paul Dobson, kindly gave me permission to share the new foreword on my blog. So without further ado…

*Quantum Computing Since Democritus* began its life as a course that I taught at the University of Waterloo in 2006. Seven years later, it became the book that you now hold. Its preface ended with the following words:

Here’s hoping that, in 2020, this book will be as badly in need of revision as the 2006 lecture notes were in 2013.

As I write this, in June 2020, a lot has happened that I would never have predicted in 2013. Donald Trump is the President of the United States, and is up for reelection shortly. This is not a political book, so let me resist the urge to comment further. Meanwhile, the coronavirus pandemic is ravaging the world, killing hundreds of thousands of people, crashing economies, and shutting down schools and universities (including mine). And in the past few weeks, protests against racism and police brutality started in America and then spread to the world, despite the danger of protesting during a pandemic.

Leaving aside the state of the world, my own life is also very different than it was seven years ago. Along with my family, I’ve moved from MIT to the University of Texas in Austin. My daughter, who was born at almost exactly the same time as *Quantum Computing Since Democritus*, is now a first-grader, and is joined by a 3-year-old son. When my daughter’s school shut down due to the coronavirus, I began home-schooling her in math, computer science, and physics—in some of the exact same topics covered in this book. I’m now engaged in an experiment to see what portion of this material can be made accessible to a 7-year-old.

But what about the material itself? How has it held up over seven years? Both the bad news and the (for you) good news, I suppose, is that it’s *not* particularly out of date. The intellectual underpinnings of quantum computing and its surrounding disciplines remain largely as they were. Still, let me discuss what *has* changed.

Between 2013 and 2020, the field of quantum computing made a striking transition, from a mostly academic pursuit to a major technological arms race. The Chinese government, the US government, and the European Union have all pledged billions of dollars for quantum computing research. Google, Microsoft, IBM, Amazon, Alibaba, Intel, and Honeywell also now all have well-funded groups tasked with building quantum computers, or providing quantum-computing-related software and services, or even just doing classical computing that’s “quantum-inspired.” These giants are joined by dozens of startups focused entirely on quantum computing.

The new efforts vary greatly in caliber; some efforts seem rooted in visions of what quantum computers will be able to help with, and how soon, that I find to be wildly overoptimistic or even irresponsible. But perhaps it’s always this way when a new technology moves from an intellectual aspiration to a commercial prospect. Having joined the field around 1999, before there were *any* commercial efforts in quantum computing, I’ve found the change disorienting.

But while some of the new excitement is based on pure hype—on marketers now mixing some “quantum” into their word-salad of “blockchain,” “deep learning,” etc., with no particular understanding of any of the ingredients—there really have been some scientific advances in quantum computing since 2013, a fire underneath the smoke.

Surely the crowning achievement of quantum computing during this period was the achievement of “quantum supremacy,” which a team at Google announced in the fall of 2019. For the first time, a programmable quantum computer was used to outperform any classical computer on earth, running any currently known algorithm. Google’s device, called “Sycamore,” with 53 superconducting qubits cooled to a hundredth of a degree above absolute zero, solved a well-defined albeit probably useless sampling problem in about 3 minutes. To compare, current state-of-the-art simulations on classical computers need a few days, even with hundreds of thousands of parallel processors. Ah, but will a better classical simulation be possible? That’s an open question in quantum complexity! The discussion of that question draws on theoretical work that various colleagues and I did over the past decade. That work in turn draws on my so-called **PostBQP**=**PP** theorem from 2004, explained in this book.

In the past seven years, there were also several breakthroughs in quantum computing theory—some of which resolved open problems mentioned in this book.

In 2018, Ran Raz and Avishay Tal gave an oracle relative to which **BQP** (Bounded-Error Quantum Polynomial-Time) is not contained in **PH** (the Polynomial Hierarchy). This solved one of the main open questions, since 1993, about where **BQP** fits in with classical complexity classes, at least in the black-box setting. (What does that mean? Read the book!) Raz and Tal’s proof used a candidate problem that I had defined in 2009 and called “Forrelation.”

Also in 2018, Urmila Mahadev gave a protocol, based on cryptography, by which a polynomial-time quantum computer (i.e., a **BQP** machine) could always prove the results of its computation to a classical polynomial-time skeptic, purely by exchanging classical messages with the skeptic. Following Urmila’s achievement, I was delighted to give her a $25 prize for solving the problem that I’d announced on my blog back in 2007.

Perhaps most spectacularly of all, in 2020, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that **MIP***=**RE**. Here **MIP*** means the class of problems solvable using multi-prover interactive proof systems with quantumly entangled provers (and classical polynomial-time verifiers), while **RE** means Recursively Enumerable: a class that includes not only all the computable problems, but even the infamous halting problem (!). To say it more simply, *entangled provers can convince a polynomial-time verifier that an arbitrary Turing machine halts*. Besides its intrinsic interest, a byproduct of this breakthrough was to answer a decades-old question in pure math, the so-called Connes Embedding Conjecture (by *refuting* the conjecture). To my knowledge, the new result represents the first time that quantum computing has reached “all the way up the ladder of hardness” to touch uncomputable problems. It’s also the first time that non-relativizing techniques, like the ones central to the study of interactive proofs, were ever used in computability theory.

In a different direction, the last seven years have witnessed an astonishing convergence between quantum information and quantum gravity—something that was just starting when *Quantum Computing Since Democritus* appeared in 2013, and that I mentioned as an exciting new direction. Since then, the so-called “It from Qubit” collaboration has brought together quantum computing theorists with string theorists and former string theorists—experts in things like the black hole information problem—to develop a shared language. One striking proposal that’s emerged from this is a fundamental role for *quantum circuit complexity*—that is, the smallest number of 1- and 2-qubit gates needed to prepare a given n-qubit state from the all-0 state—in the so-called AdS/CFT (Anti de Sitter / Conformal Field Theory) correspondence. AdS/CFT is a duality between physical theories involving different numbers of spatial dimensions; for more than twenty years, it’s been a central testbed for ideas about quantum gravity. But the duality is extremely nonlocal: a “simple” quantity in the AdS theory, like the volume of a wormhole, can correspond to an incredibly “complicated” quantity in the dual CFT. The new proposal is that the CFT quantity might be not just complicated, but literally circuit complexity itself. Fanciful as that sounds, the truth is that no one has come up with any other proposal that passes the same sanity checks. A related new insight is that the nonlocal mapping between the AdS and CFT theories is not merely analogous to, but literally an example of, a quantum error-correcting code: the same mathematical objects that will be needed to build scalable quantum computers.

When *Quantum Computing Since Democritus* was first published, some people thought it went too far in elevating computer science, and computational complexity in particular, to fundamental roles in understanding the physical world. But even I wasn’t audacious enough to posit connections like the ones above, which are now more-or-less mainstream in quantum gravity research.

I’m proud that I wrote *Quantum Computing Since Democritus*, but as the years go by, I find that I have no particular desire to revise it, or even reread it. It seems far better for the book to stand as a record of what I knew and believed and cared about at a certain moment in time.

The intellectual quest that’s defined my life—the quest to wrap together computation, physics, math, and philosophy into some sort of coherent picture of the world—might never end. But it does need to start somewhere. I’m honored that you chose *Quantum Computing Since Democritus* as a place to start or continue your own quest. I hope you enjoy it.

Scott Aaronson

Austin, Texas

June 2020