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.
