Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
Abstract
We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2O(d)loglog(n/δ) and n 2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(log n). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(log n/loglog n). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
Related
- Experimentally Testable Quantum Advantage in Shallow Circuits
- Classical Pre-Training of Large Shallow Parametrized Quantum Circuits through Pauli Propagation and deployment on Quantum Hardware
- Quantum simulation of classical RCL circuits via complexification and Schrödingerization
- Shallow data-loading circuits for multivariable functions
- Correlations decide a shallow-circuit advantage
BibTeX
@misc{koenig2026parallel,
title = {{Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D}},
author = {Robert Koenig and Marco Tomamichel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39448},
eprint = {2609.39448},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39448},
}
RIS
TY - UNPB
TI - Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
AU - Robert Koenig
AU - Marco Tomamichel
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39448
UR - https://arxiv.org/abs/2609.39448
AB - We consider quantum circuits consisting of d layers of nearest-neighbor two-qubit gates acting on n qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δ, with parallel runtime 2^O(d)loglog(n/δ) and n 2^O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(log n). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC^0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC^0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(log n/loglog n). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
ER -