Limitations of Linear Cross-Entropy as a Measure of Quantum Advantage


Chi-Ning Chou September 30, 2022.


Quantum advantage is a program aiming to demonstrate the computational advantage of incorporating quantum mechanics in near-term realizable devices. Random Circuits Sampling (RCS) is one of the leading approaches that was adopted by the recent breakthroughs of Google and USTC. Specifically, both of them were using the linear cross-entropy (linear XEB) as a measure to evaluate the computational advantage of their devices. For example, in 2019, Google achieved a score of 0.00224 XEB value using a 53-qubit quantum processor and conjectured that it requires 10,000 years for the best supercomputer to get a similar XEB value.

In this talk, I’m going to present our recent work on reexamining the usage of linear XEB as a measure of quantum advantage. I will start with giving a broad overview on the previous developments and formally set up the mathematical formulation. Next, I will state our main theoretical and numerical results and discuss their implications. Finally, if time allows, I will give a bird-eye view on the underlying new mathematical framework we developed for analyzing linear XEB.

No background in quantum computation and physics is needed but I will assume a little familiarity with basic linear algebra and probability theory. This is a joint work with Xun Gao, Marcin Kalinowski, Mikhail Lukin, Boaz Barak, and Soonwon Choi. Link to the paper:

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Are quantum speedups for learning expressive classes possible?
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Improved Quantum Query Upper Bounds Based on Classical Decision Trees
  • Interior Point Methods for Nearly Linear Time Algorithms
  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits