Quantum statistical query learning
  We propose a learning model called the quantum statistical learning QSQ
model, which extends the SQ learning model introduced by Kearns to the quantum
setting. Our model can be also seen as a restriction of the quantum PAC
learning model: here, the learner does not have direct access to quantum
examples, but can only obtain estimates of measurement statistics on them.
Theoretically, this model provides a simple yet expressive setting to explore
the power of quantum examples in machine learning. From a practical
perspective, since simpler operations are required, learning algorithms in the
QSQ model are more feasible for implementation on near-term quantum devices. We
prove a number of results about the QSQ learning model. We first show that
parity functions, (log n)-juntas and polynomial-sized DNF formulas are
efficiently learnable in the QSQ model, in contrast to the classical setting
where these problems are provably hard. This implies that many of the
advantages of quantum PAC learning can be realized even in the more restricted
quantum SQ learning model. It is well-known that weak statistical query
dimension, denoted by WSQDIM(C), characterizes the complexity of learning a
concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a
lower bound on the complexity of QSQ learning, and furthermore it is tight for
certain concept classes C. Additionally, we show that this quantity provides
strong lower bounds for the small-bias quantum communication model under
product distributions. Finally, we introduce the notion of private quantum PAC
learning, in which a quantum PAC learner is required to be differentially
private. We show that learnability in the QSQ model implies learnability in the
quantum private PAC model. Additionally, we show that in the private PAC
learning setting, the classical and quantum sample complexities are equal, up
to constant factors.
