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