Quantum Complexity Theory: Key Results & Open Challenges 🔍
Explore the latest breakthroughs and unresolved questions in quantum complexity theory with Andris Ambainis. Discover where research is headed in this rapidly evolving field.
Institute for Advanced Study
1.2K views • Aug 1, 2016
About this video
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
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
Video Information
Views
1.2K
Likes
14
Duration
01:45:30
Published
Aug 1, 2016
User Reviews
4.3
(1)