Name
Abstract | ||
|---|---|---|
We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate â in other words, does an analogue of Razâs parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called anchoring, inspired in part by the Feige-Kilian transformation, that turns any (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3055399.3055433 | STOC |
Keywords | Field | DocType |
Entangled games,parallel repetition,hardness amplification | Discrete mathematics,Combinatorial game theory,Quantum,Combinatorics,Exponential function,Quantum entanglement,Computer science,Anchoring,Quantum pseudo-telepathy,Completeness (statistics),Conjecture | Conference |
ISSN | Citations | PageRank |
0737-8017 | 2 | 0.38 |
References | Authors | |
31 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammad Bavarian | 1 | 24 | 3.59 |
| Thomas Vidick | 2 | 377 | 31.69 |
| Henry Yuen | 3 | 2 | 0.38 |