Learning in Finitely-Sampled Quantum Systems 1: Expressive Capacity*

Quantitative insight into the meaningful computational capacity of current quantum platforms is critical to efforts in quantum machine learning and sensing. We introduce an intuitive notion of expressive capacity in terms of the space of functions that can be computed, and develop a mathematical framework for analyzing the capacity of qubit-based systems in the presence of sampling noise. We obtain a tight bound for the expressive capacity of a given quantum system under S shots, and present the mathematical construction of an optimal measurement basis that is robust to sampling noise. We apply this analysis to learning through a quantum annealer-based continuous encoding and parameterized quantum circuits, highlighting how quantum correlations and system size influence the expressive capacity in the presence of sampling noise.