Tutte seminar - Andrew Childs

Exponential Improvement in Precision for Simulating Sparse Hamiltonians

Abstract:

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a significantly improved simulation of the fractional-query model using discrete quantum queries, showing that fractional queries are not much more powerful than discrete ones even for very small error. We significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. We also prove new lower bounds showing that our algorithm is optimal as a function of the error.

Based on joint work with Dominic Berry, Richard Cleve, Robin Kothari, and Rolando Somma.