Quantum Speedups Over Classical Computation

Speaker:Robin Kothari, Ph.D.
Date: Tuesday, February 7, 2017
Time: 12:00pm - 1:00pm
Location: 207 Hudson Hall , Duke
Lunch will be served.


I'll talk about two questions related to quantum speedups over classical computation. First, if we had a universal quantum computer, which computational problems should we solve on it? I'll argue that the task of simulating physical systems is one of the best choices for this and discuss the state of the art for quantum algorithms solving this problem. Second, what provable speedups can we exhibit between quantum and classical computation? Since this question is difficult to answer in the Turing machine model, I'll discuss our understanding of the problem in more restricted models. I'll describe the current best provable speedups, focusing on the recent super-Grover speedups that go beyond the quadratic separation of Grover's algorithm.


Robin received his PhD in Computer Science from the University of Waterloo in 2014, under the supervision of Andrew Childs and John Watrous. His research interests include quantum algorithms, quantum complexity theory, (quantum) query complexity, and (quantum) communication complexity. He is currently a postdoctoral associate at the Center for Theoretical Physics at Massachusetts Institute of Technology.