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:1801.03922 · SIAM Journal on Computing

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians

Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low

Published Jan 12, 2021• 148 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/18m1231511

Related papers

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

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•64 citations

Shallow Quantum Circuits for Geometrically Local Lindblad Dynamics

Zheyu Shen, Yusen Wu, Xiao Yuan +1 more

Open-system dynamics govern decoherence, transport, and engineered dissipation in quantum many-body systems. We propose a quantum algorithm for simulating time-independent, finite-range Lindblad dynamics with bounded local strength on a constant-dimensional lattice of $n$ sites, allowing noncommuting jump operators. For time $T\ge1$ and diamond-norm error at most $ε$, it has depth $O(T\operatorname{polylog}(nT/ε))$ and gate count $O(nT\operatorname{polylog}(nT/ε))$. These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density. We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are $Ω(nT)$ for the expected gate count and $Ω(T)$ for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of $Ω(\log n/\log\log n)$, showing that global accuracy can require increasing depth as the lattice grows.

quant-pharXiv:2610.05362•Oct 6, 2026•0 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•0 citations

Optimal Lower Bounds for Hamiltonian Simulation

Alexander Zlokapa, Richard R. Allen, Aram W. Harrow

For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.

quant-pharXiv:2607.19852•Jul 23, 2026•0 citations

Accelerating Quantum Dense-Output Simulation through Locality

Songqinghao Yang, Chang Liu, Junkai Wang +2 more

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.

quant-pharXiv:2609.40094•Oct 1, 2026•0 citations
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.
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.
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.
Open-system dynamics govern decoherence, transport, and engineered dissipation in quantum many-body systems. We propose a quantum algorithm for simulating time-independent, finite-range Lindblad dynamics with bounded local strength on a constant-dimensional lattice of nnn sites, allowing noncommuting jump operators. For time T≥1T\ge1T≥1 and diamond-norm error at most εεε, it has depth O(Tpolylog⁡(nT/ε))O(T\operatorname{polylog}(nT/ε))O(Tpolylog(nT/ε)) and gate count O(nTpolylog⁡(nT/ε))O(nT\operatorname{polylog}(nT/ε))O(nTpolylog(nT/ε)). These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density. We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are Ω(nT)Ω(nT)Ω(nT) for the expected gate count and Ω(T)Ω(T)Ω(T) for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn), showing that global accuracy can require increasing depth as the lattice grows.
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.
For Hamiltonian H=∑jhjH = \sum_j h_jH=∑j​hj​, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ∥hj∥\|h_j\|∥hj​∥, time ttt, and trace-distance error εεε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ∥hj∥\|h_j\|∥hj​∥ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε1/ε1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
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.