pdf icon
Volume 16 (2020) Article 11 pp. 1-8 [Note]
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
Received: December 1, 2019
Revised: February 11, 2020
Published: November 2, 2020
Download article from ToC site:
[PDF (193K)] [PS (695K)] [Source ZIP]
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.