Quantum advantage with noisy shallow circuits in 3D

Understand

Prior work has shown that there exists a relation problem which can be solved with certainty by a constant-depth quantum circuit composed of geometrically local gates in two dimensions, but cannot be solved with high probability by any classical constant depth circuit composed of bounded fan-in gates.

• Here we provide two extensions of this result.
• Firstly, we show that a separation in computational power persists even when the constant-depth quantum circuit is restricted to geometrically local gates in one dimension.
• The corresponding quantum algorithm is the simplest we know of which achieves a quantum advantage of this type.