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

Lecture notes in computer science

Nonlocal Quantum XOR Games for Large Number of Players

Andris Ambainis, Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Published Jan 1, 2010• 10 citations
Publisher
DOI
10.1007/978-3-642-13562-0_8

Related papers

Quantum strategies for simple two-player XOR games

Ricardo Faleiro

arXiv:1910.04478•Quantum Information Processing•Jul 3, 2020•3 citations

Quantum strategies are better than classical in almost any XOR game

Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis +4 more

We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.

arXiv:1112.3330•Dec 14, 2011•2 citations

Bounding Quantum-Classical Separations for Classes of Nonlocal Games

Tom Bannink, Jop Briët, Harry Buhrman +2 more

We bound separations between the entangled and classical values for several classes of nonlocal $t$-player games. Our motivating question is whether there is a family of $t$-player XOR games for which the entangled bias is $1$ but for which the classical bias goes down to $0$, for fixed $t$. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-$m$ games and show that their classical value is always at least $\frac{1}{m} + \frac{m-1}{m} t^{1-t}$. Secondly, for free XOR games, in which the input distribution is of product form, we show $β(G) \geq β^*(G)^{2^t}$ where $β(G)$ and $β^*(G)$ are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is $1-ε$ then the classical value is at least $1-\mathcal{O}(\sqrt{ε\log k})$ where $k$ is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.

arXiv:1811.11068•Leibniz international proceedings in informatics•Nov 27, 2018•11 citations

Quantum cooperative games

Azhar Iqbal, A. H. Toor

arXiv:quant-ph/0108091•Physics Letters A•Jan 1, 2002•57 citations

Classical versus quantum communication in XOR games

Marius Junge, Carlos Palazuelos, Ignacio Villanueva

arXiv:1706.02653•Quantum Information Processing•Apr 5, 2018•9 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
We bound separations between the entangled and classical values for several classes of nonlocal ttt-player games. Our motivating question is whether there is a family of ttt-player XOR games for which the entangled bias is 111 but for which the classical bias goes down to 000, for fixed ttt. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-mmm games and show that their classical value is always at least 1m+m−1mt1−t\frac{1}{m} + \frac{m-1}{m} t^{1-t}m1​+mm−1​t1−t. Secondly, for free XOR games, in which the input distribution is of product form, we show β(G)≥β∗(G)2tβ(G) \geq β^*(G)^{2^t}β(G)≥β∗(G)2t where β(G)β(G)β(G) and β∗(G)β^*(G)β∗(G) are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is 1−ε1-ε1−ε then the classical value is at least 1−O(εlog⁡k)1-\mathcal{O}(\sqrt{ε\log k})1−O(εlogk​) where kkk is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.
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.