Theory of Computing
-------------------
Title     : On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
Authors   : Scott Aaronson and Sam Gunn
Volume    : 16
Number    : 11
Pages     : 1-8
URL       : https://theoryofcomputing.org/articles/v016a011

Abstract
--------

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 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 mean squared
error even slightly better than that of the trivial estimator that
always estimates $1/2^n$. Our result automatically encompasses the
case of noisy circuits.