Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm

We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $\mathrm{\Lambda }$ on its maximum column Euclidean norm $\mathrm{\parallel }H{\mathrm{\parallel }}_{1\to 2}$. For $t\mathrm{\Lambda }\ge 1\mathrm{/}2$, simulation with operator-norm error $\epsilon$ uses $$O\text{\hspace{0.17em}⁣}(t\mathrm{\Lambda }\sqrt{d}+\sqrt{d}\log (2\mathrm{/}\epsilon ))$$ 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\mathrm{\Lambda }\ge \log (2\mathrm{/}\epsilon )$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $\mathrm{\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{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(\kappa \mathrm{/}\epsilon ))$ queries for solving $d$-sparse quantum linear systems with $\mathrm{\parallel }A\mathrm{\parallel }\le 1$ and $\mathrm{\parallel }{A}^{-1}\mathrm{\parallel }\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\mathrm{/}\epsilon ))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $\mathrm{\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].