Unconditional quantum advantage with noisy planar architectures
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.
Related
- Comment on J.Qin et al., Unconditional and Robust Quantum Metrological Advantage beyond N00N States, PRL 130, 070801 (2023) and J.A. H. Nielsen et.al., Deterministic Quantum Phase Estimation beyond N00N States. PRL 130, 123603 (2023)
- Unconditional quantum advantage from a two-round CHSH problem in one dimension
- Unconditional Quantum PAC Learning Advantage in the Large Error Regime
- Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
- Fault-Tolerant Logical Operations and Efficient State Preparation in Modular Quantum Architectures with Noisy Interfaces
BibTeX
@misc{caha2026unconditional,
title = {{Unconditional quantum advantage with noisy planar architectures}},
author = {Libor Caha and Robert Koenig and Louis Paletta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40050},
eprint = {2609.40050},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40050},
}
RIS
TY - UNPB
TI - Unconditional quantum advantage with noisy planar architectures
AU - Libor Caha
AU - Robert Koenig
AU - Louis Paletta
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40050
UR - https://arxiv.org/abs/2609.40050
AB - 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.
ER -