CaltechAUTHORS
  A Caltech Library Service

Parallel repetition via fortification: analytic view and the quantum case

Bavarian, Mohammad and Vidick, Thomas and Yuen, Henry (2016) Parallel repetition via fortification: analytic view and the quantum case. . (Submitted) http://resolver.caltech.edu/CaltechAUTHORS:20160321-071142064

[img] PDF - Submitted Version
See Usage Policy.

361Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160321-071142064

Abstract

In a recent work, Moshkovitz [FOCS ’14] presented a transformation on 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1603.05349arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:March 18, 2016. Submitted on 17 Mar 2016. Work was supported by National Science Foundation grants CCF-0939370 and CCF-1420956. Work was partially supported by the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). Work was supported by Simons Foundation grant #360893, and National Science Foundation Grants 1122374 and 1218547. Work partially conducted while visiting the IQIM at Caltech.
Funders:
Funding AgencyGrant Number
NSFCCF-0939370
NSFCCF-1420956
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Physics Frontiers CenterPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
NSF1122374
NSF1218547
Record Number:CaltechAUTHORS:20160321-071142064
Persistent URL:http://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:24 Mar 2016 20:33

Repository Staff Only: item control page