Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > TOM GUR:
All reports by Author Tom Gur:

TR23-142 | 21st September 2023
Tom Gur, Wilfred Salmon, Sergii Strelchuk

Provable Advantage in Quantum PAC Learning

Revisions: 2

We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput.
1998, 28, 1136–1153]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution ... more >>>




ISSN 1433-8092 | Imprint