A Caltech Library Service

Three-Player Entangled XOR Games are NP-Hard to Approximate

Vidick, Thomas (2016) Three-Player Entangled XOR Games are NP-Hard to Approximate. SIAM Journal on Computing, 45 (3). pp. 1007-1063. ISSN 0097-5397.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Erratum
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that for any Є > 0 the problem of finding a factor (2 - Є) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P≠NP. They can be thought of as an extension of Håstad's optimal hardness of approximation results for MAX-E3-LIN2 [J. ACM, 48 (2001), pp. 798--859] to the entangled-player setting. The key technical component of our work is a soundness analysis of a plane-vs-point low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick [Proceedings of the 53rd FOCS, IEEE, Piscataway, NJ, 2012, pp. 243-252]. Our results demonstrate the possibility of efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2016 Society for Industrial and Applied Mathematics. Received by the editors February 11, 2014; accepted for publication in revised form November 9, 2015; published electronically June 29, 2016. I am grateful to Dana Moshkovitz for helping me make my way through the classical literature on PCPs, including invaluable advice on the shortest path to obtaining constant-factor hardness of approximation results. I thank Ronald de Wolf for useful conversations that led to the discovery of an inaccuracy in a previous formulation of Corollary 4.6. I am indebted to the anonymous SICOMP referees for many useful comments that greatly helped improve the presentation, including the suggestion to use the parallel repetition theorem from [DSV14a], instead of the one from [KV11], in section 4.3.
Errata:Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate. Thomas Vidick. SIAM Journal on Computing 2020 49:6, 1423-1427; DOI: 10.1137/20M1368598
Subject Keywords:PCP theorem, XOR games, entangled games, Bell inequalities
Issue or Number:3
Classification Code:AMS subject classifications. 81P68, 68Q10
Record Number:CaltechAUTHORS:20161103-145636436
Persistent URL:
Official Citation:Three-Player Entangled XOR Games are NP-Hard to Approximate. Thomas Vidick. SIAM Journal on Computing 2016 45:3, 1007-1063; DOI: 10.1137/140956622
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71726
Deposited By: Ruth Sustaita
Deposited On:04 Nov 2016 16:13
Last Modified:14 Jan 2021 22:48

Repository Staff Only: item control page