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 Conference on Quantum, Nano and Micro Technologies (ICQNM)

Classical, Quantum and Non-signalling Resources in Bipartite Games

Gilles Brassard, Anne Broadbent, Esther Hänggi, André Allan Méthot, Stefan Wolf

Published Feb 1, 2008• 1 citation
Publisher

Abstract

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.

DOI
10.1109/icqnm.2008.18

Related papers

Quantum nonlocality, cryptography and complexity

Anne Broadbent

Quantum computing is the study of what we can and cannot do with quantum computers: computers operating based on the laws of quantum mechanics. This thesis is a collection of seven papers, dealing with three aspects of quantum computing: non-locality, cryptography and complexity. Nonlocality. Quantum nonlocality refers to the fact that, using a resource called quantum entanglement, two participants who are physically separated and unable to communicate can exhibit correlations that cannot be produced without entanglement. This gives rise to nonlocal games, which are multi-player cooperative games for which quantum players (who share entanglement) have an advantage over classical players (who share only classical information). A pseudo-telepathy game is a special case of a nonlocal game for which quantum players have a perfect winning strategy. The first paper in this thesis, On the power of non-local boxes, is a study of quantum correlations (which are non-signalling, i.e. they do not allow faster-than-light communication), as well as superquantum correlations (which are also non-signalling, but stronger than those predicted by quantum mechanics). We consider the simulation of pseudo-telepathy winning strategies with the nonlocal box (which can be seen as the most basic superquantum correlation), revealing that nonlocality and entanglement are different resources. Before our work, it was common to equate these two notions. The second paper, Classical, quantum and non-signalling resources in bipartite games, shows that the problem of deciding if a fixed game has a perfect classical winning strategy is NP-complete, while deciding if a perfect strategy exists with superquantum correlations is in P. We also establish links with the Bell-Kochen-Specker theorem, orthogonality graphs and two-prover interactive proofs. Quantum nonlocality is a phenomenon that we can, in theory, witness in the laboratory. Many experiments have been performed, but none so far have simultaneously closed all experimental loopholes. There is currently a substantial scientific effort to achieve the perfect laboratory experiment. Yet not all experimental setups are created equally: the third and fourth paper of this thesis, Entanglement swapping, light cones and elements of reality and On the logical structure of Bell theorems, show that recent proposals have classical explanations, and thus do nothing to aid in our comprehension of the quantum world. This work is scientifically valuable, since it tells us that we should not invest in the proposed lines of research. Classical and quantum cryptography. The groundbreaking work of Peter Shor in 1995 established that quantum computers can efficiently factor large integers, thus rendering most modern cryptographic systems insecure. But what quantum computers break, they also fix: Bennett and Brassard had already given in 1984 a protocol for key distribution whose security is based only on the laws of quantum mechanics. In a world with quantum computers, it seems like the only way to ensure perfect security in cryptographic tasks is to do away with computational assumptions (such as the apparent difficulty of factoring): this is the realm of information-theoretic security. In the fifth paper of this thesis, Information-theoretic security without an honest majority we give protocols to accomplish a series of six private distributed tasks (in particular, vote and anonymous message transmission), while ensuring information-theoretic security. Then, in Anonymous quantum communication, we give a protocol which, within a group, allows a sender to transfer a quantum message to a receiver ofhis choosing. The protocol ensures information-theoretic anonymity for the sender and the receiver as well as information-theoretic privacy for the message. Complexity in the measurement-based model. Finally, in Parallelizing quantum circuits, we study the depth complexity of quantum circuits, giving an automated technique for the parrallelization of quantum circuits. The development of parallel (low-depth) quantum circuits seems almost essential if we wish to implement quantum algorithms in the near future with available technology. Quantum information is usually unstable, hence we can only operate on it for a very short period of time. Parallel circuits maximize the use of this fragile quantum information. Our method is based on the recent paradigm for quantum computing called the measurement-based model. Key words: quantum information processing, pseudo-telepathy, nonlocal boxes, Bell's theorem, multi-party computation, information-theoretic security, anonymity, quantum depth complexity, measurement-based quantum computing, measurement calculus.

