Anchored Parallel Repetition for Nonlocal Games
We introduce a simple transformation on two-player nonlocal games, called "anchoring," and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige-Kilian transformation [SIAM J. Comput., 30 (2000), pp. 324-346], and has the property that if the quantum value of the original game G is v, then the quantum value of the anchored game G⊥ is 1 - (1 - α)2 · (1 - v), where α is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game G has quantum value 1. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.
2-s2.0-85129461935
Massachusetts Institute of Technology
California Institute of Technology
The Fu Foundation School of Engineering and Applied Science
2022
51
2
214
253
REVIEWED
OTHER
| Funder | Funding(s) | Grant Number | Grant URL |
NSERC | |||
AFOSR | FA9550-16-1-0495 | ||
Gordon and Betty Moore Foundation | GBMF-12500028 | ||
| Show more | |||