We show that noiseless random quantum circuits pass the linear cross-entropy benchmark (LXEB) test with high probability. If the circuits are linear depth, and thus form unitary 4-designs, the LXEB test is passed with probability $1-O(1/\sqrt{k})$, where $k$ is the number of independently drawn samples from the output distribution of the random circuit. If the circuits are of depth $\tilde O(n^2)$, and thus form unitary $n$-designs, the LXEB test is passed with probability $1-O(e^{-k \log(n)/n})$. In proving our results, we show strong concentration of the random circuit collision probability at linear depth and establish that the tails of the distribution of random circuit output probabilities start to resemble Porter-Thomas at near-quadratic depths. Our analysis employs higher moments and high-degree approximate designs.
We show that noiseless random quantum circuits pass the linear cross-entropy benchmark (LXEB) test with high probability. If the circuits are linear depth, and thus form unitary 4-designs, the LXEB test is passed with probability 1−O(1/k), where k is the number of independently drawn samples from the output distribution of the random circuit. If the circuits are of depth O~(n2), and thus form unitary n-designs, the LXEB test is passed with probability 1−O(e−klog(n)/n). In proving our results, we show strong concentration of the random circuit collision probability at linear depth and establish that the tails of the distribution of random circuit output probabilities start to resemble Porter-Thomas at near-quadratic depths. Our analysis employs higher moments and high-degree approximate designs.
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.
Linear cross-entropy benchmarking (LXEB) with random quantum circuits is a standard method for evaluating quantum computers. However, LXEB requires classically simulating the ideal output distribution of a given quantum circuit with high numerical precision, which becomes infeasible beyond approximately 50 qubits, even on state-of-the-art supercomputers. As a result, LXEB cannot be directly applied to evaluate large-scale quantum devices, which now exceed 100 qubits and continue to grow rapidly in size. To address this limitation, we introduce a constraint known as particle-number conservation into the random quantum circuits used for benchmarking. This restriction significantly reduces the size of the Hilbert space for a fixed particle number, enabling classical simulations of circuits with over 100 qubits when the particle number is O ( 1 ) . Furthermore, we propose a modified version of LXEB, called MLXEB, which enables fidelity estimation under particle-number-conserving dynamics. Through numerical simulations, we investigate the conditions under which MLXEB provides accurate fidelity estimates.
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.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. In this work, we establish quantitative guarantees for how accurately these designs reproduce the full distributions of individual output probabilities. We show that, for every strong ε-approximate unitary k-design on n qubits, the distribution of each individual output probability is within O(k(k+2n)2n+ε) in Kolmogorov distance of the finite-dimensional Porter-Thomas distribution, a beta distribution with parameters 1 and 2n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We further show that local invariance yields an exponential improvement in the dependence on k, with guarantees also in the stronger metric of total variation: every strong ε-approximate unitary k-design invariant under unitary translations acting on logk+O(1) qubits achieves error 2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify both the distributional accuracy guaranteed by moment matching and the additional structure that substantially improves it. As an application, we show that if the marginal distribution of each output probability of a strong approximate design is within Kolmogorov distance η of its Haar counterpart, then the expected Shannon entropy of the output distribution differs from its Haar value by O(η).
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any m≥0, the distribution corresponding to circuits of depth O(n2m+1log(n)) is at most O(1/nm) far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. We show that, for local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution pnoisy of a generic noisy circuit instance and the output distribution pideal of the corresponding noiseless instance shrink exponentially with the expected number of gate-level errors, as F=exp(−2sε±O(sε2)), where ε is the probability of error per circuit location and s is the number of two-qubit gates. Furthermore, if the noise is incoherent, the output distribution approaches the uniform distribution punif at precisely the same rate and can be approximated as pnoisy≈Fpideal+(1−F)punif, that is, local errors are scrambled by the random quantum circuit and contribute only white noise (uniform output). Importantly, we upper bound the total variation error (averaged over random circuit instance) in this approximation as O(Fεs), so the "white-noise approximation" is meaningful when εs≪1, a quadratically weaker condition than the εs≪1 requirement to maintain high fidelity. The bound applies when the circuit size satisfies s≥Ω(nlog(n)) and the inverse error rate satisfies ε−1≥Ω~(n). The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; it was an underlying assumption in complexity-theoretic arguments that low-fidelity random quantum circuits cannot be efficiently sampled classically. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.