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 $\Lambda$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $t\Lambda\ge1/2$, simulation with operator-norm error $\epsilon$ uses \[ O\!\left(t\Lambda\sqrt d+\sqrt d\log(2/\epsilon)\right) \] 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\Lambda\ge\log(2/\epsilon)$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $\Lambda$. 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(\kappa\sqrt d\,\mathrm{polylog}(\kappa/\epsilon))$ queries for solving $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\le\kappa$, 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(\sqrt d\log(2/\epsilon))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $\Theta(\sqrt N)$ queries for arbitrary $N\times N$ unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].