Researchers present a computational problem solvable with near-certainty by a constant-depth quantum circuit using only 3D-local operations, even in the presence of noise. No classical AC0 circuit smaller than a certain subexponential size can solve the same problem on a uniformly random instance. This result establishes the strongest known complexity-theoretic separation between classical and quantum computation that is experimentally observable without requiring full fault-tolerance, making it relevant for NISQ-era devices.
Questions this post answers
What is the strongest known complexity-theoretic separation between classical and quantum computation that can be demonstrated experimentally?
A constant-depth quantum circuit with 3D-local operations can solve a specific search problem with near-certainty even under noise, while every classical AC0 circuit (unbounded fan-in) smaller than a subexponential size fails with near-certainty on a uniformly random instance. This separation is notable because it does not rely on unproven hardness assumptions and does not require a universal fault-tolerant quantum computer. Quantum computing researchers tracking provable advantage results follow developments like this on daily.dev.