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 Ω(1ϵ(d1−e+log(1δ))) for ϵ   accuracy and 1−δ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 Ω(1ϵ(d+log(1δ))).

Research highlights► The query complexity in the quantum PAC learning model is almost the same as that in the classical PAC learning model. ► A quantum PAC learning algorithm can be considered as a POVM measurement. ► There exists a set of lower bounds on query complexity in the quantum PAC learning model.