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:1502.02974 · Physical Review A

Generalized xor games with d outcomes and the task of nonlocal computation

Ravishankar Ramanathan, Remigiusz Augusiak, Gláucia Murta

Published Feb 29, 2016• 16 citations
arXivHTMLPDF

Abstract

Two-party xor games (correlation Bell inequalities with two outcomes per party) are the most studied Bell inequalities, and one of the few classes for which the optimal quantum value is known to be exactly calculable. We study a natural generalization of the binary xor games to the class of linear games with $d>2$ outcomes, and propose an easily computable bound on the quantum value of these games. Many interesting properties such as the impossibility of a quantum strategy to win these games, and the quantum bound on the CHSH game generalized to $d$ outcomes are derived. We also use the proposed bound to prove a large-alphabet generalization of the principle of no quantum advantage in nonlocal computation, showing that quantum theory provides no advantage in the task of nonlocal distributed computation of a class of functions with $d$ outcomes for prime $d$, while general no-signaling boxes do. This task is one of the information-theoretic principles attempting to characterize the set of quantum correlations from amongst general no-signaling ones.

DOI
10.1103/physreva.93.022333

Related papers

Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

Monika Rosicka, Ravishankar Ramanathan, P. Gnaciński +4 more

We study the classical and quantum values of a class of one- and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR (XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. XOR-d games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite XOR-d game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.

New Journal of Physics•Apr 21, 2016•8 citations

The powerfulness of classical correlations

Dardo Goyeneche, Wojciech Bruzda, Ondřej Turek +2 more

Determination of classical and quantum values of bipartite Bell inequalities plays a central role in quantum nonlocality. In this work, we characterize in a simple way bipartite Bell inequalities, free of marginal terms, for which the quantum value can be achieved by considering a classical strategy, for any number of measurement settings and outcomes. These findings naturally generalize known results about nonlocal computation and quantum XOR games. Additionally, our technique allows us to determine the classical value for a wide class of Bell inequalities, having quantum advantage or not, in any bipartite scenario.

arXiv:2004.00695•Apr 1, 2020•1 citation

Linear game non-contextuality and Bell inequalities - a graph-theoretic approach

P. Gnaciński, Monika Rosicka, Ravishankar Ramanathan +4 more

We study the classical and quantum values of one- and two-party linear games, an important class of unique games that generalizes the well-known XOR games to the case of non-binary outcomes. We introduce a ``constraint graph" associated to such a game, with the constraints defining the linear game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. Linear games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite linear game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.

arXiv:1511.05415•Nov 17, 2015•2 citations

Bell inequalities from outcome equalities

Ricardo Faleiro, Flavien Hirsch, Emmanuel Zambrini Cruzeiro +1 more

In this work, we study a particular class of Bell inequalities involving only direct equality-comparisons of outcomes. In the bipartite case, the scenario can be interpreted as a natural generalization of full-correlator in- equalities (XOR games) beyond binary outputs. We define the sub-polytope of the local polytope corresponding to this scenario and solve it for several bipartite and multipartite scenarios by leveraging some structural prop- erties. In doing so, we obtain thousands of new tight inequalities, many of which are also facets of the standard local polytope. We also define unanimous Bell inequalities, a particular case of the previous class applied to the multipartite setting in which only full-equality events (all outcomes equal) are considered. We show that such inequalities can always be written as deterministic nonlocal games, and we give a simple multipartite unanimous family and prove its local bound. We show that most of these inequalities admit quantum violations, and we also display aspects of their importance for nonlocality. For instance, we identify examples where such inequalities can act as dimension witnesses, outcome witnesses, witnesses of genuine multipartite nonlocality, as well as being relevant to CHSH. These results show that these simple and elegant inequalities by themselves provide a powerful tool for discovering new Bell inequalities and device-independent witnesses.

quant-pharXiv:2603.17030•Physical Review A•Mar 19, 2026•0 citations

Quantum bounds for compiled XOR games and d -outcome CHSH games

Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle +3 more

Nonlocal games play a crucial role in quantum information theory and have numerous applications in certification and cryptographic protocols. Kalai et al. (STOC 2023) introduced a procedure to compile a nonlocal game into a single-prover interactive proof, using a quantum homomorphic encryption scheme, and showed that their compilation method preserves the classical bound of the game. Natarajan and Zhang (FOCS 2023) then showed that the quantum bound is preserved for the specific case of the CHSH game. Extending the proof techniques of Natarajan and Zhang, we show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games: bipartite XOR games and a higher dimensional generalization of CHSH (the SATWAP inequality), that we refer to as d-outcome CHSH games. We also establish that, for any pair of qubit measurements, there exists a compiled XOR game such that its near-optimal winning probability serves as a robust selftest for that particular pair of measurements. Finally, we derive computational self-testing of three anticommuting qubit observables, based on the compilation of the nonlocal game corresponding to the so-called elegant Bell inequality.

arXiv:2403.05502•Quantum•Oct 28, 2025•2 citations

XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games

Richard Cleve, Eric Culf, Aviv Taller

It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.

quant-pharXiv:2607.06876•Jul 9, 2026•0 citations
Two-party xor games (correlation Bell inequalities with two outcomes per party) are the most studied Bell inequalities, and one of the few classes for which the optimal quantum value is known to be exactly calculable. We study a natural generalization of the binary xor games to the class of linear games with d>2d>2d>2 outcomes, and propose an easily computable bound on the quantum value of these games. Many interesting properties such as the impossibility of a quantum strategy to win these games, and the quantum bound on the CHSH game generalized to ddd outcomes are derived. We also use the proposed bound to prove a large-alphabet generalization of the principle of no quantum advantage in nonlocal computation, showing that quantum theory provides no advantage in the task of nonlocal distributed computation of a class of functions with ddd outcomes for prime ddd, while general no-signaling boxes do. This task is one of the information-theoretic principles attempting to characterize the set of quantum correlations from amongst general no-signaling ones.
We study the classical and quantum values of a class of one- and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR (XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. XOR-d games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite XOR-d game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.
Determination of classical and quantum values of bipartite Bell inequalities plays a central role in quantum nonlocality. In this work, we characterize in a simple way bipartite Bell inequalities, free of marginal terms, for which the quantum value can be achieved by considering a classical strategy, for any number of measurement settings and outcomes. These findings naturally generalize known results about nonlocal computation and quantum XOR games. Additionally, our technique allows us to determine the classical value for a wide class of Bell inequalities, having quantum advantage or not, in any bipartite scenario.
We study the classical and quantum values of one- and two-party linear games, an important class of unique games that generalizes the well-known XOR games to the case of non-binary outcomes. We introduce a ``constraint graph" associated to such a game, with the constraints defining the linear game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. Linear games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite linear game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.
In this work, we study a particular class of Bell inequalities involving only direct equality-comparisons of outcomes. In the bipartite case, the scenario can be interpreted as a natural generalization of full-correlator in- equalities (XOR games) beyond binary outputs. We define the sub-polytope of the local polytope corresponding to this scenario and solve it for several bipartite and multipartite scenarios by leveraging some structural prop- erties. In doing so, we obtain thousands of new tight inequalities, many of which are also facets of the standard local polytope. We also define unanimous Bell inequalities, a particular case of the previous class applied to the multipartite setting in which only full-equality events (all outcomes equal) are considered. We show that such inequalities can always be written as deterministic nonlocal games, and we give a simple multipartite unanimous family and prove its local bound. We show that most of these inequalities admit quantum violations, and we also display aspects of their importance for nonlocality. For instance, we identify examples where such inequalities can act as dimension witnesses, outcome witnesses, witnesses of genuine multipartite nonlocality, as well as being relevant to CHSH. These results show that these simple and elegant inequalities by themselves provide a powerful tool for discovering new Bell inequalities and device-independent witnesses.
Nonlocal games play a crucial role in quantum information theory and have numerous applications in certification and cryptographic protocols. Kalai et al. (STOC 2023) introduced a procedure to compile a nonlocal game into a single-prover interactive proof, using a quantum homomorphic encryption scheme, and showed that their compilation method preserves the classical bound of the game. Natarajan and Zhang (FOCS 2023) then showed that the quantum bound is preserved for the specific case of the CHSH game. Extending the proof techniques of Natarajan and Zhang, we show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games: bipartite XOR games and a higher dimensional generalization of CHSH (the SATWAP inequality), that we refer to as d-outcome CHSH games. We also establish that, for any pair of qubit measurements, there exists a compiled XOR game such that its near-optimal winning probability serves as a robust selftest for that particular pair of measurements. Finally, we derive computational self-testing of three anticommuting qubit observables, based on the compilation of the nonlocal game corresponding to the so-called elegant Bell inequality.
It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.