Quantum advantage for learning periodic neurons with non-uniform data

Add to your list(s) Download to your calendar using vCal

• Laura Lewis, Caltech
• Thursday 20 February 2025, 14:15-15:15
• MR2.

If you have a question about this talk, please contact Laurens Lootens.

Applying quantum computers to machine learning tasks is an exciting potential direction to explore in search of quantum advantage. Theoretical frameworks such as the quantum probably approximately correct (PAC) and quantum statistical query (QSQ) models have been proposed to study quantum algorithms for learning classical functions. Despite numerous works investigating quantum advantages in these models, we nevertheless only understand it at two extremes: either exponential quantum advantages for uniform input distributions or no advantage for potentially adversarial distributions. In this work, we make progress towards filling the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a broad range of non-uniform distributions, which includes Gaussian, generalized Gaussian, and logistic distributions. To our knowledge, our work is also the first result in quantum learning theory for classical functions that explicitly considers real-valued functions. Recent advances in classical learning theory prove that learning periodic neurons is hard for any classical gradient-based algorithm, giving us an exponential quantum advantage over such algorithms. There is also strong evidence that the problem remains hard for classical statistical query algorithms and even general classical algorithms learning under small amounts of noise.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR2
• bld31

Note that ex-directory lists are not shown.