  Recent years have seen significant activity on the problem of using data for
the purpose of learning properties of quantum systems or of processing
classical or quantum data via quantum computing. As in classical learning,
quantum learning problems involve settings in which the mechanism generating
the data is unknown, and the main goal of a learning algorithm is to ensure
satisfactory accuracy levels when only given access to data and, possibly, side
information such as expert knowledge. This article reviews the complexity of
quantum learning using information-theoretic techniques by focusing on data
complexity, copy complexity, and model complexity. Copy complexity arises from
the destructive nature of quantum measurements, which irreversibly alter the
state to be processed, limiting the information that can be extracted about
quantum data. For example, in a quantum system, unlike in classical machine
learning, it is generally not possible to evaluate the training loss
simultaneously on multiple hypotheses using the same quantum data. To make the
paper self-contained and approachable by different research communities, we
provide extensive background material on classical results from statistical
learning theory, as well as on the distinguishability of quantum states.
Throughout, we highlight the differences between quantum and classical learning
by addressing both supervised and unsupervised learning, and we provide
extensive pointers to the literature.
