1 Search Results for "Gao, Xun"

Document

DOI: 10.4230/LIPIcs.ITCS.2021.30

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

Authors: Boaz Barak, Chi-Ning Chou, and Xun Gao

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

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.

Cite as

Boaz Barak, Chi-Ning Chou, and Xun Gao. Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.ITCS.2021.30,
  author =	{Barak, Boaz and Chou, Chi-Ning and Gao, Xun},
  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 =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.30},
  URN =		{urn:nbn:de:0030-drops-135699},
  doi =		{10.4230/LIPIcs.ITCS.2021.30},
  annote =	{Keywords: Quantum supremacy, Linear cross-entropy benchmark}
}

Refine by Author
1 Barak, Boaz
1 Chou, Chi-Ning
1 Gao, Xun

Refine by Classification
1 Theory of computation → Quantum complexity theory

Refine by Keyword
1 Linear cross-entropy benchmark
1 Quantum supremacy

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Gao, Xun"

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

Abstract

Cite as

Thanks for your feedback!

Could not send message