The linear cross-entropy benchmark (Linear XEB) has been used as a test for procedures simulating quantum circuits. Given a quantum circuit C with n inputs and outputs and purported simulator whose output is distributed according to a distribution p over {0,1}ⁿ, the linear XEB fidelity of the simulator is ℱ_C(p) = 2ⁿ 𝔼_{x ∼ p} q_C(x) -1, where q_C(x) is the probability that x is output from the distribution C |0ⁿ⟩. A trivial simulator (e.g., the uniform distribution) satisfies ℱ_C(p) = 0, while Google’s noisy quantum simulation of a 53-qubit circuit C achieved a fidelity value of (2.24 ±0.21)×10^{-3} (Arute et. al., Nature'19). In this work we give a classical randomized algorithm that for a given circuit C of depth d with Haar random 2-qubit gates achieves in expectation a fidelity value of Ω(n/L⋅15^{-d}) in running time poly(n,2^L). Here L is the size of the light cone of C: the maximum number of input bits that each output bit depends on. In particular, we obtain a polynomial-time algorithm that achieves large fidelity of ω(1) for depth O(√{log n}) two-dimensional circuits. This is the first such result for two dimensional circuits of super-constant depth. Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of the quantum circuit.
The linear cross-entropy benchmark (Linear XEB) has been used as a test for procedures simulating quantum circuits. Given a quantum circuit C with n inputs and outputs and purported simulator whose output is distributed according to a distribution p over {0,1}ⁿ, the linear XEB fidelity of the simulator is ℱ_C(p) = 2ⁿ 𝔼_{x ∼ p} q_C(x) -1, where q_C(x) is the probability that x is output from the distribution C |0ⁿ⟩. A trivial simulator (e.g., the uniform distribution) satisfies ℱ_C(p) = 0, while Google’s noisy quantum simulation of a 53-qubit circuit C achieved a fidelity value of (2.24 ±0.21)×10^{-3} (Arute et. al., Nature'19). In this work we give a classical randomized algorithm that for a given circuit C of depth d with Haar random 2-qubit gates achieves in expectation a fidelity value of Ω(n/L⋅15^{-d}) in running time poly(n,2^L). Here L is the size of the light cone of C: the maximum number of input bits that each output bit depends on. In particular, we obtain a polynomial-time algorithm that achieves large fidelity of ω(1) for depth O(√{log n}) two-dimensional circuits. This is the first such result for two dimensional circuits of super-constant depth. Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of the quantum circuit.
The linear cross-entropy benchmark (Linear XEB) has been used as a test for procedures simulating quantum circuits. Given a quantum circuit C with n inputs and outputs and purported simulator whose output is distributed according to a distribution p over {0,1}ⁿ, the linear XEB fidelity of the simulator is ℱ_C(p) = 2ⁿ 𝔼_{x ∼ p} q_C(x) -1, where q_C(x) is the probability that x is output from the distribution C |0ⁿ⟩. A trivial simulator (e.g., the uniform distribution) satisfies ℱ_C(p) = 0, while Google’s noisy quantum simulation of a 53-qubit circuit C achieved a fidelity value of (2.24 ±0.21)×10^{-3} (Arute et. al., Nature'19). In this work we give a classical randomized algorithm that for a given circuit C of depth d with Haar random 2-qubit gates achieves in expectation a fidelity value of Ω(n/L⋅15^{-d}) in running time poly(n,2^L). Here L is the size of the light cone of C: the maximum number of input bits that each output bit depends on. In particular, we obtain a polynomial-time algorithm that achieves large fidelity of ω(1) for depth O(√{log n}) two-dimensional circuits. This is the first such result for two dimensional circuits of super-constant depth. Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of the quantum circuit.
Recently, Google announced the first demonstration of quantum computational supremacy with a programmable superconducting processor. Their demonstration is based on collecting samples from the output distribution of a noisy random quantum circuit, then applying a statistical test to those samples called Linear Cross-Entropy Benchmarking (Linear XEB). This raises a theoretical question: how hard is it for a classical computer to spoof the results of the Linear XEB test? In this short note, we adapt an analysis of Aaronson and Chen [2017] to prove a conditional hardness result for Linear XEB spoofing. Specifically, we show that the problem is classically hard, assuming that there is no efficient classical algorithm that, given a random n-qubit quantum circuit C, estimates the probability of C outputting a specific output string, say 0^n, with variance even slightly better than that of the trivial estimator that always estimates 1/2^n. Our result automatically encompasses the case of noisy circuits.
Random circuit sampling (RCS) remains one of the most competitive frameworks for demonstrating quantum advantage in near-term noisy intermediate-scale quantum (NISQ) hardware. Unfortunately, absent error-correction, existing benchmarks to characterize these experiments, like linear cross-entropy, have been classically spoofed due to noise. Because of this, there are interesting regimes, like shallow-depth random quantum circuits, where sampling is plausibly classically intractable, but no existing benchmark can distinguish between a noisy quantum computer and an adversarial classical spoofer. In this paper, we demonstrate that the nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers, even in the presence of depolarizing noise. Further, we develop a binary classifier based on the notion of heavy output generation that features logarithmic sample complexity at short depth. Our evidence comes from exact analytic expressions for all-to-all Brownian circuit ensembles derived using replica tricks, and numerical simulations that corroborate these results for discrete Haar-random unitary circuits.
With the advent of quantum processors exceeding 100 qubits and the high engineering complexities involved, there is a need for holistically benchmarking the processor to have quality assurance. Linear cross-entropy benchmarking (XEB) has been used extensively for systems with 50 or more qubits but is fundamentally limited in scale due to the exponentially large computational resources required for classical simulation. In this work we propose conducting linear XEB with random Clifford circuits of constant to logarithmic depth, a scheme we call Clifford XEB. Since Clifford circuits can be simulated in polynomial time, Clifford XEB can be scaled to much larger systems. To validate this claim, we run numerical simulations for the classes of Clifford circuits we propose with noise and observe exponential decays. When noise levels are low, the decay rates are well correlated with the noise of each cycle assuming a multiplicative error accumulation, i.e., where the fidelities of individual gates multiply. We perform simulations of systems up to 1225 qubits, where the classical processing task can be easily dealt with by a workstation. Furthermore, using the theoretical guarantees in Chen et al. [PRX Quantum 3, 030320 (2022)], we prove that Clifford XEB with our proposed Clifford circuits must yield exponential decays under a general error model for sufficiently low errors. Our theoretical results explain some of the phenomena observed in the simulations and shed light on the behavior of general linear XEB experiments.
In recent years, several experimental groups have claimed demonstrations of ``quantum supremacy'' or computational quantum advantage. A notable first claim by Google Quantum AI revolves around a metric called the Linear Cross Entropy Benchmarking (Linear XEB), which has been used in many quantum supremacy experiments since. The complexity-theoretic hardness of spoofing Linear XEB, however, depends on the Cross-Entropy Quantum Threshold (XQUATH) conjecture put forth by Aaronson and Gunn, which has been disproven for sublinear depth circuits. In the efforts on demonstrating quantum supremacy by quantum Hamiltonian simulation, a similar benchmarking metric called the System Linear Cross Entropy Score (sXES) holds firm in light of the aforementioned negative result due to its fundamental distinction with Linear XEB. Moreover, the complexity-theoretic hardness of spoofing sXES rests on the System Linear Cross-Entropy Quantum Threshold Assumption (sXQUATH), the formal relationship of which to XQUATH is unclear. Despite the promises offered by sXES for future demonstration of quantum supremacy, in this work we show that it can be classically simulated efficiently in certain regimes.
While many statistical properties of deep random quantum circuits can be deduced, often rigorously and other times heuristically, by an approximation to global Haar-random unitaries, the statistics of constant-depth random quantum circuits are generally less well-understood due to a lack of amenable tools and techniques. We circumvent this barrier by considering a related constant-time Brownian circuit model which shares many similarities with constant-depth random quantum circuits but crucially allows for direct calculations of higher order moments of its output distribution. Using mean-field (large-n) techniques, we fully characterize the output distributions of Brownian circuits at shallow depths and show that they follow a Porter-Thomas distribution, just like in the case of deep circuits, but with a truncated Hilbert space. The access to higher order moments allows for studying the expected and typical Linear Cross-entropy (XEB) benchmark scores achieved by an ideal quantum computer versus the state-of-the-art classical spoofers for shallow Brownian circuits. We discover that for these circuits, while the quantum computer typically scores within a constant factor of the expected value, the classical spoofer suffers from an exponentially larger variance. Numerical evidence suggests that the same phenomenon also occurs in constant-depth discrete random quantum circuits, like those defined over the all-to-all architecture. We conjecture that the same phenomenon is also true for random brickwork circuits in high enough spatial dimension.