We provide a quantum algorithm for simulating the dynamics of sparse

Hamiltonians with complexity sublogarithmic in the inverse error, an

exponential improvement over previous methods. Specifically, we show that a

$d$-sparse Hamiltonian $H$ acting on $n$ qubits can be simulated for time $t$

with precision $\epsilon$ using $O\big(\tau

\frac{\log(\tau/\epsilon)}{\log\log(\tau/\epsilon)}\big)$ queries and

$O\big(\tau \frac{\log^2(\tau/\epsilon)}{\log\log(\tau/\epsilon)}n\big)$

additional 2-qubit gates, where $\tau = d^2 \|{H}\|_{\max} t$. Unlike previous

approaches based on product formulas, the query complexity is independent of

the number of qubits acted on, and for time-varying Hamiltonians, the gate

complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our

algorithm is based on a significantly improved simulation of the continuous-

and fractional-query models using discrete quantum queries, showing that the

former models are not much more powerful than the discrete model even for very

small error. We also simplify the analysis of this conversion, avoiding the

need for a complex fault correction procedure. Our simplification relies on a

new form of "oblivious amplitude amplification" that can be applied even though

the reflection about the input state is unavailable. Finally, we prove new

lower bounds showing that our algorithms are optimal as a function of the

error.