技术摘要：自适应性就是你所需要的：仅使用单副本测量的最优稳定器学习

1. 问题陈述

稳定器态（Stabilizer states）是量子纠错、容错计算以及高效经典模拟的基础。一个核心的操作性问题是，如何根据实验数据高效地识别一个未知的 $n$ 位量子比特稳定器态。

先前的研究确立了取决于测量策略的显著样本复杂度差异：

• 两副本 Bell 采样： Montanaro [9] 表明，使用对两副本进行联合 Bell 测量，$\Theta(n)$ 个副本足以学习一个稳定器态。这是信息论最优的。
• 非自适应单副本测量： 文献 [10] 证明，如果测量被限制在单副本且必须是非自适应的（即独立于之前的测量结果），则样本复杂度会跃升至 $\Omega(n^2)$。

本研究解决的开放性问题是：自适应单副本测量（即当前测量基的选择取决于之前的测量结果）是否可以消除这一二次方差距，在不需要同时对多个副本进行相干访问的情况下，实现最优的 $\Theta(n)$ 缩放。

2. 方法论

核心算法：自适应稳定器学习

作者提出了一种多项式时间算法（算法 1），该算法仅使用 $\Theta(n)$ 个单副本自适应测量即可学习任意 $n$ 位量子比特稳定器态。该算法依赖于经典反馈，逐步将未知状态转化为计算基态。

关键机制：

1. 初始化： 从恒等 Clifford 电路 $C = I$ 开始。目标是找到一个 Clifford $C$，使得 $C|\psi\rangle = |z\rangle$，其中 $|z\rangle$ 是一个计算基态。
2. 迭代轮次： 在每一轮中，算法在当前变换后的状态 $C|\psi\rangle$ 的两个独立副本上进行计算基测量，获得结果 $x$ 和 $y$。
3. 差异采样： 计算按位差值 $u = x + y$。对于稳定器态，如果 $u \neq 0$，该向量将识别出一个在计算基下非对角的稳定器生成元的 $X$ 部分。
4. 自适应更新：
   • 算法识别一个枢轴索引 $i$，使得 $u_i = 1$。
   • 应用基于 CNOT 的 Clifford 操作 $F_u$，将识别出的稳定器映射为形式 $(e_i, v')$。
   • 至关重要的是，$F_u$ 保留了所有先前发现的对角（$Z$ 型）稳定器，因为枢轴量子比特 $i$ 的选择使得现有的 $Z$ 型稳定器在其上作用为平凡操作。
   • 应用随机局部修正（$H_i$ 或 $H_i S_i$）以将新的稳定器转换为 $Z$ 型稳定器。
5. 终止： 该过程重复进行，单调增加已知的对角稳定器子空间的维度。一旦维度达到 $n$，该状态即变为计算基态，随后通过最终测量完全确定。原始状态通过 $|\psi\rangle = C^\dagger |z\rangle$ 恢复。

扩展

论文将此自适应机制扩展到了三种额外场景：

• 容错学习（Tolerant Learning）： 学习最接近混合或非稳定器输入 $\rho$ 的稳定器态，满足保真度 $F_{\text{stab}}(\rho) > \sqrt{2/3}$。算法生成候选列表并使用经典阴影（classical shadows）来估计保真度。
• 容错测试（Tolerant Testing）： 区分与稳定器态集合保真度 $\ge 1-\epsilon_1$ 和 $\le 1-\epsilon_2$ 的状态。
• 辅助记忆测试（Memory-Assisted Testing）： 使用 $k$ 个量子比特的相干量子记忆进行测试，插值于单副本（$k=0$）和两副本（$k=n$）区间。
• 低稳定器零度（Low Stabilizer Nullity）： 学习纯态，其稳定器零度为 $r$（即具有维度为 $n-r$ 的稳定器子空间的态），这包括由受限数量非 Clifford 门制备的 Clifford 电路态。

3. 核心贡献与结果

A. 最优单副本学习

主要结果证明了自适应性完全消除了单副本学习与两副本学习之间的差距。

• 定理 II.1： 使用 $N = O(n + \log(1/\delta))$ 个副本和仅有的自适应单副本测量，可以以概率 $1-\delta$ 学习一个未知的 $n$ 位量子比特稳定器态。
• 复杂度： 算法运行时间为多项式级 $O(n T^2)$，其中 $T = O(n + \sqrt{n \log(1/\delta)} + \log(1/\delta))$ 为轮数。
• 最优性： 这与已知的集体测量 $\Theta(n)$ 下界相匹配，证明了在这一设定下，不需要对多个副本进行相干访问即可实现最优的样本复杂度。

B. 容错学习与测试

• 容错学习（定理 III.1）： 对于输入 $\rho$，若 $F_{\text{stab}}(\rho) \ge f_0 > \sqrt{2/3}$，该算法输出一个与最优解保真度在 $\xi$ 之内的稳定器态，所需副本数为 $O(n + \xi^{-2}\log(1/\delta))$。
• 容错测试（定理 IV.1）： 作者提供了一个多项式时间测试器，用于区分 $F_{\text{stab}}(\rho) \ge 1-\epsilon_1$ 与 $F_{\text{stab}}(\rho) \le 1-\epsilon_2$ 的情况，其样本复杂度为 $O(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2} \log(1/\delta))$。这解决了关于使用单副本测量进行高效容错测试是否可行的开放问题。
• 下界： 论文确立了对于纯输入，$\Omega(n + \frac{\epsilon_2}{(\epsilon_2-\epsilon_1)^2})$ 个副本是必要的，从而证实了所提测试器的最优性。

