Efficient algorithm for quantum simulation

The original motivation for quantum computation was the efficient simulation of quantum systems to overcome the exponential barrier of classical algorithms. When small-scale quantum computers are created, quantum simulations are likely to be the first applications. Here we formulate an algorithm for simulation of any Hamiltonian-driven dynamics of a finite quantum system, which fully accounts for all resources used in the computation. We show that our generic algorithm has a cost that is nearly linear in time, cannot be sublinear in time, and is nearly constant in space (number of qubits) for given sparseness of the Hamiltonian matrix. Our algorithm exploits higher-order corrections to the Trotter formula and an efficient graph theory method for decomposing the Hamiltonian matrix into a sum of one-sparse Hamiltonian matrices.