We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding $*$ -algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is $*$ -isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding $*$-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is $*$-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.

arXiv:2203.02525Mar 4, 20220 citations

Lower bounds on the entanglement needed to play XOR non-local games

William Slofstra

We give an explicit family of XOR games with O(n)-bit questions requiring 2n ebits to play near-optimally. More generally, we introduce a new technique for proving lower bounds on the amount of entanglement required by an XOR game: we show that near-optimal strategies for an XOR game G correspond to approximate representations of a certain C*-algebra associated to G. Our results extend an earlier theorem of Tsirelson characterising the set of quantum strategies which implement extremal quantum correlations.We give an explicit family of XOR games with O(n)-bit questions requiring 2n ebits to play near-optimally. More generally, we introduce a new technique for proving lower bounds on the amount of entanglement required by an XOR game: we show that near-optimal strategies for an XOR game G correspond to approximate representations of a certain C*-algebra associated to G. Our results extend an earlier theorem of Tsirelson characterising the set of quantum strategies which implement extremal quantum correlations.

arXiv:1007.2248Journal of Mathematical PhysicsOct 1, 201133 citations

The structure of optimal and nearly-optimal quantum strategies for non-local XOR games

Dimiter Ostrev

We study optimal and nearly-optimal quantum strategies for non-local XOR games. First, we prove the following general result: for every non-local XOR game, there exists a set of relations with the properties: (1) a quantum strategy is optimal for the game if and only if it satisfies the relations, and (2) a quantum strategy is nearly optimal for the game if and only if it approximately satisfies the relations. Next, we focus attention on a specific infinite family of XOR games: the CHSH(n) games. This family generalizes the well-known CHSH game. We describe the general form of CHSH(n) optimal strategies. Then, we adapt the concept of intertwining operator from representation theory and use that to characterize nearly-optimal CHSH(n) strategies.We study optimal and nearly-optimal quantum strategies for non-local XOR games. First, we prove the following general result: for every non-local XOR game, there exists a set of relations with the properties: (1) a quantum strategy is optimal for the game if and only if it satisfies the relations, and (2) a quantum strategy is nearly optimal for the game if and only if it approximately satisfies the relations. Next, we focus attention on a specific infinite family of XOR games: the CHSH(n) games. This family generalizes the well-known CHSH game. We describe the general form of CHSH(n) optimal strategies. Then, we adapt the concept of intertwining operator from representation theory and use that to characterize nearly-optimal CHSH(n) strategies.

arXiv:1506.00607Jun 1, 20150 citations

Almost perfect strategies for projection games are approximately tracial

Eric Culf

Projection games constitute an important class of nonlocal games where, for any answer from the first player, there is a unique correct answer for the second player. This class of games captures nonlocal games arising from constraint satisfaction problems, oracularisations, and unique games. However, due to the asymmetry between the players, projection games are in general not synchronous, and therefore the powerful results constraining the structure of almost perfect strategies for synchronous games do not apply. In this work, we adapt results of Marrakchi and de la Salle for synchronous games to show that, in both the quantum and commuting-operator models, any strategy that wins with probability $1-\varepsilon$ in a projection game gives rise to a tracial strategy that wins with probability $1-O((L\varepsilon)^{1/4})$ , where $L$ is the inverse of the minimal conditional probability of a question for the second player being sampled given a question to the first. For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints and improving the dependence on constraint size, while also generalising to the commuting-operator setting.Projection games constitute an important class of nonlocal games where, for any answer from the first player, there is a unique correct answer for the second player. This class of games captures nonlocal games arising from constraint satisfaction problems, oracularisations, and unique games. However, due to the asymmetry between the players, projection games are in general not synchronous, and therefore the powerful results constraining the structure of almost perfect strategies for synchronous games do not apply. In this work, we adapt results of Marrakchi and de la Salle for synchronous games to show that, in both the quantum and commuting-operator models, any strategy that wins with probability $1-\varepsilon$ in a projection game gives rise to a tracial strategy that wins with probability $1-O((L\varepsilon)^{1/4})$, where $L$ is the inverse of the minimal conditional probability of a question for the second player being sampled given a question to the first. For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints and improving the dependence on constraint size, while also generalising to the commuting-operator setting.

quant-pharXiv:2603.14746Mar 17, 20260 citations

Robust self-testing for nonlocal games with robust game algebras

Yuming Zhao

