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:1506.07297 · Mathematical Programming

Linear conic formulations for two-party correlations and values of nonlocal games

Jamie Sikora, Antonios Varvitsiotis

Published Jul 29, 2016• 31 citations
arXivHTMLPDF
DOI
10.1007/s10107-016-1049-8

Related papers

Analysis of Boolean functions related to two-party nonlocal games for biased inputs

Jyotirmoy Basak, Anurag Ghosh

Quantum Information Processing•Sep 30, 2026•0 citations

Analysis of boolean functions related to binary input binary output two-party nonlocal games

Jyotirmoy Basak, Subhamoy Maitra, Prabal Paul +1 more

arXiv:2306.14815•Cryptography and Communications•Jun 9, 2023•1 citation

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

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

Ravishankar Ramanathan, Remigiusz Augusiak, Gláucia Murta

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.

arXiv:1502.02974•Physical Review A•Feb 29, 2016•23 citations

On symmetric nonlocal games

Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov +2 more

Theoretical Computer Science•Mar 25, 2013•2 citations

Monogamy of nonlocal games

David Cui, Arthur Mehta, Denis Rochette

Bell monogamy relations characterize the trade-offs in Bell inequality violations among pairs of players in multiplayer settings. In this work, we introduce a method for extending monogamy relations from a distinguished set of configurations to monogamy relations in all possible multiplayer settings. Applying this approach, we show that nonlocality in the Clauser, Horne, Shimony, and Holt game arises in only two cases: the original two-player scenario and the four-player scenario on a line. While the bound for this four-player scenario follows from known quadratic monogamy constraints, we also establish two six-party numerical monogamy relations that cannot be derived from existing results. In particular, we show there are points in the intersection of consecutive quadratic Bell monogamy relations which are not quantum realizable. Finally, we present a nonlocal game in which a single player can simultaneously saturate the quantum value with two other parties. This is an example of a nonlocal game unaffected by the monogamous nature of quantum entanglement.

arXiv:2405.20286•Physical Review Research•May 21, 2025•4 citations
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.
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.
Bell monogamy relations characterize the trade-offs in Bell inequality violations among pairs of players in multiplayer settings. In this work, we introduce a method for extending monogamy relations from a distinguished set of configurations to monogamy relations in all possible multiplayer settings. Applying this approach, we show that nonlocality in the Clauser, Horne, Shimony, and Holt game arises in only two cases: the original two-player scenario and the four-player scenario on a line. While the bound for this four-player scenario follows from known quadratic monogamy constraints, we also establish two six-party numerical monogamy relations that cannot be derived from existing results. In particular, we show there are points in the intersection of consecutive quadratic Bell monogamy relations which are not quantum realizable. Finally, we present a nonlocal game in which a single player can simultaneously saturate the quantum value with two other parties. This is an example of a nonlocal game unaffected by the monogamous nature of quantum entanglement.