Analysis of the sample complexity for PAC-learning functions defined over quantum states

技术摘要：定义在量子态上的 PAC 学习函数的样本复杂度分析

问题陈述
本文研究了特定量子设定下概率近似正确（PAC）学习的样本复杂度。与以往提供经典状态叠加态（$|x\rangle|f(x)\rangle$）作为示例的量子泛化研究不同，本研究考虑了一种概念为直接作用于量子态上的函数的模型。在此框架下，实例空间 $\mathcal{X}$ 由希尔伯特空间 $\mathcal{H}$ 中的量子态 $|\psi\rangle$ 组成，学习者接收对 $(|\phi\rangle, c(|\phi\rangle))$，其中 $|\phi\rangle$ 采样自未知分布 $D$，而 $c$ 是一个未知的概念。目标是输出一个假设 $h$，使得误差 $\text{dist}_D(h, c)$ 以 $1-\delta$ 的概率不超过 $\epsilon$。

核心问题在于：在这一量子设定中，VC 维（$d$）——这一在经典 PAC 学习中唯一表征样本复杂度的指标——是否仍然足以表征样本复杂度。

方法论与框架
作者采用了针对量子输入调整的标准 PAC 学习定义。他们分析了样本复杂度 $t_{Q,C}(\epsilon, \delta)$ 与概念类及其底层状态空间的几何属性之间的关系。

关键方法论工具包括：

1. 对立对（Opposite Pairs）： 引入了相对于概念类的量子态“对立对”概念 $\{|\psi\rangle, |\psi'\rangle\}$，即存在两个概念 $c, c'$ 满足 $c(|\psi\rangle)=c'(|\psi'\rangle)=1$ 且 $c(|\psi'\rangle)=c'(|\psi\rangle)=0$。
2. 量子 Chernoff 距离： 使用量子 Chernoff 距离 $C_Q(\sigma, \rho) = -\ln \min_{s \in [0,1]} \text{Tr}(\sigma^s \rho^{1-s})$ 来量化由学习分布导出的诱导密度矩阵的可区分性。
3. 密度矩阵分析： 构建诱导密度矩阵 $\sigma^c_D = \mathbb{E}_{|\psi\rangle \sim D} [|\psi\rangle\langle\psi| \otimes |c(|\psi\rangle)\rangle\langle c(|\psi\rangle)|]$，以分析学习者可获得的信息。
4. 线性无关性： 分析定义域中的状态呈线性无关的情况，并利用这些状态的 Gram 矩阵 $G$ 进行分析。

主要贡献与结果

1. VC 维的局限性
本文证明了仅靠 VC 维不足以表征该量子设定下的样本复杂度。

• 命题 1： 如果一个概念类包含一对对立态，则样本复杂度的下界由涉及 $F$ 的项决定，其中 $F$ 是所有对立对中平方重叠度 $|\langle \psi | \psi' \rangle|^2$ 的上确界。具体而言，如果 $F=1$（意味着存在具有任意高重叠度的对立对），即使 VC 维有限，该概念类也是不可 PAC 学习的。
• 命题 3： 作者提供了一个反例（一个基于四个状态 $\{|0\rangle, |1\rangle, |+\rangle, |-\rangle\}$ 的概念类），其中 VC 维和 $-\ln F$ 均为有限值，但该类仍是不可学习的。这证明了对 $(d, F)$ 的描述也无法完全表征可学习性。

2. 通过 $\Lambda_C(\alpha)$ 实现的精细化下界
为了解决先前边界的局限性，作者引入了一个新的函数 $\Lambda_C(\alpha)$，该函数基于在全变差距离接近的分布下，不同概念的诱导密度矩阵之间的量子 Chernoff 距离。

• 定理 1： 样本复杂度的下界为：
  $$t_{Q,C}(\epsilon, \delta) \geq c_L \left( \frac{d}{\epsilon} + \ln\frac{1}{\delta} \left( \frac{1}{\epsilon} + \frac{1}{\Lambda_C(3\epsilon)} \right) \right)$$
  该界限捕捉了 $\Lambda_C(\alpha) = 0$ 的情况，从而正确识别了不可学习的类。论文指出，$\Lambda_C(\alpha)$ 不能仅由常数 $B_C$（源自对立密度矩阵）来表征，因为 $\Lambda_C(\alpha)$ 的变化速率也会影响复杂度。

3. 线性无关状态的上界
作者为定义域状态呈线性无关的特定情况建立了上界。

• 定理 2： 如果定义域状态 $\{|\psi_i\rangle\}$ 是线性无关的，则该概念类是可 PAC 学习的，其样本复杂度为：
  $$t_{Q,C}(\epsilon, \delta) \leq c_U \left( \frac{d + \ln(1/\delta)}{\epsilon \lambda_{\min}(G)} \right)$$
  其中 $\lambda_{\min}(G)$ 是状态 Gram 矩阵的最小特征值。该结果在状态正交（$\lambda_{\min}(G)=1$）时恢复了经典界限，并表明复杂度与状态的线性无关程度成反比。

4. 多副本示例分析
论文考察了一种变体，即学习者接收 $k$ 个状态副本 $(|\phi\rangle^{\otimes k}, c(|\phi\rangle))$。

• 命题 8： 如果定义域是有限的，且选择足够大的 $k$（取决于定义域大小和重叠度），则状态变为线性无关，且样本复杂度与经典界限一致。
• 命题 9： 至关重要的是，即使允许 $k$ 依赖于 $\epsilon$ 和 $\delta$，仍然存在 VC 维有限但不可学习的概念类。当分布集中在对立对的重叠度趋近于 1 的边界处时，就会发生这种情况，这使得有限数量的副本不足以区分概念。

意义与主张
本文声称，从经典到量子 PAC 学习（即示例是量子态而非经典标签）的转变，从根本上改变了 VC 维与样本复杂度之间的关系。

• VC 维不再是一个完整的描述符；状态空间的几何属性（特别是重叠度和线性无关性）起着至关重要的作用。
• 函数 $\Lambda_C(\alpha)$ 被引入作为一个必要的参数来表征可学习性，它捕捉了特定分布下概念的不可区分性。
• 研究结果强调了使用经典描述可用与仅提供量子态之间的严格分离：在前者中，有限 VC 维保证了可学习性，但在后者中则未必如此，无论提供多少个副本（除非副本数趋于无穷大或定义域具有特定约束）。

研究结论指出，虽然在特定条件下（线性无关时）可以恢复经典界限，但要对量子样本复杂度进行通用表征，需要超越 VC 维的新度量标准。