Results and open problems in theory of quantum complexity - Andris Ambainis

Andris Ambainis University of Latvia; Member, School of Mathematics April 22, 2014 I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing: 1. Quantum vs. classical query complexity 2. Quantum vs. classical query complexity for almost all inputs 3. Quantum counterparts of Valiant-Vazirani theorem (reducing NP to unique-NP) For more videos, visit http://video.ias.edu