Simulating Hamiltonian dynamics - Andrew Childs

Hamiltonian simulation is a basic task in quantum computation, with applications both to simulating physical systems and implementing continuous-time quantum algorithms. I will describe two methods for sparse Hamiltonian simulation, one based on star decompositions and another based on discrete-time quantum walk. Both methods are faster than previously known approaches; which of the two is preferred depends on the desired accuracy of the simulation. I will also describe a technique for simulating non-sparse Hamiltonians, and show that no such method can run in time poly(||Ht||) in general. Parts of this talk are based on joint work with Dominic Berry and with Robin Kothari.