Advances in Quantum Algorithms for Hamiltonian Simulation

Hamiltonian simulation is a major potential application of quantum computers, because it enables predictions to be made for physical quantum systems, as well as providing a foundation for other quantum algorithms. Standard methods for Hamiltonian simulation involve product formulae, where the Hamiltonian evolution is a product of evolutions for a series of short times. We have developed a range of advanced algorithms with greatly improved performance. One method is to compress product formulae, which gives an exponential improvement in some parameters. A crucial part of this is an oblivious form of amplitude amplification, which allows the steps of this procedure to be performed deterministically. This also enables us to perform evolution based on a truncated Taylor series. Another approach is to use a quantum walk; using oblivious amplitude amplification we are able to perform a superposition of different numbers of steps of the walk, providing greatly improved performance.