dorsal/arxiv
View SchemaQuantum DNF Learnability Revisited
| Authors | Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0202066 |
| URL | https://arxiv.org/abs/quant-ph/0202066 |
| Journal | Proc. of Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, p595-604 |
Abstract
We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^{3}/\epsilon + s^{2}/\epsilon^{2})$, where $s$ is the size of DNF formula and $\epsilon$ is the PAC error accuracy. If $s$ and $1/\epsilon$ are comparable, this gives a modest improvement over a previously known classical query complexity of $\tilde{O}(ns^{2}/\epsilon^{2})$. We also show a lower bound of $\Omega(s\log n/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF of size $s$ with $n$ inputs under the uniform distribution.
{
"annotation_id": "c4227d4b-a6e0-40de-ae12-3140600fe6ab",
"date_created": "2026-03-02T18:01:49.386000Z",
"date_modified": "2026-03-02T18:01:49.386000Z",
"file_hash": "4f8cab02bf6cec7010ccd9621260b1b56484a63052b492defd135fdee5210480",
"private": false,
"record": {
"abstract": "We describe a quantum PAC learning algorithm for DNF formulae under the\nuniform distribution with a query complexity of $\\tilde{O}(s^{3}/\\epsilon +\ns^{2}/\\epsilon^{2})$, where $s$ is the size of DNF formula and $\\epsilon$ is\nthe PAC error accuracy. If $s$ and $1/\\epsilon$ are comparable, this gives a\nmodest improvement over a previously known classical query complexity of\n$\\tilde{O}(ns^{2}/\\epsilon^{2})$. We also show a lower bound of $\\Omega(s\\log\nn/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF\nof size $s$ with $n$ inputs under the uniform distribution.",
"arxiv_id": "quant-ph/0202066",
"authors": [
"Jeffrey C. Jackson",
"Christino Tamon",
"Tomoyuki Yamakami"
],
"categories": [
"quant-ph"
],
"journal_ref": "Proc. of Computing and Combinatorics: 8th Annual International\n Conference, COCOON 2002, p595-604",
"title": "Quantum DNF Learnability Revisited",
"url": "https://arxiv.org/abs/quant-ph/0202066"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c156be6a-49a8-4a09-8454-491a331197b6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}