← All papers
First page of Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

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

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

quant-ph Oct 2, 2026 · v2
Accompanying Lean/Mathlib package (sparse-quantum-lean) formalizes the circuit constructions and query/gate bounds, with an appendix documenting conditional coverage.
We give quantum algorithms for time-independent and time-dependent Hamiltonian simulation, linear differential equations and linear systems, all with complexity that has only square-root dependence on matrix sparsity. Our algorithms retain optimal scaling in other relevant parameters such as time, condition number and precision. For several cases we prove matching lower bounds on the joint parameters and show that the additional gate overhead is only polylogarithmic in the inverse precision. The common primitive connecting our algorithms is the Cayley transform, which provides a cheap unitary embedding of the sparse matrices. For Hamiltonian simulation and differential equations, we then use transducers to construct the desired evolution operators. For linear systems, we instead encode the solution in the kernel of a matrix and use the Cayley transform to construct a projector onto that kernel.

Quantum algorithms for sparse Hamiltonian simulation, linear differential equations and linear systems usually have cost linear in the matrix sparsity s. The goal is square-root dependence on s while keeping optimal scaling in time, condition number and precision.

Each matrix entry is placed in a 2x2 Hermitian matrix, and its Cayley transform gives a cheap unitary rotation costing a constant number of sparse-oracle queries. Transducers turn these rotations into Hamiltonian evolution, which is then used for differential equations via linear combinations of Hamiltonian simulations. Linear systems are solved by encoding the solution in a kernel and projecting onto it with a Cayley-based walk filter. A Lean source archive pinned to Lean and Mathlib 4.32.1 formalizes the circuit construction and its error bounds, and Appendix E records which results it covers and under which external hypotheses.

The algorithms achieve query complexities such as O(√s τ + √(sτ log(1/ε)) + log(1/ε)) for Hamiltonian simulation and O(√s κ log(1/ε)) for linear systems. Matching lower bounds are proved in several cases, and the gate overhead is only polylogarithmic in the inverse precision.