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

Accelerating Quantum Dense-Output Simulation through Locality

Songqinghao Yang, Chang Liu, Junkai Wang, Jingxuan Zhang, Jin-Peng Liu

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Estimating time-accumulated observables, or dense outputs, is central to extracting classical information from quantum simulations. Whereas most quantum-simulation algorithms aim to reproduce a final state or a single-time expectation value, many applications require the integrated signal $J_H(O)=\int_0^T \langle ψ(t)|O(t)|ψ(t)\rangle\,dt$. Previous Hamiltonian-simulation-based dense-output algorithms have query costs that depend on the norm of the full Hamiltonian, which can grow with system size. However, one can naturally optimize the simulation algorithm when the system structure is known. Consequently, we develop a locality-based truncation framework for the dense-output problem on lattice Hamiltonians. By truncating the Hamiltonian and tightening the resulting error with Lieb-Robinson bounds, we show that a local simulation can recover the dense output. We bound the quantum simulation error from spatial truncation and translate it into local-simulation query bounds. Our analysis includes free and interacting systems for both fermions and bosons, as well as open quantum systems governed by Lindbladians. The improvement from our truncation algorithm varies from constant to unbounded as the system size grows. We also give example applications and conduct relevant numerical experiments to support our findings.

AI Summary

The paper asks whether spatial locality reduces the cost of estimating time-integrated observables, $J_H(O)=\int_0^T\langle O(t)\rangle\,dt$. It restricts lattice dynamics to a neighbourhood of a local observable, integrates Lieb–Robinson truncation estimates, and substitutes the retained Hamiltonian’s normalization into a dense-output algorithm with baseline query bound $\mathcal O(\|H\|T^3\log(1/\delta)/\epsilon)$. For number-conserving quadratic systems with fixed particle-number cutoff $n$ and hopping decay $r^{-\alpha}$, $\alpha>D+1$, the error scales as $\mathcal O(n^2[T^2/R^{\alpha-D}+T^{5/2}/R^{(\alpha-D-\eta)/2}])$, subject to a light-cone condition. The stated query improvement is constant-factor in this regime. For slow-decay free fermions, an appendix establishes an operator-norm truncation bound $\mathcal O(J_0T^2/R^s)$ for translation-invariant hopping, where $0<s<1$ and $s\le\alpha-D/2$. The main text claims system-size-independent truncated query costs and an unbounded improvement for $D/2<\alpha<D$ at fixed time and accuracy. Extensions cover interacting fermions, bosons, and local Lindbladians. The interacting-fermion estimates give linear-in-time sufficient radii for exponentially decaying interactions and exponential-in-time radii for power-law profiles. The bosonic bounds require density control and an initially empty surrounding shell. A Lindbladian-gap analysis reports logarithmic radius growth when the gap exceeds the Lieb–Robinson rate. Finite-system calculations examine truncation, temporal cancellation, and state-dependent versus uniform errors. Stated limitations include finite-size sensitivity at stringent tolerances, missing matching lower bounds, unresolved integration with history-state methods, and the need for further treatment of stationary-state mismatch and relaxation in open systems.

Some signs of AI-generated textAI use disclosedPossible errorOverclaimsStrong assumptionsUnclear novelty
Proofs and grammars were partly verified by the Claude-5 model as well and checked with Grammarly.

Central claim may not hold: The complexity analysis conflates a one-particle hopping-row bound with the many-body Hamiltonian norm, leading to a false constant-norm claim for general fast-decaying interacting fermionic Hamiltonians. The general slow-decay free-fermion truncation theorem is not proved by its original argument, and the valid finite-section appendix establishes only a narrower translation-invariant result with restricted exponents. The slow-decay truncated-query formula omits a factor of D in the exponent obtained by converting truncation radius into the shell-sum normalization. The interacting-fermion proof establishes a local observable approximant but does not show that evolution under the restricted Hamiltonian produces that approximant or satisfies the claimed error bound. The Lindbladian gap-dependent theorem relies on an incorrect general Jordan-block decay estimate and an unjustified multiplication of relaxation and locality bounds, leaving its advertised logarithmic-radius guarantee unsupported.

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

Comments
80 pages, 13 figures

Related papers

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

Lattice Lindbladian simulation by patching and merging

Kaoru Mizuta

Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count $O(Nt \, \mathrm{polylog}(Nt/\varepsilon))$, where $N$ is the system size, $t$ is the evolution time, and $\varepsilon$ is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count $O((Nt)^{4/3} \, \mathrm{polylog}(Nt/\varepsilon))$ per sample with the sampling complexity $Θ(\varepsilon^{-2})$. The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on $1/\varepsilon$. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.

