Sparse Hamiltonians are the default input model for a large part of quantum simulation theory: an oracle tells you where the non-zero entries of each row are and what they are. In that model, standard block-encoding constructions lead to a cost that grows linearly with the sparsity s, the maximum number of non-zero entries per row. A new paper by Dominic W. Berry, Abhishek Rawat, Sophia Simon and Guang Hao Low gives algorithms whose leading cost grows only as √s, without the very large subpolynomial factors that accompanied the only previous general result of this kind, and backs them with lower bounds that nearly match.
This article was drafted with Claude and fact-checked against the cited primary sources. The paper is arXiv:2610.02939 (v1, submitted 2 October 2026, 67 pages).
Why it is worth reading
The question of square-root sparsity scaling has a long history. The paper recalls that Berry and Childs proposed √s methods in 2012 but could prove that scaling only under an extra condition on how the Hamiltonian’s norm behaves when it is split into parts, a condition that adversarial examples can violate. In 2019 Low established square-root dependence for general sparse Hamiltonians up to subpolynomial factors, which the authors describe as very large in practice. The new paper claims to remove those factors from the leading sparsity and time dependence, and it extends the same idea to linear differential equations and linear systems.
What the paper does
The main result (Theorem 4.1) concerns a Hermitian matrix H with at most s non-zero entries per row and column, where every row and column has Euclidean norm at most a known η. Writing τ = η|t| and ℓ = log(1/ε), the evolution e−itH is simulated to operator-norm error ε using O(√s·τ + √(sτℓ) + ℓ) queries to the sparse oracles. The authors state that the same bound holds for time-dependent Hamiltonians, given coherent time-indexed access and a certified time discretisation.
The paper then reports three further results:
Lower bound. A joint lower bound (Theorem 5.1) matches the leading √s·τ term and is within a factor log(e + ℓ/τ) on the mixed term. It also rules out a purely additive bound of the form O(√s·τ + ℓ).
Dissipative linear ODEs. Combining the simulator with linear combination of Hamiltonian simulations (LCHS), the matrix-query cost is O(ḡ[√s(τ + √τ) + 1]·log(Cḡ/ε)), where ḡ bounds the ratio of input-plus-source norm to final-solution norm.
Linear systems. For ‖A‖ ≤ 1 and ‖A−1‖ ≤ κ, a “Cayley walk” plus a Chebyshev filter gives O(κ√s·log(1/ε)) queries, which matches a known joint lower bound in the stated parameter range.
As a corollary, any N×N unitary can be implemented at constant precision with O(√N) queries to its entries, matching the search lower bound. The authors note that Bravo-Prieto, Harrow and Kothari obtained this bound, and the same linear-system scaling, in independent concurrent work.
The key idea
Standard sparse block encodings have normalisation s·‖H‖max, treating every entry as if it were as large as the largest one. The new construction uses the row and column Euclidean norms instead. It lifts the matrix to an “edge space” with two orientations for each non-zero entry, and builds an auxiliary operator whose compression back to the system reproduces H/(η√s). Crucially, the second moment of that operator is bounded on the subspace that couples to the system, even though its full norm can be as large as √s.
Rather than evolving under this operator, the authors apply the Cayley transform, which maps a real eigenvalue λ to (λ + i)/(λ − i) on the unit circle. Because the operator acts as a 2×2 block on each edge, the resulting unitary costs a constant number of sparse queries: query an entry, apply a known two-dimensional rotation, uncompute.
How it works
The Cayley unitary alone does not produce evolution under H. To get there, the paper uses the transducer framework of Belovs, Jeffery and Yolcu, following its recent use for time-dependent simulation by Chen, Gao, Wang and Zhou. A transducer is a unitary on public and private spaces that acts as a target unitary on the public part while returning a private “catalyst” amplitude unchanged. Here the public action is a Cayley time step (I − iΔtH/2)(I + iΔtH/2)−1, which approximates e−iΔtH with cubic local error.
Many time steps are composed with one private sector per time slot; a single coherent application of the Cayley unitary serves all of them, so refining the time mesh does not increase the query count. The circuit never prepares the catalyst. Instead, repeated reuse and averaging, implemented as a linear combination of unitaries followed by one round of oblivious amplitude amplification, filter out the mismatch. The cost is governed by two quantities: W, which bounds the catalyst’s squared norm, and Q, which controls how close the auxiliary spectrum can come to 1. Tuning a scaling parameter γ trades one against the other, and balancing them gives the stated bound. The simpler, unscaled version already gives O(√s(τ + ℓ)).
Why it matters
Sparse access is how many structured matrices, from lattice Hamiltonians to discretised differential operators, are presented to quantum algorithms. When rows have many entries but bounded Euclidean norm, replacing s by √s in the leading term changes the asymptotic cost, and the paper gives that improvement with clean, nearly tight bounds rather than through large hidden factors. The constructions also come with gate-efficient implementations for time-independent simulation and the dissipative ODE solver, with polylogarithmic overhead under stated assumptions about entry decoding and arithmetic.
A notable feature is formal verification. The time-independent simulation theorem, the constant-coefficient dissipative ODE result and the constant-error unitary-implementation bound are formalised in Lean 4 with Mathlib, in a public sparse-quantum-lean repository; the paper reports that the project compiles with 588 axiom-audit assertions that use only Lean’s standard foundational axioms.
Technical perspective (interpretation)
My reading is that the conceptual move is to separate “cheap unitary access” from “physical evolution”. The Cayley transform supplies the first at constant query cost with favourable moment bounds; the transducer turns those bounds into a simulation, without needing the auxiliary operator’s full norm to be small. It is also interesting that the time-dependent case incurs no extra query overhead in this model. Whether the √s advantage materialises for a specific application depends on how the row Euclidean norm η compares with s·‖H‖max, which is problem-dependent and not quantified for applications in the paper.
Limitations and open questions
The results are query complexities in a specific native sparse-access model, including in-place row and column locators with supplied inverses; the authors stress that a general out-of-place locator without inverse access is not substituted.
The Hamiltonian bounds are not fully tight: the upper and lower bounds differ by a factor log(e + ℓ/τ) on the mixed √(sτℓ) term.
For dissipative ODEs the authors identify the largest remaining gap; their lower bounds do not show that ḡ, √s·τ and the full precision logarithm must appear multiplicatively.
Gate-complexity bounds rely on separately stated assumptions, and gate bounds for the general non-dissipative ODE and linear-system algorithms are listed as future work.
The Lean formalisation does not cover the time-dependent extension, the linear-system algorithm, the lower bounds or the gate analyses.
There are no numerical resource estimates for concrete applications. The acknowledgements state that derivations were developed with an AI system and further checked with another.
Paper information
Title: Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
Authors: Dominic W. Berry (Macquarie University; University of Queensland), Abhishek Rawat (Macquarie University), Sophia Simon (University of Toronto; University of Queensland), Guang Hao Low (Google Quantum AI)
arXiv: 2610.02939v1 [quant-ph], submitted 2 October 2026
Formal proofs: github.com/DominicWB/sparse-quantum-lean (version 0.1.0-rc5)
Primary sources
Paper (abstract page): https://arxiv.org/abs/2610.02939
Full text (HTML): https://arxiv.org/html/2610.02939v1
Lean formalisation: https://github.com/DominicWB/sparse-quantum-lean