Unconditional Quantum PAC Learning Advantage in the Large Error Regime
Abstract
We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage λ(n) = n−ω(1), we construct a concept class that a polynomial-time quantum learner learns to agreement 1/2+λ(n) with success probability at least 1−1/nk. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement 1/2 + λ(n)/nk with success probability greater than 1/nk, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that NP nsubseteq BPP.
Related
- Comment on J.Qin et al., Unconditional and Robust Quantum Metrological Advantage beyond N00N States, PRL 130, 070801 (2023) and J.A. H. Nielsen et.al., Deterministic Quantum Phase Estimation beyond N00N States. PRL 130, 123603 (2023)
- Unconditional quantum advantage with noisy planar architectures
- Unconditional quantum advantage from a two-round CHSH problem in one dimension
- Exponential advantage in continuous-variable quantum state learning
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
BibTeX
@misc{oliveira2026unconditional,
title = {{Unconditional Quantum PAC Learning Advantage in the Large Error Regime}},
author = {Igor C. Oliveira},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23268},
eprint = {2610.23268},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23268},
}
RIS
TY - UNPB
TI - Unconditional Quantum PAC Learning Advantage in the Large Error Regime
AU - Igor C. Oliveira
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23268
UR - https://arxiv.org/abs/2610.23268
AB - We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage λ(n) = n^−ω(1), we construct a concept class that a polynomial-time quantum learner learns to agreement 1/2+λ(n) with success probability at least 1−1/n^k. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement 1/2 + λ(n)/n^k with success probability greater than 1/n^k, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that NP nsubseteq BPP.
ER -