Vojtěch Havlíček - Quantum Statistical Query Learning I of II - IPAM at UCLA
Presenter
October 19, 2023
Abstract
Recorded 19 October 2023. Vojtěch Havlíček of the IBM Thomas J. Watson Research Center presents "Quantum Statistical Query Learning I of II" at IPAM's Mathematical Aspects of Quantum Learning Workshop.
Abstract: 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.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule