Results and open problems in theory of quantum complexity

Computer Science/Discrete Mathematics Seminar II
Topic:Results and open problems in theory of quantum complexity
Speaker:Andris Ambainis
Affiliation:University of Latvia; von Neumann Fellow, School of Mathematics
Date:Tuesday, April 22
Time/Room:10:30am - 12:30pm/S-101
Video Link:http://video.ias.edu/csdm/2014/0422-AndrisAmbainis

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)