{"id":"arxiv/2610.02939","url":"https://arxiv.org/abs/2610.02939","tags":["quant-ph"],"score":0,"title":"Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers","domain":"quant-ph","source":"arxiv","authors":["Dominic W. Berry","Abhishek Rawat","Sophia Simon","Guang Hao Low"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}