{
  "id": "1209.2729",
  "version": "v3",
  "published": "2012-09-12T20:59:24.000Z",
  "updated": "2013-10-16T04:37:21.000Z",
  "title": "Characterization of Binary Constraint System Games",
  "authors": [
    "Richard Cleve",
    "Rajat Mittal"
  ],
  "comment": "Revised version corrects an error in the previous version of the proof of Theorem 1 that arises in the case of POVM measurements",
  "categories": [
    "quant-ph"
  ],
  "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.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-10-16T04:37:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "binary constraint system games",
      "characterization",
      "bcs game admits",
      "maximum entangled success probability",
      "major no-hidden-variables theorems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1209.2729C"
    }
  }
}