Time: Monday, March 6, 2017, 1:00pm @ MTH3206

Speaker: Prof. Andrew Childs (UMD)

Title: High-precision quantum algorithms

Abstract: 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. W hile 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 related "high-precision" quantum algorithms for linear systems and linear differential equations, and explore some of the potential applications of these techniques.