arXiv:2610.02939
Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
Dominic W. Berry, Abhishek Rawat, Sophia Simon, Guang Hao Low
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 $\mathcal{O}(\sqrt{s}τ+\sqrt{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 $\sqrt{s}τ$ and $\log(1/ε)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ 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}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$, 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.
AI Summary
The paper addresses whether sparse-access Hamiltonian simulation and quantum linear-equation algorithms can achieve square-root sparsity dependence without subpolynomial overheads. Its access model supplies entry values and reversible row/column locators with inverse-location access; state-preparation costs are counted separately. For an $s$-sparse Hermitian matrix with row and column Euclidean norms bounded by $\eta$, simulation for time $t$ to error $\epsilon$ uses $O(\sqrt{s}\tau+\sqrt{s\tau L}+L)$ queries, where $\tau=\eta|t|$ and $L=\log(1/\epsilon)$. The bound extends to time-dependent Hamiltonians given coherent sampled-time access and certified discretisation. A lower bound $\Omega(\sqrt{s}\tau+\sqrt{s\tau r}+r)$, with $r=L/\log(e+L/\tau)$, rules out uniformly additive time and precision costs but leaves logarithmic gaps. Constant-error implementation of an arbitrary $N\times N$ unitary follows with $O(\sqrt N)$ entry queries. The construction uses an exact entrywise Cayley representation with bounded compressed second moment, transducers, and resolvent-based filtering. Linear-combination-of-Hamiltonian-simulations methods yield dissipative ODE solvers costing $O(\bar g[\sqrt{s}(\tau+\sqrt\tau)+1]\log(C\bar g/\epsilon))$, where $\bar g$ bounds input/source norm relative to final-solution norm. A kernel walk and Chebyshev filter solve linear systems in $O(\kappa\sqrt{s}\log(1/\epsilon))$ queries, matching a joint lower bound under $\|A\|\le1$ and $\|A^{-1}\|\le\kappa$. ODE outputs and linear-system solutions are amplitude-encoded states. Dissipative precision optimality remains unresolved. Gate-efficient implementations cover time-independent simulation and dissipative ODEs under additional arithmetic, decoding, and preparation assumptions, not all extensions.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 67 pages