Characterization of binary constraint system games

DOI10.1007/978-3-662-43948-7_27MaRDI QIDQ5167752zbMATH OpenOpenAlexFDO

Authors Richard Cleve, Rajat Mittal

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

entanglementquantum informationbinary constraint systems

Mathematics Subject Classification ID

Noncooperative games (91A10)

Abstract: We consider a class of nonlocal games that are related to binary constraint systems (BCSs) in a manner similar to the games implicit in the work of Mermin [N.D. Mermin, "Simple unified form for the major no-hidden-variables theorems," Phys. Rev. Lett., 65(27):3373-3376, 1990], but generalized to n binary variables and m constraints. We show that, whenever there is a perfect entangled protocol for such a game, there exists a set of binary observables with commutations and products similar to those exhibited by Mermin. We also show how to derive upper bounds strictly below 1 for the the maximum entangled success probability of some BCS games. These results are partial progress towards a larger project to determine the computational complexity of deciding whether a given instance of a BCS game admits a perfect entangled strategy or not.

Recommendations

• On deciding the existence of perfect entangled strategies for nonlocal games
• Entangled games are hard to approximate
• Unique games with entangled provers are easy
• A lower bound on the value of entangled binary games
• scientific article; zbMATH DE number 7250160

Cited in

(30)

• A state-space approach to quantum permutations
• Maximally Entangled State in Pseudo-Telepathy Games
• 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
• Constant-sized robust self-tests for states and measurements of unbounded dimension
• Quantum logic is undecidable
• The set of quantum correlations is not closed
• Perfect strategies for non-local games
• Entanglement in non-local games and the hyperlinear profile of groups
• Quantum and non-signalling graph isomorphisms
• Classical vs quantum satisfiability in linear constraint systems modulo an integer
• Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
• Synchronous values of games
• An operator-algebraic formulation of self-testing
• Generalized satisfiability problems via operator assignments
• Analysis of Boolean functions related to binary input binary output two-party nonlocal games
• Arkhipov's theorem, graph minors, and linear system nonlocal games
• The quantum monad on relational structures
• Tsirelson's problem and an embedding theorem for groups arising from non-local games
• Nonlocal games and quantum permutation groups
• Almost synchronous quantum correlations
• Perfect commuting-operator strategies for linear system games
• Synchronous linear constraint system games
• Contextuality with a small number of observables
• On deciding the existence of perfect entangled strategies for nonlocal games
• scientific article; zbMATH DE number 7559053 (Why is no real title available?)
• Commutative d-torsion K-theory and its applications
• Characterizations of solutions for games with precedence constraints
• Extended nonlocal games from quantum-classical games
• \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
• Quantum hypergraph homomorphisms and non-local games

This page was built for publication: Characterization of binary constraint system games

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