2026-07-21T20:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13569 2024-03-06T10:52:20Z ddc:004 open_access

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits Barak, Boaz Chou, Chi-Ning Gao, Xun Quantum supremacy Linear cross-entropy benchmark 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boaz Barak and Chi-Ning Chou and Xun Gao 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.30 urn:nbn:de:0030-drops-135699 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.30 eng https://creativecommons.org/licenses/by/3.0/legalcode