Quantum Statistical Query Learning

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

• Vojtěch Havlíček, IBM T.J. Watson Research Center
• Thursday 25 January 2024, 14:15-15:30
• MR9.

If you have a question about this talk, please contact Subhayan Roy Moulik.

Joint work with Louis Schatzki (UIUC) and Srinivasan Arunachalam (IBM Almaden).

Statistical Query Learning (SQ) is a restriction of PAC learning in which learners form hypotheses by querying expectation values over the data distribution and labels. It is well known that SQ cannot learn the concept class of parities, even under uniform distribution. This shows that SQ is a restriction of PAC . 

Here we study a quantum generalization of SQ, quantum statistical query learning (QSQ) previously proposed by Arunachalam, Grilo and Yuen. It has been shown that QSQ can efficiently learn parities and is therefore a stronger learning model than SQ. It was however open how it compares to (quantum) PAC learning model.

Our main result is a task that separates quantum PAC and QSQ . To prove it, we built on Feldman‘s work on statistical query learning to derive lower bounds on QSQ learning. I will discuss our result, give details about the lower bounding technique and outline some of its applications

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
• MR9
• bld31

Note that ex-directory lists are not shown.