On deciding the existence of perfect entangled strategies for nonlocal games

DOI10.4086/CJTCS.2016.005MaRDI QIDQ2808532zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6096706 (Why is no real title available?)
• Characterization of binary constraint system games
• Infinite randomness expansion with a constant number of devices
• Interactive proofs and the hardness of approximating cliques
• Quantum cryptography based on Bell’s theorem

Cited in

(19)

• Synchronicity for quantum non-local games
• Entanglement in non-local games and the hyperlinear profile of groups
• A category of quantum posets
• Quantum and non-signalling graph isomorphisms
• Transitive nonlocal games
• Minimum quantum resources for strong non-locality
• Graph-theoretical bounds on the entangled value of non-local games
• 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
• Perfect commuting-operator strategies for linear system games
• Two party non-local games
• Characterization of binary constraint system games
• Extended nonlocal games from quantum-classical games
• Classical, quantum and nonsignalling resources in bipartite games
• Discrete quantum structures. I: Quantum predicate logic
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• Nonlocal Games with Noisy Maximally Entangled States are Decidable
• Linear conic formulations for two-party correlations and values of nonlocal games
• scientific article; zbMATH DE number 7559121 (Why is no real title available?)
• Perfect strategies for non-local 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)