CaltechAUTHORS
  A Caltech Library Service

Two-Player Entangled Games are NP-Hard

Natarajan, Anand and Vidick, Thomas (2018) Two-Player Entangled Games are NP-Hard. In: 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik , Wadern, Germany, Art. No. 20. ISBN 978-3-95977-069-9. http://resolver.caltech.edu/CaltechAUTHORS:20180822-141142977

[img] PDF - Published Version
Creative Commons Attribution.

530Kb
[img] PDF - Submitted Version
See Usage Policy.

185Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20180822-141142977

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.4230/LIPIcs.CCC.2018.20DOIArticle
https://arxiv.org/abs/1710.03062arXivDiscussion Paper
ORCID:
AuthorORCID
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
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).
Group:Institute for Quantum Information and Matter, IQIM
Funders:
Funding AgencyGrant Number
NSFCCF-1452616
NSFCCF-1553477
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSFPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
Subject Keywords:low-degree testing, entangled nonlocal games, multi-prover interactive proof systems
Classification Code:2012 ACM Subject Classification Theory of computation → Quantum complexity theory, Theory of computation → Interactive proof systems, Theory of computation → Complexity classes
Record Number:CaltechAUTHORS:20180822-141142977
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20180822-141142977
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89059
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:22 Aug 2018 21:24
Last Modified:20 Mar 2019 16:02

Repository Staff Only: item control page