Exploring POVM Hypothesis Classes: Fat Shattering, Joint Measurability, and PAC Learnability

[Submitted on 21 Aug 2023]

Download a PDF of the paper titled “Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes” by Abram Magner and Arun Padakandla

Download PDF

Abstract: This paper characterizes learnability for quantum measurement classes by establishing necessary and sufficient conditions for their PAC learnability. It also provides corresponding sample complexity bounds in the setting where the learner has access only to prepared quantum states. The paper explores previous works on this setting and identifies limitations in the empirical risk definition and VC dimension generalization upper bounds. To overcome these limitations, a new learning rule called denoised ERM is introduced, which is shown to be a universal learning rule for POVM and probabilistically observed concept classes. The paper presents quantitative sample complexity upper and lower bounds for learnability in terms of finite fat-shattering dimension and approximate finite partitionability into approximately jointly measurable subsets. It also demonstrates that every measurement class defined on a finite-dimensional Hilbert space is PAC learnable. Several example POVM classes are used to illustrate the results.