Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography

技术摘要：多体纠缠相对于量子通信的指数级优势

问题陈述
虽然已知二体量子纠缠在通信复杂度方面可以提供指数级的优势，但多体纠缠在分布式任务中的计算能力仍不为人所熟知。本文研究了在涉及多个空间分离的发送者和一个接收者的设定下，多体纠缠是否能够实现指数级的通信节省。具体而言，作者探讨了在没有预共享纠缠的情况下，真正的多体相关性（即无法简化为一系列二体相关性的相关性）与不受限制的量子通信相比，其差距如何。

方法论
作者引入了一个多体通信任务，称为多体隐藏匹配 ($mHM_n$) 及其布尔决策变体 多体布尔隐藏匹配 ($mBHM_n$)。

• 任务设置： 有 $m$ 个发送者（Alice们），每个发送者接收一个输入字符串 $x_r \in \{0, 1\}^n$，而一个接收者（Bob）接收一个作用于集合 $[n]$ 的完美匹配 $M$（或者对于布尔版本，是一个 $1/4$-部分匹配）。
• 目标： Bob 必须输出来自 $M$ 的一条边 $(i_\ell, j_\ell)$，以及所有发送者对应位的全局奇偶性：$\bigoplus_{r=1}^m (x_{r, i_\ell} \oplus x_{r, j_\ell})$。
• 对比的模型： 研究比较了各种资源模型下的通信复杂度：
  1. 带有预共享真正多体纠缠（GHZ 态）的经典通信。
  2. 在没有预共享纠缠的情况下，不受限制的量子通信。
  3. 带有共享随机性的经典通信。
• 分析工具：
  • 上界构建： 使用一种利用 $(m+1)$-体 GHZ 态的协议。发送者根据其输入进行局部幺正相位编码，并在傅里叶基下进行测量，将经典结果发送给 Bob。
  • 下界证明： 作者改编并扩展了二体隐藏匹配下界的技巧。对于无纠缠量子情况，他们采用了一种用于矩阵值函数的超收缩不等式（推广了 Kahn-Kalai-Linial 不等式），以分析输出分布与均匀分布的可区分性。

核心贡献与结果

1. 通信复杂度的指数级分离：

   • 带有多体纠缠时： 作者证明，如果发送者和接收者共享一个 GHZ 态，该任务可以通过每个发送者仅需 $O(\log n)$ 比特 的经典通信来解决。该协议利用多体相位相关性来编码局部输入，并在接收者处恢复全局奇偶性。
   • 不带预共享纠缠时： 相比之下，任何在没有预共享纠缠的情况下实现高成功概率的协议，都要求至少有一个发送者需要发送 $\Omega(\sqrt{n})$ 个量子比特 的通信，即使允许使用不受限制的量子通信也是如此。
   • 结果： 这确立了由经典通信辅助的多体纠缠与无辅助量子通信之间的指数级分离。值得注意的是，即使发送者与接收者共享二体纠缠，只要他们之间不共享真正的多体纠缠，该下界依然成立。

2. 在有界存储密码学中的应用：

   • 作者基于多体隐藏匹配问题构建了一个种子双源随机性提取器。该提取器通过两个独立的弱随机源和一个公共种子（一个匹配）来产生近乎均匀的输出。
   • 针对无纠缠对手的安全性： 该提取器对于拥有无纠缠量子侧信息的对手是安全的，前提是其存储容量为 $\sqrt{n}$ 的多项式级别。
   • 对纠缠对手的脆弱性： 如果对手拥有少量的预共享纠缠（具体而言，每个源拥有 $O(\log n)$ 个量子比特的纠缠存储），则该提取器可能会被破解。
   • 结果： 这确立了纠缠与无纠缠量子侧信息能力之间的指数级分离。破解该提取器需要多项式规模的无纠缠存储，但仅需指数级更小的纠缠存储。

意义与主张
本文声称识别出多体纠缠是一种比单纯的量子通信更强的信息处理资源。

• 通信范畴： 该工作表明，预共享 GHZ 纠缠不仅仅是量子通信的替代品，它能够实现不受限制的量子信道在没有此类资源的情况下无法实现的指数级节省。
• 密码学范畴： 研究结果阐明了有界存储密码学中的定性区别：针对无纠缠量子对手的安全性并不一定能扩展到拥有哪怕极少量预共享纠缠的对手。
• 范围： 作者将他们的密码学构建定位为一种“原理证明”而非优化的提取器，旨在主要展示纠缠与无纠缠侧信息之间的基本分离。

文章总结道，多体纠缠应被视为一种独特的计算资源，其力量超越了生成非定域相关性的范畴，为研究分布式计算任务和安全量子网络开辟了新的方向。