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.40050

Unconditional quantum advantage with noisy planar architectures

Libor Caha, Robert Koenig, Louis Paletta

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

Abstract

We consider quantum devices restricted to local operations in 2D and subject to local stochastic noise below a constant threshold. We show that such circuits are computationally more powerful than AC0-circuits, i.e., noise-free, geometrically-unconstrained constant-depth classical circuits with unbounded fan-in AND, OR and NOT gates. To this end, we exhibit a computational problem with the following properties: (i) Any instance of the problem is correctly solved with high probability by a certain geometrically 2D-local quantum circuit even if the latter is imperfectly implemented, but (ii) any polynomial-size AC0-circuit fails to solve certain instances of the problem with constant probability. To our knowledge, this isthe first complexity-theoretic separation which applies to planar quantum devices, incorporates noise-resilience and is unconditional, i.e., does not rely on complexity-theoretic assumptions. This brings the experimental demonstration of an unconditional quantum advantage closer to experimental realities.

AI Summary

Can constant-depth quantum circuits retain an unconditional computational advantage under both planar nearest-neighbor connectivity and noise? This paper constructs a relation problem solvable by uniform, polynomial-size, constant-depth $2D$-local quantum circuits under local stochastic Pauli noise below a constant threshold $p_{\rm th}>0$. Quantum success is at least $2/3$, while any depth-$D$ classical circuit with unbounded-fan-in AND/OR and NOT gates achieving average success at least $1/3$ requires size $\exp(n^{1/(\alpha D)})$ for a constant $\alpha>0$. The noise model permits correlations subject to exponentially decaying error-weight probabilities. The construction starts from an existing $1D$-local constant-depth Clifford circuit for a gate-teleportation relation with an $\mathrm{AC}^0$ lower bound. Concatenated Steane-code fault tolerance and gate teleportation compile it into a nonadaptive, constant-depth planar circuit, unfolding time into a second spatial dimension. An ideal circuit on $n_q$ qubits of depth $d$ becomes one using $n_qd\,\mathrm{poly}(\log(n_qd))$ qubits. Classical decoding is absorbed into the output relation. The key hardness-preservation argument bounds each decoded bit’s dependencies by $d^2\mathrm{poly}(\log(n_qd))$, allowing decoding by constant-depth classical circuits of quasipolynomial size when $d$ is constant. The separation concerns relation problems and $\mathrm{AC}^0$, not polynomial-time classical computation; the quantum circuits are Clifford circuits. Correctness is efficiently verifiable, but no numerical noise threshold or concrete experimental resource estimate is supplied. The discussion notes that fault-tolerant unconditional sampling advantages remain open, and cites concurrent work excluding analogous noisy shallow advantages in $1D$.

Little sign of AI-generated textAI use disclosed
Claude Fable 5 (Anthropic), GPT-5.6 Sol and GPT-6 Astra (OpenAI) were used in the writing process.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
6 pages, 2 figures

Related papers

3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits

Libor Caha, Xavier Coiteux-Roy, Robert König

Abstract Although quantum computers are believed to be more powerful than classical ones, a convincing experimental demonstration of this fact remains elusive. Proposed schemes either rely on unproven complexity-theoretic hardness assumptions, and/or require universal, fault-tolerant scalable quantum computers to implement. This has motivated the study of restricted models of computation. Constant-depth quantum circuits are known to be more powerful than unbounded fan-in classical ( $${{\mathsf{AC}}}^{0}$$ AC 0 -)circuits. Here we ask if this advantage persists in the presence of noise and under locality constraints. We present a computational problem for which every instance can be solved with near-certainty, despite noise, by a constant-depth quantum circuit with local operations in 3D. In contrast, every $${{\mathsf{AC}}}^{0}$$ AC 0 -circuit of size smaller than a certain (sub)exponential fails with near-certainty on a uniformly random instance. This constitutes a proposal with built-in fault-tolerance to experimentally observe the strongest known complexity-theoretic separation between classical and quantum computation.

arXiv:2312.09209•Nature Communications•Aug 11, 2026•13 citations

Unconditional advantage of noisy qudit quantum circuits over biased threshold circuits in constant depth

Michael de Oliveira, Sathyawageeswar Subramanian, Leandro Raffhael da Silva Mendes +1 more

The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, however, rely on computational assumptions and face verification challenges. Furthermore, steady advances in classical algorithms and machine learning make the issue of provable, practically demonstrable quantum advantage a moving target. In this work, we unconditionally demonstrate that parallel quantum computation can exhibit greater computational power than previously recognized. We prove that polynomial-size biased threshold circuits of constant depth-which model neural networks with tunable expressivity-fail to solve certain problems solvable by small constant-depth quantum circuits with local gates, for values of the bias that allow quantifiably large computational power. Additionally, we identify a family of problems that are solvable in constant depth by a universal quantum computer over prime-dimensional qudits with bounded connectivity, but remain hard for polynomial-size biased threshold circuits. We thereby bridge the foundational theory of non-local games in higher dimensions with computational advantage on emerging devices operating on a wide range of physical platforms. Finally, we show that these quantum advantages are robust to noise across all prime qudit dimensions with all-to-all connectivity, enhancing their practical appeal.

arXiv:2408.16378•Nature Communications•Apr 14, 2025•9 citations

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

Robert Koenig, Marco Tomamichel

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.

quant-pharXiv:2609.39448•Oct 1, 2026•0 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

Interactive quantum advantage with noisy, shallow Clifford circuits

Daniel Grier, Nathan Ju, Luke Schaeffer

Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC$^0$) can solve with near certainty (probability $1 - o(1)$), but that any bounded fan-in constant-depth classical circuit (NC$^0$) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC$^0$ circuits and AC$^0[p]$ circuits for all primes $p \geq 2$, and a conditional separation between noisy QNC$^0$ circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks -- that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err with constant probability over a uniformly random input. We show that is true even for quantum tasks which are $\oplus$L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography.

