  Understanding the boundary between classical simulatability and the power of
quantum computation is a fascinating topic. Direct simulation of noisy quantum
computation requires solving an open quantum many-body system, which is very
costly. Here, we develop a tensor network formalism to simulate the
time-dynamics and the Fourier spectrum of noisy quantum circuits. We prove that
under general conditions most of the quantum circuits at any constant level of
noise per gate can be efficiently simulated classically with the cost
increasing only polynomially with the size of the circuits. The result holds
even if we have perfect noiseless quantum gates for some subsets of operations,
such as all the gates in the Clifford group. This surprising result reveals the
subtle relations between classical simulatability, quantum supremacy, and
fault-tolerant quantum computation. The developed simulation tools may also be
useful for solving other open quantum many-body systems.
