  Over decades traditional information theory of source and channel coding
advances toward learning and effective extraction of information from data. We
propose to go one step further and offer a theoretical foundation for learning
classical patterns from quantum data. However, there are several roadblocks to
lay the groundwork for such a generalization. First, classical data must be
replaced by a density operator over a Hilbert space. Hence, deviated from
problems such as state tomography, our samples are i.i.d density operators. The
second challenge is even more profound since we must realize that our only
interaction with a quantum state is through a measurement which -- due to
no-cloning quantum postulate -- loses information after measuring it. With this
in mind, we present a quantum counterpart of the well-known PAC framework.
Based on that, we propose a quantum analogous of the ERM algorithm for learning
measurement hypothesis classes. Then, we establish upper bounds on the quantum
sample complexity quantum concept classes.
