Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

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^nrangle$. A trivial simulator (e.g., the uniform distribution) satisfies $mathcal{F}_C(p)=0$, while Googles noisy quantum simulation of a 53 qubit circuit $C$ achieved a fidelity value of $(2.24pm0.21)times10^{-3}$ (Arute et. al., Nature19). 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.