Algorithms for quantum simulation

One of the most important applications of quantum computation will be to simulate quantum systems efficiently in cases where classical simulations are intractable, as Feynman proposed when he first started investigating quantum computing. I will present algorithms for simulating Hamiltonian evolution and show that, in the case that the Hamiltonian is provided to an oracle, the cost of the simulation is nearly constant in space and nearly linear in time. The cost is quantified as the number of queries to the oracle, and this low cost is advantageous for quantum simulation implementations.