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

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.

25+33 pages, 13+16 figures

References in corpus (7)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Randomized Benchmarking of Quantum Gates
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model

Cited by in corpus (24)

• Phase transition in Random Circuit Sampling
• Variational Benchmarks for Quantum Many-Body Problems
• Classical algorithm for simulating experimental Gaussian boson sampling
• The computational power of random quantum circuits in arbitrary geometries
• Bell sampling from quantum circuits
• Classically estimating observables of noiseless quantum circuits
• Experimental demonstration of scalable cross-entropy benchmarking to detect measurement-induced phase transitions on a superconducting quantum processor
• Benchmarking quantum gates and circuits
• Fully scalable randomized benchmarking without motion reversal
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Robust sparse IQP sampling in constant depth
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Verifiable measurement-based quantum random sampling with trapped ions
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Probabilistic Inference in the Era of Tensor Networks and Differential Programming
• Phase transitions in sampling and error correction in local Brownian circuits
• Approximate inverse measurement channel for shallow shadows
• Error Mitigation Thresholds in Noisy Random Quantum Circuits
• Benchmarking the performance of a high-Q cavity qudit using random unitaries
• Scalable projected entangled-pair state representation of random quantum circuit states
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Provable and Verifiable Quantum Advantage in Sample Complexity
• More global randomness from less-random local gates