技术摘要：重新征服高维量子态（Qudits）上的 Bell 采样

1. 问题陈述

Bell 采样是量子信息领域的一个基本原语，特别是在分析稳定器态（stabilizer states）和测量“魔性”（magic，即非稳定器资源）时。在量子比特（qubit, $d=2$）的情况下，Bell 采样（在 Bell 基下测量两个状态的副本）及其变体 Bell 差值采样（Bell difference sampling），能够高效地学习未知的稳定器态、测试稳定器属性，并区分伪随机态与 Haar 随机态。

然而，将这些技术推广到高维量子态（qudits, $d \geq 2$）已被证明非常困难。作者的前期工作（arXiv'24）表明，将 Bell 采样自然扩展到任意维度的做法是失败的：在广义 Bell 基下测量两个稳定器态的副本，可能会产生完全随机的输出，从而无法提供关于底层稳定器群（stabilizer group）的任何信息。这种失败源于转置映射（复共轭）不是完全正的（completely positive），且对于 $d > 2$，一个稳定器态 $|S\rangle$ 及其复共轭 $|S^*\rangle$ 并不一定通过一个简单的 Pauli 算符相关联，这与量子比特情况不同（在量子比特中，$|S^*\rangle = W_z |S\rangle$）。

本文解决的核心问题是：开发一种有用的高维量子态（所有维度 $d \geq 2$）的 Bell 采样推广方法，使其能够保留量子比特情况下的强大特性，特别是采样稳定器群生成元的能力。

2. 方法论与核心原语

作者提出了一种新的子程序——偏斜 Bell 差值采样（Skewed Bell Difference Sampling），它克服了自然扩展的局限性。其核心创新是基于拉格朗日四平方和定理的一个特定酉变换。

$B_R$ 酉算符

该方法依赖于作用在四个稳定器态 $|S\rangle^{\otimes 4}$ 副本上的酉算符 $B_R$。该酉算符由一个矩阵 $R \in \mathbb{Z}_d^{4 \times 4}$ 定义，该矩阵由非负整数 $a_1, a_2, a_3, a_4$ 构造，满足 $a_1^2 + a_2^2 + a_3^2 + a_4^2 = d-1$。
矩阵 $R$ 的构造方式使得 $R J R = -I \pmod d$，其中 $J$ 是辛模（symplectic module）上的对合映射（involution map）。

关键性质： 对于任何稳定器态 $|S\rangle$，酉算符 $B_R$ 将四个副本映射为其复共轭（在 Pauli 算符意义下）：
$$B_R |S\rangle^{\otimes 4} = P(S) |S^*\rangle^{\otimes 4}$$
其中 $P(S)$ 是依赖于 $|S\rangle$ 的 Pauli 算符。这种变换有效地“混合”了状态，使稳定器群与其复共轭对齐，这是成功采样的必要条件。

注：对于特定维度（例如 $-1$是二次剩余的素数$d$），可能只需要少于四个副本（例如 2 个副本，甚至在$d \equiv 1 \pmod 4$ 时只需 1 个副本）。

采样程序

完整的偏斜 Bell 差值采样算法步骤如下：

1. 准备 8 个状态 $|\psi\rangle$ 的副本。
2. 对其中 4 个副本应用酉算符 $B_R$，将其转化为 $|S^*\rangle^{\otimes 4}$（在 Pauli 算符意义下）。
3. 将变换后的副本与原始的 4 个副本进行配对。
4. 对每对 $(|S\rangle, |S^*\rangle)$ 执行标准的 Bell 采样。
5. 计算结果之间的差值。

所得分布（记作 $\hat{p}_\psi$）被证明支撑在无符号稳定器群 $Weyl(|\psi\rangle)$ 的正交补上。如果 $|\psi\rangle$ 是一个稳定器态，则样本在稳定器群本身内均匀分布。

3. 主要贡献与结果

本文证明了这种新原语可以将多项重要的基于量子比特的结果提升到所有维度 $d \geq 2$ 的高维量子态上。

A. 稳定器态学习与隐藏稳定器群问题

