Learning Noise-Robust Stabilizer Structure via Bell Sampling

技术摘要：通过 Bell 采样学习噪声鲁棒的稳定器结构

问题陈述
本文研究了在存在噪声的情况下，学习量子态稳定器结构（stabilizer structure）的挑战。虽然对于具有低“魔法值”（non-stabilizerness）的纯态，存在利用 Bell 采样进行高效学习的算法，但现实世界的设备产生的通常是噪声态。这些噪声态被建模为对理想纯态作用一个 Pauli 通道后的结果。一个关键问题是，噪声会破坏现有混合态学习算法所依赖的“强”稳定器对称性（即满足 $\sigma_i \rho = \pm \rho$ 的性质）；一个全秩的噪声态通常除了恒等算符外，不存在精确的 Pauli 稳定器。

作者提出学习噪声态的弱稳定器（weak stabilizer），其定义为与该态对易的 Pauli 算符集合（即 $\sigma_i \rho \sigma_i^\dagger = \rho$）。对于具有足够低错误概率的 Pauli 通道，噪声态的弱稳定器与底层理想纯态的稳定器群是相同的。目标是学习一个 $\epsilon$-近似的弱稳定器 $\tilde{S}$，使得 $S \subseteq \tilde{S}$ 且纯度损失 $\Delta\gamma(\tilde{S})$ 被 $\epsilon$ 所限制。

方法论
所提出的解决方案采用了一种查找器-验证器方案（finder–verifier scheme），通过迭代构建稳定器群。

1. Bell 采样与差分采样： 该算法使用 Bell 采样（在 Bell 基下测量两个状态的副本）来生成比特串。Bell 差分样本（对两个 Bell 样本进行 XOR 操作）被用于探测状态的 Pauli 支持（Pauli support）。在无噪声情况下，这些样本完全位于稳定器群的中心化子（centralizer）内。在噪声下，样本会落在该支持之外（即“坏样本”），从而破坏群结构。
2. 验证器（The Verifier）： 这是一个用于估计候选群 $\tilde{S}$ 的投影纯度 $\gamma_{\tilde{S}}$ 的子程序。至关重要的是，验证器在初始化时抽取一组 Bell 样本，并在所有自适应查询中重复使用这些样本。它保证了：如果提议的群更新导致纯度下降低于阈值 $\Delta\epsilon^-$，则接受该更新；如果下降超过 $\Delta\epsilon^+$，则拒绝该更新。这使得查找器可以在无需为验证提供新鲜样本的情况下进行自适应更新。
3. 查找器（The Finder）： 这是一个处理 Bell 差分样本批次以提议当前猜想 $\tilde{S}$ 更新的子程序。它通过后选择（仅保留与当前 $\tilde{S}$ 对易的样本）以及对样本跨度之根（radical，即样本跨度与其中心化子的交集）的分析，来处理由坏样本引起的破坏。
4. 特定机制策略： 算法根据噪声强度 $\lambda$ 和目标精度 $\epsilon$ 调整其策略：
   • 洁净机制（Clean Regime）： 当噪声非常弱时，单个足够大的样本批次包含足够的“好”样本，能够在“坏”样本破坏根之前支撑起目标结构。查找器一次性提议整个根。
   • 中间机制（Intermediate Regime）： 当噪声适中时，单个批次无法保证整个根都是有用的。相反，查找器从根中抽取随机元素并逐个向验证器提议。这会带来 $2^t$ 的运行时开销，但保持了样本复杂度的多项式量级。
   • 噪声机制（Noisy Regime）： 当噪声较高时，根受到了过度破坏。算法回归到“自顶向下”的方法，逐个提议单个 Bell 差分样本，导致 $2^{2t}$ 的开销。

主要贡献与结果
本文确立了在全局去极化噪声（以及具有更严格阈值的任意 Pauli 噪声）下学习稳定器结构的三种性能机制：

1. 洁净机制（多项式时间与样本）：

   • 条件： 对于全局去极化噪声，若 $\lambda \lesssim \min\{0.159, \frac{n\epsilon}{4t}\}$。
   • 成本： 样本和时间复杂度均为 $n, t$ 及 $1/\epsilon$ 的多项式级别。
   • 意义： 这填补了纯态学习器（仅在 $\lambda=0$ 时有效）与不可知学习器（即使在零噪声下也是指数级成本）之间的空白。

2. 中间机制（多项式样本，指数时间）：

   • 条件： 对于全局去极化噪声，若 $\lambda \lesssim 0.159$（约 $16\%$ 的总错误概率）。
   • 成本： 样本复杂度保持为多项式，但时间复杂度按 $O(2^t \cdot \text{poly}(\cdot))$ 缩放。
   • 意义： 该机制允许在噪声过高导致无法进入洁净机制时，仍能以多项式数量的副本进行学习，代价是增加经典处理时间。

3. 噪声机制（指数时间与样本）：

   • 条件： 对于任何 $\lambda < 1$（全局去极化）或 $\lambda < 1/2$（任意 Pauli）。
   • 成本： 时间和样本复杂度均按 $O(2^{2t} \cdot \text{poly}(\cdot))$ 缩放。
   • 意义： 这提供了一个鲁棒的后备方案，适用于任何低于状态变为最大混合态阈值的噪声水平，尽管其成本是指数级的。

对于任意 Pauli 噪声，阈值更为严格（随 $O(1/t)$ 缩放），但上述三种机制的结构依然存在。

意义与主张
本文声称提供了首个在噪声足够弱的情况下，从噪声混合态中学习稳定器结构的有效（关于 $n$ 和 $t$ 的多项式时间）方法。

• 弥合差距： 它填补了精确承诺学习器（仅在 $\lambda=0$ 时高效）与不可知层析成像（在所有 $\lambda$ 下均为指数成本）之间的理论鸿沟。
• 噪声鲁棒性： 通过针对“弱”稳定器而非“强”稳定器进行学习，该算法适用于那些精确稳定器已被噪声破坏的状态。
• 实际相关性： 作者指出，在早期容错设备中，逻辑态是受 Pauli 噪声影响的低魔法值态（例如来自校正操作的噪声）。学习稳定器结构及其关联的零度（nullity）$\nu$ 可以作为诊断设备非克利福德（non-Clifford）内容的手段，并实现底层纯态的压缩层析成像。
• 局限性： 作者谦虚地指出，推导出的阈值（如 $\lambda \approx 0.159$）是基于其分析的充分条件，未必是基本下界。他们还提到，恢复“理想”态需要已知噪声通道的信息，这属于未来的研究工作。