Abstract

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