Title: On Quantum Statistical Query Learning

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

Abstract: 

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 it is a restriction of PAC. 

We study an obvious quantum generalization of SQ, proposed by Arunachalam, Grilo and Yuen, which is not separable from a quantum generalization of PAC by parity learning and our main result is a task that separates the two learning classes. To prove it, we built on Feldman‘s work on statistical query dimension, which yields lower bounds on SQ learning. I will discuss our result, the lower bounding technique and some of its applications.