Efficient algorithm for simulating Hamiltonian evolution

There are three main applications of quantum computer algorithms: the hidden subgroup problem (with Shor's factorization algorithm one important example), search problems (e.g. Grover's algorithm), and our interest here: simulation (Feynman's original motivation for the quantum computer as a tool for efficient simulation of quantum evolution whereas classical computation may be exponentially expensive). We develop an efficient quantum algorithm for simulating the evolution of a quantum state valid for any sparse Hamiltonian (as a black-box problem) for an arbitrary length of time. Specifically, when the Hamiltonian acts on qubits, has at most a constant number of nonzero entries in each row and column, and its norm is bounded by a constant, the cost of the simulation is O(log*n t^{1+1/2k}) for k any integer. In other words the cost of the simulation is nearly constant in and arbitrarily close to linear in the time of evolution; moreover we prove that an algorithm for simulating general evolution of quantum states cannot be sublinear in. Our results provide a firm algorithmic foundation for studying a quantum computer, especially with respect to assessing and optimizing the cost of the simulation. In addition our methods may lead to improved simulations for quantum control on classical computers.