Lecturer: Prof. Scott Aaronson
Affiliation: MIT
Abstract:
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.