C. 记忆-样本权衡

• 定理 V.1： 对于具有 $k$ 个量子比特记忆的稳定器测试，最优样本复杂度为 $\Theta(n - k + 1/\epsilon)$。
• 含义： 要实现亚线性样本复杂度（优于 $\Theta(n)$），必须存储几乎整个状态（$k \approx n$）。如果 $k=0$，复杂度为 $\Theta(n)$；如果 $k=n$，复杂度降至 $\Theta(1)$。

D. 学习低零度状态

• 定理 VI.1： 具有稳定器零度 $r$ 的状态（包括含有 $t$ 个 T 门的 $t$-掺杂态）可以使用 $O(2^r(n + \log(1/\delta)) + 2^r \epsilon^{-2}(r + \log(1/\delta)))$ 个副本进行学习。
• 机制： 自适应压缩的速度会减慢 $2^r$ 倍，因为只有 $2^{-O(r)}$ 比例的差异样本能揭示有效的稳定器方向。然而，“无害”的样本并不会破坏已存在的对角结构。

4. 重要性与主张

本文声称，仅靠经典自适应性就足以实现样本最优的稳定器学习，从而消除了对相干多副本访问的需求。这是一个重要的发现，因为：

1. 弥合差距： 它证明了非自适应单副本学习（$\Omega(n^2)$）与两副本 Bell 采样（$\Theta(n)$）之间的二次方分离，是由于非自适应限制造成的伪象，而非单副本测量的本质局限。
2. 实验可行性： 由于该算法仅需执行 Clifford 操作后对单副本进行计算基测量，因此它与当前的实验约束高度兼容，因为在这些约束下，相干多副本存储是非常困难的。
3. 结构性洞察： 该工作强调了稳定器学习是一个“自然的结构化设定”，在这种设定下，自适应性会产生根本性的差异。测量结果具有双重用途：既提供数据，又识别出能够简化状态且保留先前发现结构的变换。
4. 更广泛的背景： 作者指出，虽然自适应性在特定结构化任务（如玻色高斯高斯层析或稳定器学习）中有帮助，但对于一般混合态在迹距离下的统计层析，它并不能提供渐近优势。这项工作有助于划定自适应性在量子学习中何时发挥作用的边界。

论文最后提出了开放性问题，例如对于低零度状态，能否将对 $2^r$ 的乘性依赖转变为加性依赖，以及是否可以降低样本复杂度中的领先常数以匹配集体测量界限。