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

International Convention on Information and Communication Technology, Electronics and Microelectronics

Quantum Communication and Game Theory with Nonclassical Correlations

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

Published May 25, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/mipro70003.2026.11592009

Related papers

Non-local correlations and interactive games

Umesh V. Vazirani, Daniel Preda

Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics. The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT. The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible. We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size. The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific unit of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically). We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.

•Jan 1, 2011•0 citations

Quantum Coordination and Nonlocal Games: Theory and Applications

Husein Natur, Uzi Pereg

Coordination is a fundamental primitive in communication and information theory, in which distributed systems must collectively generate correlated behavior rather than merely exchange messages. In quantum networks, the nature of entanglement, quantum measurements, and nonclassical correlations introduces coordination possibilities unavailable classically. This article reviews recent advances in coordination over classical and quantum communication networks, focusing on empirical and strong coordination in multi-user settings. We consider the implications of coordination for nonlocal games, showing how it provides a natural framework for understanding the correlations that enable spatially separated players to improve their probability of winning. We present a unified framework for coordination using classical or quantum communication and pre-shared correlation resources. The review covers simulation of both entanglement and separable correlations across a variety of network architectures, including two-node, cascade, broadcast, and multiple-access networks. We study the operational differences between empirical and strong coordination, and the tradeoffs between communication and correlation resources, such as pre-shared randomness and entanglement. Coordination plays a major role in device-independent quantum key distribution (DI-QKD) schemes, in which parties can generate a secret key even if the devices used in the process have been prepared by an adversary. Furthermore, we examine the role of coordination in quantum repeaters, where distributed entanglement serves as a resource for long-distance quantum communication. The review highlights connections between coordination theory and applications such as distributed quantum systems, quantum internet architectures, and future communication networks.

quant-pharXiv:2608.09540•Aug 11, 2026•0 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•Bozok journal of science.•Apr 13, 2026•0 citations

On the power of multipartite entanglement for pseudotelepathy

Gilles Brassard, Xavier Coiteux-Roy, Rémi Ligez

As early as 1935, Schrödinger recognized entanglement as ``not one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought''. Indeed, most remarkable phenomena in quantum information science, such as quantum computing and quantum teleportation, spring from clever uses of entanglement. Among them, pseudotelepathy enables two or more players to win systematically at some cooperative games with no need for communication between them, a restriction that would make the task impossible in a classical world. We investigate the power of multipartite entanglement for pseudotelepathy. Some known games that can be won with tripartite entanglement cannot be won with bipartite entanglement, but they can be won with bipartite nonsignalling resources such as the so-called Popescu--Rohrlich nonlocal box. We exhibit a five-player game that can be won with tripartite entanglement, but not with arbitrary bipartite nonsignalling resources even in the presence of arbitrary five-partite classical resources. This illustrates both the power of bipartite nonsignalling resources (over bipartite entanglement) and the even superior power of tripartite entanglement.

quant-pharXiv:2603.17956•Proceedings of the National Academy of Sciences•Mar 19, 2026•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•8 citations

Classical, Quantum and Non-signalling Resources in Bipartite Games

Gilles Brassard, Anne Broadbent, Esther Hänggi +2 more

We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP- complete, while the problem of deciding if these games admit a non-signalling winning strategy is in P. We discuss relations between quantum winning strategies and orthogonality graphs. We also show that every pseudo-telepathy game yields both a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof system that is classically sound, but that becomes unsound when provers use shared entanglement.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2008•1 citation
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.
Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics. The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT. The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible. We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size. The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific unit of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically). We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.
Coordination is a fundamental primitive in communication and information theory, in which distributed systems must collectively generate correlated behavior rather than merely exchange messages. In quantum networks, the nature of entanglement, quantum measurements, and nonclassical correlations introduces coordination possibilities unavailable classically. This article reviews recent advances in coordination over classical and quantum communication networks, focusing on empirical and strong coordination in multi-user settings. We consider the implications of coordination for nonlocal games, showing how it provides a natural framework for understanding the correlations that enable spatially separated players to improve their probability of winning. We present a unified framework for coordination using classical or quantum communication and pre-shared correlation resources. The review covers simulation of both entanglement and separable correlations across a variety of network architectures, including two-node, cascade, broadcast, and multiple-access networks. We study the operational differences between empirical and strong coordination, and the tradeoffs between communication and correlation resources, such as pre-shared randomness and entanglement. Coordination plays a major role in device-independent quantum key distribution (DI-QKD) schemes, in which parties can generate a secret key even if the devices used in the process have been prepared by an adversary. Furthermore, we examine the role of coordination in quantum repeaters, where distributed entanglement serves as a resource for long-distance quantum communication. The review highlights connections between coordination theory and applications such as distributed quantum systems, quantum internet architectures, and future communication networks.
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.
As early as 1935, Schrödinger recognized entanglement as ``not one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought''. Indeed, most remarkable phenomena in quantum information science, such as quantum computing and quantum teleportation, spring from clever uses of entanglement. Among them, pseudotelepathy enables two or more players to win systematically at some cooperative games with no need for communication between them, a restriction that would make the task impossible in a classical world. We investigate the power of multipartite entanglement for pseudotelepathy. Some known games that can be won with tripartite entanglement cannot be won with bipartite entanglement, but they can be won with bipartite nonsignalling resources such as the so-called Popescu--Rohrlich nonlocal box. We exhibit a five-player game that can be won with tripartite entanglement, but not with arbitrary bipartite nonsignalling resources even in the presence of arbitrary five-partite classical resources. This illustrates both the power of bipartite nonsignalling resources (over bipartite entanglement) and the even superior power of tripartite entanglement.
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 bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP- complete, while the problem of deciding if these games admit a non-signalling winning strategy is in P. We discuss relations between quantum winning strategies and orthogonality graphs. We also show that every pseudo-telepathy game yields both a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof system that is classically sound, but that becomes unsound when provers use shared entanglement.