  Although a concept class may be learnt more efficiently using quantum samples
as compared with classical samples in certain scenarios, Arunachalam and de
Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more
efficient than classical ones in the quantum PAC and Agnostic learning models.
They established lower bounds on sample complexity via quantum state
identification and Fourier analysis. In this paper, we derive optimal lower
bounds for quantum sample complexity in both the PAC and agnostic models via an
information-theoretic approach. The proofs are arguably simpler, and the same
ideas can potentially be used to derive optimal bounds for other problems in
quantum learning theory.
  We then turn to a quantum analogue of the Coupon Collector problem, a classic
problem from probability theory also of importance in the study of PAC
learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC,
2020) characterized the quantum sample complexity of this problem up to
constant factors. First, we show that the information-theoretic approach
mentioned above provably does not yield the optimal lower bound. As a
by-product, we get a natural ensemble of pure states in arbitrarily high
dimensions which are not easily (simultaneously) distinguishable, while the
ensemble has close to maximal Holevo information. Second, we discover that the
information-theoretic approach yields an asymptotically optimal bound for an
approximation variant of the problem. Finally, we derive a sharp lower bound
for the Quantum Coupon Collector problem, with the exact leading order term,
via the generalized Holevo-Curlander bounds on the distinguishability of an
ensemble. All the aspects of the Quantum Coupon Collector problem we study rest
on properties of the spectrum of the associated Gram matrix, which may be of
independent interest.
