2014/11/05 by Kai-Min Chung, Chung, Kai-Min, Xiaodi Wu +3
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1411.1397
openalex publication_date 2014/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a strong parallel repetition theorem for the entangled value of\nmulti-player, one-round free games (games where the inputs come from a product\ndistribution). Our result is the first parallel repetition theorem for\nentangled games involving more than two players. Furthermore, our theorem\napplies to games where the players are allowed to output (possibly entangled)\nquantum states as answers.\n More specifically, let G be a k-player free game, with entangled value\n\val^*(G) = 1 - \ε. We show that the entangled value of the\nn-fold repetition of G, \val^*(G\⊗ n), is at most (1 -\n\ε)\Ω(n/k2). In the traditional setting of k=2 players, our\nparallel repetition theorem is optimal in terms of its dependence on \ε\nand n. For an arbitrary number of players, our result is nearly optimal: for\nall k, we exhibit a k-player free game G and n > 1 such that\n\val^*(G\⊗ n) \≥ \val^*(G)n/k. Hence, exponent\nof the repeated game value cannot be improved beyond \Ω(n/k).\n Our parallel repetition theorem improves on the prior results of [Jain, et\nal. 2014] and [Chailloux, Scarpa 2014] in a number of ways: (1) our theorem\napplies to a larger class of games (arbitrary number of players, quantum\noutputs); (2) we demonstrate that strong parallel repetition holds for the\nentangled value of free games: i.e., the base of the repeated game value is 1\n- \ε, rather than 1 - \ε2; and (3) there is no dependence of\nthe repeated game value on the input and output alphabets of G. In contrast,\nit is known that the repeated game value of classical free games must depend on\nthe output size. Thus our results demonstrate a seperation between the behavior\nof entangled games and classical games.\n