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:2610.12731

Lieb-Robinson bounds for irreversible dynamics via adaptive Dyson expansion

Carla Rubiliani, Marius Wesle, Tom Wessel

math-phquant-phSubmitted Oct 8, 2026• Announced Oct 12, 2026• 3 citations
arXivHTMLPDF

Abstract

In this note, we study a broad class of time-dependent and irreversible dynamics for quantum spin systems in both finite and infinite volume. We develop a simple and flexible strategy for expanding commutators of the form $[A,τ_{s,t} \, B]$ in terms of self-avoiding paths of sets, where $A$ and $B$ are local operators and $τ_{s,t}$ is the Heisenberg time evolution. This adaptive Dyson expansion requires no backwards time evolution and is thus also applicable to irreversible dynamics. Furthermore, we discuss how such an expansion directly implies Lieb-Robinson bounds. A central feature of our result is that the obtained Lieb-Robinson bounds are independent of any Hamiltonian and dissipative on-site terms of the generator.

AI Summary

The paper studies Lieb–Robinson bounds for time-dependent irreversible quantum lattice dynamics, focusing on how to obtain locality estimates without backward time evolution and without dependence on on-site dissipation. Its setting includes local GKSL generators and, more generally, bounded, norm-continuous dissipative superoperators, with possibly infinite-dimensional on-site Hilbert spaces. An adaptive Dyson expansion expresses $K\tau_{s,t}B$ exactly as a sum over self-avoiding paths of interaction supports connecting the supports $X$ and $Y$. Repeated Duhamel expansions progressively remove interactions intersecting previously visited sets; all intervening evolutions remain contractive. Under $\sup_{u,x}\sum_{Z\ni x}|Z|\,\|\Phi(Z,u)\|<\infty$, the expansion converges absolutely and the thermodynamic-limit evolution exists. For interactions with $F$-decay, the resulting estimate is $\|K\tau_{s,t}B\|\leq\|K\|\|B\|C_F^{-1}(e^{C_F I_{\tilde\Phi}(s,t)}-1)\sum_{x\in X,y\in Y}F(d(x,y))$, where $I_{\tilde\Phi}(s,t)=\int_s^t\|\tilde\Phi(u)\|_F\,du$. Here $\tilde\Phi$ excludes on-site terms and terms entirely inside either endpoint support. Thus these terms do not enter the bound. For ordered disjoint supports in a nearest-neighbour chain, the unique connecting path gives $\|K\tau_{s,t}B\|\leq\|K\|\|B\|(J(t-s))^d/d!$, with $d=\operatorname{dist}(X,Y)$ and $J$ the maximum intervening bond-generator norm. Finite-range bounds and operator-localization estimates also follow. The expansion extends existing Hamiltonian self-avoiding-path constructions. Local generators remain bounded and satisfy summability assumptions; infinite-dimensional sites do not imply coverage of unbounded generators. Linear-light-cone bounds for general long-range irreversible systems are deferred to future work.

No sign of AI-generated textIncremental

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Stability of slow Hamiltonian dynamics from Lieb-Robinson bounds

Daniele Toniolo, Sougato Bose

We rigorously show that a local spin system giving rise to a slow Hamiltonian dynamics is stable against generic, even time-dependent, local perturbations. The sum of these perturbations can cover a significant amount of the system's size. The stability of the slow dynamics follows from proving that the Lieb-Robinson bound for the dynamics of the total Hamiltonian is the sum of two contributions: the Lieb-Robinson bound of the unperturbed dynamics and an additional term coming from the Lieb-Robinson bound of the perturbations with respect to the unperturbed Hamiltonian. Our results are particularly relevant in the context of the study of the stability of Many-Body-Localized systems, implying that if a so called ergodic region is present in the system, to spread across a certain distance it takes a time proportional to the exponential of such distance. The non-perturbative nature of our result allows us to develop a dual description of the dynamics of a system. As a consequence we are able to prove that the presence of a region of disorder in a ergodic system implies the slowing down of the dynamics in the vicinity of that region.

