Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes

We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their probably approximately correct (PAC) learnability, along with corresponding sample complexity bounds, in the setting where the learner is given access only to prepared quantum states. We first show that the empirical risk minimization (ERM) rule proposed in previous work is not universal, nor does uniform convergence of the empirical risk characterize learnability. Moreover, we show that VC dimension generalization bounds in previous work are in many cases infinite, even for measurement classes defined on a finite-dimensional Hilbert space and even for learnable classes. To surmount the failure of the standard ERM to satisfy uniform convergence, we define a new learning rule—denoised empirical risk minimization. We show this to be a universal learning rule for both classical probabilistically observed concept classes and quantum measurement classes, and the condition for it to satisfy uniform convergence is finite fat shattering dimension of the class. The fat shattering dimension of a hypothesis class is a measure of complexity that intervenes in sample complexity bounds for regression in classical learning theory. We give sample complexity upper and lower bounds for learnability in terms of finite fat shattering dimension and approximate finite partitionability into approximately jointly measurable subsets. We link fat shattering dimension with partitionability into 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.