Name
Abstract | ||
|---|---|---|
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(perpendicular to) is 1 - (1 - alpha)(2) center dot (1 - v), where alpha 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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/21M1405927 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
nonlocal games, quantum complexity theory, quantum information, parallel repetition, hardness amplification, gap amplification | Journal | 51 |
Issue | ISSN | Citations |
2 | 0097-5397 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammad Bavarian | 1 | 0 | 0.34 |
| Thomas Vidick | 2 | 377 | 31.69 |
| Henry Yuen | 3 | 33 | 9.52 |