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

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 ( <math xmlns="http://www.w3.org/1998/Math/MathML"> <msup><mrow><mi>AC</mi></mrow> <mrow><mn>0</mn></mrow> </msup> </math> -)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 <math xmlns="http://www.w3.org/1998/Math/MathML"> <msup><mrow><mi>AC</mi></mrow> <mrow><mn>0</mn></mrow> </msup> </math> -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.