Southwest Quantum Information and Technology

On the classical hardness of spoofing linear cross-entropy benchmarking

Presenting Author: Sam Gunn, University of Texas, Austin
Contributing Author(s): Scott Aaronson

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 0^n, with variance even slightly better than that of the trivial estimator that always estimates 1/2^n. Our result automatically encompasses the case of noisy circuits.

Read this article online: https://arxiv.org/pdf/1910.12085.pdf

(Session 2 : Saturday from 10:30am - 11:00am)