Classical simulation of peaked shallow quantum circuits

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime n^{O\(log{n}\)} that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime n^O(1) if D=2 and almost-polynomial runtime n^{O\(log{log{n}}\)} for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in sqrt{n}.