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.
Part II.
- Part I. outlined a basic proof strategy for QSQ lower bounds. Here we give more detail about the QSQ lower bound proof.
- Introduces the main result: separation of QSQ and QPAC with noise.
- More on the lower bounding technique.
- Applications of QSQ?
Copyright. All Rights Reserved.