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.MFCS.2020.83
URN: urn:nbn:de:0030-drops-127533
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12753/
Go to the corresponding LIPIcs Volume Portal

Takahashi, Yasuhiro ; Takeuchi, Yuki ; Tani, Seiichiro

Classically Simulating Quantum Circuits with Local Depolarizing Noise

pdf-format:
LIPIcs-MFCS-2020-83.pdf (0.6 MB)

Abstract

We study the effect of noise on the classical simulatability of quantum circuits defined by computationally tractable (CT) states and efficiently computable sparse (ECS) operations. Examples of such circuits, which we call CT-ECS circuits, are IQP, Clifford Magic, and conjugated Clifford circuits. This means that there exist various CT-ECS circuits such that their output probability distributions are anti-concentrated and not classically simulatable in the noise-free setting (under plausible assumptions). First, we consider a noise model where a depolarizing channel with an arbitrarily small constant rate is applied to each qubit at the end of computation. We show that, under this noise model, if an approximate value of the noise rate is known, any CT-ECS circuit with an anti-concentrated output probability distribution is classically simulatable. This indicates that the presence of small noise drastically affects the classical simulatability of CT-ECS circuits. Then, we consider an extension of the noise model where the noise rate can vary with each qubit, and provide a similar sufficient condition for classically simulating CT-ECS circuits with anti-concentrated output probability distributions.

BibTeX - Entry

@InProceedings{takahashi_et_al:LIPIcs:2020:12753,
  author =	{Yasuhiro Takahashi and Yuki Takeuchi and Seiichiro Tani},
  title =	{{Classically Simulating Quantum Circuits with Local Depolarizing Noise}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ΔΎ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12753},
  URN =		{urn:nbn:de:0030-drops-127533},
  doi =		{10.4230/LIPIcs.MFCS.2020.83},
  annote =	{Keywords: Classical Simulation, Quantum Circuit, Local Depolarizing Noise}
}

Keywords: Classical Simulation, Quantum Circuit, Local Depolarizing Noise
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

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