Hardness amplification for entangled games via anchoring
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.
2-s2.0-85024397567
Massachusetts Institute of Technology
University of California, Berkeley
2017-06-19
New York, NY, USA
9781450345286
Part F128415
303
316
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
Montreal, Canada | 2017-06-19 - 2017-06-23 | ||
| Funder | Funding(s) | Grant Number | Grant URL |
NFS | PHY-1125565 | ||
NSF Physics Frontiers Center | |||
NSF | 1122374,1218547,1650733,CCF-0939370,CCF-1420956,CCF-1553477 | ||
| Show more | |||