Volume 16 (2020) Article 11 pp. 1-8 [Note]

On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking

by Scott Aaronson and Sam Gunn

Received: December 1, 2019
Revised: February 11, 2020
Published: November 2, 2020

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.

DOI: 10.4086/toc.2020.v016a011

© 2020 Scott Aaronson and Sam Gunn
Licensed under a Creative Commons Attribution License (CC-BY)