dorsal/arxiv
View SchemaQuantum versus Classical Learnability
| Authors | Rocco A. Servedio, Steven J. Gortler |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0007036 |
| URL | https://arxiv.org/abs/quant-ph/0007036 |
Abstract
We consider quantum versions of two well-studied classical learning models: Angluin's model of exact learning from membership queries and Valiant's Probably Approximately Correct (PAC) model of learning from random examples. We give positive and negative results for quantum versus classical learnability. For each of the two learning models described above, we show that any concept class is information-theoretically learnable from polynomially many quantum examples if and only if it is information-theoretically learnable from polynomially many classical examples. In contrast to this information-theoretic equivalence betwen quantum and classical learnability, though, we observe that a separation does exist between efficient quantum and classical learnability. For both the model of exact learning from membership queries and the PAC model, we show that under a widely held computational hardness assumption for classical computation (the intractability of factoring), there is a concept class which is polynomial-time learnable in the quantum version but not in the classical version of the model.
{
"annotation_id": "ca0e328e-6fe7-43ad-b6ec-fc90bf03f8ea",
"date_created": "2026-03-02T18:01:38.569000Z",
"date_modified": "2026-03-02T18:01:38.569000Z",
"file_hash": "485f8198a5720d054cc67d1622a07df383c0b2d10c03c081290496dc0550bd60",
"private": false,
"record": {
"abstract": "We consider quantum versions of two well-studied classical learning models:\nAngluin\u0027s model of exact learning from membership queries and Valiant\u0027s\nProbably Approximately Correct (PAC) model of learning from random examples. We\ngive positive and negative results for quantum versus classical learnability.\nFor each of the two learning models described above, we show that any concept\nclass is information-theoretically learnable from polynomially many quantum\nexamples if and only if it is information-theoretically learnable from\npolynomially many classical examples. In contrast to this information-theoretic\nequivalence betwen quantum and classical learnability, though, we observe that\na separation does exist between efficient quantum and classical learnability.\nFor both the model of exact learning from membership queries and the PAC model,\nwe show that under a widely held computational hardness assumption for\nclassical computation (the intractability of factoring), there is a concept\nclass which is polynomial-time learnable in the quantum version but not in the\nclassical version of the model.",
"arxiv_id": "quant-ph/0007036",
"authors": [
"Rocco A. Servedio",
"Steven J. Gortler"
],
"categories": [
"quant-ph"
],
"title": "Quantum versus Classical Learnability",
"url": "https://arxiv.org/abs/quant-ph/0007036"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e6b120a1-9a5d-4dd4-a4fa-e90448750bdc",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}