An improved lower bound on query complexity for quantum PAC learning

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.