Remarkable: “Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage,” by Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, and Soonwon Choi

In this post I would like to report about an important paper (posted Dec. 2021) by Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, and Soonwon Choi. (I am thankful to Xun Gao and  Boaz Barak for helpful discussions).

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

Here is the abstract:

Demonstrating quantum advantage requires experimental implementation of a computational task that is hard to achieve using state-of-the-art classical systems. One approach is to perform sampling from a probability distribution associated with a class of highly entangled many-body wavefunctions. It has been suggested that this approach can be certified with the Linear Cross-Entropy Benchmark (XEB). We critically examine this notion. First, in a “benign” setting where an honest implementation of noisy quantum circuits is assumed, we characterize the conditions under which the XEB approximates the fidelity. Second, in an “adversarial” setting where all possible classical algorithms are considered for comparison, we show that achieving relatively high XEB values does not imply faithful simulation of quantum dynamics. We present an efficient classical algorithm that, with 1 GPU within 2s, yields high XEB values, namely 2-12% of those obtained in experiments. By identifying and exploiting several vulnerabilities of the XEB, we achieve high XEB values without full simulation of quantum circuits. Remarkably, our algorithm features better scaling with the system size than noisy quantum devices for commonly studied random circuit ensembles. To quantitatively explain the success of our algorithm and the limitations of the XEB, we use a theoretical framework in which the average XEB and fidelity are mapped to statistical models. We illustrate the relation between the XEB and the fidelity for quantum circuits in various architectures, with different gate choices, and in the presence of noise. Our results show that XEB’s utility as a proxy for fidelity hinges on several conditions, which must be checked in the benign setting but cannot be assumed in the adversarial setting. Thus, the XEB alone has limited utility as a benchmark for quantum advantage. We discuss ways to overcome these limitations.

I. Three parameters for noisy quantum circuits:

1. F – The fidelity. If is the ideal state and is the noisy state, then the fidelity F is defined by ,
2. XEB – the linear cross entropy estimator for the fidelity
3. P(No err) – The probability of no errors (denoted in the paper by ).

II. Some issues:

a) The fidelity F cannot be read from the distribution of the samples produced by the quantum computer. Suppose we are given an unlimited number of samples (or a large number of samples for which the empirical distribution is a good approximation to the noisy distribution), what is the best way to estimate the fidelity?

b) If we have a polynomial number of samples in (1/F). What are the best ways to estimate the fidelity?

c) What in general are the relations between F, XEB, and P(No err)?

III. A basic observation:

A basic observation of the paper is that when you apply depolarizing noise to the gates, the resulting distribution has a positive correlation to the ideal distribution. (Hence this leads to positive XEB value.)  The basic idea (as I see it) is simple: let’s consider 1-gate which is a certain unitary operator U. The space of such operators is spanned by I, X, Y, and Z. Let us assume that applying to U unitary noise, say, Y, will lead to a new quantum circuit which gives uncorrelated samples and fidelity estimator 0. However, applying (I+X+Y+Z), which replace the qubit with a maximal entropy state is a very basic form of noise (depolarizing noise on the qubit on which the gate acts) and this form of noise is expected to slash the fidelity estimator by four and not send it to zero. (For 2-gates the story is similar but this time there are 16 basic possibilities for unitary noise so we can expect that a depolarizing noise will slash the linear cross entropy estimator by 1/16 (and not to zero).)

IV. Additional observations

The paper by Gao et al. describes various additional reasons for which the effect of gate errors will lead to positive correlations with the ideal distribution, and in general will lead to strict inequalities

(1)   XEB   >  P(No err)

and

(2)   XEB > F > P(No err)

First, it turns out that even a single unitary gate error can contribute to the increase of XEB  (and also to increase F), and, moreover, the effect of two (or more) gate errors can also lead to an increased XEB (and also an increased F.)

In expectation we can actually expect.

(3)    XEB > F > P(No err)

This is demonstrated by Figure 1 of the paper.

V. The idea behind the spoofing algorithm

The way Gao, Kalinowski, Chou, Lukin, Barak, and Choi used this observation is by applying such depolarization noise on a set of 2-gates that would split the circuit into two parts. This will lead to a sort of “patched” circuit for which one can make the computation separately on every patch, which gives much quicker classical algorithms.

VI The asymptotic behavior

One interesting aspect of the paper is that (as far as I could understand) when the number of qubits grows the “quantum advantage” , namely the advantage of the quantum algorithms over the classical algorithms, diminishes. As Gao et al. write

“Remarkably, the XEB value of our algorithm generally improves for larger quantum circuits, whereas that of noisy quantum devices quickly deteriorates. Such scaling continues to hold when the number of qubits is increased while the depth of the circuit and the error-per-gate are fixed…”

Remark: This conclusion assumes that you need enough samples to verify the fidelity. Philosophically one can claim that the quantum advantage may apply for producing *one* sample; After all, your argument is based anyway on extrapolation, and for supremacy experiments you cannot verify even the individual amplitudes. (I made this claim in a discussion with Daniel Lidar regarding the very nice paper by Zlokapa, Boixo, and Lidar, Boundaries of quantum supremacy via random circuit sampling, but I couldn’t persuade Daniel.)

VII Relevance to the statistical analysis and the concerns regarding the Google 2019 experiment

The paper is relevant to two important aspects of my statistical science paper with Yosi Rinott and Tomer Shoham and to our work which puts the Google 2019 experiment under scrutiny.

1. The fact that XEB is systematically larger than P(No err) may support the concern that the precise agreement of the XEB estimator with the P(No err) computation (Formula (77)) is “too good to be true,” namely, it fits too well with the researcher’s expectations rather than with physical reality.
2. The basic observation (III) implies that the exponential decay for the Fourier coefficients with the degrees, that we attributed only to readout errors is also caused by gate errors. Subsequently, the Fourier description of the data that we regarded as providing confirmation to the Google claim (see, Figure 2 in our recent paper) actually appears to show that the empirical data does not fit the theory.

Apropos Fourier methods and Xun Gao: The first I heard of Xun Gao’s work was in connection with his excellent early work with Duan Efficient classical simulation of noisy quantum computation that used Fourier methods to study quantum circuits.