Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1111.4210 · Physical Review Letters

Quasilocality and Efficient Simulation of Markovian Quantum Dynamics

Thomas Barthel, Martin Kliesch

Published Jun 5, 2012• 80 citations
arXivHTMLPDF

Abstract

We consider open many-body systems governed by a time-dependent quantum master equation with short-range interactions. With a generalized Lieb-Robinson bound, we show that the evolution in this very generic framework is quasilocal; i.e., the evolution of observables can be approximated by implementing the dynamics only in a vicinity of the observables' support. The precision increases exponentially with the diameter of the considered subsystem. Hence, time evolution can be simulated on classical computers with a cost that is independent of the system size. Providing error bounds for Trotter decompositions, we conclude that the simulation on a quantum computer is additionally efficient in time. For experiments and simulations in the Schrödinger picture, our result can be used to rigorously bound finite-size effects.

DOI
10.1103/physrevlett.108.230504

Related papers

Classical Simulation of Short-Time Quantum Dynamics

Dominik S. Wild, Alvaro Martin Alhambra

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.

arXiv:2210.11490•PRX Quantum•Jun 12, 2023•42 citations

Renormalization approach to non-Markovian open-quantum-system dynamics

Giulia Gualdi, Christiane P. Koch

We show that time induces a dynamical renormalization of the system-environment coupling in open-quantum-system dynamics. The renormalizability condition, of the interactions being either local, or, alternatively, defined on a finite continuum support, is generally fulfilled for both discrete and continuous environments. As a consequence, we find a generalized Lieb-Robinson bound to hold for local and, surprisingly, also for nonlocal interactions. This unified picture allows us to devise a controllable approximation for arbitrary non-Markovian dynamics with an a priori estimate of the worst-case computational cost.

arXiv:1111.4059•Physical Review A•Aug 26, 2013•16 citations

Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics

David Poulin

The Lieb-Robinson bound shows the existence of a maximum speed of signal propagation in discrete quantum mechanical systems with local interactions. This generalizes the concept of relativistic causality beyond field theory, and provides a powerful tool in theoretical condensed matter physics and quantum information science. Here, we extend the scope of this seminal result by considering general markovian quantum evolution, where we prove that an equivalent bound holds. In addition, we use the generalized bound to demonstrate that correlations in the stationary state of a Markov process decay on a length scale set by the Lieb-Robinson velocity and the system's relaxation time.

arXiv:1003.3675•Physical Review Letters•May 11, 2010•145 citations

Quantum computer simulations of time-dependent hamiltonians

Nathan Wiebe

In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.

•Jan 1, 2011•0 citations

Quantum master equation for many-body systems based on the Lieb-Robinson bound

Koki Shiraishi, Masaya Nakagawa, Takashi Mori +1 more

The authors derive here a local quantum master equation for many-body open quantum systems on the basis of the Lieb-Robinson bound, which places a fundamental upper bound on the propagation speed of correlations of observables. This approach clarifies the conditions under which local quantum master equations are valid and provides a microscopic justification for their use in strongly interacting systems. Numerical simulations on a one-dimensional fermionic chain demonstrate the accuracy of the derived equation.

arXiv:2404.14067•Physical review. B./Physical review. B•May 12, 2025•18 citations

Quantum simulation of non-Markovian dynamical systems

Abtin Ameri, Arkopal Dutt, Hari Krovi

Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms. We develop an algorithm for general kernels assuming that $\textsf{M} < 1$, where $\textsf{M}$ characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when $\textsf{M} \geq 1$, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when $\textsf M \geq 1$ by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.

quant-pharXiv:2608.13533•Aug 14, 2026•2 citations
We consider open many-body systems governed by a time-dependent quantum master equation with short-range interactions. With a generalized Lieb-Robinson bound, we show that the evolution in this very generic framework is quasilocal; i.e., the evolution of observables can be approximated by implementing the dynamics only in a vicinity of the observables' support. The precision increases exponentially with the diameter of the considered subsystem. Hence, time evolution can be simulated on classical computers with a cost that is independent of the system size. Providing error bounds for Trotter decompositions, we conclude that the simulation on a quantum computer is additionally efficient in time. For experiments and simulations in the Schrödinger picture, our result can be used to rigorously bound finite-size effects.
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.
We show that time induces a dynamical renormalization of the system-environment coupling in open-quantum-system dynamics. The renormalizability condition, of the interactions being either local, or, alternatively, defined on a finite continuum support, is generally fulfilled for both discrete and continuous environments. As a consequence, we find a generalized Lieb-Robinson bound to hold for local and, surprisingly, also for nonlocal interactions. This unified picture allows us to devise a controllable approximation for arbitrary non-Markovian dynamics with an a priori estimate of the worst-case computational cost.
The Lieb-Robinson bound shows the existence of a maximum speed of signal propagation in discrete quantum mechanical systems with local interactions. This generalizes the concept of relativistic causality beyond field theory, and provides a powerful tool in theoretical condensed matter physics and quantum information science. Here, we extend the scope of this seminal result by considering general markovian quantum evolution, where we prove that an equivalent bound holds. In addition, we use the generalized bound to demonstrate that correlations in the stationary state of a Markov process decay on a length scale set by the Lieb-Robinson velocity and the system's relaxation time.
In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.
The authors derive here a local quantum master equation for many-body open quantum systems on the basis of the Lieb-Robinson bound, which places a fundamental upper bound on the propagation speed of correlations of observables. This approach clarifies the conditions under which local quantum master equations are valid and provides a microscopic justification for their use in strongly interacting systems. Numerical simulations on a one-dimensional fermionic chain demonstrate the accuracy of the derived equation.
Existing quantum algorithms for simulating dynamical systems -- from Hamiltonian simulation to linear and nonlinear differential equations solvers -- simulate Markovian dynamics, in which the system's future evolution depends solely on its current state. We turn our attention to developing quantum algorithms for non-Markovian dynamical systems where the system's future evolution depends on its past history and thus has memory. Specifically, we develop efficient algorithms for linear Volterra integro-differential equations (VIDEs) with a convolution memory kernel that output a quantum state encoding the state description over a time interval or at a particular time. Given efficient circuits for the problem inputs, our algorithms achieve an exponential speedup in system size over existing classical algorithms. We develop an algorithm for general kernels assuming that M<1\textsf{M} < 1M<1, where M\textsf{M}M characterizes the strength of the memory term relative to the dissipation of the Markovian part of the dynamics. We complement this with lower bounds for general-kernel VIDEs when M≥1\textsf{M} \geq 1M≥1, showing that the problem becomes intractable for a family of systems. However, by specializing to structured kernels which admit concise decompositions over exponentials, we develop efficient quantum algorithms even when M≥1\textsf M \geq 1M≥1 by converting the VIDE into a larger set of ODEs, a procedure which we call Markovianization. As an application of the overall framework, we discuss the Mori-Zwanzig formalism used in open quantum systems and fluid dynamics. Overall, our results expand the range of dynamical systems that quantum computers can simulate efficiently.