Quantum computer simulations of time dependent Hamiltonians - Nathan Wiebe

When Feynman first introduced the idea of quantum computation, his motivation was to show that there is a way to efficiently simulate the complicated many body interactions that happen in quantum systems. Since then a wide variety of schemes have been suggested to efficiently simulate time independent quantum systems on quantum computers, but as of yet no one has suggested a rigorous method that can simulate a time dependent quantum system on a quantum computer. In this talk I will present a quantum algorithm that simulates an arbitrary finite dimensional time dependent Hamiltonian. This is important not only because it extends the range of Hamiltonians that are known to be simulateable on a quantum computer, but also because it allows us to rigorously compare the cost of emulating a Hamiltonian based model of quantum computation (such as adiabatic quantum computing) on a quantum computer. I will also explicitly show that the resources required for the simulation scale near optimally with the simulation time, and that it scales efficiently with the system size if the Hamiltonian is sparse. I will also provide quantum circuits to clarify the operations needed to simulate a time dependent Hamiltonian. Finally applications of this simulation scheme to finding the cost of emulating Hamiltonian based quantum computing models (such as adiabatic algorithms) on a circuit based quantum computer will also be discussed.