Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
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.