quant-pharXiv:2609.26372•Sep 23, 2026•4 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 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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2018•76 citations

Towards Precision Quantum Simulation of Lattice Gauge Theories

Siddharth Hariprakash

Quantum simulation of lattice gauge theories offers a path to first-principles calculations of real-time dynamics and finite-density phenomena that are inaccessible to classical Euclidean Monte Carlo methods. Realizing this potential requires a pipeline of controlled approximations---lattice discretization, truncation, digitization, state preparation, time evolution, measurement, and continuum extrapolation---each contributing errors and computational costs. General algorithmic asymptotic complexity arguments capture only part of the cost picture: the practical resources required for end-to-end simulation depend on numerical pre-factors, the cost of the subroutines that various algorithms call, and structural features of the lattice theory, all of which the asymptotic scaling leaves unspecified. This thesis develops contributions that aim to make such dependencies explicit and quantitative. We begin with a rigorous analysis of the asymptotic gate complexity of product formulas and Quantum Signal Processing (QSP) for the time evolution of general classes of lattice Hamiltonians, identifying the parameter regimes in which each method is favorable and estimating the associated pre-factors numerically. Since the cost of QSP-based simulation is dominated (in regimes of practical interest) by the block-encoding subroutine it calls, we also develop several novel block-encoding constructions tailored to bosonic lattice field theories and show that signal-processing techniques can be repurposed as highly efficient block-encoding subroutines. We then turn to the problem of truncating the Kogut--Susskind electric-field Hilbert space. Existing error bounds rely on energy-conservation arguments and require the truncation to grow with simulation time. By exploiting Hilbert space fragmentation we derive the tightest error bounds known to date: they decay factorially in the truncation parameter and are independent of simulation time. We validate them numerically for U(1) pure gauge theory and the Schwinger model. Finally, we address the continuum limit in the presence of approximate time evolution. For product formulas, we show that Trotter errors correspond to irrelevant operators that vanish in the continuum limit, which yields a renormalization trajectory independent of the Trotter step size. More generally, we introduce the Statistically-Bounded Time Evolution (SBTE) protocol, an algorithm-independent framework that treats approximation errors as a systematic uncertainty to be driven below the working statistical precision. This decouples the continuum-limit prescription from the choice of time-evolution algorithm and provides a basis for end-to-end cost comparisons across simulation methods.

•May 1, 2026•0 citations

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

Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation

