arXiv:2609.39448
Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
Robert Koenig, Marco Tomamichel
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 $2^{O(d)}\log\log(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 $\mathsf{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 $\mathsf{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/\log\log 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.
AI Summary
The paper asks whether noise-robust, unconditional shallow-circuit quantum depth advantages can occur with nearest-neighbor gates on a one-dimensional line. It considers depth-$d$ brickwork circuits on $n$ qubits, initialized in computational-basis product states, with independent single-qubit depolarization of constant strength $p$ before every layer. A randomized classical sampler approximates the output distribution within total variation distance $\delta$, using $n2^{O(d)}$ real-arithmetic operations and parallel runtime $2^{O(d)}[d\log(1/p)+\log\log(n/\delta)]$. For constant depth and noise, finite-precision Boolean implementations have bounded-fan-in depth $O((\log\log n)^2)$ and size $O(n(\log n)^4)$, or unbounded-fan-in depth $O(\log\log n)$ and size $O(n^2(\log n)^4)$. Precomputed local sampling tables yield randomized $\mathsf{AC}^0$ simulation of polynomial size, with depth at most 10. Consequently, noisy constant-depth 1D circuits cannot give a superconstant depth separation from polynomial-size randomized classical circuits with unbounded-fan-in AND/OR/NOT gates for relation problems. The proof represents each noisy two-qubit gate as a mixture containing a product-unitary “cut” branch. Complete cuts across bonds occur independently with probability $p^d$, leaving components of width $O(p^{-d}\log(n/\delta))$ with high probability. Independent samples on overlapping fixed intervals are assembled componentwise; exact local sampling uses coarse-graining to bilayer circuits and balanced-tree resampling. Without noise, this also gives an exact sampler with runtime $2^{O(d)}\log n$. The model excludes intermediate measurements, feedforward, resets, and fresh ancillas. The constant-depth classical construction has polynomial degree $O(dp^{-d})$, so the asymptotic result does not establish practical speed comparisons. Optimality of the noisy arithmetic-runtime bound remains open.
The translation of the main algorithm from the arithmetic model to Boolean circuits, together with the corresponding analysis in Appendices~\ref{app:boolean-implementation} and~\ref{app:lookup-tables}, was carried out primarily by AI through several iterations of prompting by the authors.
Error found: The abstract omits the depth-dependent factor in the noiseless sampler’s runtime: the proved bound is O(poly(2^d) log n), which simplifies to O(log n) only for constant d.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.