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 $\eta$, evolution for time $t$ to error $\epsilon$ uses $\mathcal{O}(\sqrt{s}\tau+\sqrt{s\tau\log(1/\epsilon)}+\log(1/\epsilon))$ queries, where $\tau=\eta|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 $\sqrt{s}\tau$ and $\log(1/\epsilon)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(\tau+\sqrt{\tau})+1]\log(C\bar g/\epsilon))$ queries, where $\tau$ is the evolution time multiplied by a norm bound, $\bar 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 $\mathcal{O}(\kappa\sqrt{s}\log(1/\epsilon))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\le\kappa$, 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.

arXiv:2610.02939 [quant-ph]

(or arXiv:2610.02939v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.02939 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.