{"id":"arxiv/2609.39448","url":"https://arxiv.org/abs/2609.39448","tags":["quant-ph"],"score":0,"title":"Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D","domain":"quant-ph","source":"arxiv","authors":["Robert Koenig","Marco Tomamichel"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}