dorsal/arxiv
View SchemaA Quantum Computational Learning Algorithm
| Authors | Dan Ventura, Tony Martinez |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9807052 |
| URL | https://arxiv.org/abs/quant-ph/9807052 |
Abstract
An interesting classical result due to Jackson allows polynomial-time learning of the function class DNF using membership queries. Since in most practical learning situations access to a membership oracle is unrealistic, this paper explores the possibility that quantum computation might allow a learning algorithm for DNF that relies only on example queries. A natural extension of Fourier-based learning into the quantum domain is presented. The algorithm requires only an example oracle, and it runs in O(sqrt(2^n)) time, a result that appears to be classically impossible. The algorithm is unique among quantum algorithms in that it does not assume a priori knowledge of a function and does not operate on a superposition that includes all possible states.
{
"annotation_id": "b25af5df-6950-4019-a981-0c92e0043262",
"date_created": "2026-03-02T18:02:44.350000Z",
"date_modified": "2026-03-02T18:02:44.350000Z",
"file_hash": "b5d4c34fc0423d84fc6135e1a9a0b762810b991fb3c82f2f10e0894957136362",
"private": false,
"record": {
"abstract": "An interesting classical result due to Jackson allows polynomial-time\nlearning of the function class DNF using membership queries. Since in most\npractical learning situations access to a membership oracle is unrealistic,\nthis paper explores the possibility that quantum computation might allow a\nlearning algorithm for DNF that relies only on example queries. A natural\nextension of Fourier-based learning into the quantum domain is presented. The\nalgorithm requires only an example oracle, and it runs in O(sqrt(2^n)) time, a\nresult that appears to be classically impossible. The algorithm is unique among\nquantum algorithms in that it does not assume a priori knowledge of a function\nand does not operate on a superposition that includes all possible states.",
"arxiv_id": "quant-ph/9807052",
"authors": [
"Dan Ventura",
"Tony Martinez"
],
"categories": [
"quant-ph"
],
"title": "A Quantum Computational Learning Algorithm",
"url": "https://arxiv.org/abs/quant-ph/9807052"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c132881e-d907-476d-8f60-c9cea41d57fe",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}