Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.39448

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

Robert Koenig, Marco Tomamichel

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

Related papers

A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

Jon Nelson, Joel Rajakumar, Chao Yin +2 more

Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial state. Here we show that local accumulation of noise at a depth independent of system size is already sufficient. Specifically, we prove that any geometrically local circuit composed of unital operations and interspersed with single-qubit depolarizing noise of strength $p$ after $Θ(p^{-1} \log p^{-1})$ depth can be approximately sampled from a polynomial-time classical computer. This generalizes existing results that impose anticoncentration assumptions or non-universal gate sets in order to obtain a classical sampler at such shallow depths. Our proof maps the output state of the circuit to a polymer model in statistical mechanics, and combines a convergent cluster expansion with hypercontractivity of the depolarizing channel.

quant-pharXiv:2610.00548•Oct 2, 2026•0 citations

Verifiable quantum advantage in extremely low depth

Alexandru Gheorghiu

We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

quant-pharXiv:2609.01448•Sep 2, 2026•0 citations

Limitations of Noisy Geometrically Local Quantum Circuits

Jon Nelson, Joel Rajakumar, Michael J. Gullans

Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth $ω(p^{-1}\log n)$, and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on $n$ qubits, initialized in an arbitrary product state, with nearest-neighbor gates in $O(1)$ spatial dimensions and interspersed depolarizing noise of any constant strength $p$. Our first result is that when the depth exceeds a threshold $d^*=Θ(p^{-1}\log n)$, the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its $n$-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth $\tildeΘ(p^{-1})$: after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds $\tildeΘ(p^{-1})$.

arXiv:2510.06346•Oct 7, 2025•0 citations

Unconditional Quantum Advantage for Sampling with Shallow Circuits

Adam Bene Watts, Natalie Parham

Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded.We introduce a distribution D n over { 0 , 1 } n and construct a constant-depth uniform quantum circuit family { C n } n such that C n samples from a distribution close to D n in total variation distance. For any δ < 1 we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input k n + n δ i.i.d. Bernouli random variables with entropy 1 / k and produces output close to D n in total variation distance has depth Ω ( log ⁡ log ⁡ n ) . This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs.The distribution D n and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.

arXiv:2301.00995•Quantum•Aug 12, 2026•2 citations

Quantum Advantage with Noisy Shallow Circuits in 3D

Sergey B. Bravyi, David Gosset, Robert König +1 more

Prior work has shown that there exists a relation problem which can be solved with certainty by a constant-depth quantum circuit composed of geometrically local gates in two dimensions, but cannot be solved with high probability by any classical constant depth circuit composed of bounded fan-in gates. Here we provide two extensions of this result. Firstly, we show that a separation in computational power persists even when the constant-depth quantum circuit is restricted to geometrically local gates in one dimension. The corresponding quantum algorithm is the simplest we know of which achieves a quantum advantage of this type. Our second, main result, is that a separation persists even if the shallow quantum circuit is corrupted by noise. We construct a relation problem which can be solved with near certainty using a noisy constant-depth quantum circuit composed of geometrically local gates in three dimensions, provided the noise rate is below a certain constant threshold value. On the other hand, the problem cannot be solved with high probability by a noise-free classical circuit of constant depth. A key component of the proof is a quantum error-correcting code which admits constant-depth logical Clifford gates and single-shot logical state preparation. We show that the surface code meets these criteria.

Annual Symposium on Foundations of Computer Science•Nov 1, 2019•7 citations

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates

Jon Nelson, Joel Rajakumar, Dominik Hangleiter +1 more

We construct a polynomial-time classical algorithm that samples from the output distribution of noisy geometrically local Clifford circuits with any product-state input and single-qubit measurements in any basis. Our results apply to circuits with nearest-neighbor gates on an \(O(1)\text{-D}\) architecture with depolarizing noise after each gate. Importantly, we assume that the circuit does not contain qubit resets or mid-circuit measurements. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results can be extended to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, these results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class as long as the depth is above a constant threshold. This allows us to rule out the possibility of fault-tolerance in these circuit models. As a key technical step, we prove that interspersed noise causes a decay of long-range entanglement at depths beyond a critical threshold. To prove our results, we merge techniques from percolation theory and Pauli path analysis.

