  We present an efficient quantum algorithm for simulating the evolution of a
sparse Hamiltonian H for a given time t in terms of a procedure for computing
the matrix entries of H. In particular, when H acts on n qubits, has at most a
constant number of nonzero entries in each row/column, and |H| is bounded by a
constant, we may select any positive integer $k$ such that the simulation
requires O((\log^*n)t^{1+1/2k}) accesses to matrix entries of H. We show that
the temporal scaling cannot be significantly improved beyond this, because
sublinear time scaling is not possible.
