Srinivasan Arunachalam: Optimal quantum sample complexity of learning algorithms

Опубликовано 1 февраля 2017, 0:59

We tightly determine the minimal sample complexity of learning algorithms that try to learn a target concept from quantum examples, which are the superposition-version of classical random examples. We study both the Probably Approximately Correct (PAC) and the agnostic model of learning. We prove a tight lower bound on the number of examples needed, as a function of the VC dimension of the concept class involved and the error parameters. This function coincides with the known characterizations of classical sample complexity, showing that classical and quantum sample complexity are equal up to constant factors for every concept class, both in the PAC model and in the agnostic model. We have two proof approaches, one based on quantum information theory, and one based on analysis of the properties of the Pretty Good Measurement.