  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}$.
