License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.10
URN: urn:nbn:de:0030-drops-101032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10103/
Bene Watts, Adam ;
Harrow, Aram W. ;
Kanwar, Gurtej ;
Natarajan, Anand
Algorithms, Bounds, and Strategies for Entangled XOR Games
Abstract
Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for systems of operator equations, we introduce necessary and sufficient criteria for an XOR game to have omega^* = 1, and use these criteria to derive the following results:
1) An algorithm for symmetric games that decides in polynomial time whether omega^* = 1 or omega^* < 1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known.
2) A family of games with three players and with omega^* < 1, where it takes doubly exponential time for the ncSoS algorithm to witness this. By contrast, our algorithm runs in polynomial time.
3) Existence of an unsatisfiable phase for random (non-symmetric) XOR games. We show that there exists a constant C_k^{unsat} depending only on the number k of players, such that a random k-XOR game over an alphabet of size n has omega^* < 1 with high probability when the number of clauses is above C_k^{unsat} n.
4) A lower bound of Omega(n log(n)/log log(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the (3n)^{th} level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
BibTeX - Entry
@InProceedings{benewatts_et_al:LIPIcs:2018:10103,
author = {Adam Bene Watts and Aram W. Harrow and Gurtej Kanwar and Anand Natarajan},
title = {{Algorithms, Bounds, and Strategies for Entangled XOR Games}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {10:1--10:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-095-8},
ISSN = {1868-8969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10103},
URN = {urn:nbn:de:0030-drops-101032},
doi = {10.4230/LIPIcs.ITCS.2019.10},
annote = {Keywords: Nonlocal games, XOR Games, Pseudotelepathy games, Multipartite entanglement}
}
|
Keywords: |
|
Nonlocal games, XOR Games, Pseudotelepathy games, Multipartite entanglement |
|
Collection: |
|
10th Innovations in Theoretical Computer Science Conference (ITCS 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
