  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.
