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

Nature Communications

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

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

Published Aug 11, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1038/s41467-026-76560-x

Related papers

Unconditional quantum advantage with noisy planar architectures

Libor Caha, Robert Koenig, Louis Paletta

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.

quant-pharXiv:2609.40050•Oct 1, 2026•0 citations

A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits

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

We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.

arXiv:2312.09209•Dec 14, 2023•1 citation

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

Worst-case depth hierarchy for shallow quantum circuits

Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1 more

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

quant-pharXiv:2606.16425•Jun 16, 2026•0 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•1 citation

Quantum Advantage with Shallow Circuits Under Arbitrary Corruption.

Atsuya Hasegawa, François Le Gall

Recent works by Bravyi, Gosset and Konig (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, Konig and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. We prove that this quantum advantage persists even if the quantum circuits can be subject to arbitrary corruption: in this paper we assume that any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We show that even in this model, quantum circuits can still solve in constant depth computational problems that require logarithmic depth to solve 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.

•Jan 1, 2021•0 citations
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.
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.
We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.
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.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for QNC0\mathsf{QNC}^0QNC0. For each d≥12d\ge 12d≥12, we construct a family of two-round interactive problems on which no depth-(d−1)(d-1)(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than ddd by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every ddd, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0\mathsf{QNC}^0QNC0 over NC0\mathsf{NC}^0NC0. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within QNC0\mathsf{QNC}^0QNC0, establishing a genuinely quantum hierarchy.
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 Konig (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, Konig and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. We prove that this quantum advantage persists even if the quantum circuits can be subject to arbitrary corruption: in this paper we assume that any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We show that even in this model, quantum circuits can still solve in constant depth computational problems that require logarithmic depth to solve 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.