  Noise in quantum operations often negates the advantage of quantum
computation. However, most classical simulations of quantum computers calculate
the ideal probability amplitudes either storing full state vectors or using
sophisticated tensor network contractions. Here, we investigate sampling-based
classical simulation methods for noisy quantum circuits. Specifically, we
characterize the simulation costs of two major schemes, stabilizer-state
sampling of magic states and Heisenberg propagation, for quantum circuits being
subject to stochastic Pauli noise, such as depolarizing and dephasing noise. To
this end, we introduce several techniques for the stabilizer-state sampling to
reduce the simulation costs under such noise. It revealed that in the low noise
regime, stabilizer-state sampling results in a smaller sampling cost, while
Heisenberg propagation is better in the high noise regime. Furthermore, for a
high depolarizing noise rate $\sim 10\%$, these methods provide better scaling
compared to that given by the low-rank stabilizer decomposition. We believe
that these knowledge of classical simulation costs is useful to squeeze
possible quantum advantage on near-term noisy quantum devices as well as
efficient classical simulation methods.

Quantum Physics