Event Type

Year

Physics Colloquium - When Exactly Do Quantum Computers Provide a Speedup?

prof.scottaaronsonwquantumcomputers.jpg
Date: 
Mon, 05/01/201512:00
See also: Colloquiums, 2015
Location: 
Levin Building, Lecture Hall No. 8, The Hebrew University of Jerusalem
Lecturer: 
Prof. Scott Aaronson, MIT

Twenty years after the discovery of Shor's factoring algorithm, I'll survey what we now understand about the structure of problems that admit quantum speedups. I'll start with the basics, discussing the hidden subgroup, amplitude amplification, adiabatic, and linear systems paradigms for quantum algorithms. Then I'll move on to some general results, obtained by Andris Ambainis and myself over the last few years, about quantum speedups in the black-box model. These results include the impossibility of a superpolynomial quantum speedup for any problem with permutation symmetry, and the largest possible separation between classical and quantum query complexities for any problem.