Hamiltonian simulation with nearly optimal dependence on spectral norm

We present a quantum algorithm for approximating the real time evolution $e^{-iHt}$ of an arbitrary $d$-sparse Hamiltonian to error $\epsilon$, given black-box access to the positions and $b$-bit values of its non-zero matrix entries. The complexity of our algorithm is $\mathcal{O}((t\sqrt{d}\|H\|_{1 \rightarrow 2})^{1+o(1)}/\epsilon^{o(1)})$ queries and a factor $\mathcal{O}(b)$ more gates, which is shown to be optimal up to subpolynomial factors through a matching query lower bound. This provides a polynomial speedup in sparsity for the common case where the spectral norm $\|H\|\ge\|H\|_{1 \rightarrow 2}$ is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem -- $\mathcal{O}(d^{1/2+o(1)})$ queries suffice to approximate any $d$-sparse unitary in the black-box setting, which matches the quantum search lower bound of $\Omega(\sqrt{d})$ queries and improves upon prior art [Berry and Childs, QIP 2010] of $\tilde{\mathcal{O}}(d^{2/3})$ queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number $\kappa$ using $\mathcal{O}((\kappa \sqrt{d})^{1+o(1)}/\epsilon^{o(1)})$ queries, which is a quadratic improvement in sparsity.