Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
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 0n, with mean squared error even slightly better than that of the trivial estimator that always estimates 1/2n. Our result automatically encompasses the case of noisy circuits.