People of ACM - Scott Aaronson

June 1, 2021

What has surprised you most about the development of quantum computing since you began working in the field?

What’s surprised me most is the extent to which, even before we have useful devices, quantum computing has shifted from an academic basic research enterprise to a field that’s awash in venture capital and large investments from governments and corporations. On the positive side, the new funding gives the field a much better shot at building truly scalable devices, which won’t be cheap if it can be done at all! On the negative side, people who make such big investments do so in the hope of a return, and the new environment has put enormous pressure on researchers to paint a picture of the near-term applications of quantum computers that (in my view) is often wildly overoptimistic or false. I, too, hope I‘ll live to see quantum computers influence the design of drugs, batteries, solar cells, and so forth, but I’d be surprised to see any of that in the next decade!

Will you tell us a little about the concept of quantum supremacy, and why this concept has been important to both the theoretical underpinnings of the field, as well as the ongoing efforts to build a quantum device?

“Quantum supremacy” just means the use of a quantum computer to perform some benchmark task that we have reason to believe is extremely hard for any existing classical computer. Much like the Wright brothers’ airplane, the task doesn’t need to be useful; it just needs to prove a point. We do, however, insist that the task have a clear mathematical definition (thus, simply pointing to some physical system and challenging people to predict its behavior doesn’t count). In some sense, the concept of quantum supremacy goes back to the very beginning of the field, to Feynman and Deutsch in the 1980s: beating a classical computer is a quantum computer’s entire reason for existence! Since 1994, the gold standard for quantum supremacy has been to use Shor’s algorithm, say to factor some thousand-digit number. That would be almost impossible to argue with (note that alleged prime factors are easy to check). But alas, we’re still far from building any quantum computer that can do such things; and as a separate issue, there’s no clear consensus that factoring really is hard for classical computers.

The modern push for quantum supremacy started a decade ago, when theoretical work by me and others indicated that, if you just wanted to demonstrate a clear quantum speedup, then there were huge benefits to switching attention from problems with a single right answer (like factoring) to so-called "sampling problems," where the goal is just to sample from some prescribed probability distribution. One benefit is that you can then base your belief in the hardness of classical spoofing on some of the most solid conjectures in computer science (such as the “non-collapse of the polynomial hierarchy”). A second benefit is that, to achieve quantum supremacy for these sampling tasks, you don’t necessarily need a full, error-corrected quantum computer with millions of physical qubits and gates—something we’re still quite far from. Rather, just 50-100 noisy qubits and a few hundred noisy operations on them could be enough. Around 2013, that realization jump-started an experimental quest actually to demonstrate quantum supremacy based on sampling problems—and of course, the quest finally started to bear fruit in 2019.

You should think of the existing supremacy experiments as proofs-of-principle: even though they fall short of scalability and don’t yet solve useful problems, they’ve successfully illustrated how a programmable system can harness the enormous dimension of quantum states for computational advantage. These are triumphs for the engineering groups that achieved them, and I’m proud to have played some role in causing them to happen.

Teams from Google and China have recently claimed to have developed devices that achieve quantum supremacy; how would the computer science community verify these claims?

The computer science community has been heavily involved in the effort to verify these claims since the claims came out! The central question is how hard it is to spoof the behavior of these devices using a classical computer—which is clearly a question for classical CS at least as much as for physics. My students and I have given complexity-theoretic evidence that quantum supremacy experiments are sampling probability distributions that, in least in principle, should take exponential time to sample classically. But not only is this evidence less airtight than we’d like it to be, it’s asymptotic (rather than specialized to specific numbers of qubits like 50 or 60), and doesn’t adequately account for noise and many other practical issues.

Over the past couple of years, there were partial rebuttals of Google’s quantum supremacy claim, by IBM, Alibaba, and others, which showed how to pass Google’s test for supremacy (what they called the “Linear Cross-Entropy Benchmark”), with a classical computer, orders of magnitude more quickly than Google had thought possible, although the quantum computer still retains some advantage. With the quantum supremacy claim from USTC in China, people are working on classical spoofing strategies as we speak—especially, strategies that would take advantage of imperfections in the experiment, such as the high rate of photon loss. Having said that, one can sometimes evade these spoofing attempts just by making small tweaks to the test being applied to the quantum computer’s outputs—to say nothing of improving the quantum computer, say by adding more qubits or increasing their fidelity! So I expect there to be cat-and-mouse claims and counterclaims for several more years. Just like in applied cryptography, we’ll only be truly confident about quantum supremacy once some particular claim has survived serious attempts by skeptics to shoot it down for a long time.

What is the primary focus of your research right now?

Sadly, I haven’t been getting much research done during Covid! In general, though, I continue to be interested in the fundamental capabilities and limitations of quantum computers—so, the relationships among quantum complexity classes, the power of quantum states as proofs or advice or unclonable currency, and much more.

I’m also interested in quantum computing questions that come from the study of quantum gravity and black hole information problem, which has been an exciting direction for the past decade, spearheaded by physicists like Lenny Susskind. But perhaps my most urgent focus for the next few years will be to understand better the capabilities of noisy, non-error-corrected quantum computers with a few hundred qubits. For example, can they beat classical computers at some task for which it’s easy for classical computers to verify the answer? What about generating certified random bits, or other tasks with possible real-world applications?

What advice would you offer a college student who is interested in working in the quantum computing field?

Major in CS, Physics, Math, EE, or some combination thereof. Learn as much math as you can—especially linear algebra and probability; finite groups and fields and representations are also helpful. Study classical algorithms and complexity theory too. Surprisingly, quantum mechanics (as taught in most physics departments) is not essential if you’re coming at the field from a Math/CS perspective, though of course it is if you’re coming from Physics, Engineering, or Chemistry.

In any case, if your university offers a course in quantum computing and information, then take it, obviously; then, if you do well, talk to the instructor or others afterward about research opportunities. To go further in the subject, you’ll probably want a PhD. In the meantime, there are also lots of great resources for self-study: dozens of textbooks (of which the most famous remains Quantum Computing and Quantum Information by Michael Nielsen and Isaac Chuang); MOOCs; free online lecture notes by Umesh Vazirani, John Preskill, myself, and many others; and virtually the entire literature of the field just a few clicks away on arXiv.