ÍâÍøÌìÌÃ

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.