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

Optimal bounds on the classical value of the repeated CHSH game

Andris Ambainis

quant-phSubmitted Aug 17, 2026• Announced Aug 18, 2026• 0 citations
arXivHTMLPDF

Abstract

We show that the maximum winning probability in the repeated CHSH game for classical strategies is at most $\left(\frac{1+\sqrt{5}}{4}\right)^n$. Together with a matching lower bound by Barak et al. (FOCS'2008), this determines the asymptotic value of the repeated CHSH game exactly. We also show that, if an XOR game has a gap between classical and quantum values, there is also a gap between the asymptotic values for the repeated game.

Comments
11 pages

Related papers

An explicit classical strategy for winning a ${\mathrm{CHSH}}_{q}$ game

Matej Pivoluska, Martin Plesch

A CHSH q game is a generalization of the standard two player CHSH game, with q different input and output options. In contrast to the binary game, the best classical and quantum winning strategies are not known exactly. In this paper we provide a constructive classical strategy for winning a CHSH q game, with q being a prime. Our construction achieves a winning probability better than , which is in contrast with the previously known constructive strategies achieving only the winning probability of .

arXiv:1510.07431•New Journal of Physics•Feb 12, 2016•7 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

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

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

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•0 citations

Quantum strategies are better than classical in almost any XOR game

Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis +4 more

We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.

arXiv:1112.3330•Dec 14, 2011•0 citations
We show that the maximum winning probability in the repeated CHSH game for classical strategies is at most (1+54)n\left(\frac{1+\sqrt{5}}{4}\right)^n(41+5​​)n. Together with a matching lower bound by Barak et al. (FOCS'2008), this determines the asymptotic value of the repeated CHSH game exactly. We also show that, if an XOR game has a gap between classical and quantum values, there is also a gap between the asymptotic values for the repeated game.
An explicit classical strategy for winning a CHSHq{\mathrm{CHSH}}_{q}CHSHq​ game
A CHSH q game is a generalization of the standard two player CHSH game, with q different input and output options. In contrast to the binary game, the best classical and quantum winning strategies are not known exactly. In this paper we provide a constructive classical strategy for winning a CHSH q game, with q being a prime. Our construction achieves a winning probability better than , which is in contrast with the previously known constructive strategies achieving only the winning probability of .
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.
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.
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.