Noise-induced Simulability Transition from Operator Scrambling

The complexity of simulating quantum many-body dynamics, or quantum computations, in the Heisenberg picture is governed by the scrambling of initially simple operators into superpositions of exponentially many Pauli strings. The corresponding expansion coefficients define the Pauli spectrum, whose structure controls the performance of classical algorithms based on truncating Pauli expansions. Here we determine the finite-depth Pauli spectrum of random quantum circuits, both in the noiseless case and in the presence of local noise, through its moments, given by the operator stabilizer Rényi entropies. In noiseless circuits, we uncover a hierarchy in the approach to the fully scrambled regime: low moments equilibrate at relatively short depths, while higher moments, which are sensitive to rare, large-amplitude Pauli coefficients, require parametrically larger depths. In noisy circuits, scrambling competes with an effective suppression of operator spreading. Above a critical error per cycle γ_c N=mathcal{O}(1), the operator fails to reach the fully scrambled distribution and remains supported on an atypically sparse subset of Pauli strings. Conversely, below this scale, we rigorously show that classical simulation remains exponentially hard, demonstrating that finite noise does not automatically imply classical simulability. The resulting noise-induced transition in operator complexity therefore delineates the boundary between intrinsically hard quantum dynamics and those that remain classically accessible.