Exponential Improvement in Precision for Simulating Sparse Hamiltonians
|Affiliation:||University of Waterloo|
Mathematics 3 (M3) 3127
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.
200 University Avenue West
Waterloo, ON N2L 3G1