We present an algorithm for sparse Hamiltonian simulation that has optimal
dependence on all parameters of interest (up to log factors). Previous
algorithms had optimal or near-optimal scaling in some parameters at the cost
of poor scaling in others. Hamiltonian simulation via a quantum walk has
optimal dependence on the sparsity $d$ at the expense of poor scaling in the
allowed error $\epsilon$. In contrast, an approach based on fractional-query
simulation provides optimal scaling in $\epsilon$ at the expense of poor
scaling in $d$. Here we combine the two approaches, achieving the best features
of both. By implementing a linear combination of quantum walk steps with
coefficients given by Bessel functions, our algorithm achieves near-linear
scaling in $\tau := d \|H\|_{\max} t$ and sublogarithmic scaling in
$1/\epsilon$. Our dependence on $\epsilon$ is optimal, and we prove a new lower
bound showing that no algorithm can have sublinear dependence on $\tau$.
