On deciding the existence of perfect entangled strategies for nonlocal games

DOI10.4086/CJTCS.2016.005zbMATH Open1341.91021arXiv1506.07429OpenAlexW4237461333MaRDI QIDQ2808532FDOQ2808532

Authors: L. Mančinska, David Roberson, Antonios Varvisotis 

Publication date: 24 May 2016

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Abstract: First, we consider the problem of deciding whether a nonlocal game admits a perfect entangled strategy that uses projective measurements on a maximally entangled shared state. Via a polynomial-time Karp reduction, we show that independent set games are the hardest instances of this problem. Secondly, we show that if every independent set game whose entangled value is equal to one admits a perfect entangled strategy, then the same holds for all symmetric synchronous games. Finally, we identify combinatorial lower bounds on the classical and entangled values of synchronous games in terms of variants of the independence number of appropriate graphs. Our results suggest that independent set games might be representative of all nonlocal games when dealing with questions concerning perfect entangled strategies.

Full work available at URL: https://arxiv.org/abs/1506.07429

Recommendations

• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Extended non-local games and monogamy-of-entanglement games
• Extended nonlocal games from quantum-classical games
• On the relation between Bell's inequalities and nonlocal games
• Graph-theoretical bounds on the entangled value of non-local games
• scientific article; zbMATH DE number 7559121
• On symmetric nonlocal games
• Note on maximally entangled Eisert-Lewenstein-Wilkens quantum games
• Nonlocal games and quantum permutation groups
• Constructing quantum games from symmetric non-factorizable joint probabilities

zbMATH Keywords

nonlocal gameentangled valueperfect entangled strategiesquantum independence number

Mathematics Subject Classification ID

Noncooperative games (91A10) Decision theory for games (91A35) Quantum measurement theory, state operations, state preparations (81P15) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cites Work

• Quantum cryptography based on Bell’s theorem
• Interactive proofs and the hardness of approximating cliques
• Characterization of Binary Constraint System Games
• Title not available (Why is that?)
• Infinite randomness expansion with a constant number of devices

Cited In (10)

• A category of quantum posets
• Quantum and non-signalling graph isomorphisms
• 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
• Spectral upper bound on the quantum k-independence number of a graph
• Two party non-local games
• Discrete quantum structures. I: Quantum predicate logic
• Title not available (Why is that?)
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Title not available (Why is that?)
• Linear conic formulations for two-party correlations and values of nonlocal games

This page was built for publication: On deciding the existence of perfect entangled strategies for nonlocal games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808532)