A quadratic sample complexity reduction for agnostic learning via quantum algorithms

Using quantum algorithms, we obtain, for accuracy [Formula: see text] and confidence [Formula: see text] a new sample complexity upper bound of [Formula: see text] as [Formula: see text] for a general agnostic learning model, provided the hypothesis class is of finite cardinality. This greatly improves upon a corresponding sample complexity of asymptotic order [Formula: see text] known in the literature to be attainable by means of classical (non-quantum) algorithms for an agnostic learning problem also with hypothesis class of finite cardinality (see, for example, [S. Arunachalam and R. de Wolf, J. Mach. Learn. Res. 19 (2018) 1] and the classical statistical learning theory references cited there). Thus, for general agnostic learning, the quantum speedup in the rate of learning that we achieve with respect to these results is quadratic in [Formula: see text].