A polynomial-time classical algorithm for noisy quantum circuits is presented, which computes the expectation value of any observable for any noisy quantum circuit with a small average error over input states drawn from an ensemble. The algorithm leverages the intuition that noise exponentially damps non-local correlations, enabling classical simulation by tracking local quantum information. It also allows sampling from the output distribution of a circuit in quasi-polynomial time if the distribution anti-concentrates. The algorithm is applicable to both uniform and gate-based noise models, with different runtime complexities depending on the observable and noise model. For circuits with uniform noise, the algorithm runs in polynomial time for certain observables, while for gate-based noise, it runs in quasi-polynomial time. The results have implications for quantum error mitigation, showing that efficient error mitigation strategies can only apply to circuits that are classically simulable. The algorithm is also applicable to sampling from noisy quantum circuits, with quasi-polynomial time complexity under anti-concentration conditions. The results demonstrate that noisy quantum circuits without error correction can be efficiently classically simulated, highlighting the importance of quantum error correction for achieving a scalable quantum advantage. The algorithm is extended to handle non-unital noise models and highly mixed input states, showing that such circuits can be classically simulated under certain conditions. The work provides a rigorous foundation for understanding the computational power of noisy quantum circuits and has implications for near-term quantum experiments.A polynomial-time classical algorithm for noisy quantum circuits is presented, which computes the expectation value of any observable for any noisy quantum circuit with a small average error over input states drawn from an ensemble. The algorithm leverages the intuition that noise exponentially damps non-local correlations, enabling classical simulation by tracking local quantum information. It also allows sampling from the output distribution of a circuit in quasi-polynomial time if the distribution anti-concentrates. The algorithm is applicable to both uniform and gate-based noise models, with different runtime complexities depending on the observable and noise model. For circuits with uniform noise, the algorithm runs in polynomial time for certain observables, while for gate-based noise, it runs in quasi-polynomial time. The results have implications for quantum error mitigation, showing that efficient error mitigation strategies can only apply to circuits that are classically simulable. The algorithm is also applicable to sampling from noisy quantum circuits, with quasi-polynomial time complexity under anti-concentration conditions. The results demonstrate that noisy quantum circuits without error correction can be efficiently classically simulated, highlighting the importance of quantum error correction for achieving a scalable quantum advantage. The algorithm is extended to handle non-unital noise models and highly mixed input states, showing that such circuits can be classically simulated under certain conditions. The work provides a rigorous foundation for understanding the computational power of noisy quantum circuits and has implications for near-term quantum experiments.