Efficiently simulating evolution of states on a quantum computer

Feynman [Int. J. Theoret. Phys. 21, 467-488 (1982)] suggested that a quantum computer could serve as an efficient simulator of state evolution in cases where classical algorithms are inefficient, and Lloyd [Science 273, 1073-1078 (1996)] provided the first rigorous analysis of this conjecture. Using primitives introduced by Aharonov and Ta-Shma [Proc. 35th Annual ACM Symp. on Theory of Computing, 20-29 (2003)] for studying adiabatic quantum state generation, we introduce a quantum algorithm for simulating state evolution by a time-independent Hamiltonian whose cost is nearly linear in time (and we prove that an algorithm whose cost is sub-linear in time cannot exist) and nearly quadratic in terms of the sparseness of the Hamiltonian for sparse Hamiltonian evolution [Berry, Ahokas, Cleve and Sanders, Comm. Math. Phys. 270: 359-371 (2007)]. I will also discuss our efforts to establish an efficient simulation of state evolution for time-dependent Hamiltonians that is comparable to our time-independent Hamiltonian result.