Name
Abstract | ||
|---|---|---|
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 or classical queries required for learning. These results contrast known results that show that testing black-box functions for various properties, as opposed to learning, can require exponentially more classical queries than quantum queries. We also show that, under a widely held computational hardness assumption (the intractability of factoring Blum integers), 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. For the model of exact learning from membership queries, we establish a stronger separation by showing that if any one-way function exists, then there is a class of functions which is polynomial-time learnable in the quantum setting but not in the classical setting. Thus, while quantum and classical learning are equally powerful from an information theory perspective, the models are different when viewed from a computational complexity perspective. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1137/S0097539704412910 | SIAM J. Comput. |
Keywords | Field | DocType |
pac learning,boolean function,exact learning,classical learnability,quantum setting,quantum computation,computational learning theory,learning model,membership query,classical learning,polynomial-time learnable,quantum query,quantum version,query com- plexity,classical query,computational complexity,quantum computer,one way function,polynomial time,information theory | Boolean function,Combinatorics,Algebra,Probably approximately correct learning,Computer science,Quantum computer,Quantum sort,Quantum algorithm,Computational learning theory,Learnability,Sample exclusion dimension | Journal |
Volume | Issue | ISSN |
33 | 5 | 0097-5397 |
Citations | PageRank | References |
12 | 0.78 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rocco A. Servedio | 1 | 1656 | 133.28 |
| Steven J. Gortler | 2 | 4205 | 366.17 |