•Jan 1, 2008•0 citations

Two Party Pseudo Telepathy Games

Indranil Chakrabarty

In this work we have introduced two party pseudo telepathy games with respective winning conditions. One cannot win these games deterministically by any kind of classical protocols. Interestingly we find out that in quantum world, these winning conditions can be achieved if the players share an entangled state. We also introduced a game which is impossible to win if the players are form classical world, (both probabilistically and deterministically) yet there exists a perfect quantum strategy by following which, one can attain the winning condition of the game.

•Dec 28, 2006•1 citation

Maximally entangled states are not complete for pseudo-telepathy

Olivier Lalonde

One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.

quant-pharXiv:2608.05378•Aug 7, 2026•2 citations

Consequences and Limits of Nonlocal Strategies

Richard Cleve, Peter Høyer, Ben Toner +1 more

This paper investigates the powers and limitations of quantum entanglement in the context of cooperative games of incomplete information. We give several examples of such nonlocal games where strategies that make use of entanglement outperform all possible classical strategies. One implication of these examples is that entanglement can profoundly affect the soundness property of two-prover interactive proof systems. We then establish limits on the probability with which strategies making use of entanglement can win restricted types of nonlocal games. These upper bounds may be regarded as generalizations of Tsirelson-type inequalities, which place bounds on the extent to which quantum information can allow for the violation of Bell inequalities. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies for some games.

arXiv:quant-ph/0404076•Apr 12, 2004•84 citations

Absolute nonlocality via distributed computing without communication

Łukasz Czekaj, Marcin Pawłowski, Tamás Vértesi +3 more

Understanding the role that quantum entanglement plays as a resource in various information processing tasks is one of the crucial goals of quantum information theory. Here we propose an alternative perspective for studying quantum entanglement: distributed computation of functions without communication between nodes. To formalize this approach, we propose identity games. Surprisingly, despite no signaling, we obtain that nonlocal quantum strategies beat classical ones in terms of winning probability for identity games originating from certain bipartite and multipartite functions. Moreover we show that, for a majority of functions, access to general nonsignaling resources boosts success probability two times in comparison to classical ones for a number of large enough outputs. Because there are no constraints on the inputs and no processing of the outputs in the identity games, they detect very strong types of correlations: absolute nonlocality.

