In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples.
-- Hunziker {\em et al.}~\cite{HMPPR} conjectured that for any class $C$ of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from $C$ is $O(\frac{\log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$, where $\hat{\gamma}^{C}$ is a combinatorial parameter of the class $C.$ We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class $C$, identifies any unknown function from $C$ using $O(\frac{\log |C| \log \log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$ quantum black-box queries.
-- We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). We give positive and negative results on when the quantum and classical query complexities of these intermediate problems are polynomially related to each other.
-- Finally, we improve the known lower bounds on the number of quantum examples (as opposed to quantum black-box queries) required for $(\eps,\delta)$-PAC learning any concept class of Vapnik-Chervonenkis dimension $d$ over the domain $\{0,1\}^n$ from $\Omega({\frac d n})$ to $\Omega(\frac{1}{\epsilon}\log \frac{1}{\delta}+d+\frac{\sqrt{d}}{\epsilon})$. This new lower bound comes closer to matching known upper bounds for classical PAC learning.