Statistical query learning model (SQ) is a restricted learning model that learns by querying estimates of random variables. It was originally introduced by Kearns to capture effect of noisy samples in learning. It is known that there are efficiently PAC learnable problems not efficiently learnable in SQ. Does this also hold for the quantum generalizations of these models?
We discuss quantum generalization of SQ -- the quantum statistical query learning model (QSQ) -- and compare its power to both quantum PAC and quantum PAC with separable measurements. We discuss two results: the equivalence of entangled and separable measurements for boolean function classes and a separation of QSQ and noisy quantum PAC learning. Our main technical contributions are lower bounds on QSQ learning.
We split our talk into two parts; this is part I.:
Part I.
- Motivates QSQ, describes the model in detail and outlines the main results.
- Discusses the equivalence of function learning by separable vs. entangled measurements.
- Outlines a basic proof strategy for QSQ lower bounds.
Copyright. All Rights Reserved.