Analysis of the sample complexity for PAC-learning functions defined over quantum states

A fundamental question in PAC learning is determining the number of labeled examples required to learn a concept class to a desired accuracy and confidence. In classical learning theory, this quantity is characterized by the VC-dimension, while several quantum generalizations have established analogous results when examples are provided in quantum superposition. In this work, we study a distinct quantum PAC-learning model in which concepts are functions acting on quantum states. We demonstrate that the VC-dimension, although still relevant, fails to fully capture the sample complexity of this model. To further characterize this setting, we develop a new lower bound on the required number of samples and establish an upper bound when the states in the domain are linearly independent. Remarkably, this upper bound has a form similar to the classical PAC-learning bound. We further examine a setting in which the learner receives more informative data and show that the limitations of the VC-dimension persist in this extended model.

Source: arXiv:2607.07572v1 - http://arxiv.org/abs/2607.07572v1 PDF: https://arxiv.org/pdf/2607.07572v1 Original Link: http://arxiv.org/abs/2607.07572v1