2019/10/26 by Scott Aaronson, Aaronson, Scott, Sam Gunn +1 · 8 citations
Computer Science · Engineering · Physics and Astronomy · #Advancements in Photolithography Techniques #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1910.12085
openalex publication_date 2019/10/26 · arxiv created 2020/02/06 · arxiv updated 2020/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 [2017] 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 variance even slightly better than that of the trivial estimator that always estimates 1/2n. Our result automatically encompasses the case of noisy circuits.