The Nature of Quantum Speedups

Quantum algorithms appear to outperform classical algorithms on various tasks. They generally come in two flavors: those like Shor's factoring algorithm, which appears to give an exponential speedup over classical computation but only for a structured problem (and not for NP-complete problems), and those like Grover's algorithm, which gives only a polynomial (quadratic) speedup but works even for unstructured problems.

 

In this talk, I will describe some of my work investigating the types of structure necessary for quantum speedups. I will show how to obtain the first super-quadratic speedup for an "unstructured" problem in the blackbox model. I will also describe results that shed light on the kind of structure that is required to get exponential quantum speedups over classical algorithms.