arXiv:2405.05958•May 9, 2024•14 citations

Lieb-Robinson bounds and existence of the thermodynamic limit for a class of irreversible quantum dynamics

Bruno Nachtergaele, Anna Vershynina, Valentin Anatol'evich Zagrebnov

We prove Lieb-Robinson bounds and the existence of the thermodynamic limit for a general class of irreversible dynamics for quantum lattice systems with time-dependent generators that satisfy a suitable decay condition in space.

arXiv:1103.1122•Contemporary mathematics - American Mathematical Society•Jan 1, 2011•61 citations

Lieb--Robinson Bounds and Entanglement Limits in Quantum Dynamics with Finite-Dimensional Memory

Jeet Mozumdar

We derive an extension of the Lieb--Robinson bound that accounts for memory effects in quantum lattice systems evolving under discrete-time non-Markovian dynamics generated by local interactions with finite-dimensional memory subsystems associated with each bond. The global evolution is unitary on an extended Hilbert space \[ \mathcal{H}_{\mathrm{ext}} = \bigotimes_{i=1}^{N} \mathcal{H}_i \otimes \bigotimes_{\text{bonds}} \mathcal{H}_M^{(i)}, \] while non-Markovian behavior, arising from repeated coupling to the same bond memory at successive time steps, leads to temporal correlations in the system. In this work, “finite memory” refers specifically to memory subsystems of fixed finite Hilbert space dimension whose reduced dynamics satisfy an exponential mixing condition in operator norm, meaning that correlation functions decay exponentially over time, with a characteristic timescale \(\tau\). More precisely, the memory channels satisfy \[ \left\| \mathcal{T}_M^s(X) - \mathrm{Tr}(X)\,\sigma_M \right\| \le c\, e^{-s/\tau}\, \|X\|, \] for all memory observables \(X\), where \(\sigma_M\) is a stationary state, and \(c>0\) depends only on the memory dynamics. For a one-dimensional lattice with nearest-neighbor interactions, we prove that the connected correlation function, defined as \[ C_{i,j}(t) := \sup_{\substack{A_i = A_i^\dagger,\; B_j = B_j^\dagger \\ \|A_i\|\le 1,\; \|B_j\|\le 1}} \left| \mathrm{Tr}\!\left[(A_i \otimes B_j)\rho(t)\right] - \mathrm{Tr}\!\left[A_i \rho_i(t)\right]\, \mathrm{Tr}\!\left[B_j \rho_j(t)\right] \right|, \] satisfies an exponential bound of the form \[ C_{i,j}(t) \le C_0 \exp\!\Big[-\frac{d(i,j) - v_{\mathrm{eff}}(\tau)\, t}{\xi}\Big], \] where \(d(i,j)=|i-j|\) and \(\xi>0\) is independent of system size and time. The effective velocity \(v_{\mathrm{eff}}(\tau)\) is explicitly bounded in terms of the local interaction strength and the memory mixing parameters, ensuring the system exhibits a finite light cone, meaning that information propagation is confined to a region growing linearly with time, with a well-defined maximum speed. In the limit \(\tau \to \infty\), the bound no longer guarantees a finite propagation speed, reflecting the transition to a persistent memory regime where correlations do not decay exponentially. As an operational consequence, the entanglement fidelity between two-site reduced states \(\rho_{i,j}(t)\) and a maximally entangled state satisfies \[ F_{i,j}(t) = \langle \Phi^+ | \rho_{i,j}(t) | \Phi^+ \rangle \le \tfrac{1}{2}\bigl[1 + C_{i,j}(t)\bigr]. \] These results extend Lieb--Robinson theory to a class of discrete-time quantum dynamics with memory subsystems associated with each bond, enabling resummation of multi-step memory effects into an effective correlation propagation kernel that governs the decay of temporal correlations. This establishes a quantitative relationship between the timescale of memory mixing and the effective speed of information propagation in the system.

•Apr 26, 2026•1 citation

