Multipartite entanglement in XOR games
Multipartite entanglement in XOR games
复制标题
DOI：
10.26421/qic13.3-4-11
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
J. Briët;H. Buhrman;Troy Lee;Thomas Vidick
中科院分区：
文献类型：
--
作者：
J. Briët;H. Buhrman;Troy Lee;Thomas Vidick
我们研究异或游戏背景下的多方纠缠。特别是，我们研究了纠缠偏差和经典偏差的比率，它衡量了量子或经典策略相对于均匀随机策略的最大优势。对于两人 XOR 游戏的情况，Tsirelson 证明了该比率的上限是著名的格洛腾迪克常数。相比之下，佩雷斯-加西亚等人。证明了纠缠态的存在，在三人异或游戏中，量子玩家比传统玩家拥有无限的优势。我们证明，当今文献中最常见的多部分纠缠态只能导致比经典偏差大一个常数因子的偏差。这些状态包括 GHZ 状态、任何局部单位等价于 GHZ 和不同参与者子集之间共享的最大纠缠状态（例如稳定器状态）的组合的状态，以及对于任意幅度 αi 形式的 Σiαi|i>... |i> 形式的 GHZ 状态的概括。我们的结果产生了以下令人惊讶的结果：经典的三人 XOR 游戏不遵循 XOR 并行重复定理，即使是非常弱的定理。除此之外，我们还讨论了我们的结果对通信复杂性和近似难度的影响。我们的证明基于 Blei 和 Tonge 以及 Carne 提出的 Grothendieck 不等式扩展的新颖应用，概括了 Tsirelson 使用 Grothendieck 不等式来限制两人 XOR 游戏的偏差。
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Perez-Garcia et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.