arXiv:1408.0993•Physical Review A•Sep 18, 2015•1 citation

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
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.
Quantum computing is the study of what we can and cannot do with quantum computers: computers operating based on the laws of quantum mechanics. This thesis is a collection of seven papers, dealing with three aspects of quantum computing: non-locality, cryptography and complexity. Nonlocality. Quantum nonlocality refers to the fact that, using a resource called quantum entanglement, two participants who are physically separated and unable to communicate can exhibit correlations that cannot be produced without entanglement. This gives rise to nonlocal games, which are multi-player cooperative games for which quantum players (who share entanglement) have an advantage over classical players (who share only classical information). A pseudo-telepathy game is a special case of a nonlocal game for which quantum players have a perfect winning strategy. The first paper in this thesis, On the power of non-local boxes, is a study of quantum correlations (which are non-signalling, i.e. they do not allow faster-than-light communication), as well as superquantum correlations (which are also non-signalling, but stronger than those predicted by quantum mechanics). We consider the simulation of pseudo-telepathy winning strategies with the nonlocal box (which can be seen as the most basic superquantum correlation), revealing that nonlocality and entanglement are different resources. Before our work, it was common to equate these two notions. The second paper, Classical, quantum and non-signalling resources in bipartite games, shows that the problem of deciding if a fixed game has a perfect classical winning strategy is NP-complete, while deciding if a perfect strategy exists with superquantum correlations is in P. We also establish links with the Bell-Kochen-Specker theorem, orthogonality graphs and two-prover interactive proofs. Quantum nonlocality is a phenomenon that we can, in theory, witness in the laboratory. Many experiments have been performed, but none so far have simultaneously closed all experimental loopholes. There is currently a substantial scientific effort to achieve the perfect laboratory experiment. Yet not all experimental setups are created equally: the third and fourth paper of this thesis, Entanglement swapping, light cones and elements of reality and On the logical structure of Bell theorems, show that recent proposals have classical explanations, and thus do nothing to aid in our comprehension of the quantum world. This work is scientifically valuable, since it tells us that we should not invest in the proposed lines of research. Classical and quantum cryptography. The groundbreaking work of Peter Shor in 1995 established that quantum computers can efficiently factor large integers, thus rendering most modern cryptographic systems insecure. But what quantum computers break, they also fix: Bennett and Brassard had already given in 1984 a protocol for key distribution whose security is based only on the laws of quantum mechanics. In a world with quantum computers, it seems like the only way to ensure perfect security in cryptographic tasks is to do away with computational assumptions (such as the apparent difficulty of factoring): this is the realm of information-theoretic security. In the fifth paper of this thesis, Information-theoretic security without an honest majority we give protocols to accomplish a series of six private distributed tasks (in particular, vote and anonymous message transmission), while ensuring information-theoretic security. Then, in Anonymous quantum communication, we give a protocol which, within a group, allows a sender to transfer a quantum message to a receiver ofhis choosing. The protocol ensures information-theoretic anonymity for the sender and the receiver as well as information-theoretic privacy for the message. Complexity in the measurement-based model. Finally, in Parallelizing quantum circuits, we study the depth complexity of quantum circuits, giving an automated technique for the parrallelization of quantum circuits. The development of parallel (low-depth) quantum circuits seems almost essential if we wish to implement quantum algorithms in the near future with available technology. Quantum information is usually unstable, hence we can only operate on it for a very short period of time. Parallel circuits maximize the use of this fragile quantum information. Our method is based on the recent paradigm for quantum computing called the measurement-based model. Key words: quantum information processing, pseudo-telepathy, nonlocal boxes, Bell's theorem, multi-party computation, information-theoretic security, anonymity, quantum depth complexity, measurement-based quantum computing, measurement calculus.
In this work we have introduced two party pseudo telepathy games with respective winning conditions. One cannot win these games deterministically by any kind of classical protocols. Interestingly we find out that in quantum world, these winning conditions can be achieved if the players share an entangled state. We also introduced a game which is impossible to win if the players are form classical world, (both probabilistically and deterministically) yet there exists a perfect quantum strategy by following which, one can attain the winning condition of the game.
One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.
This paper investigates the powers and limitations of quantum entanglement in the context of cooperative games of incomplete information. We give several examples of such nonlocal games where strategies that make use of entanglement outperform all possible classical strategies. One implication of these examples is that entanglement can profoundly affect the soundness property of two-prover interactive proof systems. We then establish limits on the probability with which strategies making use of entanglement can win restricted types of nonlocal games. These upper bounds may be regarded as generalizations of Tsirelson-type inequalities, which place bounds on the extent to which quantum information can allow for the violation of Bell inequalities. We also investigate the amount of entanglement required by optimal and nearly optimal quantum strategies for some games.
Understanding the role that quantum entanglement plays as a resource in various information processing tasks is one of the crucial goals of quantum information theory. Here we propose an alternative perspective for studying quantum entanglement: distributed computation of functions without communication between nodes. To formalize this approach, we propose identity games. Surprisingly, despite no signaling, we obtain that nonlocal quantum strategies beat classical ones in terms of winning probability for identity games originating from certain bipartite and multipartite functions. Moreover we show that, for a majority of functions, access to general nonsignaling resources boosts success probability two times in comparison to classical ones for a number of large enough outputs. Because there are no constraints on the inputs and no processing of the outputs in the identity games, they detect very strong types of correlations: absolute nonlocality.
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.