License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.30
URN: urn:nbn:de:0030-drops-135699
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13569/
Barak, Boaz ;
Chou, Chi-Ning ;
Gao, Xun
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
Abstract
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ⁿ⟩. 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(√{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.
BibTeX - Entry
@InProceedings{barak_et_al:LIPIcs.ITCS.2021.30,
author = {Boaz Barak and Chi-Ning Chou and Xun Gao},
title = {{Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {30:1--30:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13569},
URN = {urn:nbn:de:0030-drops-135699},
doi = {10.4230/LIPIcs.ITCS.2021.30},
annote = {Keywords: Quantum supremacy, Linear cross-entropy benchmark}
}
|
Keywords: |
|
Quantum supremacy, Linear cross-entropy benchmark |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
