Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm
Abstract
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−1|≤κ, 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].
Related
- Optimal Linear Combination of Hamiltonian Simulation for Dissipative Dynamics
- Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation
- Optimal kernel functions for linear combination of Hamiltonian simulation
- Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
BibTeX
@misc{li2026sparse,
title = {{Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm}},
author = {Zecheng Li and Chunhao Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02030},
eprint = {2610.02030},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02030},
}
RIS
TY - UNPB
TI - Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm
AU - Zecheng Li
AU - Chunhao Wang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02030
UR - https://arxiv.org/abs/2610.02030
AB - 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^−1|≤κ, 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].
ER -