NQN Seminar Series: Can Quantum Computers Speed up Gradient Descent?

Robin Kothari, Senior Researcher, Microsoft Quantum

Wednesday, November 25, 3:00 PM (Pacific Time)

Gradient descent is a popular algorithm in machine learning and optimization and finds many applications in theory and in practice. Robin Kothari asks, “Can quantum computers speed up this algorithm?” During this seminar, Kothari will discuss the meaning of the question, formalize the question in the context of first-order convex optimization and looks at prior work in this setting. Finally, he will answer the question posed in this context.

Robin Kothari is a Senior Researcher at Microsoft Quantum. His primary area of research is quantum algorithms and complexity theory. Broadly, he studies the following question: What problems can and cannot be solved faster on an ideal (i.e., scalable fault-tolerant) quantum computer? Quantum computers only solve some problems faster than traditional computers, and it is important to identify these problems. Conversely, it is important to understand where quantum computers offer no advantage, both to avoid wasting time looking for quantum advantage for these problems and to understand the fundamental limitations of quantum computers.

This talk is based on joint work with Ankit Garg, Praneeth Netrapalli, and a preprint of this work can be found on the arXiv.

Hosted by the Northwest Quantum Nexus (NQN), a coalition led by the U.S. Department of Energy’s Pacific Northwest National Laboratory, Microsoft Quantum, and the University of Washington. These monthly web-based seminars feature experts on quantum computing and its applications, and support NQN’s goal of creating a vibrant industry that will contribute to the economic vitality of the region. For questions, contact