Theory Seminar

Can Quantum Computers Outperform Gradient Descent?

Speaker: Suhail Sherif, Vector Institute, Toronto
Time: 5PM, 15th September, 2021


Gradient descent is a marvel of an algorithm that allows very efficient optimization in high-dimensional spaces. It was provably the best algorithm for well-structured optimization tasks. such as non-smooth convex optimization in large dimensions. But then came quantum computers with their fancy superpositions, pulling off amazing feats of computation. So questions of the form “Is this the best algorithm we have?” had to be asked all over again.

In this talk we will take a look at gradient descent, at the task of non-smooth convex optimization, and we’ll show that quantum computers can’t improve upon gradient descent in general.



© 2021 IIIT Hyderabad. All rights reserved.