License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.74
URN: urn:nbn:de:0030-drops-155076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15507/
Go to the corresponding LIPIcs Volume Portal

Hasegawa, Atsuya ; Le Gall, François

Quantum Advantage with Shallow Circuits Under Arbitrary Corruption

pdf-format:
LIPIcs-ISAAC-2021-74.pdf (1 MB)

Abstract

Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, König and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise.
In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits.
In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.

BibTeX - Entry

@InProceedings{hasegawa_et_al:LIPIcs.ISAAC.2021.74,
  author =	{Hasegawa, Atsuya and Le Gall, Fran\c{c}ois},
  title =	{{Quantum Advantage with Shallow Circuits Under Arbitrary Corruption}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{74:1--74:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15507},
  URN =		{urn:nbn:de:0030-drops-155076},
  doi =		{10.4230/LIPIcs.ISAAC.2021.74},
  annote =	{Keywords: Quantum computing, circuit complexity, constant-depth circuits}
}

Keywords: Quantum computing, circuit complexity, constant-depth circuits
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI