Time+Place: Thursday 08/01/2015 14:30 Room 337-8 Taub Bld.
Title: When Exactly Do Quantum Computers Provide a Speedup?
Speaker: Scott Aaronson - Colloquium Lecture https://www.csail.mit.edu/user/1324
Affiliation: M I T, Computer Science
Host: Eli Ben-Sasson


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.

Short Bio:

Scott Aaronson is an Associate Professor of Electrical Engineering and 
Computer Science at MIT.  He studied at Cornell and UC Berkeley, and did 
postdocs at the Institute for Advanced Study as well as the University 
of Waterloo.  His research focuses on the capabilities and limits of 
quantum computers, and more generally on computational complexity and 
its relationship to physics.  His first book, "Quantum Computing Since 
Democritus," was published last year by Cambridge University Press.
Aaronson has written about quantum computing for Scientific American and 
the New York Times, and writes a popular blog at 
He's received the National Science Foundation's Alan T. Waterman Award, 
the United States PECASE Award, and MIT's Junior Bose Award for 
Excellence in Teaching.

Desserts will be served from 14:15
Lecture starts at 14:30