• 问题： 在给定状态副本的情况下，识别未知的稳定器态 $|S\rangle$ 或隐藏的稳定器群 $Weyl(|\psi\rangle)$。
• 结果： 作者提供了一个量子算法，能以高概率识别稳定器群，其样本复杂度为 $O(n)$，时间复杂度为 $O(n^3)$。
• 改进： 这优于 Hinsche, Eisert, 和 Carrasco [HEC26] 最近提出的傅里叶采样方法的样本复杂度，后者需要 $O(n \log d \max\{d, \epsilon^{-1}\})$ 个样本。新方法每次最多作用于 8 个副本（对于素数维度为 4 个），而之前的方法需要 $D$ 个副本（$D$ 可能为 $2d$），这使得处理大维度 $d$ 时更具可行性。

B. 稳定器大小性质测试

• 问题： 测试一个状态是否具有至少 $d^t$ 的稳定器大小（无符号稳定器群的基数），或者是否与任何此类状态相距 $\epsilon$ 远。
• 结果： 算法能在 $O(n^3/\epsilon)$ 时间内区分这些情况，使用 $O(n/\epsilon)$ 个样本。
• 意义： 这将 Grewal 等人 [GIKL25] 的量子比特结果推广到了任意维度。其分析涉及环 $\mathbb{Z}_d$ 上的子模（submodules），而非域（fields）上的向量空间，因此需要使用 Smith 标准型来分析样本的张成空间。

C. 掺杂 Clifford 电路与伪随机性测试

• 问题： 区分 Haar 随机态与 $t$-掺杂 Clifford 电路（带有 $t$ 个非 Clifford 门的 Clifford 电路）的输出。
• 结果： 作者证明，任何满足 $t < n/2$ 的 $t$-掺杂 Clifford 电路都无法生成伪随机态。
• 改进： 这为高维量子态上的伪随机性确立了 $n/2$ 个非 Clifford 门的下界。这相对于之前的针对高维量子态的界限（曾为 $O(\log_d n)$）是一个指数级的改进，并达到了量子比特中的最佳已知界限。该算法使用 $O(n)$ 个样本在 $O(n^3)$ 时间内区分这两种情况。

D. 耐受稳定器测试（Tolerant Stabilizer Testing）

• 问题： 判断一个状态的稳定器保真度是否至少为 $1-\epsilon_1$，或者至多为 $1-\epsilon_2$（其中 $\epsilon_1 < \epsilon_2$）。
• 结果： 本文提出了两种算法：
  1. 基于 POVM 的方法： 使用特定 POVM $\Pi_r^+$ 对 Gross-Nezami-Walter (GNW) 协议进行的扩展。
  2. 基于 Bell 采样的方法： 使用偏斜 Bell 差值采样及特定测量。
• 复杂度： 两者实现的样本复杂度大致为 $O(d^2 \epsilon_2 / (\epsilon_2 - \epsilon_1)^2)$。相比于 POVM 方法（需要 $2r$ 个副本，其中 $r$ 可能很大），Bell 采样方法需要的副本数较少（8 个），尽管 POVM 方法在某些维度下可能提供更广泛的有效参数范围。

4. 意义与主张

本文声称通过提供一种非平凡且简单的推广方式，成功“重新征服”了高维量子态上的 Bell 采样，并保留了量子比特情况下的实用性。

• 理论突破： 基于拉格朗日四平方和定理构造的酉算符 $B_R$ 被视为一个具有独立研究价值的原语，它解决了在高维情况下将稳定器态映射到其复共轭时的根本障碍。
• 统一性： 这项工作统一了所有维度 $d \geq 2$ 的稳定器态理论，超越了以往仅限于素数维度的限制。
• 高效性： 尽管处理环 $\mathbb{Z}_d$ 上的模具有更高的代数复杂度，但算法仍保持了与量子比特情况相当的多项式时间和样本复杂度（$O(n^3)$ 和 $O(n)$）。
• 伪随机性界限： 关于 $n/2$ 个非 Clifford 门是实现伪随机性的必要条件的结论，显著收紧了之前的界限，缩小了量子比特与高维量子态理论之间的差距。

作者强调，他们的结果严格基于新采样分布 $\hat{p}_\psi$ 的性质，而不依赖于未证实的猜想。他们明确指出，虽然耐受测试的样本复杂度比最佳量子比特结果高出一个 $d^2$ 的因子，但这代表了首次成功将此类耐受测试协议扩展到一般高维量子态。