文章基本信息

标题：The Quantum Supremacy Tsirelson Inequality
本地全文：下载
作者：William Kretschmer
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：13:1-13:13
DOI：10.4230/LIPIcs.ITCS.2021.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit C on n qubits and a sample z â^^ {0,1}â¿, the benchmark involves computing âY¨z C 0â¿âY© Â², 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 polynomial-time classical algorithm given C can output a string z such that âY¨z C 0â¿âY© Â² 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 âY¨z C 0â¿âY© Â² â^ 2/(2â¿) on average (Arute et al., 2019). In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomial-time 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 âY¨z C 0â¿âY© Â² â¥ (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 Haar-random n-qubit unitary, or a canonical state preparation oracle for a Haar-random n-qubit 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 1-query algorithm for maximizing âY¨z C 0â¿âY© Â² on average.
关键词：quantum supremacy; quantum query complexity; random circuit sampling