Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry (2017) Parallel repetition via fortification: analytic view and the quantum case. In: 8th Innovations in Theoretical Computer Science Conference. Leibniz International Proceedings in Informatics. No.67. Dagstuhl Publishing , Art. No. 22. ISBN 9783959770293. https://resolver.caltech.edu/CaltechAUTHORS:20160321-071142064
![]() |
PDF
- Published Version
Creative Commons Attribution. 731kB |
![]() |
PDF
- Submitted Version
See Usage Policy. 369kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160321-071142064
Abstract
In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.
Item Type: | Book Section | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||
Additional Information: | © 2017 Mohammad Bavarian, Thomas Vidick, and Henry Yuen; licensed under Creative Commons License CC-BY. Date of publication: 28.11.2017. The author was supported by NSF under CCF-0939370 and CCF-1420956. The author was supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, and the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). The author was supported by Simons Foundation grant #360893, and National Science Foundation Grants 1122374 and 1218547. | ||||||||||||||||||||||
Group: | Institute for Quantum Information and Matter | ||||||||||||||||||||||
Funders: |
| ||||||||||||||||||||||
Subject Keywords: | Parallel repetition, quantum entanglement, non-local games | ||||||||||||||||||||||
Series Name: | Leibniz International Proceedings in Informatics | ||||||||||||||||||||||
Issue or Number: | 67 | ||||||||||||||||||||||
Classification Code: | 1998 ACM Subject Classification: F.1.3 Complexity Measures and Classes | ||||||||||||||||||||||
DOI: | 10.4230/LIPIcs.ITCS.2017.22 | ||||||||||||||||||||||
Record Number: | CaltechAUTHORS:20160321-071142064 | ||||||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20160321-071142064 | ||||||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||
ID Code: | 65499 | ||||||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||||||
Deposited By: | Ruth Sustaita | ||||||||||||||||||||||
Deposited On: | 24 Mar 2016 20:33 | ||||||||||||||||||||||
Last Modified: | 10 Nov 2021 23:46 |
Repository Staff Only: item control page