  We show that several quantum circuit families can be simulated efficiently
classically if it is promised that their output distribution is approximately
sparse i.e. the distribution is close to one where only a polynomially small, a
priori unknown subset of the measurement probabilities are nonzero. Classical
simulations are thereby obtained for quantum circuits which---without the
additional sparsity promise---are considered hard to simulate. Our results
apply in particular to a family of Fourier sampling circuits (which have
structural similarities to Shor's factoring algorithm) but also to several
other circuit families, such as IQP circuits. Our results provide examples of
quantum circuits that cannot achieve exponential speed-ups due to the presence
of too much destructive interference i.e. too many cancelations of amplitudes.
The crux of our classical simulation is an efficient algorithm for
approximating the significant Fourier coefficients of a class of states called
computationally tractable states. The latter result may have applications
beyond the scope of this work. In the proof we employ and extend sparse
approximation techniques, in particular the Kushilevitz-Mansour algorithm, in
combination with probabilistic simulation methods for quantum circuits.
