Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1506.00607

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

Dimiter Ostrev

Published Jun 1, 2015• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1506.00607

Related papers

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

Dimiter Ostrev

We consider the infinite family of non-local games CHSH(n). We consider nearly-optimal strategies for CHSH(n). We introduce a notion of approximate homomorphism for strategies and show that any nearly-optimal strategy for CHSH(n) is approximately homomorphic to the canonical optimal CHSH(n) strategy. This demonstrates that any nearly-optimal CHSH(n) strategy must approximately contain the algebraic structure of the canonical optimal strategy.

Quantum Information and Computation•Oct 1, 2016•6 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.

arXiv:1007.2248•Journal of Mathematical Physics•Oct 1, 2011•33 citations

Optimal, and approximately optimal, quantum strategies for $\mathrm{XOR}^{*}$ and $\mathrm{FFL}$ games

Pete Rigas

We analyze optimal, and approximately optimal, quantum strategies in two non-local settings based upon previous investigations of the XOR and CHSH games. By building upon previous arguments due to Ostrev in 2016, {\color{blue}[37]}, which characterized approximately optimal, and optimal, strategies that players Alice and Bob can adopt for increasing their respective winning probabilities, we identify additional applications of the framework for analyzing prospective quantum advantage in other game-theoretic settings. In particular, while it is possible for Alice and Bob to realize quantum advantage if they adopt strategies that are dependent upon entanglement, two-dimensional resource systems, and reversible transformations, the magnitude of the duality gap between the performance of classical and quantum strategies has not yet been classified from the perspective of error bounds. Such bounds are not only dependent upon the winning probability if Alice and Bob leverage entanglement in their strategies but also upon a suitably defined representation-theoretic intertwining operation.

arXiv:2311.12887•Nov 21, 2023•0 citations

Entanglement of approximate quantum strategies in XOR games

Dimiter Ostrev, Thomas Vidick

We characterize the amount of entanglement that is sufficient to play any XOR game near-optimally. We show that for any XOR game G and \eps>0 there is an \eps-optimal strategy for G using \lceil \eps^{-1} \rceil ebits of entanglement, irrespective of the number of questions in the game. By considering the family of XOR games CHSH(n) introduced by Slofstra (Jour. Math. Phys. 2011), we show that this bound is nearly tight: for any \eps>0 there is an n=\Theta(\eps^{-1/5}) such that \Omega(\eps^{-1/5}) ebits are required for any strategy achieving bias that is at least a multiplicative factor (1-\eps) from optimal in CHSH(n).

arXiv:1609.01652•Quantum Information and Computation•Jun 1, 2018•10 citations

Nonlocal Games Revisited: A Representation-Theoretic Path from Bell Locality to Quantum Pseudo-Telepathy

Mustafa Mert Özyılmaz, Ruchi Thareja, Houssam Nasser

Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. In this work, we develop this perspective by connecting the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement, and then introduce nonlocal games through the standard predicate/verifier formalism. We next examine a set of representative examples, including XOR games, the GHZ game, graph-based coloring games, the Mermin-Peres magic square game, and Hardy's paradox as a related logical manifestation of nonlocality. Building on this foundation, we compare four closely related representation frameworks: conditional-probability and correlation descriptions, Bell-functional formulations, entangled-value optimization, and the quantum-operator approach together with the Navascues-Pironio-Acin (NPA) hierarchy. These viewpoints are then instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasizes a different aspect of the same underlying task. Taken together, these examples show that nonlocal games can be studied simultaneously as geometric objects in correlation space, optimization problems over entangled resources, and operator-theoretic constructions. This multi-representation viewpoint clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.

quant-pharXiv:2604.09458•Apr 13, 2026•0 citations

Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games

Pete Rigas

