Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations

技术摘要：模拟量子相关性的双向平均通信成本界限

问题陈述
由纠缠引起的贝尔非定域相关性无法在没有经典通信的情况下通过局部隐变量模型进行重现，尽管已知在固定的有限贝尔场景中，有限的通信足以模拟任何相关性，但确定用于精确模拟所需的最小通信量仍然是一个具有挑战性的问题。这在输入平均通信成本设定下尤为显著，即成本是基于输入分布和随机变量进行平均的，且允许使用变长且**完全交互（双向）**的协议。本文旨在解决以下问题：给定任意有限的通信预算，是否可以展示一种有限的量子相关性，其精确模拟必然会超过该预算，即使在这些放宽了的双向、变长条件下也是如此？

方法论
作者采用了两种互补的方法论途径来推导通信成本的下界：

1. 基于非定域游戏的界限：

   • 获胜矩形（完美获胜）： 对于以确定性获胜（伪遥测）的游戏，作者改编了标准的“矩形方法”。他们将“获胜矩形”定义为局部确定性策略可以获胜的输入对子 $S \times T$ 的子集。他们证明了最大获胜矩形概率 $\alpha$ 在平行重复下是乘性的（$\alpha_n = \alpha^n$）。通过将平均通信成本与通信树中叶节点分布的熵联系起来，他们推导出了每份拷贝 $\log_2(1/\alpha)$ 的下界。
   • 获胜概率（非完美获胜）： 对于不能确定获胜的相关性，作者利用基于实现获胜概率与经典极限之间相对熵的信息论论证。他们定义了一个基于二元相对熵 $D_{bin}(w \| \omega_c)$ 的函数 $\Phi_{\omega_c}(w)$。他们表明，对于具有乘积输入分布的平行游戏，总通信成本受限于这些函数在各拷贝上的总和。

2. 线性规划 (LP) 层级结构：

   • 意识到精确模拟成本可以表述为向确定性相关性凸分解的优化问题，作者引入了一个计算上可行的层级结构。
   • 他们根据最小输入平均通信成本（$\kappa_k$）对确定性相关性进行分组。
   • 下界： 在第 $L$ 层，该层级通过仅包含成本 $\le \kappa_L$ 的确定性相关性来最小化成本，同时将剩余的概率权重计入下一层级的成本 $\kappa_{L+1}$。
   • 上界： 通过将精确分解限制在成本 $\le \kappa_k$ 的确定性相关性中，获得互补的上界。
   • 该层级在最终层级收敛于精确的输入平均成本。如果上下界在较低层级一致，则无需枚举所有策略即可确定精确成本。

主要贡献与结果

• 魔方 (Magic Square, MS) 游戏：

  • 作者证明了在均匀输入下，精确模拟 $n$ 个平行拷贝的 MS 游戏需要 $n \log_2(3/2)$ 比特 的下界。这是基于最大获胜矩形最多覆盖 $2/3$ 输入空间的结论。
  • 他们构造了一个单向通信协议，该协议实现的渐近速率为每份拷贝 $\log_2(3/2)$ 比特。这表明允许双向交互并不会降低 MS 的渐近模拟速率。
  • 因此，对于任何给定的有限预算 $B$，都存在一个有限的拷贝数 $n \approx B / \log_2(1.5)$，使得精确模拟超过 $B$ 比特。

• 平行 CHSH 游戏：

  • 对于 $n$ 拷贝 CHSH 游戏，其量子相关性的获胜概率为 $w_T = (2+\sqrt{2})/4$（超过了经典的 $3/4$），作者推导出了一个下界 $n \times D_{bin}(w_T \| 3/4) \approx 0.04627n$ 比特。
  • 这一结果确立了即使对于不能完美获胜的相关性，其精确模拟成本也随 $n$ 线性增长，从而对于足够大的 $n$，会超过任何有限预算。
  • 作者指出，虽然他们的系数比之前的最坏情况单向界要小，但其结果适用于更通用的变长、完全交互的双向协议下的输入平均成本设定。

• 界限层级：

  • 所提出的 LP 层级结构在界限一致时可以恢复精确成本。
  • 针对小型贝尔场景（例如 $2 \times 2$ 输入/输出）的数值结果恢复了已知的精确成本（例如 CHSH 的 $\sqrt{2}-1 \approx 0.4142$）。
  • 对于更大的场景，层级的第 1 层提供了非平凡的下界，通常与 EPR2 非定域含量相匹配。

意义
本文声称肯定地回答了这样一个问题：是否存在有限的量子相关性，即使在允许变长、完全交互的双向协议的情况下，也需要超过任何给定有限预算的通信量。

• 显式的有限分离： 不同于以往仅保证在大 $n$ 时成本增长的渐近结果，这项工作提供了具体的有限拷贝相关性（特别是 MS 和 CHSH），其精确模拟成本严格超过任何给定的预算。
• 界限的紧致性： 对于魔方游戏，推导出的下界被证明在渐近意义上是紧致的，因为其被一个构造性的单向协议所匹配。这确定了其精确的渐近模拟速率为每份拷贝 $\log_2(3/2)$ 比特。
• 方法论框架： 引入的 LP 层级结构提供了一种系统的方法，用于计算特定相关性的精确输入平均成本，而无需考虑所有可能的通信策略的无限空间，只要界限在计算可及的层级收敛。
• 鲁棒性： 这些界限适用于输入平均成本，而输入平均成本通常低于最坏情况成本，并且适用于完全交互的协议，这使得研究结果对于协议优化具有鲁棒性。

作者总结道，这些结果提供了一个框架，用于量化在有限贝尔场景中观察到的量子相关性所需的经典通信，这对于理解非定域性的强度以及有限交叉谈（cross-talk）下经典模型的局限性具有重要意义。