Efficient quantum algorithms for simulating sparse Hamiltonians

We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse Hamiltonian H over 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 parallel to H parallel to 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 also show that the temporal scaling cannot be significantly improved beyond this, because sublinear time scaling is not possible.