Characterization of Binary Constraint System Games
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Operator solutions of linear systems and small cancellation
Incidence systems of (3,6)- and (4,4)-graphs admit quantum solutions over Z_p for arbitrary weights, producing linear system games with perfect commuting-operator but no classical strategies.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.