A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits

Libor Caha, Xavier Coiteux-Roy, Robert Koenig

We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighb…