ﻻ يوجد ملخص باللغة العربية
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 quant
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the
We introduce a simple transformation on two-player nonlocal games, called anchoring, and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in par
We study the quantum moment problem: Given a conditional probability distribution together with some polynomial constraints, does there exist a quantum state rho and a collection of measurement operators such that (i) the probability of obtaining a p
We study properties of quantum strategies, which are complete specifications of a given partys actions in any multiple-round interaction involving the exchange of quantum information with one or more other parties. In particular, we focus on a repres
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qub