{"id":"arxiv/2610.23268","url":"https://arxiv.org/abs/2610.23268","tags":["cs.CC","quant-ph"],"score":0,"title":"Unconditional Quantum PAC Learning Advantage in the Large Error Regime","domain":"cs.CC","source":"arxiv","authors":["Igor C. Oliveira"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-16","reactions":{}}