Fat Shattering, Joint Measurability, and PAC Learnability of POVM
  Hypothesis Classes
Abram Magner Arun Padakandla
We characterize learnability for quantum measurement classes by establishing
matching necessary and sufficient conditions for their PAC learnability, along
with corresponding sample complexity bounds, in the setting where the learner
is given access only to prepared quantum states. We first probe the results
from previous works on this setting. We show that the empirical risk defined in
previous works and matching the definition in the classical theory fails to
satisfy the uniform convergence property enjoyed in the classical setting for
some learnable classes. Moreover, we show that VC dimension generalization
upper bounds in previous work are frequently infinite, even for
finite-dimensional POVM classes. To surmount the failure of the standard ERM to
satisfy uniform convergence, we define a new learning rule -- denoised ERM. We
show this to be a universal learning rule for POVM and probabilistically
observed concept classes, and the condition for it to satisfy uniform
convergence is finite fat shattering dimension of the class. We give
quantitative sample complexity upper and lower bounds for learnability in terms
of finite fat-shattering dimension and a notion of approximate finite
partitionability into approximately jointly measurable subsets, which allow for
sample reuse. We then show that finite fat shattering dimension implies finite
coverability by approximately jointly measurable subsets, leading to our
matching conditions. We also show that every measurement class defined on a
finite-dimensional Hilbert space is PAC learnable. We illustrate our results on
several example POVM classes.