 Author
 Year
 2017
 Title
 Optimal quantum sample complexity of learning algorithms
 Journal
 Leibniz International Proceedings in Informatics
 Volume
 79
 Article number
 25
 Number of pages
 31
 Document type
 Article
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

In learning theory, the VC dimension of a concept class C is the most common way to measure its "richness." A fundamental result says that the number of examples needed to learn an unknown target concept c 2 C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model Ω dd ϵ + log(1/δ) ϵ examples are necessary and sufficient for a learner to output, with probability 1δ, a hypothesis h that is ϵclose to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c 2 C, we know that Ω d d ϵ2 + log(1/δ) ϵ2 examples are necessary and sufficient to output an hypothesis h 2 C whose error is at most ϵ worse than the error of the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson [18], who showed that quantum examples are more powerful than classical examples in some fixeddistribution settings. However, At and Servedio [10], improved by Zhang [55], showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is dd1 ϵ + d + log(1/δ) ϵ for arbitrarily small constant > 0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple informationtheoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/ϵ) factor. We then give a second approach that avoids the logfactor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.
 URL
 go to publisher's site
 Other links
 Link to publication in Scopus
issue contents  Language
 English
 Note
 32nd Computational Complexity Conference : CCC 2017, July 69, 2017, Riga, Latvia.
Edited by Ryan O'Donnell.
ISBN 9783959770408  Permalink
 http://hdl.handle.net/11245.1/3a8a509aef4445a8bbf26e4b1c534303
 Downloads
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.