论文标题
GHz游戏的平行重复定理
A Parallel Repetition Theorem for the GHZ Game
论文作者
论文摘要
我们证明（3-玩家）GHz游戏的并行重复将快速的游戏的值降低到0。也就是说，在并行$ t $ times中重复的GHz游戏的值最多是$ t^{ - ω（1）} $。以前，只有$ \ frac {1} {α（t）} $的界限，其中$α$是倒数ackermann函数。 GHZ游戏最近由Dinur，Harsha，Venkat和Yuen确定为多玩家游戏，在该游戏中，所有现有的技术都证明了游戏平行重复的价值强大的界限。确实，为了证明我们的结果，我们使用了一种全新的证明技术。 Dinur，Harsha，Venkat和Yuen推测，在GHz游戏平行重复的价值上的进步可能会导致在多玩游戏游戏的并行重复问题的一般问题上进一步进步。他们建议，GHz问题分布中存在的强相关性代表了多玩家并行重复问题的“最难实例”。 研究GHz游戏并行重复的另一个动机来自量子信息领域。 GHZ游戏首先由Greenberger，Horne和Zeilinger推出，是研究量子纠缠研究的中心游戏，已在许多作品中进行了研究。例如，它用于测试量子纠缠和与设备无关的量子密码学。在这样的应用中，通常重复游戏以减少错误的可能性，因此，游戏的并行重复值可能很有用。
We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-Ω(1)}$. Previously, only a bound of $\approx \frac{1}{α(t)}$, where $α$ is the inverse Ackermann function, was known. The GHZ game was recently identified by Dinur, Harsha, Venkat and Yuen as a multi-player game where all existing techniques for proving strong bounds on the value of the parallel repetition of the game fail. Indeed, to prove our result we use a completely new proof technique. Dinur, Harsha, Venkat and Yuen speculated that progress on bounding the value of the parallel repetition of the GHZ game may lead to further progress on the general question of parallel repetition of multi-player games. They suggested that the strong correlations present in the GHZ question distribution represent the "hardest instance" of the multi-player parallel repetition problem. Another motivation for studying the parallel repetition of the GHZ game comes from the field of quantum information. The GHZ game, first introduced by Greenberger, Horne and Zeilinger, is a central game in the study of quantum entanglement and has been studied in numerous works. For example, it is used for testing quantum entanglement and for device-independent quantum cryptography. In such applications a game is typically repeated to reduce the probability of error, and hence bounds on the value of the parallel repetition of the game may be useful.