arXiv:2102.06833•Feb 13, 2021•15 citations

Quantum Advantage with Shallow Circuits Under Arbitrary Corruption

Atsuya Hasegawa, François Le Gall

Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, König and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.

arXiv:2105.00603•Leibniz international proceedings in informatics•Jan 1, 2021•5 citations
We consider quantum devices restricted to local operations in 2D and subject to local stochastic noise below a constant threshold. We show that such circuits are computationally more powerful than AC0-circuits, i.e., noise-free, geometrically-unconstrained constant-depth classical circuits with unbounded fan-in AND, OR and NOT gates. To this end, we exhibit a computational problem with the following properties: (i) Any instance of the problem is correctly solved with high probability by a certain geometrically 2D-local quantum circuit even if the latter is imperfectly implemented, but (ii) any polynomial-size AC0-circuit fails to solve certain instances of the problem with constant probability. To our knowledge, this isthe first complexity-theoretic separation which applies to planar quantum devices, incorporates noise-resilience and is unconditional, i.e., does not rely on complexity-theoretic assumptions. This brings the experimental demonstration of an unconditional quantum advantage closer to experimental realities.
Can constant-depth quantum circuits retain an unconditional computational advantage under both planar nearest-neighbor connectivity and noise? This paper constructs a relation problem solvable by uniform, polynomial-size, constant-depth 2D2D2D-local quantum circuits under local stochastic Pauli noise below a constant threshold pth>0p_{\rm th}>0pth​>0. Quantum success is at least 2/32/32/3, while any depth-DDD classical circuit with unbounded-fan-in AND/OR and NOT gates achieving average success at least 1/31/31/3 requires size exp⁡(n1/(αD))\exp(n^{1/(\alpha D)})exp(n1/(αD)) for a constant α>0\alpha>0α>0. The noise model permits correlations subject to exponentially decaying error-weight probabilities.
The construction starts from an existing 1D1D1D-local constant-depth Clifford circuit for a gate-teleportation relation with an AC0\mathrm{AC}^0AC0 lower bound. Concatenated Steane-code fault tolerance and gate teleportation compile it into a nonadaptive, constant-depth planar circuit, unfolding time into a second spatial dimension. An ideal circuit on nqn_qnq​ qubits of depth ddd becomes one using nqd poly(log⁡(nqd))n_qd\,\mathrm{poly}(\log(n_qd))nq​dpoly(log(nq​d)) qubits. Classical decoding is absorbed into the output relation. The key hardness-preservation argument bounds each decoded bit’s dependencies by d2poly(log⁡(nqd))d^2\mathrm{poly}(\log(n_qd))d2poly(log(nq​d)), allowing decoding by constant-depth classical circuits of quasipolynomial size when ddd is constant.
The separation concerns relation problems and AC0\mathrm{AC}^0AC0, not polynomial-time classical computation; the quantum circuits are Clifford circuits. Correctness is efficiently verifiable, but no numerical noise threshold or concrete experimental resource estimate is supplied. The discussion notes that fault-tolerant unconditional sampling advantages remain open, and cites concurrent work excluding analogous noisy shallow advantages in 1D1D1D.
Abstract Although quantum computers are believed to be more powerful than classical ones, a convincing experimental demonstration of this fact remains elusive. Proposed schemes either rely on unproven complexity-theoretic hardness assumptions, and/or require universal, fault-tolerant scalable quantum computers to implement. This has motivated the study of restricted models of computation. Constant-depth quantum circuits are known to be more powerful than unbounded fan-in classical ( AC0{{\mathsf{AC}}}^{0}AC0 AC 0 -)circuits. Here we ask if this advantage persists in the presence of noise and under locality constraints. We present a computational problem for which every instance can be solved with near-certainty, despite noise, by a constant-depth quantum circuit with local operations in 3D. In contrast, every AC0{{\mathsf{AC}}}^{0}AC0 AC 0 -circuit of size smaller than a certain (sub)exponential fails with near-certainty on a uniformly random instance. This constitutes a proposal with built-in fault-tolerance to experimentally observe the strongest known complexity-theoretic separation between classical and quantum computation.
The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, however, rely on computational assumptions and face verification challenges. Furthermore, steady advances in classical algorithms and machine learning make the issue of provable, practically demonstrable quantum advantage a moving target. In this work, we unconditionally demonstrate that parallel quantum computation can exhibit greater computational power than previously recognized. We prove that polynomial-size biased threshold circuits of constant depth-which model neural networks with tunable expressivity-fail to solve certain problems solvable by small constant-depth quantum circuits with local gates, for values of the bias that allow quantifiably large computational power. Additionally, we identify a family of problems that are solvable in constant depth by a universal quantum computer over prime-dimensional qudits with bounded connectivity, but remain hard for polynomial-size biased threshold circuits. We thereby bridge the foundational theory of non-local games in higher dimensions with computational advantage on emerging devices operating on a wide range of physical platforms. Finally, we show that these quantum advantages are robust to noise across all prime qudit dimensions with all-to-all connectivity, enhancing their practical appeal.
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.
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.
Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC0^00) can solve with near certainty (probability 1−o(1)1 - o(1)1−o(1)), but that any bounded fan-in constant-depth classical circuit (NC0^00) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC0^00 circuits and AC0[p]^0[p]0[p] circuits for all primes p≥2p \geq 2p≥2, and a conditional separation between noisy QNC0^00 circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks -- that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err with constant probability over a uniformly random input. We show that is true even for quantum tasks which are ⊕\oplus⊕L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography.
Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, König and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.