Characterization of binary constraint system games
From MaRDI portal
Publication:5167752
DOI10.1007/978-3-662-43948-7_27zbMATH Open1364.91015arXiv1209.2729OpenAlexW1933312167MaRDI QIDQ5167752FDOQ5167752
Authors: Richard Cleve, Rajat Mittal 
Publication date: 1 July 2014
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1209.2729
Recommendations
Cited In (30)
- Characterizations of solutions for games with precedence constraints
- Entanglement in non-local games and the hyperlinear profile of groups
- Nonlocal games and quantum permutation groups
- Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
- Title not available (Why is that?)
- Quantum and non-signalling graph isomorphisms
- The quantum monad on relational structures
- Synchronous linear constraint system games
- Generalized satisfiability problems via operator assignments
- A state-space approach to quantum permutations
- 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
- Contextuality with a small number of observables
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Extended nonlocal games from quantum-classical games
- Constant-sized robust self-tests for states and measurements of unbounded dimension
- An operator-algebraic formulation of self-testing
- On deciding the existence of perfect entangled strategies for nonlocal games
- Synchronous values of games
- Quantum hypergraph homomorphisms and non-local games
- Quantum logic is undecidable
- Commutative d-torsion K-theory and its applications
- Analysis of Boolean functions related to binary input binary output two-party nonlocal games
- Arkhipov's theorem, graph minors, and linear system nonlocal games
- Almost synchronous quantum correlations
- Classical vs quantum satisfiability in linear constraint systems modulo an integer
- The set of quantum correlations is not closed
- Maximally Entangled State in Pseudo-Telepathy Games
- \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
- Perfect strategies for 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)
