Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
Abstract
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an s-sparse Hermitian matrix with row and column Euclidean norms bounded by η, evolution for time t to error ε uses 𝒪(√sτ+√(sτlog(1/ε))+log(1/ε)) queries, where τ=η|t|. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in √sτ and log(1/ε). For dissipative linear differential equations we obtain 𝒪(g̅[√s(τ+√τ)+1]log(Cg̅/ε)) queries, where τ is the evolution time multiplied by a norm bound, g̅ bounds the ratio of combined input and source norms to the final-solution norm, and C is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give 𝒪(κ√slog(1/ε)) queries when |A|≤1 and |A−1|≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
Related
- Generalized Hamiltonian formalism for spatially nonlocal nonlinear differential equations
- Effective-Hamiltonian Quantum Solvers for Differential Equations: Alternative Constructions and Function Encodings
- High-order Magnus expansion for Hamiltonian simulation
- Effective Hamiltonian description on monitored Majorana chains: correlated power-law hoppings and unconventional entanglement scaling
- Optimal Linear Combination of Hamiltonian Simulation for Dissipative Dynamics
BibTeX
@misc{berry2026rootsparsity,
title = {{Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers}},
author = {Dominic W. Berry and Abhishek Rawat and Sophia Simon and Guang Hao Low},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02939},
eprint = {2610.02939},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02939},
}
RIS
TY - UNPB
TI - Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
AU - Dominic W. Berry
AU - Abhishek Rawat
AU - Sophia Simon
AU - Guang Hao Low
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02939
UR - https://arxiv.org/abs/2610.02939
AB - We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an s-sparse Hermitian matrix with row and column Euclidean norms bounded by η, evolution for time t to error ε uses 𝒪(√sτ+√(sτlog(1/ε))+log(1/ε)) queries, where τ=η|t|. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in √sτ and log(1/ε). For dissipative linear differential equations we obtain 𝒪(g̅[√s(τ+√τ)+1]log(Cg̅/ε)) queries, where τ is the evolution time multiplied by a norm bound, g̅ bounds the ratio of combined input and source norms to the final-solution norm, and C is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give 𝒪(κ√slog(1/ε)) queries when |A|≤1 and |A^−1|≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
ER -