  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.
