Are quantum speedups for learning expressive classes possible?


Tom Gur April 08, 2022.


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.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • Derandomization from Time-Space Tradeoffs
  • Foundations of Lattice-based Cryptography
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Brooks' Theorem in Graph Streams, A Single-Pass Semi-Streaming Algorithm for Δ-Coloring