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

Quantum Optimality in the Odd-Cycle game: the topological odd-blocker, marked connected components of the giant, consistency of pearls, vanishing homotopy

Pete Rigas

quant-phmath.PRSubmitted Nov 26, 2025• Announced Nov 27, 2025• 0 citations• Revised Feb 26, 2026 (v2)
v1 · Nov 26, 2025v2 · Feb 26, 2026
arXivHTMLPDF

Abstract

We characterize optimality of Quantum strategies for the Odd-Cycle game. Separate from other game-theoretic settings, parallel repetition for the Odd-Cycle game is related to the foam problem, which can be formulated through a minimization of the surface area. In comparison to previous works on minimizing the surface area, we quantify how properties of the marked giant connected component can be related to the maximum winning probability using Quantum strategies. Objects that we introduce to formulate such connections include the topological odd-blocker, previous examples of error bounds for other Quantum games that have been formulated by the author, pearls, consistent regions, and the cycle elimination problem.

Comments
Template (51 pages). An overview of this work is available at: https://youtu.be/CJjgJenmQSg?si=pCVl1spizptj-g4Z. Also see: https://www.youtube.com/playlist?list=PL3rTBtU0TK_BBrcvuv13MUPQKDyi2raHl, https://www.youtube.com/playlist?list=PL3rTBtU0TK_DYTpmZAHcAMFMBj9ov1oPf

Related papers

Experimental Quantum Advantage in the Odd-Cycle Game

P. Drmota, D. Main, E. M. Ainley +7 more

We report the first experimental demonstration of the odd-cycle game. We entangle two atoms separated by ∼2 m, and the players use them to win the odd-cycle game with a probability ∼26σ above that allowed by the best classical strategy. The experiment implements the optimal quantum strategy, is free of loopholes, and achieves 97.8(3)% of the theoretical limit to the quantum winning probability. We perform the associated Bell test and measure a nonlocal content of 0.54(2)-the largest value for physically separate devices, free of the detection loophole, ever observed.

arXiv:2406.08412•Physical Review Letters•Feb 21, 2025•4 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

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

A periodic point-based method for the analysis of Nash equilibria in 2 × 2 symmetric quantum games

David M. Schneider

We present a novel method of looking at Nash equilibria in 2 × 2 quantum games. Our method is based on a mathematical connection between the problem of identifying Nash equilibria in game theory, and the topological problem of the periodic points in nonlinear maps. To adapt our method to the original protocol designed by Eisert et al (1999 Phys. Rev. Lett. 83 3077–80) to study quantum games, we are forced to extend the space of strategies from the initial proposal. We apply our method to the extended strategy space version of the quantum Prisoner's dilemma and find that a new set of Nash equilibria emerge in a natural way. Nash equilibria in this set are optimal as Eisert's solution of the quantum Prisoner's dilemma and include this solution as a limit case.

Journal of Physics A Mathematical and Theoretical•Feb 9, 2011•6 citations

Information Value of Two-Prover Games

Mark Braverman, Young Kun Ko

We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) - in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective input. We study the trade-off between the information cost of the protocol and the achieved value of the game after the protocol. In particular, we show the connection of this trade-off and the amortized behavior of the game (i.e. repeated value of the game). We show that if one can win the game with at least (1 - \epsilon)-probability by communicating at most \epsilon bits of information, then one can win n copies with probability at least 2^{-O(\epsilon n)}. This gives an intuitive explanation why Raz's counter-example to strong parallel repetition [Raz2008] (the odd cycle game) is a counter-example to strong parallel repetition - one can win the odd-cycle game on a cycle of length $m$ by communicating O(m^{-2})-bits where m is the number of vertices. Conversely, for projection games, we show that if one can win n copies with probability larger than (1-\epsilon)^n, then one can win one copy with at least (1 - O(\epsilon))-probability by communicating O(\epsilon) bits of information. By showing the equivalence between information value and amortized value, we give an alternative direction for further works in studying amortized behavior of the two-prover games. The main technical tool is the "Chi-Squared Lemma" which bounds the information cost of the protocol in terms of Chi-Squared distance, instead of usual divergence. This avoids the square loss from using Pinsker's Inequality.

Leibniz international proceedings in informatics•Jan 1, 2018•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
We characterize optimality of Quantum strategies for the Odd-Cycle game. Separate from other game-theoretic settings, parallel repetition for the Odd-Cycle game is related to the foam problem, which can be formulated through a minimization of the surface area. In comparison to previous works on minimizing the surface area, we quantify how properties of the marked giant connected component can be related to the maximum winning probability using Quantum strategies. Objects that we introduce to formulate such connections include the topological odd-blocker, previous examples of error bounds for other Quantum games that have been formulated by the author, pearls, consistent regions, and the cycle elimination problem.
We report the first experimental demonstration of the odd-cycle game. We entangle two atoms separated by ∼2 m, and the players use them to win the odd-cycle game with a probability ∼26σ above that allowed by the best classical strategy. The experiment implements the optimal quantum strategy, is free of loopholes, and achieves 97.8(3)% of the theoretical limit to the quantum winning probability. We perform the associated Bell test and measure a nonlocal content of 0.54(2)-the largest value for physically separate devices, free of the detection loophole, ever observed.
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 present a novel method of looking at Nash equilibria in 2 × 2 quantum games. Our method is based on a mathematical connection between the problem of identifying Nash equilibria in game theory, and the topological problem of the periodic points in nonlinear maps. To adapt our method to the original protocol designed by Eisert et al (1999 Phys. Rev. Lett. 83 3077–80) to study quantum games, we are forced to extend the space of strategies from the initial proposal. We apply our method to the extended strategy space version of the quantum Prisoner's dilemma and find that a new set of Nash equilibria emerge in a natural way. Nash equilibria in this set are optimal as Eisert's solution of the quantum Prisoner's dilemma and include this solution as a limit case.
We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) - in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective input. We study the trade-off between the information cost of the protocol and the achieved value of the game after the protocol. In particular, we show the connection of this trade-off and the amortized behavior of the game (i.e. repeated value of the game). We show that if one can win the game with at least (1 - \epsilon)-probability by communicating at most \epsilon bits of information, then one can win n copies with probability at least 2^{-O(\epsilon n)}. This gives an intuitive explanation why Raz's counter-example to strong parallel repetition [Raz2008] (the odd cycle game) is a counter-example to strong parallel repetition - one can win the odd-cycle game on a cycle of length mmm by communicating O(m^{-2})-bits where m is the number of vertices. Conversely, for projection games, we show that if one can win n copies with probability larger than (1-\epsilon)^n, then one can win one copy with at least (1 - O(\epsilon))-probability by communicating O(\epsilon) bits of information. By showing the equivalence between information value and amortized value, we give an alternative direction for further works in studying amortized behavior of the two-prover games. The main technical tool is the "Chi-Squared Lemma" which bounds the information cost of the protocol in terms of Chi-Squared distance, instead of usual divergence. This avoids the square loss from using Pinsker's Inequality.
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.