An improved lower bound on query complexity for quantum PAC learning |
| |
Authors: | Chi Zhang |
| |
Affiliation: | Department of Computer Science, Columbia University, New York, NY 10027, USA |
| |
Abstract: | 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 for ? accuracy and 1−δ 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 . |
| |
Keywords: | PAC (Probably Approximately Correct) learning Lower bound Quantum algorithm VC dimension Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|