Document

**Published in:** LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

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.

Yasuhiro Takahashi, Yuki Takeuchi, and Seiichiro Tani. Classically Simulating Quantum Circuits with Local Depolarizing Noise. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.MFCS.2020.83, author = {Takahashi, Yasuhiro and Takeuchi, Yuki and Tani, Seiichiro}, 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 = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.83}, URN = {urn:nbn:de:0030-drops-127533}, doi = {10.4230/LIPIcs.MFCS.2020.83}, annote = {Keywords: Classical Simulation, Quantum Circuit, Local Depolarizing Noise} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

We study the computational power of shallow quantum circuits
with O(log n) initialized and n^{O(1)} uninitialized ancillary
qubits, where n is the input length and the initial state of
the uninitialized ancillary qubits is arbitrary. First, we show
that such a circuit can compute any symmetric function on n bits
that is classically computable in polynomial time. Then, we
regard such a circuit as an oracle and show that a
polynomial-time classical algorithm with the oracle can estimate
the elements of any unitary matrix corresponding to a
constant-depth quantum circuit on n qubits. Since it seems unlikely
that these tasks can be done with only O(log n) initialized
ancillary qubits, our results give evidences that adding
uninitialized ancillary qubits increases the computational power
of shallow quantum circuits with only O(log n) initialized
ancillary qubits. Lastly, to understand the limitations of
uninitialized ancillary qubits, we focus on
near-logarithmic-depth quantum circuits with them and show
the impossibility of computing the parity function on n bits.

Yasuhiro Takahashi and Seiichiro Tani. Power of Uninitialized Qubits in Shallow Quantum Circuits. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 57:1-57:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.STACS.2018.57, author = {Takahashi, Yasuhiro and Tani, Seiichiro}, title = {{Power of Uninitialized Qubits in Shallow Quantum Circuits}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {57:1--57:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.57}, URN = {urn:nbn:de:0030-drops-84907}, doi = {10.4230/LIPIcs.STACS.2018.57}, annote = {Keywords: quantum circuit complexity, shallow quantum circuit, uninitialized qubit} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail