Characterizing Pauli propagation via operator complexity

Pauli-propagation simulation represents observables in the Pauli basis and evolves their coefficients in the Heisenberg picture. In this work, we bridge operator complexity and the resource cost of Pauli-propagation methods by proving that the truncation error is governed by the Operator Stabilizer Rényi entropy (OSE) $${{{\mathcal{S}}}}^{\alpha }(O)$$. Our bounds quantify how OSE controls the compressibility of the evolving operator and give explicit prescriptions for the Top-K budget required to achieve a target accuracy. As an analytic test case, we prove that for the 1D Heisenberg model at Jz = 0, the number of non-zero Pauli coefficients generated from a local operator grows at most quadratically with the number of Trotter steps. We then benchmark the Top-K Pauli propagation on XXZ Heisenberg chains. The numerical results show high accuracy with a small truncation number K in the free regime (Jz = 0) and competitive performance against tensor-network methods, such as TDVP, in the interacting case (Jz = 0.5). These results position OSE as a resource measure for Pauli-propagation methods. Classical simulations of quantum dynamics are often limited by rapidly growing entanglement, motivating observable-based methods. Here, the authors show that operator stabilizer entropy gives a priori error bounds for Pauli propagation and determines the Pauli-term budget needed to reach a target accuracy.