dorsal/arxiv
View SchemaImproved Bounds on Quantum Learning Algorithms
| Authors | Alp Atici, Rocco A. Servedio |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0411140 |
| URL | https://arxiv.org/abs/quant-ph/0411140 |
| DOI | 10.1007/s11128-005-0001-2 |
| Journal | Quantum Information Processing, Vol. 4, No. 5, 355 - 386 (2005) |
Abstract
In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is $O(\frac{\log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$, where $\hat{\gamma}^{C}$ is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function from C using $O(\frac{\log |C| \log \log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$ quantum black-box queries. We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). We give positive and negative results on when the quantum and classical query complexities of these intermediate problems are polynomially related to each other. Finally, we improve the known lower bounds on the number of quantum examples (as opposed to quantum black-box queries) required for $(\epsilon,\delta)$-PAC learning any concept class of Vapnik-Chervonenkis dimension d over the domain $\{0,1\}^n$ from $\Omega(\frac{d}{n})$ to $\Omega(\frac{1}{\epsilon}\log \frac{1}{\delta}+d+\frac{\sqrt{d}}{\epsilon})$. This new lower bound comes closer to matching known upper bounds for classical PAC learning.
{
"annotation_id": "b398f6f1-0620-49ef-a032-009f29253263",
"date_created": "2026-03-02T18:02:13.282000Z",
"date_modified": "2026-03-02T18:02:13.282000Z",
"file_hash": "c5e55934322d5ec1126a26478c24bf6c7fa951deba637110e8a100ed1d9df6ba",
"private": false,
"record": {
"abstract": "In this article we give several new results on the complexity of algorithms\nthat learn Boolean functions from quantum queries and quantum examples.\n Hunziker et al. conjectured that for any class C of Boolean functions, the\nnumber of quantum black-box queries which are required to exactly identify an\nunknown function from C is $O(\\frac{\\log |C|}{\\sqrt{{\\hat{\\gamma}}^{C}}})$,\nwhere $\\hat{\\gamma}^{C}$ is a combinatorial parameter of the class C. We\nessentially resolve this conjecture in the affirmative by giving a quantum\nalgorithm that, for any class C, identifies any unknown function from C using\n$O(\\frac{\\log |C| \\log \\log |C|}{\\sqrt{{\\hat{\\gamma}}^{C}}})$ quantum black-box\nqueries.\n We consider a range of natural problems intermediate between the exact\nlearning problem (in which the learner must obtain all bits of information\nabout the black-box function) and the usual problem of computing a predicate\n(in which the learner must obtain only one bit of information about the\nblack-box function). We give positive and negative results on when the quantum\nand classical query complexities of these intermediate problems are\npolynomially related to each other.\n Finally, we improve the known lower bounds on the number of quantum examples\n(as opposed to quantum black-box queries) required for $(\\epsilon,\\delta)$-PAC\nlearning any concept class of Vapnik-Chervonenkis dimension d over the domain\n$\\{0,1\\}^n$ from $\\Omega(\\frac{d}{n})$ to $\\Omega(\\frac{1}{\\epsilon}\\log\n\\frac{1}{\\delta}+d+\\frac{\\sqrt{d}}{\\epsilon})$. This new lower bound comes\ncloser to matching known upper bounds for classical PAC learning.",
"arxiv_id": "quant-ph/0411140",
"authors": [
"Alp Atici",
"Rocco A. Servedio"
],
"categories": [
"quant-ph",
"cs.LG"
],
"doi": "10.1007/s11128-005-0001-2",
"journal_ref": "Quantum Information Processing, Vol. 4, No. 5, 355 - 386 (2005)",
"title": "Improved Bounds on Quantum Learning Algorithms",
"url": "https://arxiv.org/abs/quant-ph/0411140"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "483b4ead-4f47-49fe-a331-2e456fde7c34",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}