Parallel repetition for the GHZ game: A simpler proof

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 [18]. 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 [15] 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 [7] 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
EditorsMary Wootters, Laura Sanita
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772075
DOIs
StatePublished - Sep 1 2021
Event24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 - Virtual, Seattle, United States
Duration: Aug 16 2021Aug 18 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume207
ISSN (Print)1868-8969

Conference

Conference24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021
Country/TerritoryUnited States
CityVirtual, Seattle
Period8/16/218/18/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • GHZ
  • Multi-player
  • Parallel repetition
  • Polynomial

Fingerprint

Dive into the research topics of 'Parallel repetition for the GHZ game: A simpler proof'. Together they form a unique fingerprint.

Cite this