Are quantum speedups for learning expressive classes possible?

Speaker

Tom Gur April 08, 2022.

Abstract

Obtaining quantum speedups for machine learning tasks is one of the most alluring potential applications of quantum computing. Yet, despite extensive study, there are currently no provable strong separations between the power of quantum and classical learning algorithms. This talk aims to give a perspective on this problem.

We will discuss the first general connection, which was recently established, between the design of quantum algorithms and circuit lower bounds. Namely, we will show that even a marginal quantum speedup over “trivial” quantum learning algorithms would lead to major consequences in complexity lower bounds.

This result can be interpreted in two ways. On the one hand, it provides an explanation for why it is difficult to design provably correct non-trivial quantum learners, as they would imply dramatic consequences to complexity theory, showing new circuit lower bounds that are notoriously hard to prove. On the other hand, it provides a new approach for making progress on these long-standing open problems in complexity theory via the design of quantum algorithms.

The talk is based on a FOCS 2021 paper, joint with Srinivasan Arunachalam, Alex B. Grilo, Igor C. Oliveira, and Aarthi Sundaram, as well as on an upcoming work.