  We describe a method to simulate Hamiltonian evolution on a quantum computer
by repeatedly using a superposition of steps of a quantum walk, then applying a
correction to the weightings for the numbers of steps of the quantum walk. This
correction enables us to obtain complexity which is the same as the lower bound
up to double-logarithmic factors for all parameter regimes. The scaling of the
query complexity is $O\left( \tau \frac{\log\log\tau}{\log\log\log\tau} +
\log(1/\epsilon) \right)$ where $\tau := t\|H\|_{\max}d$, for $\epsilon$ the
allowable error, $t$ the time, $\|H\|_{\max}$ the max-norm of the Hamiltonian,
and $d$ the sparseness. This technique should also be useful for improving the
scaling of the Taylor series approach to simulation, which is relevant to
applications such as quantum chemistry.
