Simulating Hamiltonian evolution on a quantum computer

Efficiently simulating arbitrary Hamiltonian evolution was the earliest motivating application for quantum computation, yet its algorithmic formulation is less advanced than those addressing search and factorization problems. Here we present an efficient quantum algorithm for simulating quantum state evolution for a sparse time- independent Hamiltonian in terms of computing its matrix elements. For n qubits and at most a constant number of nonzero entries in each row, and a constant bound on the norm of the Hamiltonian, our algorithm cost is nearly linear in time and nearly constant in space [1]. We show how the algorithm can be adapted for efficiently simulating time- dependent Hamiltonian evolution of a state on a quantum computer with similar costs [2].\r\n