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

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

Pete Rigas

Published Nov 21, 2023• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2311.12887

Related papers

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•4 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

An explicit nonlocal game of quantum value one that needs exponential entanglement

Nidhal Mghirbi, Seth Douglas

How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with $1687$ equations in $1993$ variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability $1-\varepsilon$ needs entanglement entropy $\varepsilon^{-1+o(1)}$, hence local dimension $\exp(\varepsilon^{-1+o(1)})$. The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension $\exp(C\varepsilon^{-1}\log(1/\varepsilon))$ suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in $1/\varepsilon$. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision $\sqrt\varepsilon$, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of $\varepsilon$ is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH$(n)$ games need $\Theta(\min(n,1/\varepsilon))$ ebits, and the linear system game of Slofstra and Vidick needs local dimension $\Theta(\varepsilon^{-1/2})$.

•Oct 27, 2026•2 citations

Quantum Communication and Game Theory with Nonclassical Correlations

Kristóf Vörös, Prof Miklós Kozlovszky

Classical game theory is constrained by the limits of local realism. This paper presents simple problems from game theory, where pre-shared entangled states and non-classical correlations (specifically Popescu-Rohrlich boxes) allow players to exceed classical winning probabilities. We provide a rigorous mathematical foundation for bipartite and multipartite quantum systems, analyzing the spectral decomposition of operators and tensor product eigenproblems. Four specific games are analyzed: the CHSH game, Strong/Weak Coin Flipping, the Casino Game, and Magic Squares. We demonstrate that for the Magic Square game, quantum resources transition the optimal winning probability from 8/9 to certainty of probability 1. Finally, we reference to a Python-based desktop application of our previous work, that emulates non-local correlations using a hardware-assisted quantum API.

International Convention on Information and Communication Technology, Electronics and Microelectronics•May 25, 2026•0 citations

Optimal Strategies for Winning Certain Coset-Guessing Quantum Games

Michael Schleppy, Emina Soljanin, Nicolas Swanson

In a recently introduced coset guessing game, Alice plays against Bob and Charlie, aiming to meet a joint winning condition. Bob and Charlie can only communicate before the game starts to devise a joint strategy. The game we consider begins with Alice preparing a 2m-qubit quantum state based on a random selection of three parameters. She sends the first m qubits to Bob and the rest to Charlie, and then reveals to them her choice for one of the parameters. Bob is supposed to guess one of the hidden parameters, Charlie the other, and they win if both guesses are correct. From previous work, we know that the probability of Bob’s and Charlie’s guesses being simultaneously correct goes to zero exponentially as m increases. We derive a tight upper bound on this probability and show how Bob and Charlie can achieve it. While developing an optimal strategy, we devised an encoding circuit using only and Hadamard gates, which builds CSS codes from EPR pairs using only local operations. We found that the role of quantum information that Alice communicates to Bob and Charlie is to make their responses correlated rather than improve their individual (marginal) correct guessing rates.

arXiv:2410.08160•IEEE Journal on Selected Areas in Information Theory•Jan 1, 2025•1 citation

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games

Andris Ambainis, Jānis Iraids

Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of $n$ players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any $n$-player symmetric XOR game the entangled value of the game is $Θ(\frac{\sqrt{\ln{n}}}{n^{1/4}})$ adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is $Θ(\sqrt{\ln{n}})$ for almost any symmetric XOR game.

arXiv:1302.2347•Leibniz international proceedings in informatics•Jan 1, 2013•2 citations
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.
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.
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.
How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with 168716871687 equations in 199319931993 variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability 1−ε1-\varepsilon1−ε needs entanglement entropy ε−1+o(1)\varepsilon^{-1+o(1)}ε−1+o(1), hence local dimension exp⁡(ε−1+o(1))\exp(\varepsilon^{-1+o(1)})exp(ε−1+o(1)). The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension exp⁡(Cε−1log⁡(1/ε))\exp(C\varepsilon^{-1}\log(1/\varepsilon))exp(Cε−1log(1/ε)) suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in 1/ε1/\varepsilon1/ε. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision ε\sqrt\varepsilonε​, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of ε\varepsilonε is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH(n)(n)(n) games need Θ(min⁡(n,1/ε))\Theta(\min(n,1/\varepsilon))Θ(min(n,1/ε)) ebits, and the linear system game of Slofstra and Vidick needs local dimension Θ(ε−1/2)\Theta(\varepsilon^{-1/2})Θ(ε−1/2).
Classical game theory is constrained by the limits of local realism. This paper presents simple problems from game theory, where pre-shared entangled states and non-classical correlations (specifically Popescu-Rohrlich boxes) allow players to exceed classical winning probabilities. We provide a rigorous mathematical foundation for bipartite and multipartite quantum systems, analyzing the spectral decomposition of operators and tensor product eigenproblems. Four specific games are analyzed: the CHSH game, Strong/Weak Coin Flipping, the Casino Game, and Magic Squares. We demonstrate that for the Magic Square game, quantum resources transition the optimal winning probability from 8/9 to certainty of probability 1. Finally, we reference to a Python-based desktop application of our previous work, that emulates non-local correlations using a hardware-assisted quantum API.
In a recently introduced coset guessing game, Alice plays against Bob and Charlie, aiming to meet a joint winning condition. Bob and Charlie can only communicate before the game starts to devise a joint strategy. The game we consider begins with Alice preparing a 2m-qubit quantum state based on a random selection of three parameters. She sends the first m qubits to Bob and the rest to Charlie, and then reveals to them her choice for one of the parameters. Bob is supposed to guess one of the hidden parameters, Charlie the other, and they win if both guesses are correct. From previous work, we know that the probability of Bob’s and Charlie’s guesses being simultaneously correct goes to zero exponentially as m increases. We derive a tight upper bound on this probability and show how Bob and Charlie can achieve it. While developing an optimal strategy, we devised an encoding circuit using only and Hadamard gates, which builds CSS codes from EPR pairs using only local operations. We found that the role of quantum information that Alice communicates to Bob and Charlie is to make their responses correlated rather than improve their individual (marginal) correct guessing rates.
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of nnn players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any nnn-player symmetric XOR game the entangled value of the game is Θ(ln⁡nn1/4)Θ(\frac{\sqrt{\ln{n}}}{n^{1/4}})Θ(n1/4lnn​​) adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is Θ(ln⁡n)Θ(\sqrt{\ln{n}})Θ(lnn​) for almost any symmetric XOR game.