Zheyu Shen, Yusen Wu, Penghui Yao +2 more

Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $ε$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/ε))$ and gate count $O(nT\log(nT/ε))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $ε$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $Ω(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.

quant-pharXiv:2610.01839•Oct 2, 2026•0 citations
Estimating time-accumulated observables, or dense outputs, is central to extracting classical information from quantum simulations. Whereas most quantum-simulation algorithms aim to reproduce a final state or a single-time expectation value, many applications require the integrated signal JH(O)=∫0T⟨ψ(t)∣O(t)∣ψ(t)⟩ dtJ_H(O)=\int_0^T \langle ψ(t)|O(t)|ψ(t)\rangle\,dtJH​(O)=∫0T​⟨ψ(t)∣O(t)∣ψ(t)⟩dt. Previous Hamiltonian-simulation-based dense-output algorithms have query costs that depend on the norm of the full Hamiltonian, which can grow with system size. However, one can naturally optimize the simulation algorithm when the system structure is known. Consequently, we develop a locality-based truncation framework for the dense-output problem on lattice Hamiltonians. By truncating the Hamiltonian and tightening the resulting error with Lieb-Robinson bounds, we show that a local simulation can recover the dense output. We bound the quantum simulation error from spatial truncation and translate it into local-simulation query bounds. Our analysis includes free and interacting systems for both fermions and bosons, as well as open quantum systems governed by Lindbladians. The improvement from our truncation algorithm varies from constant to unbounded as the system size grows. We also give example applications and conduct relevant numerical experiments to support our findings.
The paper asks whether spatial locality reduces the cost of estimating time-integrated observables, JH(O)=∫0T⟨O(t)⟩ dtJ_H(O)=\int_0^T\langle O(t)\rangle\,dtJH​(O)=∫0T​⟨O(t)⟩dt. It restricts lattice dynamics to a neighbourhood of a local observable, integrates Lieb–Robinson truncation estimates, and substitutes the retained Hamiltonian’s normalization into a dense-output algorithm with baseline query bound O(∥H∥T3log⁡(1/δ)/ϵ)\mathcal O(\|H\|T^3\log(1/\delta)/\epsilon)O(∥H∥T3log(1/δ)/ϵ).
For number-conserving quadratic systems with fixed particle-number cutoff nnn and hopping decay r−αr^{-\alpha}r−α, α>D+1\alpha>D+1α>D+1, the error scales as O(n2[T2/Rα−D+T5/2/R(α−D−η)/2])\mathcal O(n^2[T^2/R^{\alpha-D}+T^{5/2}/R^{(\alpha-D-\eta)/2}])O(n2[T2/Rα−D+T5/2/R(α−D−η)/2]), subject to a light-cone condition. The stated query improvement is constant-factor in this regime. For slow-decay free fermions, an appendix establishes an operator-norm truncation bound O(J0T2/Rs)\mathcal O(J_0T^2/R^s)O(J0​T2/Rs) for translation-invariant hopping, where 0<s<10<s<10<s<1 and s≤α−D/2s\le\alpha-D/2s≤α−D/2. The main text claims system-size-independent truncated query costs and an unbounded improvement for D/2<α<DD/2<\alpha<DD/2<α<D at fixed time and accuracy.
Extensions cover interacting fermions, bosons, and local Lindbladians. The interacting-fermion estimates give linear-in-time sufficient radii for exponentially decaying interactions and exponential-in-time radii for power-law profiles. The bosonic bounds require density control and an initially empty surrounding shell. A Lindbladian-gap analysis reports logarithmic radius growth when the gap exceeds the Lieb–Robinson rate. Finite-system calculations examine truncation, temporal cancellation, and state-dependent versus uniform errors.
Stated limitations include finite-size sensitivity at stringent tolerances, missing matching lower bounds, unresolved integration with history-state methods, and the need for further treatment of stationary-state mismatch and relaxation in open systems.
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.
Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count O(Nt polylog(Nt/ε))O(Nt \, \mathrm{polylog}(Nt/\varepsilon))O(Ntpolylog(Nt/ε)), where NNN is the system size, ttt is the evolution time, and ε\varepsilonε is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count O((Nt)4/3 polylog(Nt/ε))O((Nt)^{4/3} \, \mathrm{polylog}(Nt/\varepsilon))O((Nt)4/3polylog(Nt/ε)) per sample with the sampling complexity Θ(ε−2)Θ(\varepsilon^{-2})Θ(ε−2). The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on 1/ε1/\varepsilon1/ε. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.
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 simulation of lattice gauge theories offers a path to first-principles calculations of real-time dynamics and finite-density phenomena that are inaccessible to classical Euclidean Monte Carlo methods. Realizing this potential requires a pipeline of controlled approximations---lattice discretization, truncation, digitization, state preparation, time evolution, measurement, and continuum extrapolation---each contributing errors and computational costs. General algorithmic asymptotic complexity arguments capture only part of the cost picture: the practical resources required for end-to-end simulation depend on numerical pre-factors, the cost of the subroutines that various algorithms call, and structural features of the lattice theory, all of which the asymptotic scaling leaves unspecified. This thesis develops contributions that aim to make such dependencies explicit and quantitative. We begin with a rigorous analysis of the asymptotic gate complexity of product formulas and Quantum Signal Processing (QSP) for the time evolution of general classes of lattice Hamiltonians, identifying the parameter regimes in which each method is favorable and estimating the associated pre-factors numerically. Since the cost of QSP-based simulation is dominated (in regimes of practical interest) by the block-encoding subroutine it calls, we also develop several novel block-encoding constructions tailored to bosonic lattice field theories and show that signal-processing techniques can be repurposed as highly efficient block-encoding subroutines. We then turn to the problem of truncating the Kogut--Susskind electric-field Hilbert space. Existing error bounds rely on energy-conservation arguments and require the truncation to grow with simulation time. By exploiting Hilbert space fragmentation we derive the tightest error bounds known to date: they decay factorially in the truncation parameter and are independent of simulation time. We validate them numerically for U(1) pure gauge theory and the Schwinger model. Finally, we address the continuum limit in the presence of approximate time evolution. For product formulas, we show that Trotter errors correspond to irrelevant operators that vanish in the continuum limit, which yields a renormalization trajectory independent of the Trotter step size. More generally, we introduce the Statistically-Bounded Time Evolution (SBTE) protocol, an algorithm-independent framework that treats approximation errors as a systematic uncertainty to be driven below the working statistical precision. This decouples the continuum-limit prescription from the choice of time-evolution algorithm and provides a basis for end-to-end cost comparisons across simulation methods.
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.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy εεε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an nnn-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1T\ge1T≥1, with circuit depth O(Tlog⁡(nT/ε))O(T\log(nT/ε))O(Tlog(nT/ε)) and gate count O(nTlog⁡(nT/ε))O(nT\log(nT/ε))O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time TTT in the stated regime and sufficiently small fixed error εεε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). This matches our O(log⁡n)O(\log n)O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.