Quantum Versus Classical Learnability

DSpace/Manakin Repository

Quantum Versus Classical Learnability

Citable link to this page


Title: Quantum Versus Classical Learnability
Author: Servedio, Rocco A.; Gortler, Steven

Note: Order does not necessarily reflect citation order of authors.

Citation: Servedio, Rocco A. and Steven J. Gortler. 2001. Quantum versus classical learnability. In Computational complexity: Proceedings of the 16th IEEE conference on computational complexity, June 18-21, 2001, Chicago, Illinois, ed. IEEE Conference on Computational Complexity, 138-148. Also published as Equivalences and separations between quantum and classical learnability. 2004. SIAM Journal on Computing 33(5): 1067-1092.
Full Text & Related Files:
Abstract: Motivated by work on quantum black-box query complexity, we consider quantum versions of two well-studied models of learning Boolean functions: Angluin's (1988) model of exact learning from membership queries and Valiant's (1984) Probably Approximately Correct (PAC) model of learning from random examples. For each of these two learning models we establish a polynomial relationship between the number of quantum versus classical queries required for learning. Our results provide an interesting contrast to known results which show that testing black-box functions for various properties can require exponentially more classical queries than quantum queries. We also show that under a widely held computational hardness assumption there is a class of Boolean functions which is polynomial-time learnable in the quantum version but not the classical version of each learning model; thus while quantum and classical learning are equally powerful from an information theory perspective, they are different when viewed from a computational complexity perspective.
Published Version: http://dx.doi.org/10.1109/CCC.2001.933881
Other Sources: http://siamdl.aip.org/dbt/dbt.jsp?KEY=SMJCAT&Volume=33&Issue=5
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2640574
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search