The Nature of Quantum Speedups

Talk
Shalev Ben-David
Talk Series: 
Time: 
02.23.2017 11:00 to 12:00
Location: 

AVW 4172

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.