The Power of Randomized and Quantum Computation
Shalev Ben-David, Massachusetts Institute of Technology
Randomized and quantum computing offer potential improvements over deterministic algorithms, and challenge our notion of what should be considered efficient computation. A fundamental question in complexity theory is to try to understand when these resources help; on which tasks do randomized or quantum algorithms outperform deterministic ones?
In this talk, I will describe some of my work investigating this question, primarily in the query complexity (blackbox) model. I will show how to obtain the first super-quadratic separation between randomized and quantum algorithms, beating the quadratic speedup of Grover search. I will also describe a characterization of the problems that can give rise to exponential randomized (or quantum) speedups when some suitable promise is placed on their input.
BIO: Shalev is a final-year PhD student at MIT advised by Scott Aaronson. His interests lie in computational complexity and quantum computing.