arXiv · Oct 1, 2026
Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm
By Zecheng Li, Chunhao Wang
We give a quantum algorithm for simulating a d-sparse Hermitian Hamiltonian H, assuming a known upper bound Λ on its maximum column Euclidean norm ‖H‖_(1→2). For tΛ≥1/2, simulation with operator-norm error ε uses [ O(tΛ√ d+√ dlog(2/ε)) ] sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For d>1 and tΛ≥log(2/ε), the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of Λ. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain O(κ√ d polylog(κ/ε)) queries for solving d-sparse quantum linear systems with ‖A‖≤1 and ‖A⁻¹‖≤κ, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most d nonzero entries per row and column using O(√ dlog(2/ε)) queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields Θ(√ N) queries for arbitrary N× N unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].