Applications of Lieb-Robinson Bounds to Quantum Dynamics with and without Disorder

Jake Reschke

This dissertation presents new results on two problems concerning the dynamics of certainclasses of interacting many-body systems in quantum mechanics. Chapter 1 is an introduction,\nwhich includes mathematical preliminaries and a summary of the results.\nIn Chapter 2 we introduce the notion of transmission time to study the dynamics of disordered\nquantum spin chains and prove results relating its behavior to many-body localization properties.\nWe also study two versions of the so-called Local Integrals of Motion (LIOM) representation of\nspin chain Hamiltonians and their relation to dynamical many-body localization. We prove that\nuniform-in-time dynamical localization expressed by a zero-velocity Lieb-Robinson bound implies\nthe existence of a LIOM representation of the dynamics as well as a weak converse of this statement.\nWe also prove that for a class of spin chains satisfying a form of exponential dynamical localization,\nsparse perturbations result in a dynamics in which transmission times diverge at least as a power\nlaw of distance, with a power for which we provide lower bound that diverges with increasing\nsparseness of the perturbation.\nIn Chapter 3 we introduce a class of UV-regularized two-body interactions for fermions in Rd\nand prove a Lieb-Robinson estimate for the dynamics of this class of many-body systems. As a\nstep toward this result, we also prove a propagation bound of Lieb-Robinson type for Schrodinger\noperators. We apply the propagation bound to prove the existence of infnite-volume dynamics as\na strongly continuous group of automorphisms on the CAR algebra.

•Jan 1, 2021•0 citations

Lieb-Robinson Bounds with Exponential-in-Volume Tails

Ben T. McDonough, Chao Yin, Andrew Lucas +1 more

Lieb-Robinson bounds demonstrate the emergence of locality in many-body quantum systems. Intuitively, Lieb-Robinson bounds state that, with local or exponentially decaying interactions, the correlation that can be built up between two sites separated by distance r after a time t decays as exp  ( v t − r ) , where v is the emergent Lieb-Robinson velocity. In many problems, it is important to also capture how much of an operator grows to act on r d sites in d spatial dimensions. Perturbation theory and cluster expansion methods suggest that, at short times, these volume-filling operators are suppressed as exp  ( − r d ) . We confirm this intuition, showing that, for r > v t , the volume-filling operator is suppressed by exp  ( − ( r − v t ) d / ( v t ) d − 1 ) . This closes a conceptual and practical gap between the cluster expansion and the Lieb-Robinson bound. We then present two very different applications of this new bound. Firstly, we obtain improved bounds on the classical computational resources necessary to simulate many-body dynamics with error tolerance ε for any finite time t : as ε becomes sufficiently small, only ε − O ( t d − 1 ) resources are needed. A protocol that likely saturates this bound is given. Secondly, we prove that disorder operators have volume-law suppression near the “solvable (Ising) point” in quantum phases with spontaneous symmetry breaking, which implies a new diagnostic for distinguishing many-body phases of quantum matter.

arXiv:2502.02652•PRX Quantum•Aug 20, 2025•10 citations

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians

