Vidick, Thomas (2013) Three-player entangled XOR games are NP-hard to approximate. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 766-775. ISBN 978-0-7695-5135-7. https://resolver.caltech.edu/CaltechAUTHORS:20140910-100149541
|
PDF
- Submitted Version
See Usage Policy. 479kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20140910-100149541
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 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.
Item Type: | Book Section | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||
ORCID: |
| ||||||||||||
Additional Information: | © 2013 IEEE. Supported by the National Science Foundation under Grant No. 0844626. | ||||||||||||
Funders: |
| ||||||||||||
Subject Keywords: | PCP theorem; entangled games; XOR games; Bell inequalities | ||||||||||||
DOI: | 10.1109/FOCS.2013.87 | ||||||||||||
Record Number: | CaltechAUTHORS:20140910-100149541 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20140910-100149541 | ||||||||||||
Official Citation: | Vidick, T., "Three-Player Entangled XOR Games Are NP-Hard to Approximate," Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on , vol., no., pp.766,775, 26-29 Oct. 2013 doi: 10.1109/FOCS.2013.87 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6686213&isnumber=6686124 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 49529 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | Tony Diaz | ||||||||||||
Deposited On: | 10 Sep 2014 18:40 | ||||||||||||
Last Modified: | 10 Nov 2021 18:45 |
Repository Staff Only: item control page