log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Quantum Speedups over Classical Computation
Wednesday, February 15, 2017, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

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.

Bio

Robin Kothari is a post-doctoral associate at the Center for Theoretical Physics at MIT. He earned a M.Math and Ph.D. at the David R. Cheriton School of Computer Science and Institute for Quantum Computing at the University of Waterloo and a B.Tech at the Indian Institute of Technology Bombay.

This talk is organized by Todd Holden