We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies. In comparison to a previous work of the author, arXiv: 2311.12887, which applied a 2016 framework due to Ostrev for constructing error bounds beyond CHSH and XOR games, in addition to the existence of well-posed semidefinite programs for determining primal feasible solutions, along with quantum-classical duality gaps, it continues to remain of interest to further develop the construction of error bounds, and related objects, to game-theoretic settings with several participants. In such settings, one encounters a rich information theoretic landscape, not only from the fact that there exists a significantly larger combinatorial space of possible strategies for each player, but also several opportunities for pronounced quantum advantage. We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage, in $\mathrm{XOR}^{*}$, compiled $\mathrm{XOR}^{*}$, and strong parallel repetition variants of $\mathrm{XOR}^{*}$ games.

arXiv:2505.06322•May 9, 2025•0 citations
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 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.
Optimal, and approximately optimal, quantum strategies for XOR∗\mathrm{XOR}^{*}XOR∗ and FFL\mathrm{FFL}FFL games
We analyze optimal, and approximately optimal, quantum strategies in two non-local settings based upon previous investigations of the XOR and CHSH games. By building upon previous arguments due to Ostrev in 2016, {\color{blue}[37]}, which characterized approximately optimal, and optimal, strategies that players Alice and Bob can adopt for increasing their respective winning probabilities, we identify additional applications of the framework for analyzing prospective quantum advantage in other game-theoretic settings. In particular, while it is possible for Alice and Bob to realize quantum advantage if they adopt strategies that are dependent upon entanglement, two-dimensional resource systems, and reversible transformations, the magnitude of the duality gap between the performance of classical and quantum strategies has not yet been classified from the perspective of error bounds. Such bounds are not only dependent upon the winning probability if Alice and Bob leverage entanglement in their strategies but also upon a suitably defined representation-theoretic intertwining operation.
We characterize the amount of entanglement that is sufficient to play any XOR game near-optimally. We show that for any XOR game G and \eps>0 there is an \eps-optimal strategy for G using \lceil \eps^{-1} \rceil ebits of entanglement, irrespective of the number of questions in the game. By considering the family of XOR games CHSH(n) introduced by Slofstra (Jour. Math. Phys. 2011), we show that this bound is nearly tight: for any \eps>0 there is an n=\Theta(\eps^{-1/5}) such that \Omega(\eps^{-1/5}) ebits are required for any strategy achieving bias that is at least a multiplicative factor (1-\eps) from optimal in CHSH(n).
Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. In this work, we develop this perspective by connecting the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement, and then introduce nonlocal games through the standard predicate/verifier formalism. We next examine a set of representative examples, including XOR games, the GHZ game, graph-based coloring games, the Mermin-Peres magic square game, and Hardy's paradox as a related logical manifestation of nonlocality. Building on this foundation, we compare four closely related representation frameworks: conditional-probability and correlation descriptions, Bell-functional formulations, entangled-value optimization, and the quantum-operator approach together with the Navascues-Pironio-Acin (NPA) hierarchy. These viewpoints are then instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasizes a different aspect of the same underlying task. Taken together, these examples show that nonlocal games can be studied simultaneously as geometric objects in correlation space, optimization problems over entangled resources, and operator-theoretic constructions. This multi-representation viewpoint clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.
Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, XOR∗\mathrm{XOR}^{*}XOR∗, compiled XOR, XOR∗\mathrm{XOR}^{*}XOR∗, and strong parallel repetiton of XOR, XOR∗\mathrm{XOR}^{*}XOR∗, and FFL games
We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies. In comparison to a previous work of the author, arXiv: 2311.12887, which applied a 2016 framework due to Ostrev for constructing error bounds beyond CHSH and XOR games, in addition to the existence of well-posed semidefinite programs for determining primal feasible solutions, along with quantum-classical duality gaps, it continues to remain of interest to further develop the construction of error bounds, and related objects, to game-theoretic settings with several participants. In such settings, one encounters a rich information theoretic landscape, not only from the fact that there exists a significantly larger combinatorial space of possible strategies for each player, but also several opportunities for pronounced quantum advantage. We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage, in XOR∗\mathrm{XOR}^{*}XOR∗, compiled XOR∗\mathrm{XOR}^{*}XOR∗, and strong parallel repetition variants of XOR∗\mathrm{XOR}^{*}XOR∗ games.