Metraipolis › archive › dc_1187e614ef4b
Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries — arXiv:2609.38403
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.38403
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:47:12.253Z
- SHA-256 of the archived text
cf0dd4f2cc4ab37b15052ead2e9e30bcd276bd241cc0087ff319b1c93ad1399d- Stable URL of this page
https://metraipolis.com/documento/dc_1187e614ef4b
How to cite
Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries — arXiv:2609.38403 — arXiv (en), https://arxiv.org/abs/2609.38403 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1187e614ef4b (Metraipolis archive dc_1187e614ef4b, sha256 cf0dd4f2cc4ab37b15052ead2e9e30bcd276bd241cc0087ff319b1c93ad1399d)
BibTeX
@misc{dc1187e614ef4b,
title = {Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries — arXiv:2609.38403},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.38403},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1187e614ef4b; sha256 cf0dd4f2cc4ab37b15052ead2e9e30bcd276bd241cc0087ff319b1c93ad1399d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38403. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Whether quantum computation can reduce the amount of data sampled from an unknown probability distribution required to learn a prediction rule is a fundamental question in quantum machine learning. Quantum PAC learning studies this question using quantum data as a quantum state whose squared amplitudes encode the unknown distribution from which classical learning data are sampled. With only copies of such quantum data, the optimal worst-case sample complexity asymptotically matches that of classical PAC learning. In contrast, access to both a state-preparation unitary for this state and its inverse can improve the query-complexity dependence on the accuracy parameter in realizable learning. However, it has remained unclear whether forward-only access allows such an improvement. In this work, taking the worst case over compatible state-preparation unitaries and their finite ambient dimensions, we show that the optimal forward-only query complexities of realizable and agnostic learning are, respectively, $\Theta((d+\log(1/\delta))/\varepsilon)$ and $\Theta((d+\log(1/\delta))/\varepsilon^2)$, where $d$ is the VC dimension of the concept class, $\varepsilon$ the accuracy parameter, and $\delta$ the failure probability. These bounds match the optimal sample complexities with classical data or quantum data copies. To prove them, we establish a reduction using $q$ copies of the prepared state to approximate the Haar-averaged output of any $q$-query forward-only algorithm. These results show that forward-only access cannot provide an asymptotic query-complexity advantage over learning from classical data or quantum data copies in this worst-case setting, and establish the essential role of inverse access in the known realizable-setting improvement. Our reduction also provides a new framework for analyzing limitations of forward state-preparation access via state-copy lower bounds. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LG). Categorie arXiv: Quantum Physics (quant-ph) ; Machine Learning (cs.LG); Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2609.38403 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T13:18:10.562Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).