高 XEB 分数能证明不可信量子采样器什么？

高分不等于采样正确

随机电路采样实验给设备一个 n 量子比特上的随机电路 C，要求它返回按理想输出分布 p(z) = |<z|C|0^n>|^2 抽取的字符串 z，共 N = 2^n 个结果。由于用完整分布检验少量样本不可行，样本改用线性交叉熵基准（XEB）打分：经典计算机计算返回字符串 z1,...,zk 的理想概率，并报告平均值 (N/k) sum_i p(zi)。论文采用未平移约定 B = 1 + F_XEB，其中 F_XEB 是实验 XEB 保真度。

两个参考分数锚定了尺度。均匀随机字符串的期望分数为 1，因为理想概率之和为 1。诚实采样器的期望分数为 N sum_z p(z)^2，即理想分数，对随机电路约为 2。2019 年的实验报告约为 1.002。

促使这篇论文的差距在于，得分高不等于采样正确。一个知道 p 且总是返回最可能字符串的设备，其得分会远高于诚实采样器——对 Haar 随机态约为 ln N，当 n = 60 时约为 42，而诚实采样器约为 2——尽管其输出完全可预测。因此论文追问：高交叉熵分数究竟能证明不可信量子设备的什么性质，并聚焦于认证随机性。

理想分数充当 Tsirelson 界

论文在量子查询模型中工作，并把理想分数刻画为高效设备的 Tsirelson 界。在贝尔实验中，量子策略赢得 CHSH 博弈的概率至多为 cos^2(pi/8) ≈ 0.854，即 Tsirelson 界；在该界上，即使以公开输入和对手的量子寄存器为条件，任一方的输出比特仍携带一比特最小熵。其缺点是两个设备不能通信，而只接收比特的用户无法验证这一条件。

这里研究的替代方案通过复用采样实验，用单个设备认证随机性。验证者发送挑战电路，设备必须快速用样本作答，验证者随后检查其 XEB 分数。称为 Eve 的对手可能制造了该设备，可能与其共享纠缠，并可能在事后获知电路。即使理想样本对 Eve 也不是完全不可预测的，因为知道电路让她能猜出其最可能的输出。

论文的结果与 CHSH 类比紧密对应。对于进行 o(N^(1/3)) 次查询的算法，理想分数表现得像 Tsirelson 界：这类算法超过它的幅度不超过 o(1)，而 O(N^(1/3)) 次查询足以以常数幅度超过它。只进行一次查询的诚实采样器，在算法进行约 N^(1/3) 次查询之前，一直保持到 o(1) 意义下的最优。

以常数幅度超过理想分数需要 N^(1/3) 次查询

定理 1.1 给出了超过理想分数的查询代价。对于有 N 个结果的傅里叶采样，进行至多 q 次查询的算法满足 B(A) ≤ 3 + O(q^(3/2)/sqrt(N) + q^3/N)。特别地，期望分数为 3 + epsilon（0 < epsilon ≤ 4）需要 q ≥ (3 epsilon / 16)^(2/3) N^(1/3)。对于通过规范 oracle O_phi 访问的 Haar 随机态，B(A) ≤ 2N/(N+1) + O(q^(3/2)/sqrt(N) + q^3/N)；在 Haar 随机酉访问下，同样的界成立，但多一项 O(q log N / sqrt(N))。因此，期望分数为 2 + epsilon（0 < epsilon ≤ 1）在规范 oracle 下需要 Omega(epsilon^(2/3) N^(1/3)) 次查询；当 N 相对于 epsilon 足够大时，在 Haar 随机酉访问下也是如此。

这些界是紧的。Kre21 的 O(N^(1/3)) 查询算法的一个变体——论文称之为平方算法——进行 O(N^(1/3)) 次查询，对傅里叶采样的期望分数至少为 5 - o(1)，对两种 Haar 访问形式的期望分数至少为 3 - o(1)。因此，对傅里叶采样中每个固定的 b 属于 (3,5)，以及对两种 Haar 访问形式中每个固定的 b 属于 (2,3)，达到 B(A) ≥ b 的查询复杂度都是 Theta(N^(1/3))，其中下界中的常数依赖于 b。

论文指出，这证明了此前关于 Haar 随机态的一个猜想，并将其推广到傅里叶采样。论文还给出一个具体尺度：在 N^(1/4) 次查询处，此前下界仍允许常数优势，而分数与理想分数之差保持在 O(N^(-1/8)) 以内；期望傅里叶分数为 4 需要超过 0.32 N^(1/3) 次查询，当 n = 60 时超过 3 x 10^5 次。

平方算法解释了 1/3 指数的来源

平方算法抽取 m 个理想样本并存储结果。存储集合的总概率量级为 m/N，振幅放大把再多一个理想样本落入其中的概率提升到接近 1。这花费 m + O(sqrt(N/m)) 次查询，当 m = N^(1/3) 时为 O(N^(1/3))。更可能的结果被更频繁地存储，而按 p 在落入存储集合条件下分布的放大样本，又再次偏向它们。结果输出 z 的概率近似正比于 p(z)^2，这解释了该名称。

输出分布正比于 p(z)^2 的采样器得分为 N sum_z p(z)^3 / sum_z p(z)^2，即相邻矩之比；对近似高斯的傅里叶系数为 15/3 = 5，对近似指数的 Haar 概率为 6/2 = 3。为达到这些分数，该变体运行固定次数的放大步骤，并针对存储集合的典型概率进行调参。该算法与寻找碰撞的量子算法结构相同，后者的查询复杂度也是 N^(1/3)，但论文表示不知道两个问题之间存在归约。

