Unbounded degree overhead for Alice-conditioned quantum Bell certificates

技术摘要：Alice 条件量子 Bell 证书的无界度数开销

问题陈述
本文研究了在约束证书结构下，在 Navascués–Pironio–Acín (NPA) 层级内认证量子 Bell 界限的计算成本。具体而言，它研究了“Alice 条件”层级，其中每个平方和 (SOS) 项必须仅涉及 Alice 的一个测量问题。这种结构与编译后的非局域博弈以及特定的密码学健全性证明（例如“nice-SOS”路径）相关。核心问题在于：将证书限制为这种“单问题”结构，是否会对标准（无约束）证书的 SOS 分解度数造成有界的开销。作者重点研究了倾斜 CHSH (tilted-CHSH) 系列 Bell 泛函，该系列的标准证书已知在二级（level two）是精确的。

方法论
作者结合了分析构造、代数验证以及在半正定规划 (SDP) 和算子代数框架内的数值优化。

1. 层级与锥 (Hierarchies and Cones)： 研究比较了实数 Bell 空隙空间中的两个 SOS 证书锥：

   • $D_k$：标准 $k$ 度证书（总约减长度 $\le k$ 的词）。
   • $O_k$：Alice 条件 $k$ 度证书（由 Alice 的问题/回答索引的块中，长度 $\le k$ 的 Bob 词）。
     转换度数 $d_{std}$ 和 $d_{os}$ 被定义为认证特定界限 $\beta$ 所需的最小层级。

2. 分析反例 (无界开销)： 为了证明没有任何有限的条件层级包含所有标准二级证书，作者利用基于无穷二面体群 ($\mathbb{Z}_2 * \mathbb{Z}_2$) 正泛函的容许见证构造了反例。

   • 他们利用 Fejér 加权迹 (Fejér-weighted trace) 构造了一个将质量集中在特定 Bob 词上的正泛函。
   • 通过减去一个对应于权重为 $r_k \sim k^{-2}$ 的确定性 Bob 回应的秩一项，他们创建了一个见证，该见证在特定的倾斜参数 $\alpha \to 2$（趋向局部端点）时，违反了任何有限条件层级 $k$ 的正定性约束。
   • 该构造依赖于移动平均的 Gram 矩阵，其中秩一减法项仅在条件层级足够高时才保持半正定。

3. 区间上的精确证书： 相反，为了识别开销有界的机制，作者为特定的倾斜参数 $\alpha$ 区间构造了精确证书。

   • 最优面归约 (Optimal-Face Reduction)： 他们利用倾斜 CHSH 博弈的最优策略来识别矩矩阵的核 (kernel)。这通过将对偶证书搜索简化为在核的正交补上寻找半正定 (PSD) 矩阵。
   • 有理函数族： 对于区间 $\alpha \in [13/10, 3/2]$，他们对量子界限和策略核进行参数化。他们构造了一个连续的证书族，其 Gram 矩阵是度数为 20 的矩阵多项式。
   • Bernstein 正定性： 他们通过将这些多项式展开为 Bernstein 基并检查所有系数矩阵是否严格半正定，来验证它们在区间上的正定性。

4. 随机性认证： 本文将这些 Bell 界限的分离转化为设备无关的随机性认证。通过使用涉及猜测概率函数凹性的接触准则 (contact criterion)，他们表明 Bell 界限的分离直接意味着认证最小熵的分离。

主要贡献与结果

• 无界度数开销： 主要结果（定理 1）证明，对于倾斜 CHSH 系列，没有任何有限层级的 Alice 条件层级包含所有标准二级证书。具体而言，当倾斜参数 $\alpha$ 趋于局部端点 ($\alpha \to 2$) 时，所需的条件层级 $d_{os}$ 至少以 $\Omega((2-\alpha)^{-1/2})$ 的速度增长。

  • 对于任何整数 $k$，都存在一个倾斜参数 $\alpha_k$，使得标准证书在二级是精确的（$d_{std}=2$），但条件证书要求的层级严格大于 $k$（$d_{os} > k$）。
  • 这确立了“单问题”限制即使在存在低度数标准证书的情况下，也会导致代数资源的无界增加。

• 区间上的精确有限转换： 尽管在端点附近存在无界开销，但作者证明（定理 2）在连续区间 $\alpha \in [13/10, 3/2]$ 上，开销恰好为一个层级。

  • 对于该范围内的所有 $\alpha$，$d_{std} = 2$ 且 $d_{os} = 3$。
  • 这是通过使用经 Bernstein 正定性验证的显式有理函数证书族来证明的，证明了条件层级在该子系列中恰好在三级（level 3）闭合。

• 一级值的分离： 本文修正了之前关于一级等价性的说法。作者证明（定理 3.7）对于 $\alpha > 0$ 的倾斜 CHSH，标准一级值严格大于 Alice 条件一级值 ($\omega_{std}^1 > \omega_{os}^1$)。这是因为一级条件块通过（通过块标签）隐式包含了总度数为三的矩，而这在标准一级截断中是不存在的。

• 设备无关随机性： 作者展示了无界度数开销具有操作上的后果（定理 3）。对于一系列 $s_k \to 2$ 的 CHSH 值，使用条件层级 $k$ 认证的最小熵严格低于量子最优值，且在特定点处偏差超过 $10^{-3}$ 比特。这意味着没有任何有限的条件层级能认证整个针对量子侧信息的最佳 CHSH 随机性权衡。

• 对编译健全性的启示： 这些结果为编译非局域博弈健全性证明中的 “nice-SOS” 输入提供了定量障碍。在接近端点的倾斜界限下，用于精确 nice-SOS 证书的 Bob 词因子的度数必须随 $\Omega(\epsilon^{-1/2})$ 增长，这限制了此类证明处理任意倾斜时的效率。

意义与主张
本文声称区分了“普通 SOS 度数”与“由单问题证书结构所施加的资源”。它证明了由单问题证书结构驱动的结构性约束可以从根本上改变 NPA 层级的收敛特性，这在以密码学应用（编译博弈）为动机的场景中尤为重要。

• 主张的审慎性： 作者明确指出，他们并非声称编译协议安全性失效或有限密钥率失败。结果关注的是单轮认证方法的精度以及精确证书所需的代数度数。
• 开放问题： 作者承认，虽然证明了渐近下界为 $\Omega(\epsilon^{-1/2})$，但对于每个固定的亚临界倾斜，是否存在精确有限闭合的上限或证明仍是一个开放问题。数值饱和现象暗示了平方根增长，但尚未建立匹配该指数的严格上界。
• 文献修正： 本工作完善了对标准与条件层级关系的理解，特别修正了先前关于倾斜 CHSH 一级值相等的断言，并澄清了此处使用的原始 PVM 商与 POVM/localizer 过滤之间的区别。

综上所述，本文确立了虽然 Alice 条件层级在特定的参数机制下可以在低层级实现精确，但它们在量子集边界附近会遭受无界度数开销的影响，从而无法在精确认证任务中普遍取代标准层级。