We analyze the complexity of classically simulating continuous-time dynamics of locally interacting quantum spin systems with a constant rate of entanglement breaking noise. We prove that a polynomial time classical algorithm can be used to sample from the state of the spins when the rate of noise is higher than a threshold determined by the strength of the local interactions. Furthermore, by encoding a 1D fault tolerant quantum computation into the dynamics of spin systems arranged on two or higher dimensional grids, we show that for several noise channels, the problem of weakly simulating the output state of both purely Hamiltonian and purely dissipative dynamics is expected to be hard in the low-noise regime.
We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable
A at time
t. By analyzing the convergence of the perturbative expansion in the interaction strength
λ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime
λ∣t∣2D+1=O(1), when the Hamiltonian is geometrically local on a
D-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to
λ∣t∣=O(1) with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to
λ∣t∣=O(1), modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.