Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

Dominic W. Berry, Abhishek Rawat, Sophia Simon, Guang Hao Low

arXivarxiv/2610.02939Oct 2, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.02939
curl -X POST /api/v1/records/arxiv/2610.02939/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.02939/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'