  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.
