Fetching the paper…

Reading the bibliography…

2019

On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking

Aaronson, Scott, Gunn, Sam

Original
PDF
Post on X

Understand

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.

On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking · Around

Built on

The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov · 2011
Earlier work this paper cites.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
M. J. Bremner, R. Jozsa, and D. J. Shepherd · 2011
Earlier work this paper cites.
Complexity-theoretic foundations of quantum supremacy experiments
Scott Aaronson and Lijie Chen · 2017
Earlier work this paper cites.
Characterizing quantum supremacy in near-term devices
Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven · 2018
Earlier work this paper cites.

Similar

Approximate unitary t t -designs by short random quantum circuits using nearest-neighbor and long-range gates
Original
Aram Harrow and Saeed Mehraban · 2018
Cited alongside, same era.
Explicit lower bounds on strong quantum simulation
Original
Cupjin Huang, Michael Newman, and Mario Szegedy · 2018
Cited alongside, same era.
Quantum supremacy using a programmable superconducting processor
Frank Arute et al · 2019
Cited alongside, same era.
Quantum supremacy and the complexity of random circuit sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh V. Vazirani · 2019
Cited alongside, same era.

Then

Automatic tensor network contraction, Oct 2019
Johnnie Gray · 2019
Closest in time.
Efficient classical simulation of random shallow 2D quantum circuits
Original
John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, and Aram W. Harrow · 2019
Closest in time.
Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
Original
Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…