Quantum computer simulations of time dependent hamiltonians

Feynman's original motivation for the quantum computer resulted from a conjecture that quantum computers could efficiently simulate any quantum system, whereas classical computers cannot. Since then many quantum simulation schemes have verified his conjecture for sparse time independent Hamiltonians. However all proposals that have been put forward so far for simulating time dependent Hamiltonians only address sparse Hamiltonians and have complexity that scales as O(t^{3/2}). We address these issues by presenting a quantum computer simulation scheme that can simulate many non-sparse time-dependent Hamiltonians that uses arbitrary-order decomposition formulae to achieve complexity of O(t^{1+epsilon)) for arbitrary epsilon>0, provided the time dependence is suitably smooth. Since O(t) complexity has been proven to be optimal, our simulation scheme demonstrates near optimal performance for the broadest class of Hamiltonians considered so far.