Agnostic learning of qudit stabilizer states

技术摘要：Qudit 稳定子态的不可知学习 (Agnostic Learning of Qudit Stabilizer States)

问题陈述
本文探讨了高效学习未知量子态的经典描述这一基本任务。虽然学习任意态会受到维度诅咒的影响，但学习结构化态（如稳定子态）则是可行的。然而，现有的稳定子态算法通常运行在“可实现”（realizable）设置下，即假设未知态与理想稳定子态完全匹配。在现实场景中，噪声会使目标态偏离这种理想结构。这激发了不可知学习（agnostic learning）问题：给定未知态 $|\psi\rangle$ 的副本，该态与某个未知的稳定子态的保真度为 $\tau$，目标是输出一个稳定子态 $|\phi\rangle$，使得 $F(|\psi\rangle, |\phi\rangle) \ge \max_{|\phi'\rangle \in \mathcal{C}} F(|\psi\rangle, |\phi'\rangle) - \varepsilon$，其中 $\mathcal{C}$ 是稳定子态类。

虽然 Chen 等人 [STOC '25] 最近解决了比特系统（$d=2$）的这一问题并使用了稳定子引导框架（stabilizer bootstrapping framework），但对于qudit 系统（其局部维度 $d > 2$ 为奇素数）的问题在很大程度上仍未得到探索。直接推广比特技术会失败，原因在于 Weyl 算符的行为以及测量结果分布存在根本性的结构差异。

方法论与关键技术
作者通过克服三个主要的数学挑战，将稳定子引导框架推广到了 qudit 系统：

1. 标准 Bell 差分采样（Bell Difference Sampling）的失效： 在比特系统中，Bell 差分采样产生来自 Weyl 分布 $q_\psi$ 的样本。在 qudit 系统中，直接推广会产生一种扭曲的分布，无法收敛于稳定子群。作者采用了偏斜 Bell 差分采样（skewed Bell difference sampling，由 Allcock 等人 [23] 在可实现设置中引入）。该协议使用一个由模 $d$ 的二次剩余构造的纠缠幺正算符来处理四个态的副本。为了处理不可知设置中联合分布的复杂性，作者分析了单个输出字符串的边缘分布 $B_\psi$。

2. 边缘分布的反集中性（Anti-Concentration）： 引导过程的一个关键要求是采样分布必须在当前已知子群之外的稳定子群元素上放置足够的质量（反集中性）。作者证明，对于目标稳定子群 $S$ 的任何真子空间 $T$，边缘分布满足 $\sum_{x \in S \setminus T} B_\psi(x) \ge \Omega(\tau^6)$。

   • 核心见解： 该证明通过将问题归约为单 qudit 情况，绕过了针对一般 $d$ 所需的复杂多元优化。他们利用单 qudit 稳定子态构成复投影 2-设计且构成 $d+1$ 个相互无偏基（MUBs）这一事实，建立了单 qudit 态稳定子保真度的下界（$2/(d+1)$）。

3. Weyl 算符的非厄米性： 在比特设置中，Weyl 算符是厄米的，允许通过伯努利均值估计高效地进行相关性批估计。对于 qudit ($d>2$)，Weyl 算符通常是非厄米的，这使得 $\langle \psi | W_x | \psi \rangle$ 为复数。作者通过解决这个问题，利用 SWAP 测试 单独估计平方相关性 $|\langle \psi | W_x | \psi \rangle|^2$，而不是依赖于厄米观测量。

算法框架
所提出的算法遵循迭代的稳定子引导程序：

1. 采样： 执行偏斜 Bell 差分采样以从边缘分布 $B_\psi$ 中获得 Pauli 字符串。
2. 过滤： 估计采样字符串与当前工作态的平方相关性。保留“高相关性”字符串（那些相关性 $> 1 - 1/(12d^2)$ 的字符串）。
3. 基构造： 从交换的（commuting）高相关性字符串中形成一个基。如果该基是不完整的（不能生成完整的稳定子群），反集中性性质确保了以 $\Omega(\tau^6)$ 的概率采样到一个位于当前扩张之外的新稳定子元素。
4. 引导： 如果发现低相关性的稳定子元素，则在其本征基下测量态并进行后选择。这会使保真度相对于目标稳定子态得到常数倍的放大。
5. 迭代： 重复此过程，使用放大的态直到识别出完整的稳定子群。

此外，对于高保真度机制（$\tau > \cos^2(\pi/8)$），作者提出了一个精简算法。他们证明，在此机制下，稳定子群内部的 Weyl 算符平方相关性与外部的平方相关性在数值上有严格的分离。这允许采用直接的基于阈值的方法，从而绕过迭代引导机制，实现多项式复杂度。

结果与复杂度
本文提出了第一个用于不可知学习纯态 qudit 稳定子态（$d > 2$ 素数）的高效量子算法。

• 一般机制： 给定一个未知的 $n$-qudit 态，其稳定子保真度为 $\tau$，算法能以高概率输出一个保真度至少为 $\tau - \varepsilon$ 的稳定子态。

  • 样本复杂度： $O(n \log n) \cdot (d/\tau)^{O(d^2 \log(1/\tau))} + O(d/\varepsilon^2 \log^2(1/\tau))$。
  • 时间复杂度： $O(n^3/\varepsilon^2) \cdot (d/\tau)^{O(d^2 \log(1/\tau))}$。
  • 当 $\tau = 1/\text{poly}(n)$ 时，复杂度为拟多项式（quasi-polynomial），与已知的最佳比特算法结果相匹配。

• 高保真度机制 ($\tau > \cos^2(\pi/8) + \gamma$)：

  • 样本复杂度： $O(d^4 n \log n / \gamma^2)$。
  • 时间复杂度： $O(n^3 + n^2 d^4 \log n / \gamma^2)$。
  • 该机制允许多项式时间解法。

• 推论：

  • 魔力估计（Magic Estimation）： 该算法能够高效估计量子态的“魔力”（通过稳定子保真度量化），具有加性误差 $\varepsilon$。
  • 列表解码（List-Decoding）： 该方法可以扩展到输出所有保真度 $\ge \tau$ 的稳定子态列表。

意义与主张
作者声称这项工作通过将比特结果扩展到 qudit，完成了不可知学习稳定子态的图景。其重要性在于：

1. 弥补差距： 提供了第一个在 qudit 设置下进行不可知学习的高效解法，此前由于在推广 Bell 差分采样方面的结构性障碍，该问题一直处于开放状态。
2. 鲁棒性： 该算法旨在处理噪声（不可知设置），使其适用于现实的量子系统，其中态并非完美的稳定子。
3. 基础工具： 本文建立了关于偏斜 Bell 差分采样的新的反集中性界限，并利用 2-设计属性证明了单 qudit 稳定子保真度的下界，这些成果可能具有独立的实用价值。
4. 魔力量化： 通过实现对稳定子保真度的有效估计，这项工作为量化量子魔力（作为量子优势的关键资源）提供了一个实用的工具。

作者指出，目前的结果仅限于奇素数维度，将结果扩展到复合维度或混合态仍是一个开放的挑战。他们还强调，对 $1/\tau$ 的拟多项式依赖是与比特算法共同面临的限制，在保持对 $n$ 和 $1/\varepsilon$ 的多项式依赖的同时将其改进为多项式时间，是一个重大的开放性问题。