Quantum Simulation Circuits for Sparse Hamiltonians

In 1982, Feynman suggested a quantum computer would efficiently simulate quantum systems and illustrated this concept with Heisenberg chains (Int. J. Theor. Phys, 21, 467), which are difficult to solve on a classical computer. Recently, building upon the work of Aharonov and Ta-Shma (Proc. 35th Annual ACM Symp. on Theory of Computing, 20-29), Berry, Ahokas, Cleve, and Sanders (arxiv:quant-ph/0508139) developed an algorithm that simulates state evolution for generic sparse time-independent Hamiltonians, which accounts for all resources and has a cost that is nearly linear in time. We present a quantum circuit protocol to implement this algorithm. Furthermore we discuss the adaptation of this scheme for a broad class of time-dependent Hamiltonians.