arXiv preprint ·
Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
High-Rate Quantum Codes with Proven Distance and Low-Weight Measurements
Exact Finite-Channel Schur Moments of the Wigner-Smith Matrix with a Tunnel Barrier
Gaussian Fisher Information Is Superadditive
Parallelizing Dissipative Quantum Algorithms
Where Quantum Fourier Sampling Stops Short: A Three-Gate Audit Protocol for Delay-PUF Security Models
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.