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.

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

量子学习的经典验证

Classical Verification of Quantum Learning

Recent progress towards theoretical interpretability guarantees for AI has
been made with classifiers that are based on interactive proof systems. A
prover selects a certificate from the datapoint and sends it to a verifier who
decides the class. In the context of machine learning, such a certificate can
be a feature that is informative of the class. For a setup with high soundness
and completeness, the exchanged certificates must have a high mutual
information with the true class of the datapoint. However, this guarantee
relies on a bound on the Asymmetric Feature Correlation of the dataset, a
property that so far is difficult to estimate for high-dimensional data. It was
conjectured in W\"aldchen et al. that it is computationally hard to exploit the
AFC, which is what we prove here.
We consider a malicious prover-verifier duo that aims to exploit the AFC to
achieve high completeness and soundness while using uninformative certificates.
We show that this task is $\mathsf{NP}$-hard and cannot be approximated better
than $\mathcal{O}(m^{1/8 - \epsilon})$, where $m$ is the number of possible
certificates, for $\epsilon>0$ under the Dense-vs-Random conjecture. This is
some evidence that AFC should not prevent the use of interactive classification
for real-world tasks, as it is computationally hard to be exploited.

通过交互式证明系统和证明者选择一个具有信息量的证书的方式，以达到高完整性和声音，从而对具有高互信息的证书进行边际分析，区分高维数据集。进而证明 Asymmetric Feature Correlation 是难以计算利用的，从而推断它不会阻止交互分类用于现实任务。