Quantum data access and quantum processing can make certain classically
intractable learning tasks feasible. However, quantum capabilities will only be
available to a select few in the near future. Thus, reliable schemes that allow
classical clients to delegate learning to untrusted quantum servers are
required to facilitate widespread access to quantum learning advantages.
Building on a recently introduced framework of interactive proof systems for
classical machine learning, we develop a framework for classical verification
of quantum learning. We exhibit learning problems that a classical learner
cannot efficiently solve on their own, but that they can efficiently and
reliably solve when interacting with an untrusted quantum prover. Concretely,
we consider the problems of agnostic learning parities and Fourier-sparse
functions with respect to distributions with uniform input marginal. We propose
a new quantum data access model that we call "mixture-of-superpositions"
quantum examples, based on which we give efficient quantum learning algorithms
for these tasks. Moreover, we prove that agnostic quantum parity and
Fourier-sparse learning can be efficiently verified by a classical verifier
with only random example or statistical query access. Finally, we showcase two
general scenarios in learning and verification in which quantum
mixture-of-superpositions examples do not lead to sample complexity
improvements over classical data. Our results demonstrate that the potential
power of quantum data for learning tasks, while not unlimited, can be utilized
by classical agents through interaction with untrusted quantum entities.

研究利用交互式证明系统框架来进行量子学习的经典验证，通过 “混合超位置” 量子示例提出了针对求解量子难题的新的量子数据访问模型，并证明了经典验证器只需随机例子或统计查询访问，就能有效地验证量子学习。