Abstract
The linear crossentropy 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 53qubit 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 2qubit 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 polynomialtime algorithm that achieves large fidelity of ω(1) for depth O(√{log n}) twodimensional circuits. This is the first such result for two dimensional circuits of superconstant 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 ChiNing Chou and Xun Gao},
title = {{Spoofing Linear CrossEntropy Benchmarking in Shallow Quantum Circuits}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {30:130:20},
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/13569},
URN = {urn:nbn:de:0030drops135699},
doi = {10.4230/LIPIcs.ITCS.2021.30},
annote = {Keywords: Quantum supremacy, Linear crossentropy benchmark}
}
Keywords: 

Quantum supremacy, Linear crossentropy benchmark 
Collection: 

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

2021 
Date of publication: 

04.02.2021 