Noise-induced shallow circuits and absence of barren plateaus Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck França, and Yihui Quek We study the impact of uncorrected noise on quantum circuits, showing that any noise 'truncates' most quantum circuits to effectively logarithmic depth for computing Pauli expectation values. We prove that quantum circuits under non-unital noise exhibit no barren plateaus for cost functions composed of local observables. By leveraging the effective shallowness, we design a classical algorithm to estimate Pauli expectation values within inverse-polynomial additive error with high probability. The algorithm's runtime is independent of circuit depth and operates in polynomial time for one-dimensional architectures and quasi-polynomial time for higher-dimensional ones. Our results show that, unless circuits are carefully engineered to take advantage of noise, noisy quantum circuits are unlikely to be preferable over shallow circuits for algorithms that output Pauli expectation value estimates. We also show that most quantum circuits with non-unital noise behave qualitatively as noisy shallow circuits for estimating Pauli expectation values. Beyond this task, we establish that the majority of noisy quantum circuits become independent of initial states. Our results highlight the importance of noise in near-term quantum computation and show that non-unital noise can lead to different conclusions than unital noise. We also show that most quantum circuits with non-unital noise behave like shallow circuits for computing Pauli expectation values. Our results provide insights into the complexity of sampling from noisy random circuits.Noise-induced shallow circuits and absence of barren plateaus Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck França, and Yihui Quek We study the impact of uncorrected noise on quantum circuits, showing that any noise 'truncates' most quantum circuits to effectively logarithmic depth for computing Pauli expectation values. We prove that quantum circuits under non-unital noise exhibit no barren plateaus for cost functions composed of local observables. By leveraging the effective shallowness, we design a classical algorithm to estimate Pauli expectation values within inverse-polynomial additive error with high probability. The algorithm's runtime is independent of circuit depth and operates in polynomial time for one-dimensional architectures and quasi-polynomial time for higher-dimensional ones. Our results show that, unless circuits are carefully engineered to take advantage of noise, noisy quantum circuits are unlikely to be preferable over shallow circuits for algorithms that output Pauli expectation value estimates. We also show that most quantum circuits with non-unital noise behave qualitatively as noisy shallow circuits for estimating Pauli expectation values. Beyond this task, we establish that the majority of noisy quantum circuits become independent of initial states. Our results highlight the importance of noise in near-term quantum computation and show that non-unital noise can lead to different conclusions than unital noise. We also show that most quantum circuits with non-unital noise behave like shallow circuits for computing Pauli expectation values. Our results provide insights into the complexity of sampling from noisy random circuits.