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.
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 2D-local quantum circuits under local stochastic Pauli noise below a constant threshold pth>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(n1/(αD)) for a constant α>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 AC0 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 nq qubits of depth d becomes one using nqdpoly(log(nqd)) qubits. Classical decoding is absorbed into the output relation. The key hardness-preservation argument bounds each decoded bit’s dependencies by d2poly(log(nqd)), allowing decoding by constant-depth classical circuits of quasipolynomial size when d is constant.
The separation concerns relation problems and AC0, 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.
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 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 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 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 2O(d)loglog(n/δ) and n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime 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-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-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 Ω(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) can solve with near certainty (probability 1−o(1)), but that any bounded fan-in constant-depth classical circuit (NC0) 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 circuits and AC0[p] circuits for all primes p≥2, and a conditional separation between noisy QNC0 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 ⊕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.