Quantum versus Classical Learnability.
S. Gortler and R. Servedio.
Sixteenth Annual Conference on Computational Complexity (CCC), 2001, pp. 138-148.


Abstract:

Motivated by recent work on quantum black-box query complexity, we consider quantum versions of two well-studied models of learning Boolean functions: Angluin's model of exact learning from membership queries and Valiant's 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.


Postscript or pdf.


A combined version which also includes results from ICALP 01 paper appeared as Equivalences and Separations between Quantum and Classical Learnability in SIAM Journal on Computing 33(5), 2004, pp. 1067-1092.


Postscript or pdf.


Back to main papers page