**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.