Recent progress in the development of quantum technologies has enabled the direct investigation of the dynamics of increasingly complex quantum many-body systems.This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage.Here, we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian.For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error.In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb-Robinson bound.Our results use cluster-expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence.This has important physical consequences besides our efficient algorithms.In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.
Recent progress in the development of quantum technologies has enabled the direct investigation of the dynamics of increasingly complex quantum many-body systems.This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage.Here, we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian.For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error.In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb-Robinson bound.Our results use cluster-expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence.This has important physical consequences besides our efficient algorithms.In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.
Simulating physical systems has been an important application of classical and quantum computers. In this article we present an efficient classical algorithm for simulating time-dependent quantum mechanical Hamiltonians over constant periods of time. The algorithm presented here computes the mean value of an observable over the output state of such short-time Hamiltonian evolutions. In proving the performance of this algorithm we use Lieb-Robinson type bounds to limit the evolution of local operators within a lightcone. This allows us to divide the task of simulating a large quantum system into smaller systems that can be handled on normal classical computers.
We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error ϵ using O(nTpolylog(nT/ϵ)) gates with depth O(Tpolylog(nT/ϵ)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/ϵ. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires Ω(nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb--Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.
The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian H and constant evolution time t, our method estimates expectation values of the form ⟨ψ∣eiHtOe−iHt∣ψ⟩ for global Pauli observables O and stabilizer states ∣ψ⟩, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.
We establish general conditions for the rapid convergence of propagation algorithms for computing expectation values of local observables in quantum many-body systems, covering both spin and fermionic systems. Our results apply to evolutions that are sufficiently contractive, providing a general mechanism by which contractivity controls the growth generated by local interactions and enables efficient classical simulation. As a first application, we consider noisy time evolution generated by local Hamiltonians on arbitrary interaction graphs. We show that the dynamics can be efficiently simulated when the noise strength λ is sufficiently large compared to the degree of the interaction graph. More generally, for systems with an interaction strength u, our bounds determine a time horizon tmax as a function of the interaction strength u, the noise strength λ, and the interaction structure below which the algorithm is efficient. In the noiseless limit, λ=0, our analysis extends the efficiently simulable time scale from log(1/u) proved in Facelli, Fawzi, and Fawzi (2026) to tmax∼1/u matching the recent improvement by Zhao, Marvian and Tong (2026). As a second application, we apply the same framework to the computation of local observables in Gibbs states of local Hamiltonians. We consider a pseudo-Lindbladian whose steady state is the Gibbs state and show that, at sufficiently high temperature, its propagation algorithm converges rapidly. In particular, for weakly-interacting systems with interaction strength u, our result applies up to inverse temperatures β∼log(1/u).
We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and encompasses all physically reasonable Hamiltonians. Our algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error ε using O(T polylog(nT/ε)) gates with depth O(T polylog(nT/ε)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/ε. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires (nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.
Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.