Revised: February 11, 2020

Published: November 2, 2020

**Keywords:**Quantum Supremacy, quantum complexity, sampling complexity

**ACM Classification:**F.1.3, F.1.2

**AMS Classification:**81P68, 68Q17

**Abstract:**
[Plain Text Version]

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.