High-precision quantum algorithms

The original motivation for quantum computing came from the problem of simulating the behavior of quantum systems, a task that is apparently intractable for classical computers. While we have known for two decades that quantum computers can efficiently simulate quantum mechanics, recent work has significantly improved the performance of the best known algorithms. The goal of quantum simulation is to produce an approximation of the ideal output state that is accurate to within some desired precision ε. Until recently, the best quantum simulation algorithms had complexity polynomial in 1/ε. In this talk, I will describe an approach developed in collaboration with Berry, Cleve, Kothari, and Somma that achieves complexity sublogarithmic in 1/ε, an exponential improvement. I will also describe a related "high-precision" quantum algorithm for linear systems and explore some of the potential applications of these techniques.