Binary Constraint System Games and Locally Commutative Reductions
arXiv:1310.3794
Abstract
A binary constraint system game is a two-player one-round non-local game defined by a system of Boolean constraints. The game has a perfect quantum strategy if and only if the constraint system has a quantum satisfying assignment [R. Cleve and R. Mittal, arXiv:1209.2729]. We show that several concepts including the quantum chromatic number and the Kochen-Specker sets that arose from different contexts fit naturally in the binary constraint system framework. The structure and complexity of the quantum satisfiability problems for these constraint systems are investigated. Combined with a new construct called the commutativity gadget for each problem, several classic NP-hardness reductions are lifted to their corresponding quantum versions. We also provide a simple parity constraint game that requires EPR pairs in perfect strategies where is the number of variables in the constraint system.
arXiv comment21 pages, 6 figures; v2 contains an explicit proof of Lemma 4, a theorem on HORN-SAT* and several extended discussions
References in corpus (10)
- Hidden Variables and the Two Theorems of John Bell
- The cost of exactly simulating quantum entanglement with classical communication
- Quantum NP - A Survey
- Lower bounds on the entanglement needed to play XOR non-local games
- A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
- Three-player entangled XOR games are NP-hard to approximate
- Extending and Characterizing Quantum Magic Games
- Characterization of Binary Constraint System Games
- Bell Violations through Independent Bases Games
- On the quantum chromatic number of a graph
Cited by in corpus (11)
- Estimating quantum chromatic numbers
- Perfect Commuting-Operator Strategies for Linear System Games
- Algebras, Synchronous Games and Chromatic Numbers of Graphs
- Robust self-testing for linear constraint system games
- Matrices with high completely positive semidefinite rank
- Universal security for randomness expansion from the spot-checking protocol
- Characterization of Binary Constraint System Games
- Learning optimal quantum models is NP-hard
- Deciding the existence of perfect entangled strategies for nonlocal games
- Generalized Satisfiability Problems via Operator Assignments
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization