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.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper
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
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Subject Keywords:low-degree testing, entangled nonlocal games, multi-prover interactive proof systems
Series Name:Leibniz International Proceedings in Informatics
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89059
Deposited By: George Porter
Deposited On:22 Aug 2018 21:24
Last Modified:16 Nov 2021 00:31

Repository Staff Only: item control page