Jeongwan Haah, Matthew B. Hastings, Robin Kothari +1 more

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 $\epsilon$ using ${\mathcal O}( nT {polylog} (nT/\epsilon))$ gates with depth ${\mathcal O}(T { polylog} (nT/\epsilon))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. 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 ${\widetilde{\Omega}}(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.

arXiv:1801.03922•SIAM Journal on Computing•Jan 12, 2021•226 citations
In this note, we study a broad class of time-dependent and irreversible dynamics for quantum spin systems in both finite and infinite volume. We develop a simple and flexible strategy for expanding commutators of the form [A,τs,t B][A,τ_{s,t} \, B][A,τs,t​B] in terms of self-avoiding paths of sets, where AAA and BBB are local operators and τs,tτ_{s,t}τs,t​ is the Heisenberg time evolution. This adaptive Dyson expansion requires no backwards time evolution and is thus also applicable to irreversible dynamics. Furthermore, we discuss how such an expansion directly implies Lieb-Robinson bounds. A central feature of our result is that the obtained Lieb-Robinson bounds are independent of any Hamiltonian and dissipative on-site terms of the generator.
The paper studies Lieb–Robinson bounds for time-dependent irreversible quantum lattice dynamics, focusing on how to obtain locality estimates without backward time evolution and without dependence on on-site dissipation. Its setting includes local GKSL generators and, more generally, bounded, norm-continuous dissipative superoperators, with possibly infinite-dimensional on-site Hilbert spaces.
An adaptive Dyson expansion expresses Kτs,tBK\tau_{s,t}BKτs,t​B exactly as a sum over self-avoiding paths of interaction supports connecting the supports XXX and YYY. Repeated Duhamel expansions progressively remove interactions intersecting previously visited sets; all intervening evolutions remain contractive. Under sup⁡u,x∑Z∋x∣Z∣ ∥Φ(Z,u)∥<∞\sup_{u,x}\sum_{Z\ni x}|Z|\,\|\Phi(Z,u)\|<\inftysupu,x​∑Z∋x​∣Z∣∥Φ(Z,u)∥<∞, the expansion converges absolutely and the thermodynamic-limit evolution exists.
For interactions with FFF-decay, the resulting estimate is ∥Kτs,tB∥≤∥K∥∥B∥CF−1(eCFIΦ~(s,t)−1)∑x∈X,y∈YF(d(x,y))\|K\tau_{s,t}B\|\leq\|K\|\|B\|C_F^{-1}(e^{C_F I_{\tilde\Phi}(s,t)}-1)\sum_{x\in X,y\in Y}F(d(x,y))∥Kτs,t​B∥≤∥K∥∥B∥CF−1​(eCF​IΦ~​(s,t)−1)∑x∈X,y∈Y​F(d(x,y)), where IΦ~(s,t)=∫st∥Φ~(u)∥F duI_{\tilde\Phi}(s,t)=\int_s^t\|\tilde\Phi(u)\|_F\,duIΦ~​(s,t)=∫st​∥Φ~(u)∥F​du. Here Φ~\tilde\PhiΦ~ excludes on-site terms and terms entirely inside either endpoint support. Thus these terms do not enter the bound. For ordered disjoint supports in a nearest-neighbour chain, the unique connecting path gives ∥Kτs,tB∥≤∥K∥∥B∥(J(t−s))d/d!\|K\tau_{s,t}B\|\leq\|K\|\|B\|(J(t-s))^d/d!∥Kτs,t​B∥≤∥K∥∥B∥(J(t−s))d/d!, with d=dist⁡(X,Y)d=\operatorname{dist}(X,Y)d=dist(X,Y) and JJJ the maximum intervening bond-generator norm. Finite-range bounds and operator-localization estimates also follow.
The expansion extends existing Hamiltonian self-avoiding-path constructions. Local generators remain bounded and satisfy summability assumptions; infinite-dimensional sites do not imply coverage of unbounded generators. Linear-light-cone bounds for general long-range irreversible systems are deferred to future work.
We rigorously show that a local spin system giving rise to a slow Hamiltonian dynamics is stable against generic, even time-dependent, local perturbations. The sum of these perturbations can cover a significant amount of the system's size. The stability of the slow dynamics follows from proving that the Lieb-Robinson bound for the dynamics of the total Hamiltonian is the sum of two contributions: the Lieb-Robinson bound of the unperturbed dynamics and an additional term coming from the Lieb-Robinson bound of the perturbations with respect to the unperturbed Hamiltonian. Our results are particularly relevant in the context of the study of the stability of Many-Body-Localized systems, implying that if a so called ergodic region is present in the system, to spread across a certain distance it takes a time proportional to the exponential of such distance. The non-perturbative nature of our result allows us to develop a dual description of the dynamics of a system. As a consequence we are able to prove that the presence of a region of disorder in a ergodic system implies the slowing down of the dynamics in the vicinity of that region.
We derive an extension of the Lieb--Robinson bound that accounts for memory effects in quantum lattice systems evolving under discrete-time non-Markovian dynamics generated by local interactions with finite-dimensional memory subsystems associated with each bond. The global evolution is unitary on an extended Hilbert space Hext=⨂i=1NHi⊗⨂bondsHM(i), \mathcal{H}_{\mathrm{ext}} = \bigotimes_{i=1}^{N} \mathcal{H}_i \otimes \bigotimes_{\text{bonds}} \mathcal{H}_M^{(i)}, Hext​=⨂i=1N​Hi​⊗⨂bonds​HM(i)​, while non-Markovian behavior, arising from repeated coupling to the same bond memory at successive time steps, leads to temporal correlations in the system. In this work, “finite memory” refers specifically to memory subsystems of fixed finite Hilbert space dimension whose reduced dynamics satisfy an exponential mixing condition in operator norm, meaning that correlation functions decay exponentially over time, with a characteristic timescale τ\tauτ. More precisely, the memory channels satisfy ∥TMs(X)−Tr(X) σM∥≤c e−s/τ ∥X∥, \left\| \mathcal{T}_M^s(X) - \mathrm{Tr}(X)\,\sigma_M \right\| \le c\, e^{-s/\tau}\, \|X\|, ∥TMs​(X)−Tr(X)σM​∥≤ce−s/τ∥X∥, for all memory observables XXX, where σM\sigma_MσM​ is a stationary state, and c>0c>0c>0 depends only on the memory dynamics. For a one-dimensional lattice with nearest-neighbor interactions, we prove that the connected correlation function, defined as Ci,j(t):=sup⁡Ai=Ai†,Bj=Bj†∥Ai∥≤1,∥Bj∥≤1∣Tr ⁣[(Ai⊗Bj)ρ(t)]−Tr ⁣[Aiρi(t)] Tr ⁣[Bjρj(t)]∣, C_{i,j}(t) := \sup_{\substack{A_i = A_i^\dagger,\; B_j = B_j^\dagger \\ \|A_i\|\le 1,\; \|B_j\|\le 1}} \left| \mathrm{Tr}\!\left[(A_i \otimes B_j)\rho(t)\right] - \mathrm{Tr}\!\left[A_i \rho_i(t)\right]\, \mathrm{Tr}\!\left[B_j \rho_j(t)\right] \right|, Ci,j​(t):=supAi​=Ai†​,Bj​=Bj†​∥Ai​∥≤1,∥Bj​∥≤1​​∣Tr[(Ai​⊗Bj​)ρ(t)]−Tr[Ai​ρi​(t)]Tr[Bj​ρj​(t)]∣, satisfies an exponential bound of the form Ci,j(t)≤C0exp⁡ ⁣[−d(i,j)−veff(τ) tξ], C_{i,j}(t) \le C_0 \exp\!\Big[-\frac{d(i,j) - v_{\mathrm{eff}}(\tau)\, t}{\xi}\Big], Ci,j​(t)≤C0​exp[−ξd(i,j)−veff​(τ)t​], where d(i,j)=∣i−j∣d(i,j)=|i-j|d(i,j)=∣i−j∣ and ξ>0\xi>0ξ>0 is independent of system size and time. The effective velocity veff(τ)v_{\mathrm{eff}}(\tau)veff​(τ) is explicitly bounded in terms of the local interaction strength and the memory mixing parameters, ensuring the system exhibits a finite light cone, meaning that information propagation is confined to a region growing linearly with time, with a well-defined maximum speed. In the limit τ→∞\tau \to \inftyτ→∞, the bound no longer guarantees a finite propagation speed, reflecting the transition to a persistent memory regime where correlations do not decay exponentially. As an operational consequence, the entanglement fidelity between two-site reduced states ρi,j(t)\rho_{i,j}(t)ρi,j​(t) and a maximally entangled state satisfies Fi,j(t)=⟨Φ+∣ρi,j(t)∣Φ+⟩≤12[1+Ci,j(t)]. F_{i,j}(t) = \langle \Phi^+ | \rho_{i,j}(t) | \Phi^+ \rangle \le \tfrac{1}{2}\bigl[1 + C_{i,j}(t)\bigr]. Fi,j​(t)=⟨Φ+∣ρi,j​(t)∣Φ+⟩≤21​[1+Ci,j​(t)]. These results extend Lieb--Robinson theory to a class of discrete-time quantum dynamics with memory subsystems associated with each bond, enabling resummation of multi-step memory effects into an effective correlation propagation kernel that governs the decay of temporal correlations. This establishes a quantitative relationship between the timescale of memory mixing and the effective speed of information propagation in the system.
This dissertation presents new results on two problems concerning the dynamics of certainclasses of interacting many-body systems in quantum mechanics. Chapter 1 is an introduction,\nwhich includes mathematical preliminaries and a summary of the results.\nIn Chapter 2 we introduce the notion of transmission time to study the dynamics of disordered\nquantum spin chains and prove results relating its behavior to many-body localization properties.\nWe also study two versions of the so-called Local Integrals of Motion (LIOM) representation of\nspin chain Hamiltonians and their relation to dynamical many-body localization. We prove that\nuniform-in-time dynamical localization expressed by a zero-velocity Lieb-Robinson bound implies\nthe existence of a LIOM representation of the dynamics as well as a weak converse of this statement.\nWe also prove that for a class of spin chains satisfying a form of exponential dynamical localization,\nsparse perturbations result in a dynamics in which transmission times diverge at least as a power\nlaw of distance, with a power for which we provide lower bound that diverges with increasing\nsparseness of the perturbation.\nIn Chapter 3 we introduce a class of UV-regularized two-body interactions for fermions in Rd\nand prove a Lieb-Robinson estimate for the dynamics of this class of many-body systems. As a\nstep toward this result, we also prove a propagation bound of Lieb-Robinson type for Schrodinger\noperators. We apply the propagation bound to prove the existence of infnite-volume dynamics as\na strongly continuous group of automorphisms on the CAR algebra.
Lieb-Robinson bounds demonstrate the emergence of locality in many-body quantum systems. Intuitively, Lieb-Robinson bounds state that, with local or exponentially decaying interactions, the correlation that can be built up between two sites separated by distance r after a time t decays as exp  ( v t − r ) , where v is the emergent Lieb-Robinson velocity. In many problems, it is important to also capture how much of an operator grows to act on r d sites in d spatial dimensions. Perturbation theory and cluster expansion methods suggest that, at short times, these volume-filling operators are suppressed as exp  ( − r d ) . We confirm this intuition, showing that, for r > v t , the volume-filling operator is suppressed by exp  ( − ( r − v t ) d / ( v t ) d − 1 ) . This closes a conceptual and practical gap between the cluster expansion and the Lieb-Robinson bound. We then present two very different applications of this new bound. Firstly, we obtain improved bounds on the classical computational resources necessary to simulate many-body dynamics with error tolerance ε for any finite time t : as ε becomes sufficiently small, only ε − O ( t d − 1 ) resources are needed. A protocol that likely saturates this bound is given. Secondly, we prove that disorder operators have volume-law suppression near the “solvable (Ising) point” in quantum phases with spontaneous symmetry breaking, which implies a new diagnostic for distinguishing many-body phases of quantum matter.
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 nnn qubits for time TTT up to error ϵ\epsilonϵ using O(nTpolylog(nT/ϵ)){\mathcal O}( nT {polylog} (nT/\epsilon))O(nTpolylog(nT/ϵ)) gates with depth O(Tpolylog(nT/ϵ)){\mathcal O}(T { polylog} (nT/\epsilon))O(Tpolylog(nT/ϵ)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nTnTnT and polylogarithmic in 1/ϵ1/\epsilon1/ϵ. 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){\widetilde{\Omega}}(nT)Ω(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.