Journal
INFORMATION PROCESSING LETTERS
Volume 111, Issue 1, Pages 40-45Publisher
ELSEVIER
DOI: 10.1016/j.ipl.2010.10.007
Keywords
PAC (Probably Approximately Correct); learning; Lower bound; Quantum algorithm; VC dimension; Computational complexity
Categories
Funding
- National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [0829537] Funding Source: National Science Foundation
Ask authors/readers for more resources
In this paper, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. For a concept class with VC dimension d, the lower bound is Omega(1/epsilon(d(1-e) + log(1/delta))) for epsilon accuracy and 1 - delta confidence, where e can be an arbitrarily small positive number. The lower bound is very close to the best lower bound known on query complexity for the classical PAC learning model, which is Omega(1/epsilon(d + log(1/delta))) (c) 2010 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
