Cross-entropy benchmarking

After some further consideration I think it's quite clear that the only probability mass function evaluated in the computation of is that of the classically computed ideal distribution, denoted in the main paper.

This leads me to the conclusion that the phrasing of the following excerpt from section IV.C of the Supplemental Information (and especially the part underlined in red) is a bit unfortunate/misleading:

Just because the empirically measured bitstrings are coming from the uniform distribution doesn't mean that is suddenly for all . , as it goes into the calculation of the , is still the probability of sampling bitstring from the classically computed ideal distribution. This is in general not .

The correct reasoning is that the fact that will be (and ) when bitstrings are sampled from the uniform distribution follows from the definitions of expectation and probability mass function:

The definition of expected value is the following sum where is the probability of bitstring being sampled from the classically computed ideal quantum circuit, is the probability of being sampled from the non-ideal empirical distribution, and the sum runs over all possible bitstrings.

When bitstrings are coming from the uniform distribution will always be so can be broken out of the sum: When you sum any probability mass function (of which is one example) over all the possible outcomes you by definition get 1, and thus:

I think that the original rationale for using the linear cross-entropy (XEB) score as a metric to claim quantum computational supremacy was valid, but we may now be at a point now where the continued use of linear XEB for random circuit sampling on transmon qubit architectures to score and claim quantum advantage is not as justified as it was maybe in 2019, at least for two reasons:

1. It was known from the beginning that classical verification of cross-entropy scores scales exponentially with the number of qubits. This is still true today as it was in 2019. We still have no way to efficiently verify the output from a set of strings generated by a quantum computer (or, for that matter, by the algorithms of Aharanov et al.) But, with about 60 or so qubits, this was hoped and expected to be in the goldilocks zone of not being too hard verify efficiently nor too easy to be classically spoofed. If we used much more than that (say, with more than 100 qubits), we cannot even classically calculate the linear XEB score.

2. Much of the work you mentioned, for example IBM's initial response, required exponential resources not just to verify but also to even generate samples - whereas a quantum computer (even with a dilution refrigerator) would use exponentially fewer resources to generate the samples. But, what Aharanov et al. showed was that a classical computer could generate noisy samples from random circuit sampling where the resources to generate these samples grow polynomially - even though it takes exponential resources to verify and calculate the score.

There might be a handful of remaining loopholes to consider - for example, if we could keep the depth of our RCS algorithm constant the Aharanov et al. paper might not carry through. I also don't know the implications of the recent work for Boson Sampling experiments.

Another frustration is that without cross-entropy benchmarking, we don't know the best answer to what other ways do we have to prove that we've gone beyond classical with our computational resources in the NISQ era? Shor's algorithm is out, as it requires error correction. Some neat approaches of Kahanamoku-Meyer et al. might eventually be viable, but there's perhaps a long way to go.

I also like the new results of Chen et al. on the NISQ complexity class, suggesting that there likely still is exponential advantage for some carefully chosen problems even in the presence of noise - but instantiating these problems seems a bit tough now. For example, the Bernstein-Vazirani problem requires $O(1)$ quantum, but $O(n)$ classical queries (using perfect qubits); this is changed to $O(\log n)$ NISQ queries - still an exponential separation.