Source-linked AI summary
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
Boaz Barak, Chi-Ning Chou, Xun Gao
TL;DR
Linear XEB tests quantum-circuit simulators, raising the question of whether classical hardness of full simulation also rules out non-trivial benchmark scores. The paper gives a classical randomized algorithm for circuits with small light cones and reports non-trivial expected fidelity for logarithmic-depth constant-dimensional circuits. Its results indicate that benchmark performance need not be equivalent to full simulation, though the analyzed sample-complexity bounds are partial.
Problem
The paper investigates whether classical hardness of full quantum-circuit simulation also rules out classical algorithms achieving non-trivial Linear XEB fidelity.
Source: §1 · p. 3Method
The authors give a classical randomized algorithm for circuits with Haar random 2-qubit gates and small light cones.
Source: §1 · p. 3Results
For every constant α, the corollary’s fidelity bound is at least 1/poly(n), and it is ω(1) when α < 1/4.
Source: §1 · p. 4Takeaways & Limitations
The results provide evidence that achieving non-trivial Linear XEB performance need not require full circuit simulation.
Source: §1 · pp. 3–4The sample-complexity analysis handles variance rather than higher moments, and the authors report only partial bounds.
Source: Probability over circuits · p. 4, §6 · p. 13
Abstract
from arXiv · showhide
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\}^n$, the linear XEB fidelity of the simulator is $\mathcal{F}_{C}(p) = 2^n \mathbb{E}_{x \sim p} q_C(x) -1$ where $q_C(x)$ is the probability that $x$ is output from the distribution $C|0^n\rangle$. A trivial simulator (e.g., the uniform distribution) satisfies $\mathcal{F}_C(p)=0$, while Google's noisy quantum simulation of a 53 qubit circuit $C$ achieved a fidelity value of $(2.24\pm0.21)\times10^{-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 $\Omega(\tfrac{n}{L} \cdot 15^{-d})$ in running time $\textsf{poly}(n,2^L)$. Here $L$ is the size of the \emph{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 $\omega(1)$ for depth $O(\sqrt{\log n})$ two-dimensional circuits. To our knowledge, 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.
1 Introduction
The introduction questions whether classical hardness of full quantum-circuit simulation also implies hardness of achieving non-trivial Linear XEB fidelity. It presents a classical approach for circuits with small light cones and reports non-trivial expected-fidelity results for logarithmic-depth constant-dimensional circuits, while noting limits on the Google-like regime and empirical guarantees.
1 Introduction
- The proposed classical algorithm targets Linear XEB directly rather than fully simulating the circuit, and the authors present it as evidence that the two tasks need not be equivalent.The paper says its algorithm does not reach the Google experiment’s parameter regime.Source: §1 · pp. 3–4
- Linear XEB fidelity is 2^n times the expected circuit output probability q_C(x) under simulator distribution p, minus 1; uniform or circuit-independent sampling scores zero.Google’s noisy simulation of two-dimensional 53-qubit, depth-20 circuits achieved approximately (2.24 ± 0.21) × 10^-3.Source: §1 · p. 3
- For general circuits, light cones can grow exponentially with depth, whereas in one- and two-dimensional circuits their size is polynomial in depth.The light cone of an output bit is the set of input bits connected to it by paths through the circuit.Source: §1 · p. 3
- For every constant α, the corollary’s fidelity bound is at least 1/poly(n), and it is ω(1) when α < 1/4.The corollary considers constant-dimensional circuits of depth d = α log n with Haar random 2-qubit gates.Source: §1 · p. 4
- The corollary covers logarithmic depth, whereas the Google experiment’s depth is roughly comparable to √n; earlier literature achieved good Linear XEB performance only at constant depth.The authors describe their result as the first for two-dimensional circuits of super-constant depth.Source: §1 · p. 4
1.1 From expectation to concentration.
- Empirical Linear XEB is computed from samples, and proving inverse-polynomial success probability with polynomially many samples is more challenging than bounding expected fidelity.The introduction says the paper’s probability bounds are weaker than the optimal bounds one could hope for.Source: §1.1 · p. 4
Probability over circuits.
The section gives partial guarantees on fidelity across circuits and algorithmic randomness, while noting that prior work either targeted full simulation or handled only restricted settings. Its empirical-sample guarantees rely on collision-probability bounds, with the two-dimensional case remaining conjectural.
Probability over circuits.
- For logarithmic-depth circuits, the algorithm achieves 1/poly(n) fidelity with probability at least 1/poly(n) over circuits.The authors conjecture that fidelity concentrates more sharply around its expectation.Source: Probability over circuits · p. 4
- An upper bound on q_C's collision probability yields an upper bound on the samples needed for empirical linear XEB; the authors describe their sample-complexity bounds as partial and likely non-optimal.For random one-dimensional circuits of depth at least c log n, CP(q_C)=O(2^-n), implying inverse-polynomial empirical fidelity with polynomially many samples.Source: Probability over circuits · p. 4
- For one-dimensional circuits of depth at least c log n, CP(q_C)=O(2^-n); the analogous bound for two-dimensional circuits of depth Ω(√log n) is conjectured.If the two-dimensional bound holds, the authors say it would imply 1/poly(n) empirical fidelity with polynomial samples and constant fidelity with sub-exponential samples.Source: Probability over circuits · p. 4
1.2 Prior works
- Earlier work did not directly bound linear XEB performance independently of full-distribution approximation, and cited two-dimensional simulation results addressed only small constant depth.The cited constant-depth approach relies on area-law entanglement; the cited work indicates a transition to volume-law entanglement beyond a constant depth.Source: §1.2 · p. 5
- Prior noisy-circuit work covered restricted classes and more general random circuits, while recent numerical studies considered matrix-product approximations under state fidelity.Low-degree Fourier expansions were also considered for approximating quantum states.Source: §1.2 · p. 5
2 Preliminaries
The preliminaries specify circuit architecture, light cones, and random-gate circuits, then introduce tensor networks as a graphical language for representing the operations used in the paper.
2 Preliminaries
- A circuit skeleton specifies the wiring architecture through layers and permutations, while the light cone size is the largest number of inputs connected to any output.The preliminaries note that the section can be consulted as needed and that tensor networks may be unfamiliar to some readers.Source: §2 · p. 5
- An output-bit marginal can be computed using only that bit's light cone, in time O(2^L) when the circuit skeleton has light cone size L.The example computes an output marginal using only the inputs in its light cone.Source: §2 · p. 6
- Random quantum circuits are specified by a circuit skeleton and gate ensembles, with Haar-random 4 × 4 unitaries defining Haar-random two-qubit circuits.The gates are assigned to the skeleton's gate locations.Source: §2 · p. 6
2.1 Tensor networks
- Tensor networks represent multilinear maps graphically; here the paper restricts attention to qubits and two-qubit gates.Gate boxes encode matrix coordinates, states are triangles, and lines represent equality of their endpoint indices.Source: §2.1 · pp. 6–7
3 Our Algorithm
The algorithm samples selected output bits from their circuit marginals and fills the rest uniformly, avoiding simulation of the full circuit. Its analysis reduces expected fidelity to a single-output-bit calculation for Haar-random gates.
3 Our Algorithm
- The algorithm computes marginals for m output qubits with disjoint light cones, samples those bits accordingly, and samples all remaining bits uniformly.It chooses m from 1 to floor(n/L); the stated running time is at most poly(n, 2^L).Source: §3 · p. 7
3.1 Analysis
- For circuits with light-cone size at most L, Haar-random 2-qubit gates, and depth at most d, the algorithm’s expected linear XEB is bounded by Theorem 3.1.The result applies to the distribution of circuits specified by those conditions; the theorem’s bound is not fully visible in the supplied passage.Source: §3.1 · p. 8
- The proof reduces the m-output-bit analysis to one output bit, then uses Haar integration and a tensor-network change of basis to obtain a Markov-chain lower bound.The analysis applies the integration formula to each gate and uses the resulting Markov-chain representation to lower-bound the single-bit contribution.Source: §3.1 · p. 8
4 Single qubit analysis
For Haar-random 2-qubit gates, the expected linear XEB contribution of a single output qubit is at least 15^-d. The proof turns Haar averages into a Markov-chain calculation using tensor networks and a Pauli-basis change.
4 Single qubit analysis
- For each output qubit, the expected linear XEB contribution is at least 15^-d for circuits of depth at most d with Haar-random 2-qubit gates.The section also states that the single-qubit contribution is of order 15^-d.Source: §4 · p. 8
- Haar integration rewrites the expected single-gate behavior as an explicit transition matrix, simplifying the circuit tensor network to a Markov chain.This Markov-chain representation is used to lower-bound the expected single-qubit fidelity contribution.Source: §4 · p. 9
4.1 Proof of Lemma 4.3
- The derivation applies Haar integration in a tensor-network representation, changes from the standard to Pauli basis, and finds zero in specified cases and 2^-4 · 15^-1 in all other cases.Zero occurs when σ1 = σ2 = I and at least one of σ1′, σ2′ is not I, or when at least one of σ1, σ2 is not I and σ1′ = σ2′ = I.Source: §4.1 · pp. 10–11
4.2 Proof of Lemma 4.4
- For Lemma 4.4, the proof applies the single-gate representation across independent gates and uses Pauli-gate orthogonality to compose the layers.The input and output layers are then incorporated to complete the Markov-chain representation.Source: §4.2 · pp. 11–12
5 Wrapping up: from single output bit to many bits
The proof extends the single-output-bit analysis to several output bits by selecting disjoint light cones and using their marginal probabilities. It also establishes a lower bound on the probability, over circuits, of obtaining non-trivial fidelity.
5 Wrapping up: from single output bit to many bits
- The algorithm selects output qubits with disjoint light cones and assigns each full output string probability 2^(m-n) times the selected bits’ joint marginal probability.Disjoint light cones make the selected bits’ joint marginal factor into a product of individual marginals.Source: §5 · p. 12
- The proof applies the single-qubit analysis to the selected outputs and takes expectation over the circuit distribution to complete Theorem 1.1.The argument uses independence of the selected outputs under the circuit distribution.Source: §5 · pp. 12–13
5.1 Probability over circuits
- Corollary 5.4 gives a randomized poly(n, 2^L)-time algorithm with a lower bound on its probability of obtaining non-trivial fidelity over circuits.The supplied corollary passage does not expose the full probability bound.Source: §5.1 · p. 13
6 Sample complexity analysis
The sample-complexity analysis uses variance and collision probability to control empirical linear XEB, and proves an O(2^m) sample bound for a stated family of 1D random circuits. It also notes that variance-based bounds can be loose and leaves a 2D extension as future work.
6.1 A variance/collision probability approach
- Chebyshev’s inequality bounds the samples needed for empirical XEB to approach its expectation using Var_x∼p[F_C(x)]/(ε^2δ), with the circuit fixed.The bound gives a probability guarantee over the randomness of p.Source: §6.1 · p. 13
- Bounding the algorithm’s variance reduces to bounding the ideal output distribution’s collision probability.For a uniform output distribution, the passage gives variance O(2^m); choosing m = O(log n) makes the sample complexity polynomial.Source: §6.1 · p. 14
- At depth 1, biased-coin-like marginals can have exponentially large variance even though O(1) samples suffice, so variance-based sample bounds may be loose.The passage describes this depth-1 marginal behavior as occurring with high probability.Source: §6.1 · p. 14
- The expected collision probability is O(2^-n) for 1D circuits of depth at least log(n)/log(5/4); extending the proof to 2D circuits is left for future work.The authors also state a conjecture about 2D random circuits, but its depth condition is truncated in the supplied passage.Source: §6.1 · pp. 14–15
6.2 The sample complexity of 1D random circuits of logarithmic depth
- For 1D Haar-random circuits of depth Ω(log n), the sample complexity is O(2^m) with high probability under the theorem’s stated qudit-dimension and output-qubit conditions.The theorem requires qudit dimension at least 4 and m no greater than floor(n/2d).Source: §6.2 · p. 15
6.3 Proof of Lemma 6.6
- The proof recasts the second moment as a spin-system counting problem, moving from a hexagonal lattice to triangular-lattice domain walls in one-to-one correspondence with spin configurations.The lattice representation uses Haar-gate integration and local summation over blue vertices.Source: §6.3 · pp. 16–18
A Useful properties of quantum circuits and tensor networks
The appendix collects properties of quantum circuits and tensor networks. In particular, output-qubit marginals factor when their light cones are disjoint.
A Useful properties of quantum circuits and tensor networks
- Lemma A.1 considers the marginal probability of the first output qubit, summing over outputs whose first bit is b.The passage invokes linearity and the identity that the corresponding sum of projectors is |b⟩⟨b| ⊗ I⊗n−1.Source: A Useful properties of quantum… · p. 20
- The appendix lists trace and matrix-multiplication properties for unitary matrices of two-qubit gates.It also introduces properties of Pauli matrices in tensor networks; one stated distinction assigns 1 to I and Z and 0 to X and Y.Source: A Useful properties of quantum… · pp. 20–21
- Disjoint light cones make the joint marginal probability of the selected outputs equal the product of their individual marginal probabilities.The proof says gates with no path to those outputs cancel in the tensor network, leaving separate networks for each output.Source: A Useful properties of quantum… · pp. 21–22