Published June 2018
| Submitted + Published
Book Section - Chapter
Open
Two-Player Entangled Games are NP-Hard
- Creators
-
Natarajan, Anand
-
Vidick, Thomas
- Other:
- Servedio, Rocco A.
Abstract
We show that it is NP-hard to approximate, to within an additive constant, the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length. As a corollary, the inclusion NEXP subseteq MIP^*, first shown by Ito and Vidick (FOCS'12) with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test of Raz and Safra (STOC'97) against two entangled provers.
Additional Information
© Anand Natarajan and Thomas Vidick; licensed under Creative Commons License CC-BY. Supported by NSF CAREER Grant CCF-1452616. Supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).Attached Files
Published - LIPIcs-CCC-2018-20.pdf
Submitted - 1710.03062.pdf
Files
1710.03062.pdf
Files
(732.9 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:67cc574727755e7e7d1c8e63b8bd2c56
|
190.1 kB | Preview Download |
|
md5:b1e5b5d611bb83323da0dfb9ae951d32
|
542.8 kB | Preview Download |
Additional details
- Eprint ID
- 89059
- Resolver ID
- CaltechAUTHORS:20180822-141142977
- CCF-1452616
- NSF
- CCF-1553477
- NSF
- FA9550-16-1-0495
- Air Force Office of Scientific Research (AFOSR)
- Institute for Quantum Information and Matter (IQIM)
- PHY-1125565
- NSF
- GBMF-12500028
- Gordon and Betty Moore Foundation
- Created
-
2018-08-22Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter
- Series Name
- Leibniz International Proceedings in Informatics