We give an operator-algebraic formulation of robust self-testing in terms of states on C*-algebras. We show that a quantum correlation p is a robust self-test only if among all (abstract) states, there is a unique one achieving p. We show that the "if" direction of this statement also holds, provided that p is optimal/perfect for a nonlocal game that has a robust game algebra. This last condition applies to many nonlocal games of interest, including all XOR games, synchronous games, and boolean constrained system (BCS) games. For those nonlocal games with robust game algebras, we prove that self-testing is equivalent to the uniqueness of finite-dimensional tracial states on the associated game algebra, and robust self-testing is equivalent to the uniqueness of amenable tracial states. Applying this tracial-state characterization of self-testing to parallel repetition, we show that a synchronous game is a self-test for perfect quantum strategies if and only if its parallel repeated version is a self-test for perfect quantum strategies. As a proof approach, we give the first quantitative Gower-Hatami theorem that is applicable to C*-algebras. Here "quantitative" means there is a constructive bound on the distance between the approximate representations and exact representations. We also demonstrate how this quantitative Gowers-Hatami theorem can be used to calculate the explicit robustness function of a self-test.We give an operator-algebraic formulation of robust self-testing in terms of states on C*-algebras. We show that a quantum correlation p is a robust self-test only if among all (abstract) states, there is a unique one achieving p. We show that the "if" direction of this statement also holds, provided that p is optimal/perfect for a nonlocal game that has a robust game algebra. This last condition applies to many nonlocal games of interest, including all XOR games, synchronous games, and boolean constrained system (BCS) games. For those nonlocal games with robust game algebras, we prove that self-testing is equivalent to the uniqueness of finite-dimensional tracial states on the associated game algebra, and robust self-testing is equivalent to the uniqueness of amenable tracial states. Applying this tracial-state characterization of self-testing to parallel repetition, we show that a synchronous game is a self-test for perfect quantum strategies if and only if its parallel repeated version is a self-test for perfect quantum strategies. As a proof approach, we give the first quantitative Gower-Hatami theorem that is applicable to C*-algebras. Here "quantitative" means there is a constructive bound on the distance between the approximate representations and exact representations. We also demonstrate how this quantitative Gowers-Hatami theorem can be used to calculate the explicit robustness function of a self-test.

arXiv:2411.03259Nov 5, 20240 citations

Satisfiability problems and algebras of Boolean constraint system games

Connor Paddock, William Slofstra

Mermin and Peres showed that there are Boolean constraint systems (BCSs) that are not satisfiable but are satisfiable with quantum observables. This has led to a burgeoning theory of quantum satisfiability for constraint systems, connected to nonlocal games and quantum contextuality. In this theory, different types of quantum satisfying assignments can be understood as representations of the BCS algebra of the system. This theory is closely related to the theory of synchronous games and algebras, and every synchronous algebra is a BCS algebra and vice versa. The purpose of this paper is to further develop the role of BCS algebras in this theory and tie up some loose ends: We give a new presentation of BCS algebras in terms of joint spectral projections and show that it is equivalent to the standard definition. We construct a constraint system that is C∗-satisfiable but not tracially satisfiable. We show that certain reductions between constraint systems lead to ∗-homomorphisms between the BCS algebras of the systems, and we use this to streamline and strengthen several results of Atserias, Kolaitis, and Severini on analogues of Schaefer’s dichotomy theorem. In particular, we show that the question of whether or not there is a nonhyperlinear group is linked to dichotomy theorems for RU-satisfiability.Mermin and Peres showed that there are Boolean constraint systems (BCSs) that are not satisfiable but are satisfiable with quantum observables. This has led to a burgeoning theory of quantum satisfiability for constraint systems, connected to nonlocal games and quantum contextuality. In this theory, different types of quantum satisfying assignments can be understood as representations of the BCS algebra of the system. This theory is closely related to the theory of synchronous games and algebras, and every synchronous algebra is a BCS algebra and vice versa. The purpose of this paper is to further develop the role of BCS algebras in this theory and tie up some loose ends: We give a new presentation of BCS algebras in terms of joint spectral projections and show that it is equivalent to the standard definition. We construct a constraint system that is C∗-satisfiable but not tracially satisfiable. We show that certain reductions between constraint systems lead to ∗-homomorphisms between the BCS algebras of the systems, and we use this to streamline and strengthen several results of Atserias, Kolaitis, and Severini on analogues of Schaefer’s dichotomy theorem. In particular, we show that the question of whether or not there is a nonhyperlinear group is linked to dichotomy theorems for RU-satisfiability.

arXiv:2310.07901Illinois Journal of MathematicsApr 1, 20250 citations

*

-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is

*

-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.

1-\varepsilon

in a projection game gives rise to a tracial strategy that wins with probability

1-O((L\varepsilon)^{1/4})

, where

L

is the inverse of the minimal conditional probability of a question for the second player being sampled given a question to the first. For constraint system games, this strengthens the rounding result of Paddock by eliminating the dependence on number of constraints and improving the dependence on constraint size, while also generalising to the commuting-operator setting.