Efficient quantum 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 as opposed to classical computation, which may be exponentially expensive). We develop an efficient quantum algorithm for simulating quantum for any (unknown) Hamiltonian over any time t. Specifically, when the Hamiltonian acts on n 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 n 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 t. 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.