Optimal Bounds for Quantum Learning via Information Theory
I will discuss our recent work on finding lower bounds to solve three problems in Quantum Learning Theory: Quantum PAC learning, Quantum Agnostic Learning and Quantum Coupon Collector. Our main goal was to use tools from Quantum Information Theory, specifically the data processing inequality, to obtain these results, instead of going for more exotic ones. We succeed in doing so for the first two problems, and we show concretely that it doesn't work for the last problem, due to an inherent loss of information that is possible even for valid learning algorithms, for which we give a bound using an alternate method that utilizes the analysis we went through previously. We hope that these tools are broadly applicable to other quantum learning problems.
Add event to calendar