arXiv:2411.02535•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•1 citation
We consider quantum circuits consisting of ddd layers of nearest-neighbor two-qubit gates acting on nnn 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)log⁡log⁡(n/δ)2^{O(d)}\log\log(n/δ)2O(d)loglog(n/δ) and n2O(d)n 2^{O(d)}n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(log⁡n)O(\log n)O(logn). 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\mathsf{AC}^0AC0-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\mathsf{AC}^0AC0-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)Ω(\log n/\log\log n)Ω(logn/loglogn). 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.
Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial state. Here we show that local accumulation of noise at a depth independent of system size is already sufficient. Specifically, we prove that any geometrically local circuit composed of unital operations and interspersed with single-qubit depolarizing noise of strength ppp after Θ(p−1log⁡p−1)Θ(p^{-1} \log p^{-1})Θ(p−1logp−1) depth can be approximately sampled from a polynomial-time classical computer. This generalizes existing results that impose anticoncentration assumptions or non-universal gate sets in order to obtain a classical sampler at such shallow depths. Our proof maps the output state of the circuit to a polymer model in statistical mechanics, and combines a convergent cluster expansion with hypercontractivity of the depolarizing channel.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[log⁡log⁡]\mathsf{QNC}^0[\log\log]QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0\mathsf{QAC}^0QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth ω(p−1log⁡n)ω(p^{-1}\log n)ω(p−1logn), and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on nnn qubits, initialized in an arbitrary product state, with nearest-neighbor gates in O(1)O(1)O(1) spatial dimensions and interspersed depolarizing noise of any constant strength ppp. Our first result is that when the depth exceeds a threshold d∗=Θ(p−1log⁡n)d^*=Θ(p^{-1}\log n)d∗=Θ(p−1logn), the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its nnn-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth Θ~(p−1)\tildeΘ(p^{-1})Θ~(p−1): after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds Θ~(p−1)\tildeΘ(p^{-1})Θ~(p−1).
Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded.We introduce a distribution D n over { 0 , 1 } n and construct a constant-depth uniform quantum circuit family { C n } n such that C n samples from a distribution close to D n in total variation distance. For any δ < 1 we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input k n + n δ i.i.d. Bernouli random variables with entropy 1 / k and produces output close to D n in total variation distance has depth Ω ( log ⁡ log ⁡ n ) . This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs.The distribution D n and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.
Prior work has shown that there exists a relation problem which can be solved with certainty by a constant-depth quantum circuit composed of geometrically local gates in two dimensions, but cannot be solved with high probability by any classical constant depth circuit composed of bounded fan-in gates. Here we provide two extensions of this result. Firstly, we show that a separation in computational power persists even when the constant-depth quantum circuit is restricted to geometrically local gates in one dimension. The corresponding quantum algorithm is the simplest we know of which achieves a quantum advantage of this type. Our second, main result, is that a separation persists even if the shallow quantum circuit is corrupted by noise. We construct a relation problem which can be solved with near certainty using a noisy constant-depth quantum circuit composed of geometrically local gates in three dimensions, provided the noise rate is below a certain constant threshold value. On the other hand, the problem cannot be solved with high probability by a noise-free classical circuit of constant depth. A key component of the proof is a quantum error-correcting code which admits constant-depth logical Clifford gates and single-shot logical state preparation. We show that the surface code meets these criteria.
We construct a polynomial-time classical algorithm that samples from the output distribution of noisy geometrically local Clifford circuits with any product-state input and single-qubit measurements in any basis. Our results apply to circuits with nearest-neighbor gates on an O(1)-DO(1)\text{-D}O(1)-D architecture with depolarizing noise after each gate. Importantly, we assume that the circuit does not contain qubit resets or mid-circuit measurements. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results can be extended to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, these results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class as long as the depth is above a constant threshold. This allows us to rule out the possibility of fault-tolerance in these circuit models. As a key technical step, we prove that interspersed noise causes a decay of long-range entanglement at depths beyond a critical threshold. To prove our results, we merge techniques from percolation theory and Pauli path analysis.