Three-Player Entangled XOR Games are NP-Hard to Approximate
- Creators
-
Vidick, Thomas
Abstract
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.
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/20M1368598Attached Files
Published - 140956622.pdf
Submitted - 1302.1242v1.pdf
Erratum - 20m1368598.pdf
Files
Additional details
- Eprint ID
- 71726
- Resolver ID
- CaltechAUTHORS:20161103-145636436
- Created
-
2016-11-04Created from EPrint's datestamp field
- Updated
-
2023-06-01Created from EPrint's last_modified field