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

Quantum bounds on multiplayer linear games and device-independent witness of genuine tripartite entanglement

Gláucia Murta, Ravishankar Ramanathan, Natália S. Móller, Marcelo Terra Cunha

Published Feb 3, 2016• 16 citations
arXivHTMLPDF

Abstract

Here we study multiplayer linear games, a natural generalization of xor games to multiple outcomes. We generalize a recently proposed efficiently computable bound, in terms of the norm of a game matrix, on the quantum value of two-player games to linear games with $n$ players. As an example, we bound the quantum value of a generalization of the well-known CHSH game to $n$ players and $d$ outcomes. We also apply the bound to show in a simple manner that any nontrivial functional box, that could lead to trivialization of communication complexity in a multiparty scenario, cannot be realized in quantum mechanics. We then present a systematic method to derive device-independent witnesses of genuine tripartite entanglement.

DOI
10.1103/physreva.93.022305

Related papers

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

Multiplayer XOR games and quantum communication complexity with clique-wise entanglement

Jop Briët, Harry Buhrman, Troy Lee +1 more

XOR games are a simple computational model with connections to many areas of complexity theory. Perhaps the earliest use of XOR games was in the study of quantum correlations. XOR games also have an interesting connection to Grothendieck's inequality, a fundamental theorem of analysis, which shows that two players sharing entanglement can achieve at most a constant factor advantage over players following classical strategies in an XOR game. Perez-Garcia et al. show that when the players share GHZ states, this advantage is bounded by a constant. We use a multilinear generalization of Grothendieck's inequality due to Blei and Tonge to simplify the proof of the second result and extend it to the case of so-called Schmidt states, answering an open problem of Perez-Garcia et al. Via a reduction given in that paper, this answers a 35-year-old problem in operator algebras due to Varopoulos, showing that the space of compact operators on a Hilbert space is a Q-algebra under Schur product. A further generalization of Grothendieck's inequality due to Carne lets us show that the gap between the entangled and classical value is at most a constant in any multiplayer XOR game in which the players are allowed to share combinations of GHZ states and EPR pairs of any dimension. As an application of our results, we show that the discrepancy method in communication complexity remains a lower bound in the multiparty model where the players have quantum communication and the kinds of entanglement discussed above. This answers an open question of Lee, Schechtman, and Shraibman.

arXiv:0911.4007•Nov 20, 2009•25 citations

A nonlocal game for witnessing quantum networks

Ming‐Xing Luo

Abstract Nonlocal game as a witness of the nonlocality of entanglement is of fundamental importance in various fields. The well-known nonlocal games or equivalent linear Bell inequalities are only useful for Bell networks consisting of single entanglement. Our goal in this paper is to propose a unified method for constructing cooperating games in network scenarios. We propose an efficient method to construct multipartite nonlocal games from any graphs. The main idea is the graph representation of entanglement-based quantum networks. We further specify these graphic games with quantum advantages by providing a simple sufficient and necessary condition. The graphic games imply a linear Bell testing of the nonlocality of general quantum networks consisting of EPR states. It also allows generating new instances going beyond CHSH game. These results have interesting applications in quantum networks, Bell theory, computational complexity, and theoretical computer science.

arXiv:1906.08398•npj Quantum Information•Oct 25, 2019•43 citations

Multipartite entanglement in XOR games

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Quantum Information Processing•Mar 1, 2013•1 citation

Multipartite entanglement in XOR games

Jop Briët, Harry Buhrman, Troy Lee +1 more

We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form $\sum_i \alpha_i \ket{i}\cdots\ket{i}$ for arbitrary amplitudes $\alpha_i$. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.

Quantum Information and Computation•Mar 1, 2013•17 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
Here we study multiplayer linear games, a natural generalization of xor games to multiple outcomes. We generalize a recently proposed efficiently computable bound, in terms of the norm of a game matrix, on the quantum value of two-player games to linear games with nnn players. As an example, we bound the quantum value of a generalization of the well-known CHSH game to nnn players and ddd outcomes. We also apply the bound to show in a simple manner that any nontrivial functional box, that could lead to trivialization of communication complexity in a multiparty scenario, cannot be realized in quantum mechanics. We then present a systematic method to derive device-independent witnesses of genuine tripartite entanglement.
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.
XOR games are a simple computational model with connections to many areas of complexity theory. Perhaps the earliest use of XOR games was in the study of quantum correlations. XOR games also have an interesting connection to Grothendieck's inequality, a fundamental theorem of analysis, which shows that two players sharing entanglement can achieve at most a constant factor advantage over players following classical strategies in an XOR game. Perez-Garcia et al. show that when the players share GHZ states, this advantage is bounded by a constant. We use a multilinear generalization of Grothendieck's inequality due to Blei and Tonge to simplify the proof of the second result and extend it to the case of so-called Schmidt states, answering an open problem of Perez-Garcia et al. Via a reduction given in that paper, this answers a 35-year-old problem in operator algebras due to Varopoulos, showing that the space of compact operators on a Hilbert space is a Q-algebra under Schur product. A further generalization of Grothendieck's inequality due to Carne lets us show that the gap between the entangled and classical value is at most a constant in any multiplayer XOR game in which the players are allowed to share combinations of GHZ states and EPR pairs of any dimension. As an application of our results, we show that the discrepancy method in communication complexity remains a lower bound in the multiparty model where the players have quantum communication and the kinds of entanglement discussed above. This answers an open question of Lee, Schechtman, and Shraibman.
Abstract Nonlocal game as a witness of the nonlocality of entanglement is of fundamental importance in various fields. The well-known nonlocal games or equivalent linear Bell inequalities are only useful for Bell networks consisting of single entanglement. Our goal in this paper is to propose a unified method for constructing cooperating games in network scenarios. We propose an efficient method to construct multipartite nonlocal games from any graphs. The main idea is the graph representation of entanglement-based quantum networks. We further specify these graphic games with quantum advantages by providing a simple sufficient and necessary condition. The graphic games imply a linear Bell testing of the nonlocality of general quantum networks consisting of EPR states. It also allows generating new instances going beyond CHSH game. These results have interesting applications in quantum networks, Bell theory, computational complexity, and theoretical computer science.
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form Σiαi|i〉... |i〉 for arbitrary amplitudes αi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical \emph{biases}, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, \PG proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form ∑iαi∣i⟩⋯∣i⟩\sum_i \alpha_i \ket{i}\cdots\ket{i}∑i​αi​∣i⟩⋯∣i⟩ for arbitrary amplitudes αi\alpha_iαi​. Our results have the following surprising consequence: \emph{classical} three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of two-player XOR games.
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.