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

Area of Science:

• Quantum computation
• Computational complexity theory
• Quantum information science

Background:

• Quantum computers promise greater power than classical computers, but experimental proof is lacking.
• Existing quantum computing schemes often require fault-tolerant systems or rely on unproven assumptions.
• Restricted models of computation are being explored to demonstrate quantum advantage.
• Constant-depth quantum circuits show superiority over classical AC^0 circuits.

Purpose of the Study:

• To investigate if quantum advantage persists in noisy environments and under locality constraints.
• To propose a computational problem solvable by constant-depth, local 3D quantum circuits despite noise.
• To establish a strong complexity-theoretic separation between classical and quantum computation.

Main Methods:

• Development of a specific computational problem.
• Utilizing constant-depth quantum circuits with local operations in 3D.
• Analysis of circuit performance under noisy conditions.
• Comparison with classical AC^0 circuits of comparable size.

Main Results:

• A proposed problem is solved with near-certainty by a noisy, constant-depth, local 3D quantum circuit.
• Classical AC^0 circuits of subexponential size fail with near-certainty on the same problem.
• Demonstration of a significant complexity-theoretic gap between classical and quantum computation.

Conclusions:

• Constant-depth quantum circuits with local operations exhibit noise resilience.
• This work provides a practical proposal for experimentally observing a strong quantum advantage.
• The findings highlight the potential of restricted quantum computation models.