License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.62
URN: urn:nbn:de:0030-drops-147551
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14755/
Go to the corresponding LIPIcs Volume Portal

Girish, Uma ; Holmgren, Justin ; Mittal, Kunal ; Raz, Ran ; Zhan, Wei

Parallel Repetition for the GHZ Game: A Simpler Proof

pdf-format:
LIPIcs-APPROX62.pdf (0.7 MB)

Abstract

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis.
The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting.
Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

BibTeX - Entry

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.62,
  author =	{Girish, Uma and Holmgren, Justin and Mittal, Kunal and Raz, Ran and Zhan, Wei},
  title =	{{Parallel Repetition for the GHZ Game: A Simpler Proof}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14755},
  URN =		{urn:nbn:de:0030-drops-147551},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.62},
  annote =	{Keywords: Parallel Repetition, GHZ, Polynomial, Multi-player}
}

Keywords: Parallel Repetition, GHZ, Polynomial, Multi-player
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI