Summer 2022 Quantum Supremacy Updates

I returned last week from the NSF Workshop on Quantum Advantage and Next Steps at the University of Chicago. Thanks so much to Chicago CS professor (and my former summer student) Bill Fefferman and the other organizers for making this workshop a reality. Given how vividly I remember the situation 12 years ago, when the idea of sampling-based quantum supremacy was the weird obsession of me and a few others, it was particularly special to attend a workshop on the topic with well over a hundred participants, some in-person and some on Zoom, delayed by covid but still excited by the dramatic experimental progress of the past few years.

Of course there’s a lot still to do. Many of the talks drew an exclamation point on something I’ve been saying for the past couple years: that there’s an urgent need for better quantum supremacy experiments, which will require both theoretical and engineering advances. The experiments by Google and USTC and now Xanadu represent a big step forward for the field, but since they started being done, the classical spoofing attacks have also steadily improved, to the point that whether “quantum computational supremacy” still exists depends on exactly how you define it.

Briefly: if you measure by total operations, energy use, or CO2 footprint, then probably yes, quantum supremacy remains. But if you measure by number of seconds, then it doesn’t remain, not if you’re willing to shell out for enough cores on AWS or your favorite supercomputer. And even the quantum supremacy that does remain might eventually fall to, e.g., further improvements of the algorithm due to Gao et al. For more details, see, e.g., the now-published work of Pan, Chen, and Zhang, or this good popular summary by Adrian Cho for Science.

If the experimentalists care enough, they could easily regain the quantum lead, at least for a couple more years, by (say) repeating random circuit sampling with 72 qubits rather than 53-60, and hopefully circuit depth of 30-40 rather than just 20-25. But the point I made in my talk was that, as long as we remain in the paradigm of sampling experiments that take ~2ⁿ time to verify classically and also ~2ⁿ time to spoof classically (where n is the number of qubits), all quantum speedups that we can achieve will be fragile and contingent, however interesting and impressive. As soon as we go way beyond what classical computers can keep up with, we’ve also gone way beyond where classical computers can check what was done.

I argued that the only solution to this problem is to design new quantum supremacy experiments: ones where some secret has been inserted in the quantum circuit that lets a classical computer efficiently verify the results. The fundamental problem is that we need three properties—

1. implementability on near-term quantum computers,
2. efficient classical verifiability, and
3. confidence that quantum computers have a theoretical asymptotic advantage,

and right now we only know how to get any two out of the three. We can get 1 and 2 with QAOA and various other heuristic quantum algorithms, 1 and 3 with BosonSampling and Random Circuit Sampling, or 2 and 3 with Shor’s algorithm or Yamakawa-Zhandry or recent interactive protocols. To get all three, there are three obvious approaches:

1. Start with the heuristic algorithms and find a real advantage from them,
2. Start with BosonSampling or Random Circuit Sampling or the like and figure out how to make them efficiently verifiable classically, or
3. Start with protocols like Kahanamoku-Meyer et al.’s and figure out how to run them on near-term devices.

At the Chicago workshop, I’d say that the most popular approach speakers talked about was 3, although my own focus was more on 2.

Anyway, until a “best-of-all-worlds” quantum supremacy experiment is discovered, there’s plenty to do in the meantime: for example, better understand the classical hardness of spoofing Random Circuit Sampling with a constant or logarithmic number of gate layers. Understand the best that classical algorithms can do to spoof the Linear Cross-Entropy Benchmark for BosonSampling, and build on Grier et al. to understand the power of BosonSampling with a linear number of modes.

I’ll be flying back with my family to Austin today after seven weeks at the Jersey shore, but I’ll try to field any questions about the state of quantum supremacy in general or this workshop in particular in the comments!