Skip to main content

The Nature of Quantum Speedups

Board3.JPG

Speaker

Shalev Ben-David(MIT)

Event Type

CS Seminar

Date & Time

February 23, 2017, 11:00am

Where to Attend

AV Williams 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.