Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits

Nolan J. Coble, Matthew Coudron

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit $C$ acting on $n$ qubits, and any bit string $x\in \{0,1{\}}^n$, can compu…