Optimal Quantum Sample Complexity of Learning Algorithms
  $ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a
concept class $C$ is the most common way to measure its "richness." In the PAC
model $$ \Theta\Big(\frac{d}{\eps} + \frac{\log(1/\delta)}{\eps}\Big) $$
examples are necessary and sufficient for a learner to output, with probability
$1-\delta$, a hypothesis $h$ that is $\eps$-close to the target concept $c$. In
the related agnostic model, where the samples need not come from a $c\in C$, we
know that $$ \Theta\Big(\frac{d}{\eps^2} + \frac{\log(1/\delta)}{\eps^2}\Big)
$$ examples are necessary and sufficient to output an hypothesis $h\in C$ whose
error is at most $\eps$ worse than the best concept in $C$.
  Here we analyze quantum sample complexity, where each example is a coherent
quantum state. This model was introduced by Bshouty and Jackson, who showed
that quantum examples are more powerful than classical examples in some
fixed-distribution settings. However, Atici and Servedio, improved by Zhang,
showed that in the PAC setting, quantum examples cannot be much more powerful:
the required number of quantum examples is $$
\Omega\Big(\frac{d^{1-\eta}}{\eps} + d + \frac{\log(1/\delta)}{\eps}\Big)\mbox{
for all }\eta> 0. $$ Our main result is that quantum and classical sample
complexity are in fact equal up to constant factors in both the PAC and
agnostic models. We give two approaches. The first is a fairly simple
information-theoretic argument that yields the above two classical bounds and
yields the same bounds for quantum sample complexity up to a $\log(d/\eps)$
factor. We then give a second approach that avoids the log-factor loss, based
on analyzing the behavior of the "Pretty Good Measurement" on the quantum state
identification problems that correspond to learning. This shows classical and
quantum sample complexity are equal up to constant factors.
