Abstract
A leading proposal for verifying nearterm quantum supremacy experiments on noisy random quantum circuits is linear crossentropy benchmarking. For a quantum circuit C on n qubits and a sample z ∈ {0,1}ⁿ, the benchmark involves computing ⟨zC0ⁿ⟩², i.e. the probability of measuring z from the output distribution of C on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomialtime classical algorithm given C can output a string z such that ⟨zC0ⁿ⟩² is substantially larger than 1/(2ⁿ) (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit C, sampling z from the output distribution of C achieves ⟨zC0ⁿ⟩² ≈ 2/(2ⁿ) on average (Arute et al., 2019).
In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomialtime quantum algorithm do substantially better than 2/(2ⁿ)? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to C. We show that, for any ε ≥ 1/poly(n), outputting a sample z such that ⟨zC0ⁿ⟩² ≥ (2 + ε)/2ⁿ on average requires at least Ω((2^{n/4})/poly(n)) queries to C, but not more than O (2^{n/3}) queries to C, if C is either a Haarrandom nqubit unitary, or a canonical state preparation oracle for a Haarrandom nqubit state. We also show that when C samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from C is the optimal 1query algorithm for maximizing ⟨zC0ⁿ⟩² on average.
BibTeX  Entry
@InProceedings{kretschmer:LIPIcs.ITCS.2021.13,
author = {William Kretschmer},
title = {{The Quantum Supremacy Tsirelson Inequality}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {13:113:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13552},
URN = {urn:nbn:de:0030drops135524},
doi = {10.4230/LIPIcs.ITCS.2021.13},
annote = {Keywords: quantum supremacy, quantum query complexity, random circuit sampling}
}
Keywords: 

quantum supremacy, quantum query complexity, random circuit sampling 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 