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

3D-local noisy shallow quantum circuits outperform classical AC 0 circuits on certain problems, demonstrating a strong complexity separation despite noise and locality constraints.

• Why it matters: Proving quantum advantage remains challenging due to reliance on unproven assumptions or the need for fault-tolerant, scalable quantum computers. Establishing practical, experimentally observable differences is crucial for validating quantum supremacy.
• What they did: The authors designed a computational problem solvable with near-certainty by a 3D-local, noisy, constant-depth quantum circuit, while classical AC 0 circuits of similar size fail with high probability on random instances.
• The result: This work provides a fault-tolerant, experimentally feasible demonstration of quantum computational superiority, highlighting the robustness of quantum advantage even under realistic noise and locality conditions.