Efficient quantum algorithms for simulating sparse Hamiltonians

We present an efficient quantum algorithm for simulating the evolution of an arbitrary sparse Hamiltonian for a given time in terms of a procedure for computing the matrix entries of the Hamiltonian. In particular, for a fixed number of qubits and at most a constant number of nonzero entries in each row or column, with the norm of the Hamiltonian bounded by a constant, we show that the Hamiltonian system can be simulated on a quantum computer in slightly superlinear time with log-star accesses to matrix elements of the Hamiltonian matrix. These results suggest that physical systems can be simulated on a quantum computer with a time-cost nearly linear in the physical time of evolution, and the cost of the simulation is effectively independent of the number of qubits used.