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:2505.06322

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

Published May 9, 2025• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2505.06322

Related papers

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•8 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.

arXiv:1506.00607•Jun 1, 2015•1 citation

Multipartite entanglement in XOR games

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Quantum Information Processing•Mar 1, 2013•1 citation

Multipartite entanglement in XOR games

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form $\sum_i \alpha_i \ket{i}\cdots\ket{i}$ for arbitrary amplitudes $\alpha_i$. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Quantum Information and Computation•Mar 1, 2013•17 citations

Quantum XOR Games

Oded Regev, Thomas Vidick

We introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck’s inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance that players can obtain in a given game, both in the case that they have no shared entanglement and that they share unlimited entanglement. As a byproduct of the algorithm, we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.

arXiv:1207.4939•ACM Transactions on Computation Theory•Aug 31, 2015•61 citations

Quantum XOR Games

Oded Regev, Thomas Vidick

We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck's inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance players can obtain in a given game, both in case they have no shared entanglement and in case they share unlimited entanglement. As a byproduct of the algorithm we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2013•17 citations
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.
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 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 multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form ∑iαi∣i⟩⋯∣i⟩\sum_i \alpha_i \ket{i}\cdots\ket{i}∑i​αi​∣i⟩⋯∣i⟩ for arbitrary amplitudes αi\alpha_iαi​. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
We introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck’s inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance that players can obtain in a given game, both in the case that they have no shared entanglement and that they share unlimited entanglement. As a byproduct of the algorithm, we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.
We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck's inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance players can obtain in a given game, both in case they have no shared entanglement and in case they share unlimited entanglement. As a byproduct of the algorithm we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.