文章基本信息
- 标题：Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
- 本地全文：下载
- 作者：Boaz Barak ; Chi-Ning Chou ; Xun Gao 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2021
- 卷号：185
- 页码：30:1-30:20
- DOI：10.4230/LIPIcs.ITCS.2021.30
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：The linear cross-entropy benchmark (Linear XEB) has been used as a test for procedures simulating quantum circuits. Given a quantum circuit C with n inputs and outputs and purported simulator whose output is distributed according to a distribution p over {0,1}â¿, the linear XEB fidelity of the simulator is â"±_C(p) = 2â¿ ð"¼_{x â^¼ p} q_C(x) -1, where q_C(x) is the probability that x is output from the distribution C 0â¿âY©. A trivial simulator (e.g., the uniform distribution) satisfies â"±_C(p) = 0, while Googleâs noisy quantum simulation of a 53-qubit circuit C achieved a fidelity value of (2.24 ±0.21)Ã-10^{-3} (Arute et. al., Nature'19). In this work we give a classical randomized algorithm that for a given circuit C of depth d with Haar random 2-qubit gates achieves in expectation a fidelity value of Ω(n/Lâ<.15^{-d}) in running time poly(n,2^L). Here L is the size of the light cone of C: the maximum number of input bits that each output bit depends on. In particular, we obtain a polynomial-time algorithm that achieves large fidelity of Ï(1) for depth O(â^S{log n}) two-dimensional circuits. This is the first such result for two dimensional circuits of super-constant depth. Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of the quantum circuit.
- 关键词：Quantum supremacy; Linear cross-entropy benchmark