分数的提升并非来自存储样本中的重复结果——当 m = N^(1/3) 时它们以高概率互不相同——而是来自放大样本与其中一个样本的巧合。平方算法的输出分布接近碰撞分布 r_p(z) = p(z)^2 / sum_y p(y)^2，即从 p 独立抽取两个样本、在它们相等的条件下其公共值的分布。该算法以平均全变差距离 O(N^(-1/3)) 采样该分布。

接近理想的分数证明几乎所有输出比特

定理 1.2 讨论接近理想的分数能证明多少随机性。对于傅里叶采样以及通过规范态制备 oracle 访问的 Haar 随机态，进行多项式次查询且分数与理想分数相差 o(1) 的设备，其 n 比特输出具有 n - O(log n) 比特平滑最小熵，即使面对与设备纠缠并在事后获知 oracle 的对手也是如此。论文称这近乎最优。

该保证以平滑参数为 o(1) 的平滑最小熵表述，这是提取器可以直接使用的量。论文将其与此前单轮保证中邻近态约 gamma n 比特的冯·诺依曼熵，以及使用熵累积的多轮保证进行对比。对于没有量子边信息的傅里叶样本列表，此前的保证是整个列表 n/40 比特。

设定上的两点差异很重要。第一，在这篇论文中 Eve 获知 oracle 本身；在此前模型中，设备查询 C' = VCW，其中 V 施加独立随机相位，W 是在与 |0^n> 正交的子空间上 Haar 随机且固定 |0^n> 的变换，Eve 获知 C，而 V 和 W 保持秘密。论文表示，对于获知完整 Haar 随机酉的 Eve，它没有相应结果。第二，该结果覆盖了面对纠缠 Eve 的傅里叶采样，而此前只对表现为诚实采样器的设备分析过。论文称两组结果互补：此前的结果从任何对经典界的违反中证明常数比例的随机性，而这些结果在分数与理想分数相差 o(1) 时证明除 O(log n) 比特外的全部随机性。

进展度量限制设备获得优势的速度

两个下界都依赖进展度量，它们限制超过理想分数的幅度，且每次查询只略微增加。对于傅里叶采样，论文像压缩 oracle 技术那样纯化随机函数的选择。在此表示中，纯化寄存器的基态由 {0,1}^n 的子集索引，称为记录集，每次查询至多改变记录集中的一个点。记录点的数量本身不是有用的度量，因为算法可以记录许多点而不超过诚实采样器的分数；重要的是这些点如何排列。

在诚实采样器中，输出为 z 的那部分态在 Hadamard 基态 |chi_z> = H^{tensor n}|z> = N^(-1/2) sum_x (-1)^(z·x)|x> 中恰好记录一个点。要得更高分，输出分支必须具有以其 Hadamard 基态系数移除一对点的非零振幅。该度量是相干移除这类对的振幅范数；比较一次查询前后的对移除，会留下另一个待移除的记录点，系数为 O(1/sqrt(N))。

对于 Haar 随机态，自然的类比是统计重复振幅，如 alpha_z^2 或 |alpha_z|^2，但归一化 sum_z |alpha_z|^2 = 1 的每一项都重复一个振幅，尽管该和是常数。论文改为在概率单纯形上的正交多项式中展开态，在该展开中归一化具有零阶，并使用 Dirichlet 正交多项式展开中平均阶数的平方根，由一个观测效应的精确恒等式控制。论文解释说，此前方法止步于 N^(1/4)，因为归约到 |phi> 的普通副本会在统计任何碰撞之前引入 q 的二次代价；避免这一损失需要对查询本身进行论证，因为查询对态的影响是相干的，不留下算法学到了什么的经典记录。

认证止于何处以及该比较什么

论文明确指出，从定理到可部署协议还隔着若干步骤。当前设备运行在远离随机性定理所需区域的地方：2019 年实验得分约 1.002，而理想分数约 2，而定理 1.2 需要亏损小到平滑参数 eta ≤ 1/2。对于这类设备，论文称 AH23 的保证才是相关的。所有结果都在 oracle 模型中，论文称这是无条件下保证的代价。定理还假设对被认证那一次运行的期望分数有界，而协议观察有限样本的经验分数、以通过测试为条件，并运行多轮。此外，挑战来自真正随机的 oracle 而非短种子，因此论文不声称随机性扩展。对于 Haar 随机态，结果需要规范 oracle O_phi 而非酉访问。

最具决策相关性的比较，是两种认证机制之间的比较，而非两个分数之间的比较。进行多项式次查询且分数与理想分数相差 o(1) 的设备，具有 n - O(log n) 比特平滑最小熵，平滑参数为 o(1)，因此 Eve 的实际猜测概率至多为 2^(-n + O(log n)) + eta = o(1)。而进行 O(N^(1/3)) 次查询的设备可以反过来达到理想分数，同时 Eve 以约 1/2 的概率猜中，论文将其画作把平方算法与 Eve 已知的输出混合的类比。区分这两种机制的阈值是分数亏损：随机性保证是在亏损小到 eta ≤ 1/2 时表述的，而不是当前硬件中约 1.002 对 2 的差距。因此，比较采样实验的读者应当追问：设备位于该亏损的哪一侧，以及所援引的保证是 AH23 的常数比例认证，还是这里证明的近乎全熵认证。

本文引用的文献