A Parallel Repetition Theorem for the GHZ Game
A Parallel Repetition Theorem for the GHZ Game
复制标题
DOI：
--
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Justin Holmgren;R. Raz
中科院分区：
文献类型：
--
作者：
Justin Holmgren;R. Raz
我们证明了平行重复的（3人）GHZ游戏多项式快速减少游戏的值为0。也就是说，并行重复$t $次的GHZ博弈的值至多为$t ^{-\Omega（1）}$。以前，只有一个界$\approx\frac {1}{\alpha（t）}$，其中$\alpha $是逆阿克曼函数，是已知的。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^{-\Omega(1)}$. Previously, only a bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ 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.