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.
lower bound learning vc dimension pac (probably approximately correct) quantum algorithm computational complexity