# A nonlocal game for witnessing quantum networks

Ming-Xing Luo  1The School of Information Science and Technology, Southwest
Jiaotong University, Chengdu 610031, China;
2CSNMT, International Cooperation Research Center of China, Chengdu 610031,
China

###### Abstract

Nonlocal game as a witness of the nonlocality of entanglement is of
fundamental importance in various fields. The red 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.

## Introduction

A nonlocal game is generally described as multiple space-separated players
interacting with a referee. The communication between players are forbidden.
Remarkably, it is related to Bell theory that is fundament in quantum
mechanics 1 when players are allowed to share classical resources or quantum
entangled resources. Clauser-Horne-Shimony-Holt (CHSH) game as a distributed
evaluating of Boolean equation: $y_{1}\oplus y_{2}=x_{1}\wedge{}x_{2}$,
provides the first notable way for witnessing the nonlocality of Einstein-
Podolsky-Rosen (EPR) state, 1,2,3,4,5,6 where $x_{i},y_{i}$ are respective
binary input and output. The shared entanglement permits a quantum strategy
with larger winning probability than all classical strategies.

Generally, a nonlocal game allows all the players to determine a joint
strategy from the complete knowledge of inputs distribution and the predicate
conditions for win. The corresponding procedure can be featured by a
generalized hidden variable model with classical sources or quantum sources.1
One fundamental problem is to determine whether quantum mechanics is superior
to classical theory in terms of nonlocal tasks. These evaluations are
equivalent to solving special optimization problems from Tsirelson’s
reductions. 7 Unfortunately, no efficient algorithm exists for general
multipartite nonlocal games. 8,9,10,11,12,13 Besides verifying entanglement,
nonlocal games have so far inspired numerous applications, such as multi-
prover interactive proofs, 14,15,16 quantum proof verification, 17,18 hardness
of approximation, 19,20,21 PCP conjecture, 22,23,24 separating correlations,
25,26,27,28 and communication complexity theory.29,30

There are various interesting nonlocal games except for CHSH games. XOR games
are the most well studied.31,32,33,34 The global task is to XOR of the
outcomes of all players. Other games include Kochen-Specker game,4,31 non-zero
sum games,35,36 magic square game,37 graph isomorphism game,38 Bayesian
game,39 and conflicting interest game.40 The key to achieve a quantum
advantage is the nonlocal correlations generated by local measurements on the
shared entangled states. Similar correlations are not achievable by remote
players using local strategies with any shared classical resources. These
tasks show the important role of quantum entanglement in information
processing.41 Comparison to single entanglement,1 the network scenarios of
multiple independent sources require the nonlinear Bell inequalities to test
the nonlocality.42,43,44,45 Hence, how to construct meaningful nonlocal games
should be interesting in scaling applications of entangled resources. Two
related problems are as follows:

Problem 1. How to efficiently construct nonlocal games for space-separated
players who share a quantum network consisting of entangled states?

Problem 2. How to characterize nonlocal games with or without quantum
advantages in network scenarios?

The goal of this paper is to address these problems in the context of
cooperative nonlocal games, as shown in Fig.1. We propose a unified method to
construct multipartite games from graph representations of general multi-
source networks. Each game is determined by some subgraphs that can be
constructed efficiently. Note that for any graph with $N$ nodes, the proposed
method provides $O(4^{nN})$ different nonlocal games with $n$ players. These
graphic nonlocal games will further be classified in terms of the quantum
advantage using a simple sufficient and necessary condition. The result holds
for the same probability distribution of all inputs going beyond previous
algorithmic results 47 or semi-definite programs.7,10,11,48,49 Surprisingly,
the present graphic games allow testing the nonlocality of multi-source
quantum networks going beyond previous CHSH game for single
entanglement.1,2,3,36 Compared with the recent nonlinear witness,42,43,44,45
the graphic game provides the first verification of general networks using
linear Bell testing beyond semiquantum game.46 The new result is also useful
for nonlocal satisfiability problems going beyond CHSH game 3 and cubic
game.37 The graphic game finally extends the guessing your neighbor’s input
(GYNI) game.50,51 The present model provides novel instances to feature
nonlocal games with different performances.52

Figure 1: Cooperating nonlocal game. A referee chooses questions $x_{k}$s from
a finite set according to a prior distribution $p(\textbf{x})$, and sends to
players. Each player $\textsf{A}_{k}$ should output an answer $y_{k}$ based on
the received question $x_{k}$ and the shared resource without communicating
with other players. The referee then evaluates a payoff function $F$ with all
outputs and inputs to determine win or lose for all the players.

## Result

### Nonlocal multipartite cooperating games

An $n$-player nonlocal cooperating game consists of $n$ players
$\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{n}$ and a referee,31 as
shown in Fig.1. All the players agree with a joint strategy beforehand but
cannot communicate with each other during the game. The referee firstly
chooses $n$ questions: $x_{1},x_{2},\cdots,x_{n}$ from a finite set ${\cal
X}:=X_{1}\times X_{2}\times\cdots\times X_{n}$ according to a known
distribution $p(\textbf{x})$. And then, sends $x_{i}$ to $\textsf{A}_{i}$,
$i=1,2,\cdots,n$. All the players are now required to reply with answers
$y_{1},y_{2},\cdots,y_{n}$ chosen from a finite set ${\cal Y}:=Y_{1}\times
Y_{2}\times\cdots\times Y_{n}$ to the referee. Finally, the referee determines
whether all the players win or lose the game according to a payoff function:
$F:{\cal X}\times{\cal Y}\to\\{0,1\\}$, i.e., win if
$F(\textbf{x},\textbf{y})=1$ and lose if $F(\textbf{x},\textbf{y})=0$, where
$\textbf{x}=x_{1}x_{2}\cdots x_{n}$, $\textbf{y}=y_{1}y_{2}\cdots y_{n}$. The
optimal average winning probability of all the players, i.e., the nonlocal
value of the game, is defined by:

$\displaystyle\varpi_{c}=\sup_{\Omega}\sum_{\textbf{x},\textbf{y},\lambda}p(\textbf{x})\mu(\lambda)F(\textbf{x},\textbf{y})P(\textbf{y}|\textbf{x},\lambda)$
(1)

Here, $\mu(\lambda)$ is the probability measure of the hidden classical
resource $\lambda$ and satisfies $\sum_{\lambda}\mu(\lambda)=1$.
$P(\textbf{y}|\textbf{x},\lambda)$ denotes the joint conditional probability
depending on the shared randomness $\lambda$. The supremum is over all the
possible classical spaces $\Omega$ of hidden variables $\lambda$. Generally,
it is hard to approximate the nonlocal value $\varpi_{c}$ of multipartite
games.10,11,49 From the linearity of $\varpi_{c}$ with respect to all
probability distributions, it is sufficient use deterministic strategies for
all the players, i.e., $p(\lambda)=1$ for some $\lambda$.

In quantum scenarios, players are allowed to share various entangled states
and perform quantum measurements (with noncommuting operators which are
different from commuting operators in classical physics) to obtain answers.
Let $\rho$ be the shared entangled state. Denote positive-operator valued
measurements (POVMs) of all the observers as $\\{M_{y_{1}}^{x_{1}}\\}$,
$\\{M_{y_{1}}^{x_{2}}\\}$, $\cdots,\\{M_{y_{n}}^{x_{n}}\\}$, which depend on
the received questions $x_{1},x_{2},\cdots,x_{n}$. These operators satisfy the
normalization conditions: $\sum_{y_{i}}M_{y_{i}}^{x_{i}}=\mathbb{I}$ for
$i=1,2,\cdots,n$, where $\mathbb{I}$ is the identity operator. The optimal
winning probability for all the quantum players to player a cooperating
nonlocal game defined above is defined by:

$\displaystyle\varpi_{q}=\sup\sum_{\textbf{x},\textbf{y}}p(\textbf{x})F(\textbf{x},\textbf{y}){\rm{}Tr}[\otimes_{j=1}^{n}M_{y_{j}}^{x_{j}}\rho],$
(2)

where the supremum is over all the possible quantum states and local POVMs.
Note that each linear Bell-type inequality is equivalent to a cooperating
nonlocal game.53 The nonlocal value $\varpi_{q}$ is related to the Tsirelson
bound of linear Bell inequality.7 A central problem in the non-locality theory
is to find computable good bounds of nonlocal value $\varpi_{q}$.7,31
Unfortunately, it is QMA-hard to approximate the nonlocal value of
$\varpi_{q}$.17,53

### Graphic games

CHSH game provides a novel idea to witness a bipartite entanglement.2,3 As a
natural extension, it would be of interesting to characterize multiple
entangled states shared by space-separated observers in a network scenarios.
Although the linear testing of single entanglement53,55,56 allows designing
equivalent nonlocal game, it is unknown how to construct meaningful nonlocal
games for multi-source quantum networks that requires nonlinear testing
42,43,44,45 or semiquantum testing.46 To address this problem, we propose a
general method to construct nonlocal games from any graphs with only vertices.
Surprisingly, the graphic games can be completely classified with respect to
the nonlocal values. To explain the main result, we firstly present the
following definitions.

Definition 1. (The graphic representation of quantum networks) Consider a
multi-source network ${\cal N}_{q}$ consisting of multiple independent EPR
states shared by different observers. Its graphic representation is defined as
a vertex graph ${\cal G}_{q}$, where each node denotes one entanglement.

Figure 2: Graphic representation of multi-source quantum networks consisting
of EPR states. (a) Star-type network. Each of $n-1$ observers share one EPR
state with the center observer. (b) Chain-type network of entanglement
swapping in long distance. Any two adjacent observers share one EPR state.
Each entanglement is schematically represented by one vertex in graph. The
relationship that two observers share one entangled state is equivalent to two
players sharing one vertex, where each player owns vertices with the same
color.

Some typical examples of quantum networks are shown in Fig.2. Generally, for
any graph, we can assign a subgraph to each player accord to the input. In
this case, the relation that two observers share one entangled state is
equivalent to two players sharing one vertex, see Fig.2, where each player
owns some vertices with the same color. These nonlocal games can be then
characterized by using the consistency conditions on the common vertices
shared by different players. Formally, the graphic game is defined as follows:

Definition 2. An $n$-partite graphic game is a six-tuple: $({\cal G},{\cal
A},{\cal V},{\cal X},{\cal Y},F)$. ${\cal G}$ is a general graph with vertex
set $V$ (the edges are not required in this application). ${\cal A}$ denotes
the set of all the players $\textsf{A}_{i}$s and referee. ${\cal V}$ denotes
the set of all the vertex sets $V^{x_{i}}\subseteq V$ owned by players, where
$V^{x_{i}}$ denotes the set of vertices assigned to the player
$\textsf{A}_{i}$ according to the input question $x_{i}$. Assume that
$V^{x_{i}}$s satisfy the following conditions: $V^{x_{i}}\cap
V^{x_{j}}=\emptyset$ for $x_{i}=x_{j}=1$ with $1\leq i<j\leq m$, where $m$ is
a parameter satisfying $1\leq m<n$. ${\cal X}$ denotes the set of binary
problems $x_{1},x_{2},\cdots,x_{n}\in\\{0,1\\}$. ${\cal Y}$ denotes the set of
all the assignments on vertices (as outputs) by players. $F:{\cal
X}\times{\cal Y}\to\\{0,1\\}$ is a payoff function depending on all the inputs
and outputs of players. A graphic game is implemented as follows:

  * Input-The referee randomly chooses binary question $x_{i}$ according to the distribution $\\{p,1-p\\}$, and sends to the player $\textsf{A}_{i}$, $i=1,2,\cdots,n$.

  * Output-The player $\textsf{A}_{i}$ assigns an integer $y_{i}\in\\{\pm 1\\}$ on each vertex in the set $V^{x_{i}}$, and sends all the assignments to the referee secretly.

  * Winning conditions-All the players win the graphic game, i.e., $F(\textbf{x},\textbf{y})=1$, if and only if their assignments satisfy the following consistency conditions:

    * (a)

$S^{x_{i}}=1$ for $i=m+1,m+2,\cdots,n$;

    * (b)

$S^{x_{i};x_{j}}=-1$ when $x_{i}=x_{j}=1$, or $1$ otherwise, for $1\leq i\leq
m<j\leq n$;

    * (c)

$S^{x_{i};x_{j}}=S^{x_{j};x_{i}}=1$ for $m<i<j\leq n$;

where $S^{x_{i}}$ denotes the product of all the assignments of the player
$\textsf{A}_{i}$, and $S^{x_{i};x_{j}}$ denotes the product of all the
assignments by the player $\textsf{A}_{i}$ on the vertices shared with the
player $\textsf{A}_{j}$.

Definition 2 contains previous nonlocal games 3,31,37 as special cases. The
consistency conditions (the conditions (b) and (c) in Definition 2) are
important for the most of nonlocal games.3 Quantum correlations derived from
entangled resources can satisfy these kinds of requirements with higher
winning probability over all classical achievable correlations. Here, $m$ is a
free parameter satisfying $1\leq m<n$, which is used to feature the players
whose assignments satisfy the consistency conditions. Specifically, the
consistency conditions should be satisfied by the outputs of all the players
to win a nonlocal game. Our graphic game is then similar to a nonlocal
computation such as CHSH game with nonlinear restrictions shown in conditions
(a)-(c). Generally, for a graph ${\cal G}$ with $N$ vertices, there are
$2^{N}-1$ nontrivial subgraphs, which imply $O(4^{nN})$ different graphic
games. It is hard to evaluate or approximate the nonlocal values for all these
games. Hence, it should be interesting if some restricted games can be
distinguished.

Figure 3: A graphic nonlocal game. (a) A graph with two vertices. (b) A
graphic game with two players. The player $\textsf{A}_{i}$ holds the vertex
$v_{i}$ independent of the input, $i=1,2$. (c) A graphic game with two
players. The player $\textsf{A}_{1}$ holds the vertex $v_{x_{1}}$ depending on
its input $x_{1}$ while the player $\textsf{A}_{2}$ owns the vertices
$v_{1},v_{2}$ independent of the input. (d) A graphic game with two players.
The player $\textsf{A}_{i}$ holds the vertexes $v_{1},v_{2}$ independent of
the input, $i=1,2$. The players can share classical or quantum resources.

### Toy example

Take the graph ${\cal G}$ shown in Fig.3(a) as an example. There are two
players in Fig.3(b). Each player holds one vertex independent of inputs, where
their outputs are $1-2x_{1},1-2x_{2}$. There is no consistency requirement for
two players with $m=1$. It is easy to obtain $\varpi_{c}=1$ for classical
players. Hence, there is no quantum advantage from $\varpi_{q}=\varpi_{c}=1$.
For the game in Fig.2(c), the player $\textsf{A}_{1}$ holds different vertices
$v_{x_{1}+1}$ according to the input $x_{1}$ while $\textsf{A}_{2}$ owns the
whole graph independent of the input. In this case, two players have to
satisfy the consistency requirements in conditions (b) and (c), i.e.,
$y_{1;A_{1}}=y_{1;A_{2}}=1$ and $y_{2;A_{1}}=y_{2;A_{2}}=-1$, where
$y_{i;A_{j}}$ denotes the assignment on the vertex $v_{i}$ by the player
$\textsf{A}_{j}$. Now, assume that the player $\textsf{A}_{1}$ assigns
$1-2x_{1}$ on the shared one vertex according to the input $x_{1}$. The player
$\textsf{A}_{2}$ assigns the same value of $1-2x_{2}$ on two vertices. With
these assignments, the graphic game is equivalent to CHSH game. 3 This implies
a strict quantum advantage for two players who share an EPR state.2 Similar
result holds for the graphic game shown in Fig.3(d). To explain the main
result, some definitions will be introduced beforehand.

Definition 3. Consider a graphic game with $n$ players
$\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{n}$. For each $i$ with
$1\leq i\leq m$, ${\cal A}_{i}$ denotes the set of players $\textsf{A}_{j}$s
($m+1\leq j\leq n$) who share vertices with $\textsf{A}_{i}$ for each input
$x_{i}x_{j}$, i.e.,

$\displaystyle{\cal{}A}_{i}=\\{\textsf{A}_{j}|V^{x_{i}}\cap{V}^{x_{j}}\not=\emptyset,\forall
x_{i},x_{j}=0,1\\}.$ (3)

Definition 4. Denote ${\cal{}A}^{s}_{i}$ as the set of players as follows:

$\displaystyle{\cal
A}^{s}_{i}=\\{(\textsf{A}_{i},\textsf{A}_{i_{1}},\cdots,\textsf{A}_{i_{s-1}})|\textsf{A}_{i_{j}}\in{\cal
A}_{i},V^{x_{i}}\cap(\cap_{j=1}^{s-1}V^{x_{i_{j}}})\not=\emptyset,\forall
x_{i},x_{2},\cdots,x_{i_{s-1}}=0,1\\},$ (4)

where each element consists of $s$ players
$\textsf{A}_{i},\textsf{A}_{i_{1}},\cdots,\textsf{A}_{i_{s-1}}$ who share
common vertices for each input $x_{i}x_{i_{1}}\cdots{}x_{i_{s-1}}$, and $2\leq
s\leq n-m$.

${\cal A}^{s}_{i}$ characterizes the consistency requirements among $s$
players of $\textsf{A}_{j}$s and $\textsf{A}_{i}$. In what follows, we omit
the case that all the players have no common vertex because of
$\varpi_{c}=\varpi_{q}$.

Definition 5. Let $I_{i}$ be an integer associated with ${\cal{}A}^{s}_{i}$
as:

$\displaystyle I_{i}=\min\\{s|{\cal{}A}^{s}_{i}\not=\emptyset\\},\forall
i=1,2,\cdots,m.$ (5)

With these definitions, we find all the graphic games with quantum advantages
when proper consistency conditions are satisfied.

Theorem 1. For any graphic game with $\varpi_{c}\not=1$, there is a quantum
advantage, i.e., $\varpi_{q}>\varpi_{c}$, if and only if
$\min\\{I_{1},I_{2},\cdots,I_{m}\\}=2$.

Theorem 1 presents a sufficient and necessary condition for graphic games with
quantum advantage. One example is shown in Fig.3(b). This provides the first
instance for Problem 2 with a deterministic separation of classical
correlations and quantum correlations in correlation space. It is interesting
to intuitively show the relationship between $I_{i}$ and quantum advantage.
Note that ${\cal{}A}^{s}_{i}$ shown in Eq.(4) features the number of players
who have the consistency requirements with $\textsf{A}_{i}$ independent of
inputs. If one divides a network into $m$ subnetworks according to players
$\textsf{A}_{i}$s ($i=1,2,\cdots,m$) who have no shared vertices, $I_{i}$ is
then used to describe the topology characters of a given network. Specially,
it means that the network consists of star-type in Fig.2(a) networks or chain-
type subnetworks in Fig.2(b) for $I_{i}=2$. For $I_{i}=k>2$, the network
consists of various cyclic subnetworks. In this case, similar to previous
nonlinear method 42,43,44,45 Theorem 1 implies that there is no useful linear
testing scheme for cyclic networks. One example is triangle network 42,45. The
proof is inspired by the unbalanced CHSH game shown in Supplementary Notes 1
and 2.6,37 To explain the main idea, consider a graphic game ${\cal G}$ with
$m=1$ consisting of three players
$\textsf{A}_{1},\textsf{A}_{2},\textsf{A}_{3}$. Two different games ${\cal
G}_{i}$ are defined as follows. ${\cal G}_{1}$ requires that the outputs of
two pairs of players $\\{\textsf{A}_{1},\textsf{A}_{2}\\}$, and
$\\{\textsf{A}_{1},\textsf{A}_{3}\\}$ are consistency simultaneously. ${\cal
G}_{2}$ requires that the outputs of three pairs of players
$\\{\textsf{A}_{1},\textsf{A}_{2}\\}$, and
$\\{\textsf{A}_{1},\textsf{A}_{3}\\}$, and
$\\{\textsf{A}_{2},\textsf{A}_{3}\\}$ are consistency simultaneously. Both
games can be regarded as two and three simultaneous CHSH games, respectively.
Theorem 1 means that ${\cal G}_{1}$ has a quantum advantage with $I_{1}=2$
while ${\cal G}_{2}$ has no quantum advantage with $I_{1}=3$. The main reason
is that there are too many restrictions in ${\cal G}_{2}$ to achieve a quantum
advantage. This provides a new witness for entanglement-based quantum
networks45 and nonlocal games.33

### Witnessing multi-source quantum networks

Multi-source quantum networks can extend applications of single-source Bell
network in large scale.60,61 However, it is hard to verify these distributive
entangled states in global pattern due to the non-convexity of quantum
correlations. One useful way is to make use of some nonlinear Bell-type
inequalities.42,43,44,45 Interestingly, the present model provides another
witness for general quantum networks. Specifically, let one vertex
schematically represent one EPR state, as shown in Definition 1.2 Any multi-
source quantum network consisting of EPR states is equivalent to a graph with
lots of vertices. Some examples are shown in Fig.2. Fig.2(a) presents a star-
type quantum network, where each pair of $\textsf{B}_{i}$ and A share one EPR
state $|\Phi\rangle_{i}$, $i=1,2,\cdots,n-1$. Its graphic representation
consists of $n-1$ vertices $v_{1},v_{2},\cdots,v_{n-1}$. The assumption that
each pair of players share one EPR state can be schematically represented by
sharing one vertex in terms of the graphic game in Definition 2. Similar
representation holds for chain-type network shown in Fig.2(b). From the
equivalent reformations, there are lots of testing to achieve a quantum
advantage when the graphic games are defined. Generally, from Theorem 1 we
obtain a corollary as:

Corollary 1. For any quantum network ${\cal N}_{q}$ consisting of EPR states
shared by $n$ observers, there are nonlocality witnesses in terms of graphic
game if ${\cal N}_{q}$ is $k$-independent with $k\geq 2$.

In Corollary 1, $k$-independence means that there are a set of $k$ observers
who do not share any entanglement among themselves. Note that for verifying
quantum networks, all the shared vertices $V^{x_{i}}$s are independent of
inputs. From the equivalent reduction,45 any $k$-independent network is
equivalent to a generalized star-type network, as shown in Fig.2(a). The proof
of Corollary 1 follows easily from the corresponding graphic games, where
$\min_{i}I_{i}=2$ because no more than two players share vertices. Take the
star-type network shown in Fig.2(a) as an example. Each pair of players
$\\{\textsf{B}_{i},\textsf{A}\\}$ shares one vertex $v_{i}$ independent of
their inputs, $i=1,2,\cdots,n-1$. There exists quantum advantage because of
$I_{1}=2$ by assuming $m=1$ (or $m=n-1$). For the chain-type network shown in
Fig.2(b), each vertex $v_{i}$ is owned by two adjacent players
$\textsf{A}_{i}$ and $\textsf{A}_{i+1}$. One can define different $m$ by
choosing the players without sharing vertices (independent in quantum
networks).45 Quantum advantages hold for these graphic games. Generally, the
present graphic games allow the first linear testing for multi-source quantum
networks consisting of EPR states.

### CHSH game

Two equivalent forms of CHSH game in Ref.[3] are shown in Fig.3(c) and
Fig.3(d). Another extension is cube game, which is defined over an
$n$-dimensional cube graph ${\cal G}$ with $2^{n}$ vertices represented by
$\\{(q_{1},q_{2},\cdots,q_{n}),\forall q_{i}=0,1\\}$, as shown in Fig.4(a),
where $m=1$. Specially, the referee randomly chooses binary question
$x_{i}\in\\{0,1\\}$ according to a given distribution $\\{p,1-p\\}$, and sends
it to the player $\textsf{A}_{i}$. Each player assigns $1$ or $-1$ to their
own vertices on $n-1$-dimensional hyperplane defined by
$\\{(q_{1},q_{2},\cdots,q_{n})|q_{i}=x_{i}\\}$ and sends to the referee. All
the players win the game if and only if their assignments satisfy the
requirements in Definition 2. From Theorem 1, it follows that the cubic game
has no quantum advantage over all the classical strategies when $n\geq 3$,
where $I_{1}=n$. Our result is different from a recent result with relaxed
consistency conditions.35 Another simple extension with $m\geq 1$ is defined
as: the player $\textsf{A}_{i}$ owns the local subgraph defined by
$\\{(q_{1},q_{2},\cdots,q_{n})|q_{1}=q_{2}=\cdots=q_{m}=x_{i}\\}$ for
$i=1,2,\cdots,m$, and $\\{(q_{1},q_{2},\cdots,q_{n})|q_{j}=x_{j}\\}$ for
$j=m+1,m+2,\cdots,n$. Note that any two players of
$\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{m}$ have no common subgraph
for all the inputs. It is straightforward to check that this generalization
has quantum advantage when $m=n-1$.

Figure 4: Some graphic games. (a) Cubic game. Each player owns all the
vertices on a 2-dimensional plane (denoted by $A_{i}$, $B_{j}$, $C_{k}$) with
different colors depending on the input. (b) The equivalent graphic game of
GYNI game.50 Each player owns three vertices of one subgraph (denoted by $A$,
$B$, $C$) with different colors. Here, the edges with dot lines are used for
visualization.

### Distributive SAT problems

A Boolean satisfiability problem (SAT) aims to check some given equations.62
The decision problem is of central importance in theoretical computer science,
complexity theory and algorithmic theory.63 Interestingly, each graphic game
is equivalent to a distributive SAT problem. Take the game shown in Fig.4(a)
as an example. Let $y_{i,x_{j}}$ be assignment on the vertex $v_{i}$ by
$\textsf{A}_{j}$ according to the input $x_{j},i=1,2,\cdots,8;j=1,2,3$. From
Definition 2, the winning conditions are equivalent to Boolean equations with
48 variables. Theorem 1 shows a qualitative decision without quantum advantage
from shared entangled resources. Generally, for an $n$-player graphic game
involving $N$ vertices, there are $O(nN)$ conditions which should be
checked.64 Theorem 1 provides an intuitive completion for distributive SAT
problems with different resources using graphic game model. Hence, in
applications, an equivalent graphic game should be found for special decision
problems. One possible way is to reduce the required clauses firstly even if
it is hard. And then, define a graphic game clause-by-clause. Special output
strategies may be applied as guess your neighbour’s input (GYNI) game. 50

### GYNI game

Guess your neighbour’s input (GYNI) game has recently been proposed to
separate the multipartite quantum correlations from classical correlations. 50
This game is equivalently represented by a graphic game, as shown in Fig.4(b).
The original consistency requirements are equivalently reduced to special
output strategies for all the players, where the input is assigned the vertex
$v_{2i-1}$ for the players $\textsf{A}_{i},i=1,2,3$. This kind of graphic game
has no quantum advantage for any quantum resources. It can be viewed as a
relaxed graphic game satisfying partial consistency conditions in Definition
2. Here, we prove a more generalized result. Specifically, consider the
following winning condition, i.e., $F(\textbf{x},\textbf{y})=1$ if
$y_{i}=f_{i}(\textbf{x})$ for all $i$s; Otherwise,
$F(\textbf{x},\textbf{y})=0$. Here, $f_{i}$ denotes some function of the input
bit series x. As an example, $f_{i}(\textbf{x})$ can be regarded as the
restriction of the product of all the assigned values in the graphic games.

Theorem 2. There is no quantum advantage for a multipartite nonlocal game if
${\cal F}:\textbf{x}\mapsto(f_{1}(\textbf{x}),f_{2}(\textbf{x})$, $\cdots$,
$f_{n}(\textbf{x}))$ is injective.

The proof is similar to its in Ref.[50] which is shown in Supplementary Note
3. This provides another feature to address Problem 2. Some examples are
presented as follows.

Example 1. Consider $f_{1},f_{2},\cdots,f_{n}$ be any permutation in the
permutation group $S_{n}$. Take $n=3$ as an example. All the permutations are
given by $S_{3}=\\{(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2)\\}$, where $(1)$
denotes the identity operator, $(i,j)$ denotes the permutation of $i\to j$ and
$j\to i$, and $(i,j,k)$ denotes the permutation of $i\to j$, $j\to k$ and
$k\to i$. Now, define the expected output of three parties as $g(i,j,k)$ for
the corresponding inputs $i,j,k$ where $g\in S_{3}$. For the games with
$(f_{1},f_{2},f_{3})=(i,j,k)$ are previous games of guessing the neighbor’
input. 50 From Theorem 2, there is no quantum advantage for this kind of games
over classical resources.

Example 2. Consider $f_{1},f_{2},\cdots,f_{n}$ be any injective mapping going
beyond the permutation group $S_{n}$, where $\\{0,1\\}^{n}$ is input space
while $\mathbb{R}^{n}$ is output space. Take $n=3$ as an example. Consider the
following mappings: ${\cal
F}_{1}:(x_{1},x_{2},x_{3})\mapsto(x_{2}+x_{3},x_{1}+x_{3},x_{1}+x_{2})$ and
${\cal
F}_{2}:(x_{1},x_{2},x_{3})\mapsto(2^{x_{1}}-2^{x_{2}+x_{3}},2^{x_{2}}-2^{x_{1}+x_{3}},2^{x_{3}}-2^{x_{1}+x_{2}})$.
Both mappings are injective. If the mappings are used as the winning
conditions of players, Theorem 2 implies no quantum advantages for these
games.

Example 3. Define $f_{i}=\prod_{j=1}^{k_{i}}s_{i_{j}}$, for $i=1,2,\cdots,n$.
Assume that $s_{i_{1}},s_{i_{2}},\cdots{},s_{i_{k_{i}}}$ denote special
assigns on the subgarph shared by the player $\textsf{A}_{j}$. If
$s_{i}\in\\{\pm 1\\}$, the new game falls into graphic game proved in Theorem
1 when $f_{i}$s are injective mappings. There is no quantum advantage from
Theorem 1 or Theorem 2. Interestingly, similar result holds for
$s_{i}\in\mathbb{R}$ going beyond the games stated in Theorem 1.

## Discussion

Theorem 1 provides a result for separating quantum correlations from classical
correlations in terms of multi-source networks. The consistency conditions in
Definition 2 characterize the ”incompatible measurements” derived from quantum
mechanics. These conditions should be carefully designed for special goals in
applications. Unfortunately, the graphic game cannot solve generalized XOR
game which is an extension of CHSH game. 1,3,31 Another interesting problem is
how to define meaningful consistency conditions such as assignments on edges
going beyond Definition 2 for different goals including verifying general
cyclic networks. 42,45

Generally, we presented a unified way to construct multipartite nonlocal games
using graph representations of entanglement-based quantum networks. The
graphic games with quantum advantage are distinguished from others for general
graphs. The new model is useful for witnessing general quantum networks
consisting of EPR states. This can be regarded as a new feature of multi-
source networks going beyond nonlinear Bell-type inequalities and semiquantum
game. Our results are interesting in Bell theory, quantum Internet,
theoretical computer science, and distributive computations.

## Data availability

There is no data for the theoretical result.

## References

  * (1) Bell, J. S. On the einstein podolsky rosen paradox. Phys. 1, 195 (1964).
  * (2) Einstein, A., Podolsky, B., Rosen, N. Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47, 777-780 (1935).
  * (3) Clauser, J. F., Horne, M. A., Shimony, A. and Holt, R. A. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880-884 (1969).
  * (4) Kochen, S. and Specker, E. P. The problem of hidden variables in quantum mechanics. J. Math. Mec. 17, 59-87 (1967).
  * (5) Werner, R. F. Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model. Phys. Rev. A 40, 4277 (1989).
  * (6) Lawson, T., Linden, N. and Popescu, S. Biased nonlocal quantum games, http://arxiv.org/abs/1011.6245, (2010).
  * (7) Cirel’son, B. S. Quantum generalizations of Bell’s inequality. Lett. Math. Phys. 4, 83-100 (1980).
  * (8) Gurvits, L. Classical deterministic complexity of edmonds problem and quantum entanglement. In Proc. of the 35th ACM symp. on Theory of comp., pp. 10-19, 2003.
  * (9) Doherty, A. C., Liang, Y. C., Toner, B. & Wehner, S. The quantum moment problem and bounds on entangled multi-prover games. In 23rd Annual IEEE Conference on Computational Complexity, pp.199-210, 2008.
  * (10) Harrow, A. W., Natarajan, A., and Wu, X. Limitations of Semidefinite Programs for Separable States and Entangled Games. Commun. Math. Phys. 366, 423 C468 (2019).
  * (11) Kempe, J., Kobayashi, H., Matsumoto, K., Toner, B. & Vidick, T. Entangled games are hard to approximate. SIAM J. Computing 40, 848-877 (2011).
  * (12) Hastad, J. Some optimal inapproximability results. J. ACM 48, 798-859 (2001).
  * (13) Navascués, M., Guryanova, Y., Hoban, M. J. and Acin, A. Almost quantum correlations. Nat. Commun. 6, 6288 (2015).
  * (14) Ben-Or, M., Goldwasser, S., Kilian, J., and Widgerson, A. Multi-prover interactive proofs: how to remove intractability assumptions. Proc. of the twentieth annual ACM symposium on Theory of computing-STOC, ACM, pp. 113-131, 1988.
  * (15) Gutoski, G. and Watrous, J. Toward a general theory of quantum games. In Proc. of the thirty-ninth annual ACM symposium on Theory of computing, ACM, pp. 565-574, 2007.
  * (16) Ito, T., Kobayashi, H., Preda, D., Sun, X. and Yao, A. C. C. Generalized Tsirelson inequalities, commuting-operator provers, and multi-prover interactive proof systems. 23rd Annual IEEE Conference on Computational Complexity, IEEE, pp. 187-198, 2008.
  * (17) Babai, L., Fortnow, L., and Lund, C. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3-40 (1991).
  * (18) Reichardt, B. W., Unger, F., and Vazirani, U. Classical command of quantum systems. Nature 496, 456 (2013).
  * (19) Ji, Z. Classical verification of quantum proofs. In Proc. of the forty-eighth annual ACM symposium on Theory of Computing, ACM, pp. 885-898, 2016.
  * (20) Feige, U., Goldwasser, S., Lovsz, L., Safra, S., and Szegedy, M. Interactive proofs and the hardness of approximating cliques, J. ACM, 43, 268-292 (1996).
  * (21) Vidick, T. Three-player entangled XOR games are NP-hard to approximate. SIAM J. Comput. 45, 1007-1063 (2016).
  * (22) Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. Proof verification and the hardness of approximation problems. J. ACM 45, 501-555 (1998).
  * (23) Arora, S. and Safra, S. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 70-122 (1998).
  * (24) Aharonov, D., Arad, I. and Vidick, T. Guest column: the quantum PCP conjecture. ACM Sigact News 44, 47-79 (2013).
  * (25) Slofstra, W. Tsirelson’s problem and an embedding theorem for groups arising from non-local games, http://arxiv.org/abs/1606.03140, (2016).
  * (26) Slofstra, W. The set of quantum correlations is not closed, http://arxiv.org/abs/1703.08618, (2017).
  * (27) Dykema, K., Paulsen, V. I. & Prakash, J. Non-closure of the set of quantum correlations via graphs. Commun. Math. Phys., 365, 1125-1142 (2019).
  * (28) Coladangelo, A. and Stark, J. Unconditional separation of finite and infinite-dimensional quantum correlations, http://arxiv.org/abs/1804.05116 (2018).
  * (29) Brassard, G., et al. Limit on nonlocality in any world in which communication complexity is not trivial. Phys. Rev. Lett. 96, 250401 (2006).
  * (30) Buhrman, H., Cleve, R., Massar, S. and De Wolf, R. Nonlocality and communication complexity. Rev. Mod. Phys. 82, 665 (2010).
  * (31) Cleve, R., Hoyer, P., Toner, B., and Watrous, J. Consequences and limits of nonlocal strategies, Proc. 19th IEEE Conf. on Computational Complexity, pp.236-249, 2004.
  * (32) Ramanathan, R., Augusiak, R. and Murta, G. Generalized XOR games with $d$ outcomes and the task of non-local computation. Phys. Rev. A  93, 022333 (2016).
  * (33) Ambainis, A., et al. Quantum strategies are better than classical in almost any XOR game, International Colloquium on Automata, Languages, and Programming, Springer, Berlin, Heidelberg, pp.25-37, 2012.
  * (34) Regev, O. and Vidick, T. Quantum XOR games, ACM Trans. Comput. Theory  7, 15 (2015).
  * (35) Eisert, J., Wilkens, M. and Lewenstein, M. Quantum games and quantum strategies. Phys. Rev. Lett. 83, 3077 (1999).
  * (36) Mermin, N. D. Extreme quantum entanglement in a superposition of macroscopically distinct states. Phys. Rev. Lett. 65, 1838 (1990).
  * (37) He, X., Fang, K., Sun, X. and Duan, R. Quantum advantages in hypercube game, http://arxiv.org/abs/1806.02642 (2018).
  * (38) Atserias, A., et al. Quantum and non-signalling graph isomorphisms. J. Comb. Theory B, 136, 289-328 (2019).
  * (39) Brunner, N. and Linden, N. Connection between Bell nonlocality and Bayesian game theory. Nat. Commun. 4, 2057 (2013).
  * (40) Pappa, A., et al. Nonlocality and conflicting interest games. Phys. Rev. Lett. 114, 020401 (2015).
  * (41) Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V. and Wehner, S. Bell nonlocality. Rev. Mod. Phys. 86, 419 (2014).
  * (42) Branciard, C., Gisin, N. and Pironio, S. Characterizing the nonlocal correlations created via entanglement swapping. Phys. Rev. Lett. 104, 170401 (2010).
  * (43) Rosset, D., et al. Nonlinear Bell inequalities tailored for quantum networks. Phys. Rev. Lett. 116, 010403 (2016).
  * (44) Chaves, R. Polynomial bell inequalities. Phys. Rev. Lett. 116, 010402 (2016).
  * (45) Luo, M.-X. Computationally efficient nonlinear Bell inequalities for quantum networks. Phys. Rev. Lett. 120, 140402 (2018).
  * (46) Luo, M.-X. Nonlocality of all the quantum networks. Phys. Rev. A 98, 042317. (2018).
  * (47) Chailloux, A., Mancinska, L., Scarpa, G. and Severini, S. Graph-theoretical bounds on the entangled value of non-local games, In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography, pp.67, 2014.
  * (48) Wehner, S. Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities. Phys. Rev. A 73, 022110 (2006).
  * (49) Fortnow, L., Rompel, J. and Sipser, M. On the power of multi-prover interactive protocols. Theor. Comput. Sci. 134, 545-557 (1994).
  * (50) Almeida, M. L., et al. Guess your neighbor’s input: A multipartite nonlocal game with no quantum advantage. Phys. Rev. Lett. 104, 230404 (2010).
  * (51) Wang, H. M., Zhou, H. Y., Mu, L. Z. and Fan, H. Classification of no-signaling correlation and the guess your neighbor’s input game. Phys. Rev. A 90, 032112 (2014).
  * (52) Linden, N., Popescu, S., Short, A. J. and Winter, A. Quantum nonlocality and Beyond: limits from nonlocal computation.  Phys. Rev. Lett. 99, 180502 (2007).
  * (53) Silman, J., Machnes, S. and Aharon, N. On the relation between Bell’s inequalities and nonlocal games. Phys. Lett. A 372, 3796 (2008).
  * (54) Gharibian, S. and Kempe, J. Approximation algorithms for QMA-complete problems. SIAM J. Comput. 41, 1028-1050 (2012).
  * (55) Li, M. and Fei, S.-M. Gisin’s theorem for arbitrary dimensional multipartite states. Phys. Rev. Lett. 104, 240502 (2010).
  * (56) Yu, S., Chen, Q., Zhang, C., Lai, C. H. and Oh, C. H. All entangled pure states violate a single Bell’s inequality. Phys. Rev. Lett. 109, 120402 (2012).
  * (57) Collins, D., Gisin, N. Linden, N., Massar, S., & Popescu, S. Bell inequalities for arbitrarily high-dimensional systems. Phys. Rev. Lett. 88, 040404 (2002).
  * (58) Son, W., Lee, J. & Kim, M. S. Generic Bell inequalities for multipartite arbitrary dimensional systems.  Phys. Rev. Lett. 96, 060406 (2006).
  * (59) Duan, L.-M., Lukin, M., Cirac, J. I., and Zoller, P. Long-distance quantum communication with atomic ensembles and linear optics. Nature 414, 413 (2001).
  * (60) Kimble, H. J. The quantum Internet. Nature 453, 1023 (2008).
  * (61) Ritter, S., et al. An elementary quantum network of single atoms in optical cavities. Nature 484, 195 (2012).
  * (62) Cook, S. A. The complexity of theorem-proving procedures, In Proc. of the Third ACM Symposium on Theory of Computing, pp.151-158, 1971.
  * (63) Schaefer, T. J. The complexity of satisfiability problems, In Proc. of the tenth annual ACM symposium on Theory of computing, pp. 216-226, 1978.
  * (64) Zhao, Y., Zhang, L. & Malik, S. Chaff: Engineering an efficient SAT solver, In Proc. of the 38th annual Design Automation Conference, pp. 530-535, ACM, 2001.

## Acknowledgements

This work was supported by the National Natural Science Foundation of China
(Nos.61772437,61702427), Sichuan Youth Science and Technique Foundation
(No.2017JQ0048), and Fundamental Research Funds for the Central Universities
(No.2018GF07).

## SUPPLEMENTARY NOTE 1: THE PROOF OF THE SUFFICIENT CONDITION OF THEOREM 1

We present the following Lemma first.

Lemma 1. For any graph representable nonlocal game with $m=1$, assume that
$p(x_{i})$s have the same distribution. Then, $\varpi_{q}>\varpi_{c}$ if and
only if $I_{1}=2$.

Proof of Theorem 1. The proof of Theorem 1 is easily from Lemma 1. Actually,
$\min\\{I_{1},I_{2},\cdots,I_{m}\\}=2$ is equivalent to $I_{j}=2$. So, there
exist quantum advantages over all the classical strategies with shared
classical resources with respect to the subgraph involved in the observer
$\textsf{A}_{j}$. The result can be easily extended to the global graph from
the fact that $\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{m}$ have no
shared subgraphs for all the inputs being ”1” from the assumption. $\square$.

The proof of Lemma 1 in Supplementary Note 1 is very long and then divided
into two parts. The ”if part” will be proved in Supplementary Note 1 while the
”only part” will be proved in Supplementary Note 2.

Case 1. General reduction of the winning probability

The following proof is inspired by the unbalanced CHSH game LLP ; HFSD . The
key is to separate the optimal classical bound from the Tsirelson’s bound of
the expect winning probability Cir . Note that Tsirelson Cir  proved that the
optimal nonlocal values or quantum bounds are achievable for generalized
linear games using the maximally entangled EPR states EPR . Hence, from the
equivalence of linear game and Bell inequality, it is sufficient to prove
$\varpi_{c}<\varpi_{q}$ with the optimal bounds $\varpi_{c}$ and $\varpi_{q}$
when $I_{1}=2$. For the result of the main text, it only needs to prove that
there are quantum strategies for all players such that their joint winning
probability is larger than classical upper bound of $\varpi_{c}$, where it is
very hard to find the achievable optimal quantum bound $\varpi_{q}$.

For input question series $\textbf{x}=x_{1}x_{2}\cdots{}x_{n}$, denote the
product of assignments on the common vertices $V^{x_{i}}\cap{}V^{x_{j}}$ with
respect to two players $\textsf{A}_{i}$ and $\textsf{A}_{j}$ as:

$\displaystyle\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}=\prod_{\forall
v\in{}V^{x_{i}}\cap{}V^{x_{j}}}y_{i}(v),$ (S1)
$\displaystyle\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}=\prod_{\forall
v\in{}V^{x_{i}}\cap{}V^{x_{j}}}y_{j}(v),$ (S2)

where the outputs of the player $\textsf{A}_{i}$ with respect to the player
$\textsf{A}_{j}$ are respectively defined by
$\vec{y}_{ij}=y_{i}(v_{j_{1}})y_{i}(v_{j_{2}})\cdots y_{i}(v_{j_{s}})$ for
$v_{j_{1}},v_{j_{2}},\cdots,v_{j_{s}}\in V^{x_{i}}$, which depend on the input
$x_{i}$. The consistency condition (c) of Definition 2 of the main text is
equivalent to the following equations:

$\displaystyle\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}=\zeta^{\vec{y}_{ji}}_{x_{j},x_{i}},\forall
m<i<j\leq n.$ (S3)

Hence, the valuation function $F(\textbf{x},\textbf{y})$ can be rewritten into

$\displaystyle
F(\textbf{x},\textbf{y})=\prod_{i,j}\delta(\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}=\zeta^{\vec{y}_{ji}}_{x_{i},x_{j}})$
(S4)

where $\textbf{y}=\vec{y}_{1}\vec{y}_{2}\cdots\vec{y}_{n}$ denote the outputs
of all players, $\vec{y}_{i}=\vec{y}_{i\,1}\vec{y}_{i\,2}\cdots\vec{y}_{i\,n}$
denote the outputs of the player $\textsf{A}_{i}$, and $\delta(\cdot)$ denotes
the characteristic function, i.e., $\delta(x)=1$ if $x$ is true and $0$ for
other cases.

Now, denote all the shared resources as $\rho$, which may be a global
multipartite entanglement, entangled subsystems such as EPR states, or shared
classical states (hidden state model) Cir . In what follows, we assume that
all the quantum resources are EPR states EPR . For given inputs x, denote the
measurement of the player $\textsf{A}_{i}$ as $M_{x_{i}}^{\vec{y}_{i}}$,
$i=1,2,\cdots,n$. We have
$M_{x_{i}}^{\vec{y}_{i}}=\otimes_{j=1}^{n}M_{x_{i}}^{\vec{y}_{ij}}$, where
$M_{x_{i}}^{\vec{y}_{ij}}$ denotes the measurement of the player
$\textsf{A}_{i}$ on the subsystem correlated with one subsystem shared by the
player $\textsf{A}_{j}$. The joint probability for the outputs y conditional
on the inputs x is given by
$P(\textbf{y}|\textbf{x})=\langle\otimes_{i=1}^{n}M_{x_{i}}^{\vec{y}_{i}}\rangle={\rm
Tr}(\otimes_{i=1}^{n}M_{x_{i}}^{\vec{y}_{i}}\rho)$. So, any strategy with the
inputs x, which satisfy the consistency condition shown in Eq.(S3), can imply
the average winning probability as follows:

$\displaystyle P_{\textbf{x}}=$
$\displaystyle\sum_{\textbf{y}}F(\textbf{x},\textbf{y})P(\textbf{y}|\textbf{x})$
$\displaystyle=$
$\displaystyle\sum_{\textbf{y}}F(\textbf{x},\textbf{y})\langle(\otimes_{i=1}^{n}M_{x_{i}}^{\vec{y}_{i}})\rangle$
(S5) $\displaystyle=$
$\displaystyle\sum_{\textbf{y}}\prod_{i<j}\delta(\zeta^{\vec{y}_{i}}_{x_{i},x_{j}}=\zeta^{\vec{y}_{j}}_{x_{i},x_{j}})\langle\otimes_{i=1}^{n}M_{x_{i}}^{\vec{y}_{i}}\rangle$
(S6) $\displaystyle=$
$\displaystyle\sum_{\textbf{y}}\prod_{i<j}\langle\delta(\zeta^{\vec{y}_{i}}_{x_{i},x_{j}}=\zeta^{\vec{y}_{j}}_{x_{i},x_{j}})(M_{x_{i}}^{\vec{y}_{ij}}\otimes
M_{x_{j}}^{\vec{y}_{ji}})\rangle$ (S7) $\displaystyle=$
$\displaystyle\prod_{i<j}\sum_{\vec{y}_{ij},\vec{y}_{ji}}\langle\delta(\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}=\zeta^{\vec{y}_{ji}}_{x_{i},x_{j}})(M_{x_{i}}^{\vec{y}_{ij}}\otimes
M_{x_{j}}^{\vec{y}_{ji}})\rangle$ (S8)

Eq.(S5) follows from the definition of the conditional probability
$P(\textbf{y}|\textbf{x})$. Eq.(S6) is obtained by using Eq.(S4). In Eq.(S7),
the expect operation $\langle M_{x_{i}}^{\vec{y}_{ij}}\otimes
M_{x_{j}}^{\vec{y}_{ji}}\rangle$ is performed on the shared system of the
players $\textsf{A}_{i}$ and $\textsf{A}_{j}$. Moreover, it has taken use of
the equalities:
$M_{x_{j}}^{\vec{y}_{ji}}M_{x_{j}}^{\vec{y}_{ji}}=M_{x_{j}}^{\hat{y}_{ji}}$
for the projection operators $M_{x_{j}}^{\vec{y}_{ji}}$, $i,j=1,\cdots,n$.
Eq.(S8) is from the swapping of two operations by using the orthogonal
conditions: $M_{x_{i}}^{\vec{y}_{ij}}M_{x_{i}}^{\vec{y^{\prime}}_{ij}}={\bf
0}$ with $\vec{y}_{ij}\not=\vec{y^{\prime}}_{ij}$ for any $x_{i}$, $i,j$,
where $M_{x_{i}}^{\vec{y}_{ij}}$ and $M_{x_{i}}^{\vec{y^{\prime}}_{ij}}$ are
projection operators of the subsystem owned by the player $\textsf{A}_{i}$.

Note that
$\delta(\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}=\zeta^{\vec{y}_{ji}}_{x_{i},x_{j}})=\frac{1}{2}(1+\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}\zeta^{\vec{y}_{ji}}_{x_{i},x_{j}})$
for any $i,j=1,2,\cdots,n$. It follows from Eq.(S8) that

$\displaystyle P_{\textbf{x}}=$
$\displaystyle\prod_{i<j}\frac{1}{2}\langle(\sum_{\hat{y}_{ij},\hat{y}_{ji}}M_{x_{i}}^{\hat{y}_{ij}}\otimes
M_{x_{j}}^{\hat{y}_{ji}}$
$\displaystyle+\sum_{\hat{y}_{ij},\hat{y}_{ji}}\zeta^{\hat{y}_{ij}}_{x_{i},x_{j}}\zeta^{\hat{y}_{ji}}_{x_{i},x_{j}}M_{x_{i}}^{\hat{y}_{ij}}\otimes
M_{x_{j}}^{\hat{y}_{ji}})\rangle$ $\displaystyle=$
$\displaystyle\prod_{i<j}\frac{1}{2}\langle(\mathbb{I}+\hat{M}_{x_{i},x_{j}}\otimes\hat{M}_{x_{j},x_{i}})\rangle$
(S9)

where
$\hat{M}_{x_{i},x_{j}}=\sum_{\vec{y}_{ij}}\zeta^{\vec{y}_{ij}}_{x_{i},x_{j}}M_{x_{i}}^{\vec{y}_{ij}}$
denotes the successful measurement of the player $\textsf{A}_{i}$ on the
system shared with the player $\textsf{A}_{j}$.
$\hat{M}_{x_{j},x_{i}}=\sum_{\vec{y}_{ji}}\zeta^{\vec{y}_{ji}}_{x_{j},x_{i}}M_{x_{i}}^{\vec{y}_{ji}}$
denotes the successful measurement of the player $\textsf{A}_{j}$ on the
system shared with the player $\textsf{A}_{i}$, for each $x_{i},x_{j},i,j$. In
Eq.(S9), it has used the completeness of measurement operators:
$\\{M_{x_{i}}^{\vec{y}_{ij}},\forall\vec{y}_{ij}\\}$ and
$\\{M_{x_{j}}^{\vec{y}_{ji}},\forall\vec{y}_{ji}\\}$ for each $i,j$, i.e.,
$\sum_{\vec{y}_{ji}}M_{x_{j}}^{\vec{y}_{ji}}=\mathbb{I}$ and
$\sum_{\vec{y}_{ij}}M_{x_{i}}^{\vec{y}_{ij}}=\mathbb{I}$ with the identity
operator $\mathbb{I}$. The total expect winning probability is given by:

$\displaystyle\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}=\sum_{\textbf{x}}p(\textbf{x})\prod_{i<j}\frac{1}{2}\langle(\mathbb{I}+\hat{M}_{x_{i},x_{j}}\hat{M}_{x_{j},x_{i}})\rangle$
(S10)

where the tensor operation $\otimes$ is omitted for convenience because the
measurement operators are clearly implemented on different local systems
identified by their subindexes.

And then, Eq.(S10) is rewritten into

$\displaystyle\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}=$
$\displaystyle\sum_{\textbf{x}}p(\textbf{x})\langle\prod_{i=2}^{n}\frac{1}{2}(\mathbb{I}+\hat{M}_{x_{1},x_{i}}\hat{M}_{x_{i},x_{1}})$
$\displaystyle\times\prod_{j=2}^{n-1}\prod_{k=3}^{n}\frac{1}{2}(\mathbb{I}+\hat{M}_{x_{j},x_{k}}\hat{M}_{x_{k},x_{j}})\rangle$
$\displaystyle=$
$\displaystyle\sum_{\textbf{x}}p(\textbf{x})\prod_{i=2}^{n}\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{1},x_{i}}\hat{M}_{x_{i},x_{1}}\rangle$
$\displaystyle\times\prod_{j=2}^{n-1}\prod_{k=3}^{n}\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{j},x_{k}}\hat{M}_{x_{k},x_{j}}\rangle$
(S11) $\displaystyle=$
$\displaystyle\sum_{\textbf{x}}p_{*}p(\textbf{x})\prod_{l=1}^{k}\prod_{j=s_{l}}^{n_{l}}\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i_{l}},x_{j}}\hat{M}_{x_{j},x_{i_{l}}}\rangle$
(S12)

Eq.(S12) holds for classical hidden resources by simple evaluations under the
no-signalling principle, where goal is to evaluate the maximal winning
probability over all the resources. For a quantum model, it is sufficient to
take use of EPR states as shared resources, i.e., each pair of players
$\textsf{A}_{i},\textsf{A}_{j}$ can share some EPR states. From the assumption
of the consistency condition, it is sufficient to consider the outputs of each
pair of players who have common subgraphs. For other pairs, the consistency
condition can be easily satisfied by setting their outputs be $1$ for all the
vertices. Hence, it is reasonable to denote $p_{*}$ in Eq.(S12) as the success
probability of all pairs without common subgraphs. It means that all the
players can win the game with a constant success probability regards of their
input distributions and shared resources. Here, we assume that for each
$j=1,2,\cdots,m$, all the pairs of players $\textsf{A}_{i_{j}}$ and
$\textsf{A}_{t}$ have common vertices for $t=s_{j},s_{j}+1,\cdots,n_{j}$,
where $s_{j}$ and $n_{j}$ satisfy
$1<s_{1}<n_{1}<s_{1}<n_{2}<\cdots<s_{m}<n_{m}<n$.

The following proof is divided into two cases: One is that there is no more
than two players sharing vertices, and the other is for general case that
there are more than two players sharing vertices shown in Supplementary Note
2.

Case 2. Proof of the sufficient part of Lemma 1

Due to the requirements of the consistency conditions (a) and (b) in
Definition 2 of the main text for the first player $\textsf{A}_{1}$ ($m=1$ in
Lemma 1 in Supplementary Note 1), there exist four common vertex sets
$V^{x_{1}x_{j}}$ for each pair of players $\textsf{A}_{1}$ and
$\textsf{A}_{j}$ satisfying that

$\displaystyle\hat{M}_{x_{1},x_{j}}$
$\displaystyle=(-1)^{x_{1}}\hat{M}_{x_{1},1-x_{j}},$ (S13)
$\displaystyle\hat{M}_{x_{j},x_{1}}$ $\displaystyle=\hat{M}_{x_{j},1-x_{1}},$
(S14)

for binary inputs $x_{1},x_{j}$, where Eq.(S14) follows from the non-signaling
condition.

Now, assume that there is no more than two players sharing vertices, i.e.,
$I_{1}=2$. From Eqs.(S12)-(S14), the total winning probability can be
rewritten into:

$\displaystyle\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}=$ $\displaystyle
p_{*}[p\prod_{i=s_{1}}^{n_{1}}\frac{1}{2}\langle\mathbb{I}+p\hat{M}_{x_{1}=0,x_{i}}\hat{M}_{x_{i}=0,x_{1}}$
$\displaystyle+q\hat{M}_{x_{1}=0,x_{i}}\hat{M}_{x_{i}=1,x_{1}}\rangle$
$\displaystyle+q\prod_{i=s_{1}}^{n_{1}}\frac{1}{2}\langle\mathbb{I}+p\hat{M}_{x_{1}=1,x_{i}}\hat{M}_{x_{i}=0,x_{1}}$
$\displaystyle-q\hat{M}_{x_{1}=1,x_{i}}\hat{M}_{x_{i}=1,x_{1}}\rangle]$
$\displaystyle\times\prod_{i=2}^{k}\prod_{j=s_{i}+1}^{n_{i}}\frac{1}{2}\langle\mathbb{I}+p\hat{M}_{x_{i}=0,x_{j}}\hat{M}_{x_{j}=0,x_{i}}$
$\displaystyle+q\hat{M}_{x_{i}=0,x_{j}}\hat{M}_{x_{j}=1,x_{i}}+p\hat{M}_{x_{i}=1,x_{j}}\hat{M}_{x_{j}=0,x_{i}}$
$\displaystyle-q\hat{M}_{x_{i}=1,x_{j}}\hat{M}_{x_{j}=1,x_{i}}\rangle]$ (S15)

In Eq.(S15), for the simplicity we assume $i_{j}=j$ for $j=1,2,\cdots,k$,
$s_{1}=k+1$ and $s_{j}=n_{j-1}+1$ for $j=2,3,\cdots,k$. Moreover, Eq.(S15)
follows from the independence assumption of input distributions, where
$\\{p,q=1-p\\}$ denotes the input distribution of each player.
$\mathbb{I}+p\hat{M}_{x_{i}=0,x_{j}=0}\hat{M}_{x_{j}=0,x_{i}=0}+q\hat{M}_{x_{i}=0,x_{j}=1}\hat{M}_{x_{j}=1,x_{i}=0}$
and
$\mathbb{I}+p\hat{M}_{x_{i}=1,x_{j}=0}\hat{M}_{x_{j}=0,x_{i}=1}-q\hat{M}_{x_{i}=1,x_{j}=1}\hat{M}_{x_{j}=1,x_{i}=1}$
are positive semidefinite operators that can be regarded as quantum
observable.

To complete the proof, three subcases will be considered for following the
main idea, please see Supplementary Figure 1.

Figure 5: (Color online) Schematic diagram of graphic games in Case one. Each
player owns some vertices in a fixed graph that is known to all the players.
(a) The players $\textsf{A}_{1}$ and $\textsf{A}_{2}$ share a subgraph with
vertices $v_{1},\cdots,v_{s}$ while all the other players do not share
subgraph. (b) Each pair of two players $\textsf{A}_{1}$ and $\textsf{A}_{i}$
share a subgraph for $i=2,3,\cdots,k$ while all the other players do not share
subgraph. Here, any two players $\textsf{A}_{i}$ and $\textsf{A}_{j}$ share
some subgraph for $i,j=2,3,\cdots,k$. (c) Each group of players
$\textsf{A}_{i_{1}},\textsf{A}_{i_{2}},\cdots,\textsf{A}_{i_{j}}$ share some
subgraph with the player $\textsf{A}_{i}$ for $i=2,3,\cdots,m$ while all the
other players have no common subgraph.

Subcase 1. $m=1$ and $s_{1}=n_{1}=2$ as shown in Supplementary Figure 1(a).

Lemma 2. For an unbalanced CHSH game with the input probability distribution
$\\{p_{00},p_{01},p_{10},p_{11}\\}$, the quantum advantage exists if the
following conditions satisfy

  * (i)

$(\frac{1}{p_{10}}-\frac{1}{p_{11}})^{2}-(\frac{1}{p_{00}}+\frac{1}{p_{01}})^{2}<0$
if $\min\\{p_{10},p_{11}\\}\leq\min\\{p_{00},p_{01}\\}$;

  * (ii)

$(\frac{1}{p_{00}}-\frac{1}{p_{01}})^{2}-(\frac{1}{p_{10}}+\frac{1}{p_{11}})^{2}<0$
if $\min\\{p_{10},p_{11}\\}>\min\\{p_{00},p_{01}\\}$.

The proof can be easily followed from its stated in Ref.LLP ; CHSH .

Hence, when $m=1$ and $n_{1}=2$ from Eq.(S12) it follows that

$\displaystyle\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}=$
$\displaystyle\frac{p_{*}}{2}+\frac{p_{*}}{2}p^{2}\langle\hat{M}_{0,2}\hat{M}_{2,0}\rangle+pq\langle\hat{M}_{0,2}\hat{M}_{2,1}\rangle$
$\displaystyle+pq\langle\hat{M}_{1,2}\hat{M}_{2,0}\rangle-q^{2}\langle\hat{M}_{1,2}\hat{M}_{2,1}\rangle,$
(S16)

where $\hat{M}_{0,2}:=\hat{M}_{x_{1}=0,x_{2}}$,
$\hat{M}_{1,2}:=\hat{M}_{x_{1}=1,x_{2}}$,
$\hat{M}_{2,0}:=\hat{M}_{x_{2}=0,x_{1}}$ and
$\hat{M}_{2,1}:=\hat{M}_{x_{2}=1,x_{1}}$.

From Lemma 2 in Supplementary Note 1, we can easily obtain that the quantum
advantage exists for graphic games with the same input probability
distribution of all players.

Subcase 2. $m=1$ and $n_{m}>2$ as shown in Supplementary Figure 1(b).

In this case, suppose $s_{1}=2$ for convenience. Consider classical resources,
i.e., $\langle\hat{M}_{x_{1}=0,i}\rangle$,
$\langle\hat{M}_{x_{1}=1,i}\rangle$, $\langle\hat{M}_{x_{i}=0,1}\rangle$,
$\langle\hat{M}_{x_{i}=1,1}\rangle\in\\{\pm 1\\}$, from Eq.(S15) it follows
that

$\displaystyle\varpi_{c}:$
$\displaystyle=\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$
$\displaystyle=p_{*}p_{0}+p_{*}(1-p_{0})p_{0}^{n_{1}-1},$ (S17)

where $p_{0}$ is defined by $p_{0}:=\max\\{p,q\\}$.

When entangled resources are applied for all players, it is easy to get
$(p\hat{M}_{x_{1}=0,i}\hat{M}_{x_{i}=0,1}+q\hat{M}_{x_{1}=0,i}\hat{M}_{x_{i}=1,1})^{2}$
$+(p\hat{M}_{x_{1}=1,i}\hat{M}_{x_{i}=0,1}-q\hat{M}_{x_{1}=1,i}\hat{M}_{x_{i}=1,1})^{2}=2-4pq=:c^{2}\geq
1$ for any distributions $\\{p,q\\}$. Define
$p\hat{M}_{x_{1}=0,i}\hat{M}_{x_{i}=0,1}+q\hat{M}_{x_{1}=0,i}\hat{M}_{x_{i}=1,1}=c\cos\theta_{i}\mathbb{I}$
and
$p\hat{M}_{x_{1}=1,i}\hat{M}_{x_{i}=0,1}-q\hat{M}_{x_{1}=1,i}\hat{M}_{x_{i}=1,1}=c\sin\theta_{i}\mathbb{I}$
w.r.s the eigenvalue decomposition of the observable. It follows from Eq.(S12)
that

$\displaystyle\varpi_{q}:=$
$\displaystyle\max_{\rho,\forall\\{M_{x_{j}}^{\hat{y}_{j}}\\}}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$
$\displaystyle=$
$\displaystyle\max_{\forall\theta_{j}}[\frac{p_{*}p}{2^{{n_{1}}-1}}\prod_{i=2}^{n_{1}}(1+c\cos\theta_{i})+\frac{p_{*}q}{2^{{n_{1}}-1}}\prod_{i=2}^{n_{1}}(1+c\sin\theta_{i})]$
$\displaystyle=$
$\displaystyle\frac{p_{*}}{2^{{n_{1}}-1}}[1+\max_{\forall\theta_{j}}\sum_{i=i}^{{n_{1}}-1}\sum_{S_{i}}\prod_{\theta_{j}\in
S_{i}}\gamma_{j}$ $\displaystyle\times(p\prod_{\theta_{j}\in
S_{i}}\cos\theta_{j}+q\prod_{\theta_{j}\in S_{i}}\sin\theta_{j})]$ (S18)

where the summation $\sum_{S_{i}}$ is over all the possible subsets $S_{i}$.
Here, $S_{i}$ denotes the subset of
$\\{\theta_{2},\theta_{3},\cdots,\theta_{n_{1}}\\}$ with $i$ angles
$\theta_{j}$s.

Lemma 3 Luo . For any $\theta_{1},\theta_{2},\cdots,\theta_{s}\in[0,\pi/2]$
and integer $s\geq 2$, the following inequality holds

$\displaystyle(\prod_{i=1}^{s}\sin\theta_{i})^{\frac{1}{s}}\leq\sin(\frac{1}{s}\sum_{i=1}^{s}\theta_{i}),$
$\displaystyle(\prod_{i=1}^{s}\cos\theta_{i})^{\frac{1}{s}}\leq\cos(\frac{1}{s}\sum_{i=1}^{s}\theta_{i}),$
(S19)

where the equality holds if and only if
$\theta_{1}=\theta_{2}=\cdots=\theta_{s}$.

By using Lemma 3 in Supplementary Note 1, Eq.(S18) can be rewritten into

$\displaystyle\varpi_{q}=$
$\displaystyle\frac{p_{*}}{2^{{n_{1}}-1}}[1+\max_{\forall\theta_{j}}\sum_{i=1}^{{n_{1}}-1}\sum_{S_{i}}\prod_{\theta_{j}\in
S_{i}}c$ $\displaystyle\times(p\cos^{i}\Theta_{i}+q\sin^{i}\Theta_{i})]$ (S20)
$\displaystyle=$
$\displaystyle\frac{p_{*}}{2^{{n_{1}}-1}}[1+\max_{\theta}\sum_{i=1}^{{n_{1}}-1}\sum_{S_{i}}\prod_{\theta_{j}\in
S_{i}}c$ $\displaystyle\times(p\cos^{i}\theta+q\sin^{i}\theta)]$ (S21)
$\displaystyle=$
$\displaystyle\frac{p_{*}}{2^{{n_{1}}-1}}\max_{\theta}[p\prod_{i=2}^{n_{1}}(1+c\cos\theta)$
$\displaystyle+q\prod_{i=2}^{n_{1}}(1+c\sin\theta)]$ (S22)

where $\Theta_{i}=\frac{1}{i}\sum_{\theta_{j}\in S_{i}}\theta_{j}$. In
Eq.(S21), the maximum achieves when the equality in inequality (S20) holds,
i.e., $\theta_{2}=\theta_{3}=\cdots=\theta_{n_{1}}:=\theta$ from Lemma 3 in
Supplementary Note 1.

Consider $p\geq 1/2$ for the simplicity. It follows from Eq.(S22) that

$\displaystyle\varpi_{q}=$
$\displaystyle\frac{p_{*}}{2^{n_{1}-1}}\max_{\theta}[p(1+c\cos\theta)^{n_{1}-1}+q(1+c\sin\theta)^{n_{1}-1}]$
$\displaystyle\geq$
$\displaystyle\frac{p_{*}}{2^{n_{1}-1}}\max_{\theta}[p2^{n_{1}-1}(1+\frac{1}{2}(n_{1}-1)(c\cos\theta-1))$
$\displaystyle+q2^{n_{1}-1}p^{n_{1}-1}(1+(n_{1}-1)$
$\displaystyle\times(\frac{1}{2p}+\frac{c}{2p}\sin\theta-1))]$ (S23)
$\displaystyle=$ $\displaystyle
pp_{*}+qp_{*}p^{n_{1}-1}+2^{n_{1}-2}(n_{1}-1)\max_{\theta}[pc\cos\theta$
$\displaystyle+qp^{n_{1}-2}c\sin\theta+qp^{n_{1}-2}-2qp^{n_{1}-1}-p]$
$\displaystyle=$ $\displaystyle
p_{*}p+p_{*}qp^{n_{1}-1}+p_{*}2(n_{1}-1)[c\sqrt{p^{2}+q^{2}p^{2n_{1}-4}}$
$\displaystyle+qp^{n_{1}-2}-2qp^{n_{1}-1}-p]$ $\displaystyle>$ $\displaystyle
p_{*}p+p_{*}qp^{n_{1}-1}$ (S24) $\displaystyle=$ $\displaystyle\varpi_{c}$

when $p,q$ satisfy the following inequality:

$\displaystyle
c\sqrt{p^{2}+q^{2}p^{2n_{1}-4}}+qp^{n_{1}-2}-2qp^{n_{1}-1}-p>0.$ (S25)

Here, inequality (S23) follows from the inequality: $(1\pm x)^{s}\geq 1\pm sx$
for any $x\in[0,1]$ and $s\geq 1$. Inequality (S24) follows from the
inequality:
$\max_{\theta}[pc\cos\theta+qp^{n_{1}-2}c\sin\theta]=c\sqrt{p^{2}+q^{2}p^{2n_{1}-4}}$,
where $\cos\theta=p/\sqrt{p^{2}+q^{2}p^{2n_{1}-4}}$. Actually, we can prove
that the inequality (S25) holds for $p\geq 1/2$ and $s\geq 3$ as follows:

$\displaystyle\Delta:=$ $\displaystyle(c-2qp^{n_{1}-1}-p)^{2}$
$\displaystyle=$
$\displaystyle(2-4pq)(p^{2}+q^{2}p^{2n_{1}-4})-q^{2}p^{2n_{1}-4}(2p-1)^{2}$
$\displaystyle-2qp^{n_{1}-2}(2p-1)-p^{2}$ $\displaystyle=$ $\displaystyle
q^{2}p^{2n_{1}-4}+p^{2}-4qp^{3}-2qp^{n_{1}-2}(2p-1)$ $\displaystyle=$
$\displaystyle p(p+4p^{3}+(2p^{-3}+4p^{-1})x+(p^{-5}+p^{-3})x^{2}$
$\displaystyle-2p^{-4}x^{2}-6p^{-2}x-4p^{2})$ (S26) $\displaystyle:=$
$\displaystyle f(x)$ (S27)

In Eq.(S26), $x=p^{n_{1}}$. Note that
$f^{\prime}(x)=2(p^{-4}+p^{-2}-2p^{-3})x+2p^{-2}+4-6p^{-1}\geq 0$ for any
$x\in[0,1]$ because of $p^{-4}+p^{-2}-2p^{-3}\geq 0$ and
$2p^{-2}+4-6p^{-1}\leq 0$ for $p\in(1/2,1]$. It follows from Eq.(S26) that

$\displaystyle\min_{x}f(x)=$ $\displaystyle f(p^{3})$ $\displaystyle=$
$\displaystyle p(2-4p-2p^{2}+5p^{3})$ $\displaystyle\geq$
$\displaystyle\frac{1}{16}>0$

when $x=p^{3}$, i.e., $n_{1}=3$.

Similarly, it is easy to prove $\varpi_{q}>\varpi_{c}$ when $p<1/2$. Hence,
from Eqs.(S24) and (S27) we get

$\displaystyle\varpi_{q}>\varpi_{c}.$ (S28)

Subcase 2. $m\geq 2$ as shown in Supplementary Figure 1(c).

This case can be easily followed by using the subcases 1 and 2, where no
consistency condition is required for
$\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{m}$.

## SUPPLEMENTARY NOTE 2. PROOF OF NECESSARY CONDITION OF LEMMA 1

In this note, we prove the necessary condition of Lemma 1 shown in
Supplementary Note 1. Specifically, no quantum advantage exists when there are
more than two players who share vertices. The proof is based on the reductions
given Eqs.(S1)-(S12) shown in Supplementary Note 1. To complete the proof,
consider two cases as follows: one is for the case that $l$ players
$\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{l}$ have common vertices
shown in Supplementary Figure 2(a), and the other is for general case shown in
Supplementary Figure 2(b).

Figure 6: (Color online) Schematic diagram of graphic games in subcase two.
Each player owns some vertices in a fixed graph which is known for all the
players. (a) The players
$\textsf{A}_{1},\textsf{A}_{2},\cdots,,\textsf{A}_{l}$ share the vertices
$v_{1},v_{2},\cdots,v_{s}$ while all the other players do not share vertices.
(b) General case. There are more than two players who share vertices. Some
pair players have common vertices while some players do not share vertices.

Case 1. The players $\textsf{A}_{1},\textsf{A}_{2},\cdots,\textsf{A}_{l}$ have
some common vertices as shown in Supplementary Figure 2(a).

In this case, we firstly assume that $l=3$ for convenience. For the classical
resources, i.e.,
$\langle\hat{M}_{x_{1}=0,i}\rangle,\langle\hat{M}_{x_{1}=1,i}\rangle,\langle\hat{M}_{x_{i}=0,1}\rangle,\langle\hat{M}_{x_{i}=1,1}\rangle\in\\{\pm
1\\}$, from Eq.(S12) we have

$\displaystyle\varpi_{c}=$
$\displaystyle\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$ $\displaystyle=$
$\displaystyle\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}(\sum_{\textbf{x}}p_{*}p(\textbf{x})[\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{1},2}\hat{M}_{x_{2},1}\rangle]$
$\displaystyle\times[\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{1},3}\hat{M}_{x_{3},1}\rangle]\times[\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{2},3}\hat{M}_{x_{3},2}\rangle])$
(S29)

where $p_{*}$ is the success probability of all the pairs without the
consistency requirements.

Note that all players $\textsf{A}_{1},\cdots,\textsf{A}_{l}$ share the same
vertex set. Denote $A_{0}:=\hat{M}_{x_{1}=0,2}=\hat{M}_{x_{1}=0,3}$,
$A_{1}:=\hat{M}_{x_{1}=1,2}=\hat{M}_{x_{1}=1,3}$,
$B_{0}:=\hat{M}_{x_{2}=0,1}=\hat{M}_{x_{2}=0,3}$,
$B_{1}:=\hat{M}_{x_{2}=1,1}=\hat{M}_{x_{2}=1,3}$,
$C_{0}:=\hat{M}_{x_{3}=0,1}=\hat{M}_{x_{3}=0,2}$,
$C_{1}:=\hat{M}_{x_{3}=1,1}=\hat{M}_{x_{3}=1,2}$. From Eq.(S30) it follows
that

$\displaystyle\varpi_{c}=$
$\displaystyle\frac{p_{*}}{4}\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}[p^{3}(1+\langle\,A_{0}B_{0}\rangle+\langle\,B_{0}C_{0}\rangle+\langle\,A_{0}C_{0}\rangle)$
$\displaystyle+p^{2}q(1+\langle\,A_{0}B_{0}\rangle+\langle\,B_{0}C_{1}\rangle+\langle\,A_{0}C_{1}\rangle)$
$\displaystyle+p^{2}q(1+\langle\,A_{0}B_{1}\rangle+\langle\,B_{1}C_{0}\rangle+\langle\,A_{0}C_{0}\rangle)$
$\displaystyle+pq^{2}(1+\langle\,A_{0}B_{1}\rangle+\langle\,B_{1}C_{1}\rangle+\langle\,A_{0}C_{1}\rangle)$
$\displaystyle+p^{2}q(1+\langle\,A_{1}B_{0}\rangle+\langle\,B_{0}C_{0}\rangle+\langle\,A_{1}C_{0}\rangle)$
$\displaystyle+q^{3}(1-\langle\,A_{1}B_{1}\rangle+\langle\,B_{1}C_{1}\rangle-\langle\,A_{1}C_{1}\rangle)]$
(S30) $\displaystyle=$ $\displaystyle\left\\{\begin{array}[]{ll}\displaystyle
p_{*}(1-2p+3p^{2}-p^{3})&\mbox{ for }0<p\leq\frac{1}{2};\\\
p_{*}p(1+p-p^{2})&\mbox{ for }\frac{1}{2}\leq p<1.\end{array}\right.$ (S31)

Eq.(S31) can be proved as follows. The simulation of $\varpi_{c}$ is shown in
Supplementary Figure 3. From the simple assumptions (deterministic strategies
of all classical players) of $A_{i},B_{j},C_{k}\in\\{\pm 1\\}$, using
Eq.(S30), it follows that

$\displaystyle\varpi_{c}=\frac{p_{*}}{4}\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}[\alpha_{0}p^{3}+\alpha_{1}p^{2}q+\alpha_{2}pq^{2}+\alpha_{3}q^{2}],$ (S32)

where $\alpha_{i}$s are defined by:

$\displaystyle\alpha_{0}$
$\displaystyle=1+\langle\,A_{0}B_{0}\rangle+\langle\,B_{0}C_{0}\rangle+\langle\,A_{0}C_{0}\rangle$
$\displaystyle\leq 4,$ $\displaystyle\alpha_{1}$
$\displaystyle=3+\langle\,A_{0}B_{0}\rangle+\langle\,B_{0}C_{1}\rangle+\langle\,A_{0}C_{1}\rangle+\langle\,A_{0}B_{1}\rangle$
$\displaystyle+\langle\,B_{1}C_{0}\rangle+\langle\,A_{0}C_{0}\rangle+\langle\,A_{1}B_{0}\rangle+\langle\,B_{0}C_{0}\rangle+\langle\,A_{1}C_{0}\rangle$
$\displaystyle\leq 12,$ $\displaystyle\alpha_{3}$
$\displaystyle=1+\langle\,A_{0}B_{1}\rangle+\langle\,B_{1}C_{1}\rangle+\langle\,A_{0}C_{1}\rangle$
$\displaystyle\leq 4,$ $\displaystyle\alpha_{3}$
$\displaystyle=1-\langle\,A_{1}B_{1}\rangle+\langle\,B_{1}C_{1}\rangle-\langle\,A_{1}C_{1}\rangle$
$\displaystyle\leq 4.$

When $p>1/2$, i.e., $p>q$, we have $p^{3},p^{2}q>pq^{2},q^{3}$, and
$\max\alpha_{0}\geq\alpha_{3}$, $\alpha_{1}>\alpha_{2}$. Note that
$\varpi_{c}$ is a linear combination of four vertices
$\\{p^{3},p^{2}q,pq^{2},q^{3}\\}$ for each $p,q$. The maximum of $\varpi_{c}$
is achievable by optimizing $\alpha_{0}p^{3}+\alpha_{1}p^{2}q$. It easily
follows that
$\langle\,A_{0}B_{0}\rangle=\langle\,B_{0}C_{0}\rangle=\langle\,A_{0}C_{0}\rangle=\langle\,B_{0}C_{1}\rangle=\langle\,A_{0}C_{1}\rangle=\langle\,A_{0}B_{1}\rangle=\langle\,B_{1}C_{0}\rangle=\langle\,A_{1}B_{0}\rangle=\langle\,A_{1}C_{0}\rangle=1$.
Moreover, $A_{i},B_{i},C_{j}$ are binary output observable. Similar result
holds for $p<1/2$.

In what follows, it needs to prove that the quantum bound $\varpi_{q}$ derived
from quantum measurements on any quantum resources satisfying
$\varpi_{q}=\varpi_{c}$. It will be completed by three steps. Step one is used
to prove the result for three players while the other is used for the case of
more than three players.

Figure 7: (Color online) The optimal average winning probability of classical
players.

S1. $l=3$.

Assume that the entangled resource is $\rho$ for all the players. Note that
$\hat{M}_{x_{i},j}=\hat{M}_{x_{i},s}$ for any $i$, $i,s\leq k$. Denote
$A_{x_{1}}:=\hat{M}_{x_{1},2},A_{x_{1}}^{\prime}:=\hat{M}_{x_{1},3}$,
$B_{x_{2}}:=\hat{M}_{x_{2},1},B_{x_{2}}^{\prime}:=\hat{M}_{x_{2},3}$,
$C_{x_{3}}:=\hat{M}_{x_{3},1},C_{x_{3}}^{\prime}:=\hat{M}_{x_{3},2}$ as
quantum observable performed on different shared subsystems. From Eq.(S12) it
follows that

$\displaystyle\varpi_{q}=$
$\displaystyle\max_{\rho,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$ $\displaystyle=$
$\displaystyle\frac{1}{8}\max_{\rho,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}(\sum_{\textbf{x}}p_{*}p(\textbf{x})[\langle\mathbb{I}+A_{x_{1}}B_{x_{2}}\rangle]$
$\displaystyle\times[\langle\mathbb{I}+A^{\prime}_{x_{1}}C_{x_{3}}\rangle]\times[\langle\mathbb{I}+B^{\prime}_{x_{2}}C^{\prime}_{x_{3}}\rangle])$
(S33)

From the consistency conditions, for the inputs $x_{1}x_{2}x_{3}=101$ or
$110$, the winning probability is zero since $A_{1}=B_{0}$,
$A^{\prime}_{1}=-C_{1}$, $B_{0}=B_{0}^{\prime}=C_{1}=C_{1}^{\prime}$, and
$A_{1}=A^{\prime}_{1}$ (on the common vertices of three players)
($A_{1}=-B_{1}$, $A^{\prime}_{1}=C_{0}$, $A_{1}=A_{1}^{\prime}$, and
$B_{1}=B_{1}^{\prime}=C_{0}=C_{0}^{\prime}$) have no solution simultaneously.
From consistency conditions $\hat{M}_{x_{1},j}=(-1)^{x_{1}}\hat{M}_{x_{j},1}$
and Eq.(S33) we get that

$\displaystyle\varpi_{q}=$
$\displaystyle\frac{1}{8}p_{*}\max_{\rho,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}[p^{3}\langle\mathbb{I}+A_{0}B_{0}\rangle\langle\mathbb{I}+A^{\prime}_{0}C_{0}\rangle$
$\displaystyle\times\langle\mathbb{I}+B^{\prime}_{0}C^{\prime}_{0}\rangle$
$\displaystyle+p^{2}q\langle\mathbb{I}+A_{0}B_{0}\rangle\langle\mathbb{I}+A^{\prime}_{0}C_{1}\rangle\langle\mathbb{I}+B^{\prime}_{0}C^{\prime}_{1}\rangle$
$\displaystyle+p^{2}q\langle\mathbb{I}+A_{0}B_{1}\rangle\langle\mathbb{I}+A^{\prime}_{0}C_{0}\rangle\langle\mathbb{I}+B^{\prime}_{1}C^{\prime}_{0}\rangle$
$\displaystyle+pq^{2}\langle\mathbb{I}+A_{0}B_{1}\rangle]\langle\mathbb{I}+A^{\prime}_{0}C_{1}\rangle\langle\mathbb{I}+B^{\prime}_{1}C^{\prime}_{1}\rangle$
$\displaystyle+p^{2}q\langle\mathbb{I}+A_{1}B_{0}\rangle]\langle\mathbb{I}+A^{\prime}_{1}C_{0}\rangle\langle\mathbb{I}+B^{\prime}_{0}C^{\prime}_{0}\rangle$
$\displaystyle+q^{3}\langle\mathbb{I}-A_{1}B_{1}\rangle\langle\mathbb{I}-A^{\prime}_{1}C_{1}\rangle\langle\mathbb{I}+B^{\prime}_{1}C^{\prime}_{1}\rangle]$
$\displaystyle\leq$
$\displaystyle\frac{1}{4}p_{*}\max_{\rho,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}[p^{3}\langle(\mathbb{I}+A_{0}B_{0})(\mathbb{I}+A^{\prime}_{0}C_{0})\rangle$
$\displaystyle+p^{2}q\langle(\mathbb{I}+A_{0}B_{0})(\mathbb{I}+A^{\prime}_{0}C_{1})\rangle$
$\displaystyle+p^{2}q\langle(\mathbb{I}+A_{0}B_{1})(\mathbb{I}+A^{\prime}_{0}C_{0})\rangle$
$\displaystyle+pq^{2}\langle(\mathbb{I}+A_{0}B_{1})(\mathbb{I}+A^{\prime}_{0}C_{1})\rangle$
$\displaystyle+p^{2}q\langle(\mathbb{I}+A_{1}B_{0})(\mathbb{I}+A^{\prime}_{1}C_{0})\rangle$
$\displaystyle+q^{3}\langle(\mathbb{I}-A_{1}B_{1})(\mathbb{I}-A^{\prime}_{1}C_{1})\rangle]$
(S34) $\displaystyle=$
$\displaystyle\frac{1}{4}p_{*}\max_{\rho,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}[p+p^{2}q+q^{3}+\langle\,CHSH_{AB}\rangle$
$\displaystyle+\langle\,CHSH_{AC}\rangle+\langle{\cal L}_{ABC}\rangle]$ (S35)

where three operators $CHSH_{AB},CHSH_{AC}$ and ${\cal L}_{ABC}$ are defined
by:

$\displaystyle CHSH_{AB}=$ $\displaystyle
p^{2}A_{0}B_{0}+pqA_{0}B_{1}+p^{2}qA_{1}B_{0}-q^{3}A_{1}B_{1},$ $\displaystyle
CHSH_{AC}=$ $\displaystyle
p^{2}A_{0}C_{0}+pqA_{0}C_{1}+p^{2}qA_{1}C_{0}-q^{3}A_{1}C_{1},$
$\displaystyle{\cal L}_{ABC}=$ $\displaystyle
p^{3}A_{0}B_{0}C_{0}+p^{2}qA_{0}B_{1}C_{0}+p^{2}qA_{0}B_{0}C_{1}$
$\displaystyle+pq^{2}A_{0}B_{1}C_{1}+p^{2}qA_{1}B_{0}C_{0}+q^{3}A_{1}B_{1}C_{1}$

Here, inequality (S34) has used the inequalities:
$\langle\mathbb{I}+B_{i}C_{j}\rangle\leq 2$. In Eq.(S35), we have taken use of
the equalities: $A_{i}=A_{i}^{\prime}$ from the consistency assumption.

Since $\|B_{i}\|,\|C_{i}\|\leq 1$, from Eq.(S35) it follows that

$\displaystyle{\cal L}_{ABC}$
$\displaystyle\leq\left\\{\begin{array}[]{ll}{\cal
L}_{AB}:=&p^{2}A_{0}B_{0}+pqA_{0}B_{1}\\\
&+p^{2}qA_{1}B_{0}+q^{3}A_{1}B_{1}\\\ {\cal
L}_{AC}:=&p^{2}A_{0}C_{0}+pqA_{0}C_{1}\\\
&+p^{2}qA_{1}C_{0}+q^{3}A_{1}C_{1}\end{array}\right.$ (S36)

where all the coefficients are positive, and the maximum is achievable by
assuming $A_{i},B_{i}\geq 0$.

When $p\geq q$, $CHSH_{AB}+\frac{1}{2}{\cal
L}_{AB}=\frac{1}{2}(3p^{2}A_{0}B_{0}+3pqA_{0}B_{1}+p^{2}qA_{1}B_{0}-3q^{3}A_{1}B_{1})$
is a generalized CHSH operator. From Lemma 2 in Supplementary Note 1, the
Tsirelson’s bound (or quantum maximum in terms of entangled resources) is no
larger than the classical maximum for $p\geq q$. It implies that no quantum
advantage exists for graphic game. Similarly, it easily follows that the
Tsirelson’s bound of $CHSH_{AC}+\frac{1}{2}{\cal L}_{AC}$ is no larger than
the classical maximum for $p\geq q$. Hence, from Eqs.(S30) and (S35), we have
proved that $\varpi_{q}\leq\varpi_{c}$ for any $p,q$ with $p\geq q$.

When $p_{0}\leq p_{1}$, note that $CHSH_{AB}+\frac{1}{2}{\cal
L}_{AB}=\frac{1}{2}(3p^{2}A_{0}B_{0}+3pqA_{0}B_{1}+3q^{3}A_{1}B_{1}-p^{2}qA_{1}B_{0})$
that is a generalized CHSH operator. From Lemma 2 in Supplementary Note 1, no
quantum advantage exists for graphic game with $p\leq q$. Furthermore, the
Tsirelson’s bound of $CHSH_{AC}+\frac{1}{2}{\cal L}_{AC}$ is no larger than
its classical bound for $p\leq q$ in terms of graphic game. From Eqs.(S30) and
(S35), we have proved $\varpi_{q}\leq\varpi_{c}$ for any $p,q$ with $p\leq q$.
Finally, we have shown that $\varpi_{q}\leq\varpi_{c}$ for any input
distributions $p,q$.

S2. $l>3$ as shown in Supplementary Figure 2(a).

Since all the players $\textsf{A}_{1},\cdots,\textsf{A}_{l}$ share the same
vertex set, it follows that $\hat{M}_{x_{i}=0,j}=\hat{M}_{x_{i}=0,s}$ for any
$i$ and $1\leq i\not=s\leq l$. From Eq.(S12) we get

$\displaystyle\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}=$
$\displaystyle\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$ $\displaystyle=$
$\displaystyle p_{*}\sum_{\textbf{x}}p_{*}p(\textbf{x})\prod_{1\leq i<j\leq
l}(\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i},j}\hat{M}_{x_{j},i}\rangle)$
(S37) $\displaystyle=$ $\displaystyle
p_{*}\sum_{\textbf{x}}p(\textbf{x})\Delta_{1}\times\Delta_{2}\times\Delta_{3},$
(S38)

where $\Delta_{1}$ is a partial summation involving the first three players
($\textsf{A}_{1},\textsf{A}_{2},\textsf{A}_{3}$), $\Delta_{2}$ is a partial
summation involving other $l-3$ players of
$\textsf{A}_{4},\textsf{A}_{5},\cdots,\textsf{A}_{k}$, and $\Delta_{3}$ is a
partial summation for other terms. These partial summations $\Delta_{i}$ are
respectively defined as:

$\displaystyle\Delta_{1}=$ $\displaystyle\prod_{1\leq i<j\leq
3}(\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i},j}\hat{M}_{x_{j},i}\rangle),$
(S39) $\displaystyle\Delta_{2}=$ $\displaystyle\prod_{4\leq
i<j\leq{}l}(\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i},j}\hat{M}_{x_{j},i}\rangle),$
(S40) $\displaystyle\Delta_{3}=$ $\displaystyle\prod_{1\leq
i<j\leq{}l,(i,j)\not\in{\cal I}_{1}\cup{\cal
I}_{2}}(\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i},j}\hat{M}_{x_{j},i}\rangle)$
(S41)

where ${\cal I}_{1}$ and ${\cal I}_{2}$ denote the respective domain of
$\Delta_{1}$ and $\Delta_{2}$.

From the consistency assumption, the only nonzero winning probability for all
the inputs with $x_{1}=1$ are $x_{1}x_{2}\cdots x_{k}=10\cdots 0,11\cdots 1$.
In this case, for $x_{1}=0$, it follows that $\Delta_{2},\Delta_{3}\leq 1$
because of
$\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i},j}\hat{M}_{x_{j},i}\rangle\leq 1$
for all $i,j$. Moreover, for $x_{1}=1$ it follows that $\Delta_{2}\leq 1$
because of
$\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{i},j}\hat{M}_{x_{j},i}\rangle\leq 1$
for all $i,j\geq 4$, and
$\Delta_{3}\leq\prod_{i=4}^{l}(\frac{1}{2}\langle\mathbb{I}-\hat{M}_{x_{1},i}\hat{M}_{x_{i},1}\rangle)$
since
$\frac{1}{2}\langle\mathbb{I}+\hat{M}_{x_{j},i}\hat{M}_{x_{i},j}\rangle\leq 1$
for $j=2\geq 2$ and all $i$s. Hence, when $p\geq q$, from Eqs.(S38)-(S41) we
obtain that

$\displaystyle\varpi_{c}:=$
$\displaystyle\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$ $\displaystyle=$
$\displaystyle p_{*}\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}(p\sum_{x_{2},\cdots,x_{l}}p(x_{2})\cdots{}p({x_{k}})\Delta_{1}(x_{1}=0)$
$\displaystyle+pq^{l-1}\Delta_{1}(x_{1}=1,x_{2}=x_{3}=0))$ (S42)
$\displaystyle=$ $\displaystyle p_{*}(p+p^{l-1}q)$ (S43) $\displaystyle=$
$\displaystyle p_{*}(p+p^{l-1}-p^{l}).$ (S44)

Eq.(S42) follows from the assignments of $\hat{M}_{x_{i},j}=1$ for all $i,j$.
Eq.(S43) follows from the normalization condition of the distributions
$p(x_{1}),p(x_{2}),\cdots,p(x_{k})$. Eq.(S44) has used the equality: $p+q=1$.

Similarly, for $q\geq p$ we can obtain

$\displaystyle\varpi_{c}=$
$\displaystyle\max_{\lambda,\\{M_{x_{i}}^{\hat{y}_{i}}\\},\forall
i}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$ $\displaystyle=$
$\displaystyle p_{*}(p+(1-p)^{l}).$ (S45)

Now, for all the inputs of $x_{1}x_{2}\cdots x_{l}$, the Tsirelson’s bound of
$\Delta_{2}$ is no larger than its classical bound $1$ with
$\hat{M}_{x_{i},j}=\hat{M}_{x_{j},i}=1$ for $p\geq q$ or
$\hat{M}_{x_{i},j}=\hat{M}_{x_{j},i}=1$ except for $\hat{M}_{x_{1},j}=-1$ when
$q\geq p$. From Eq.(S38), it follows that

$\displaystyle\varpi_{q}=$
$\displaystyle\max_{\rho,\forall\\{M_{x_{j}}^{\hat{y}_{j}}\\}}\sum_{\textbf{x}}p(\textbf{x})P_{\textbf{x}}$
$\displaystyle\leq$ $\displaystyle
p_{*}\max_{\rho,\forall\\{M_{x_{j}}^{\hat{y}_{j}}\\}}[\sum_{x_{2},x_{3}}pp(x_{2})p(x_{3})\Delta_{1}(x_{1}=0)$
$\displaystyle+qp^{l-1}\Delta_{1}(x_{1}=1,x_{2}=x_{3}=0)$
$\displaystyle+q^{l}\Delta_{1}(x_{1}=x_{2}=x_{3}=1)\prod_{i=4}^{l}(\frac{1}{2}\langle\mathbb{I}-\hat{M}_{x_{1},i}\hat{M}_{x_{i},1}\rangle)]$
$\displaystyle\leq$ $\displaystyle p_{*}\max_{\rho,\\{\forall
M_{x_{i}}^{\hat{y}_{i}}\\}}[\sum_{x_{2},x_{3}}pp(x_{2})p(x_{3})\Delta_{1}(x_{1}=0)$
$\displaystyle+qp^{l-1}\Delta_{1}(x_{1}=1,x_{2}=x_{3}=0)$
$\displaystyle+q^{l}\Delta_{1}(x_{1}=x_{2}=x_{3}=1)]$ (S46) $\displaystyle:=$
$\displaystyle\frac{1}{4}p_{*}\max_{\rho,\\{\forall
M_{x_{i}}^{\hat{y}_{i}}\\}}[p+p^{l-1}q+q^{l}+\langle\widehat{CHSH}_{AB}\rangle$
$\displaystyle+\langle\,\widehat{CHSH}_{AC}\rangle+\langle\widehat{\cal
L}_{ABC}\rangle],$ (S47)

where we have taken the notions of $A_{i},B_{i},C_{i}$ defined in Eq.(S35),
and three partial operators are defined as:

$\displaystyle\widehat{CHSH}_{AB}=$ $\displaystyle
p^{2}A_{0}B_{0}+pqA_{0}B_{1}+p^{l-1}qA_{1}B_{0}-q^{l}A_{1}B_{1},$
$\displaystyle\widehat{CHSH}_{AC}=$ $\displaystyle
p^{2}A_{0}C_{0}+pqA_{0}C_{1}+p^{l-1}qA_{1}C_{0}-q^{l}A_{1}C_{1},$
$\displaystyle\widehat{\cal L}_{ABC}=$ $\displaystyle
p^{3}A_{0}B_{0}C_{0}+p^{2}qA_{0}B_{1}C_{0}+p^{2}qA_{0}B_{0}C_{1}$
$\displaystyle+pq^{2}A_{0}B_{1}C_{1}+p^{l-1}qA_{1}B_{0}C_{0}+q^{l}A_{1}B_{1}C_{1}.$

Eq.(S46) has used the inequalities:
$\frac{1}{2}\langle\mathbb{I}-\hat{M}_{x_{1},i}\hat{M}_{x_{i},1}\rangle\leq 1$
for all $i$. Note that

$\displaystyle\widehat{\cal L}_{ABC}$
$\displaystyle\leq\left\\{\begin{array}[]{ll}\widehat{\cal
L}_{AB}:=&p^{2}A_{0}B_{0}+pqA_{0}B_{1}\\\
&+p^{l-1}qA_{1}B_{0}+q^{l}A_{1}B_{1}\\\ \widehat{\cal
L}_{AC}:=&p^{2}A_{0}C_{0}+pqA_{0}C_{1}\\\
&+p^{l-1}qA_{1}C_{0}+q^{l}A_{1}C_{1}\end{array}\right.$ (S48)

Similar to Eq.(S35), the operator bound (quantum bound) of the generalized
CHSH operators $\widehat{CHSH}_{AB}+\frac{1}{2}\widehat{\cal L}_{AB}$ and
$\widehat{CHSH}_{AC}+\frac{1}{2}\widehat{\cal L}_{AC}$ is no larger than its
classical bound. Moreover, it is easy to prove that $p_{*}(p+p^{l-1}-p^{l})$
and $p_{*}(p+(1-p)^{l})$ are the optimal classical bounds of the corresponding
generalized operators defined in Eq.(S47) for $p\geq q$ and $p\leq q$,
respectively. We obtain that

$\displaystyle\varpi_{q}\leq$
$\displaystyle\left\\{\begin{array}[]{lll}p_{*}(p+p^{l-1}-p^{l})\mbox{ for
}p\geq q,\\\ p_{*}(p+(1-p)^{l})\mbox{ for }p\leq q.\end{array}\right.$ (S49)

Consequently, from Eq.(S44), (S45) and (S49) we proved that

$\displaystyle\varpi_{q}\leq\varpi_{c}.$ (S50)

It means that no quantum advantage exists for graphic game in this case.

## SUPPLEMENTARY NOTE 3. THE PROOF OF THEOREM 2

From Theorem 1 of the main text, the graphic game with proper restrictions or
consistency conditions has quantum advantage. Conversely, it is not true even
if for the uniform inputs. Specifically, there are different games with only
one or two common vertices, which have quantum advantage or not. So, it
requires further restrictions for characterizing these games without quantum
advantage. One example is guessing your neighbor game GYNI . Here, we provide
a generalized result. Specifically, we consider the winning conditions, i.e.,
$F(\textbf{x},\textbf{y})=1$ if $a_{i}=f_{i}(\textbf{x})$ for all $i$s;
Otherwise, $F(\textbf{x},\textbf{y})=0$. Here, $f_{i}$ denotes some function
of the input x. As an example, $f_{i}(\textbf{x})$ can be regarded as the
restriction of the product of all the assigned values in the graphic games.

Theorem 2. There is no quantum advantage for multipartite nonlocal game if
${\cal
F}:\textbf{x}\mapsto(f_{1}(\textbf{x}),f_{2}(\textbf{x}),\cdots,f_{n}(\textbf{x}))$
is injective.

Proof of Theorem 2. Inspired by the quantum game GYNI , we show that the
optimal classical and quantum winning strategies are identical for any prior
distribution $p$ of the inputs. Note that there is a simple classical strategy
achieving a winning probability

$\displaystyle\varpi_{c}\geq\max_{\textbf{x}}(p(\textbf{x})+p(\overline{\textbf{x}}))$
(S51)

where $\overline{\textbf{x}}$ denotes the negation of the input string x,
$\overline{\textbf{x}}=(\overline{x}_{1},\overline{x}_{2},\cdots,\overline{x}_{n})$
with $\overline{x}_{i}=x_{i}\oplus 1$, and $\oplus$ denotes addition modulo 2.
This strategy is based on the following simple observation from the assumption
of ${\cal F}$.

  * Let $\textbf{x}^{*}$ be an arbitrary string. If $\textbf{x}\not=\textbf{x}^{*}$, $\overline{\textbf{x}^{*}}$, then it follows that $(f_{1}(\textbf{x}^{*}),\cdots,f_{n}(\textbf{x}^{*}))\not=(f_{1}(\textbf{x}),\cdots,f_{n}(\textbf{x}))$, and $(f_{1}(\overline{\textbf{x}^{*}}),\cdots,f_{n}(\overline{\textbf{x}^{*}}))\not=(f_{1}(\textbf{x}),\cdots,f_{n}(\textbf{x}))$. (S52)

Indeed, if this was not the case, we would have that for any $i$, either
$x_{i}\not=y_{i}$ or $x_{i+1}=y_{i+1}$. But this would in turn imply that
either $\textbf{x}=\textbf{x}^{*}$ or $\textbf{x}=\overline{\textbf{x}^{*}}$,
which is contradiction with the assumption.

Let a classical strategy be specified by the string $\textbf{x}^{*}$, where
each party sends out the bit $y_{i}=f_{i}(\textbf{x}^{*})$ if it received the
input $x^{*}_{i}$, and outputs $y_{i}=f_{i}(\overline{\textbf{x}^{*}})$ if it
received $\overline{x^{*}_{i}}$. It obviously follows that
$P(y_{i}=f_{i}(\textbf{x}^{*})|\textbf{x}^{*})=1$ and
$P(y_{i}=f_{i}(\overline{\textbf{x}^{*}})|\overline{\textbf{x}^{*}})=1$. On
the other hand, $P(y_{i}|\textbf{x})=0$ for all
$\textbf{x}\not=\textbf{x}^{*},\overline{\textbf{y}}$. Indeed, from the
observation (S52), there exists an index $i$ such that $x_{i}=x^{*}_{i}$, but
for which $x^{*}_{i+1}\not=x_{i+1}$. Since ${\cal F}$ is injective, it follows
that
$(f_{1}(\textbf{x}^{*}),f_{2}(\textbf{x}^{*}),\cdots,f_{n}(\textbf{x}^{*}))\not=(f_{1}(\textbf{x})$,
$f_{2}(\textbf{x})$, $\cdots,f_{n}(\textbf{x}))$, and
$(f_{1}(\overline{\textbf{x}^{*}}),f_{2}(\overline{\textbf{x}^{*}}),\cdots,f_{n}(\overline{\textbf{x}^{*}}))\not=(f_{1}(\textbf{x}),f_{2}(\textbf{x}),\cdots,f_{n}(\textbf{x}))$.
The winning probability of this classical strategy equals to
$p(\textbf{x}^{*})+p(\overline{\textbf{y}})$, which yields Eq.(S51) if we take
$\textbf{x}^{*}$ to be
$p(\textbf{x}^{*})+p(\overline{\textbf{x}^{*}})=\max_{\textbf{x}}(p(\textbf{x})+p(\overline{\textbf{x}}))$.

We now prove that there is no better quantum (hence classical) strategy. In
the most general quantum protocol, the players share an entangled state $\rho$
and perform projective measurements on their subsystem depending on their
inputs $x_{i}$. They output their measurement results $y_{i}$. Denote
$M^{x_{i}}_{y_{i}}$ as the projection operator associated to the output
$y_{i}$ for the input $x_{i}$. The probability that all players produce the
correct output is given by

$\displaystyle
P(y_{1}=f_{1}(\textbf{x}),\cdots,y_{n}=f_{n}(\textbf{x})|\textbf{x})$
$\displaystyle=$ $\displaystyle\langle M^{x_{1}}_{f_{1}}\otimes\cdots\otimes
M^{x_{n}}_{f_{n}}\rangle$ $\displaystyle=$ $\displaystyle{\rm
Tr}[(M^{x_{1}}_{f_{1}}\otimes\cdots\otimes M^{x_{n}}_{f_{n}})\rho],$ (S53)

The average winning probability is

$\displaystyle\varpi_{q}=\max_{\rho,\forall\\{M^{x_{i}}_{y_{i}}\\}}\sum_{\textbf{x}}p(\textbf{x})\langle
M_{\textbf{x}}\rangle$ (S54)

where $M_{\textbf{x}}$ is given by
$M_{\textbf{x}}=M^{x_{1}}_{f_{1}}\otimes\cdots\otimes M^{x_{n}}_{f_{n}}$ for
short, and $\langle\cdot\rangle$ is associated with some fixed quantum system
$\rho$. Note that the operators $M_{\textbf{x}}$ satisfy the following
properties

$\displaystyle M^{2}_{\textbf{x}}=M_{\textbf{x}},$ (S55) $\displaystyle
M_{\textbf{x}}M_{\textbf{x}^{*}}=0\mbox{ if
}\textbf{x}\not=\textbf{x}^{*},\overline{\textbf{x}^{*}}.$ (S56)

The first property follows from the fact that $M_{\textbf{x}}$s are projection
operators. The second follows from the orthogonality relations:
$M^{x_{i}}_{y_{i}}M^{x_{i}}_{\overline{y}_{i}}=0$ and observation in Eq.(S52).
Note that protocols involving mixed states or general measurements can all be
represented in the above form by expanding the dimensionality of the initial
state.

Using Eqs.(S55) and (S56), we show that
$\varpi_{q}=\max_{\rho,\forall\\{M^{x_{i}}_{y_{i}}\\}}\sum_{\textbf{x}}p(\textbf{x})M_{\textbf{x}}\leq\varpi_{c}$,
where ”$\leq$” should be understood as an operator inequality, i.e., $A\leq B$
means that $\langle A\rangle\leq\langle B\rangle$ for all $\rho$. Note that we
cannot assume $p(\textbf{x})+p(\overline{\textbf{x}})=\varpi_{c}$, but
$p(\textbf{x})+p(\overline{\textbf{x}})\leq\varpi_{c}$ for all x since the
normalization condition of $\sum_{\textbf{x}}p(\textbf{x})=1$. In fact, we
have

$\displaystyle\Delta=$
$\displaystyle(\sqrt{\varpi_{c}}-\sum_{\textbf{x}}\alpha_{\textbf{x}}M_{\textbf{x}})^{2}+\frac{1}{2}\sum_{\textbf{x}}(\beta_{\textbf{x}}M_{\textbf{x}}-\beta_{\overline{\textbf{x}}}M_{\overline{\textbf{x}}})^{2}$
$\displaystyle=$
$\displaystyle\varpi_{c}-2\sum_{\textbf{x}}(\varpi_{c}-p(\overline{\textbf{x}}))M_{\textbf{x}}$
$\displaystyle+\sum_{\textbf{x}}\alpha_{\textbf{x}}^{2}M_{\textbf{x}}+\sum_{\textbf{x}}\alpha_{\textbf{x}}\alpha_{\overline{\textbf{x}}}M_{\textbf{x}}M_{\overline{\textbf{x}}}$
$\displaystyle+\frac{1}{2}\sum_{\textbf{x}}\frac{p(\textbf{x})p(\overline{\textbf{x}})}{\varpi_{c}}(M_{\textbf{x}}+M_{\overline{\textbf{x}}}$
$\displaystyle-
M_{\textbf{x}}M_{\overline{\textbf{x}}}-M_{\overline{\textbf{x}}}M_{\textbf{x}})$
(S57)

where
$\alpha_{\textbf{x}}=\sqrt{\varpi_{c}}-p(\overline{\textbf{x}})/\sqrt{\varpi_{c}}$
and
$\beta_{\textbf{x}}=\sqrt{p(\textbf{x})p(\overline{\textbf{x}})/\varpi_{c}}$.
Eq.(S57) is followed from Eq.(S55). And then, we have

$\displaystyle\Delta=$
$\displaystyle\varpi_{c}-2\sum_{\textbf{x}}(\varpi_{c}-p(\overline{\textbf{x}}))M_{\textbf{x}}+\sum_{\textbf{x}}\frac{p^{2}(\overline{\textbf{x}})}{\varpi_{c}}M_{\textbf{x}}$
$\displaystyle+\sum_{\textbf{x}}\varpi_{c}M_{\textbf{x}}-2\sum_{\textbf{x}}p(\overline{\textbf{x}})M_{\textbf{x}}$
$\displaystyle+\sum_{\textbf{x}}(\varpi_{c}-p(\overline{\textbf{x}})-p(\textbf{x})+\frac{p(\textbf{x})p(\overline{\textbf{x}})}{\varpi_{c}})M_{\overline{\textbf{x}}}M_{\textbf{x}}$
$\displaystyle+\frac{1}{2}\sum_{\textbf{x}}\frac{p(\textbf{x})p(\overline{\textbf{x}})}{\varpi_{c}}(M_{\textbf{x}}+M_{\overline{\textbf{x}}}-M_{\textbf{x}}M_{\overline{\textbf{x}}}-M_{\overline{\textbf{x}}}M_{\textbf{x}})$
$\displaystyle=$
$\displaystyle\varpi_{c}-\sum_{\textbf{x}}\varpi_{c}M_{\textbf{x}}+\sum_{\textbf{x}}(\varpi_{c}-p(\textbf{x})-p(\overline{\textbf{x}}))M_{\textbf{x}}M_{\overline{\textbf{x}}}$
$\displaystyle+\sum_{\textbf{x}}\frac{p(\overline{\textbf{x}})(p(\textbf{x})+p(\overline{\textbf{x}}))}{\varpi_{c}}M_{\textbf{x}}$
(S58) $\displaystyle\leq$
$\displaystyle\varpi_{c}-\sum_{\textbf{x}}\varpi_{c}M_{\textbf{x}}+\sum_{\textbf{x}}p(\overline{\textbf{x}})M_{\textbf{x}}$
$\displaystyle+\sum_{\textbf{x}}(\varpi_{c}-p(\textbf{x})-p(\overline{\textbf{x}}))M_{\textbf{x}}M_{\overline{\textbf{x}}}$
(S59) $\displaystyle=$
$\displaystyle\varpi_{c}-\sum_{\textbf{x}}(\varpi_{c}-p(\overline{\textbf{x}}))M_{\textbf{x}}$
$\displaystyle+\sum_{\textbf{x}}(\varpi_{c}-p(\textbf{x})-p(\overline{\textbf{x}}))M_{\textbf{x}}M_{\overline{\textbf{x}}}$
$\displaystyle\leq$
$\displaystyle\varpi_{c}-\sum_{\textbf{x}}(\varpi_{c}-p(\overline{\textbf{x}}))M_{\textbf{x}}$
$\displaystyle+\sum_{\textbf{x}}(\varpi_{c}-p(\textbf{x})-p(\overline{\textbf{x}}))M_{\textbf{x}}$
(S60) $\displaystyle=$
$\displaystyle\varpi_{c}-\sum_{\textbf{x}}p(\textbf{x})M_{\textbf{x}},$ (S61)

In Eq.(S58), we have taken use of the commutate of projection operators, i.e.,
$M_{\textbf{x}}M_{\overline{\textbf{x}}}=M_{\overline{\textbf{x}}}M_{\textbf{x}}$,
and identity
$\sum_{\textbf{x}}\frac{p(\overline{\textbf{x}})p(\textbf{x})}{\varpi_{c}}M_{\overline{\textbf{x}}}=\sum_{\textbf{x}}\frac{p(\textbf{x})p(\overline{\textbf{x}})}{\varpi_{c}}M_{\textbf{x}}$.
Eq.(S59) follows from the inequality :
$p(\textbf{x})+p(\overline{\textbf{x}})\leq\varpi_{c}$ which is derived from
the inequality (S51). Eq.(S60) follows from the operator inequality of
$M_{\textbf{x}}M_{\overline{\textbf{x}}}\leq M_{\textbf{x}}$. From Eq.(S51),
it follows that

$\displaystyle\max_{\rho,\forall\\{M^{x_{i}}_{y_{i}}\\}}\sum_{\textbf{x}}p(\textbf{x})M_{\textbf{x}}\leq\varpi_{c}.$
(S62)

The inequality of
$\sum_{\textbf{x}}p(\textbf{x})P(y_{1}=f_{1}(\textbf{x}),\cdots,y_{n}=f_{n}(\textbf{x})|\textbf{x})\leq\varpi_{c}$
can be interpreted as a Bell inequality whose local and quantum bound
coincide. Note that any POVM measurements associated with non-commuting
operators can be realized using projection measurements in an extended state
space. The proof stated above is also independent of quantum resources. This
explains the same bound of the classical and quantum payoffs.

## References

  * (1) Lawson, T., Linden, N. and Popescu, S. Biased nonlocal quantum games, http://arxiv.org/abs/1011.6245 (2010).
  * (2) He, X., Fang, K., Sun, X. and Duan, R. Quantum advantages in hypercube game, http://arxiv.org/abs/1806.02642 (2018).
  * (3) Cirel’son, B. S. Quantum generalizations of Bell’s inequality. Lett. Math. Phys. 4, 83-100 (1980).
  * (4) Einstein, A., Podolsky, B., Rosen, N. Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47, 777-780 (1935).
  * (5) Clauser, J. F., Horne, M. A., Shimony, A., and Holt, R. A. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880-884 (1969).
  * (6) Luo, M. X. Computationally efficient nonlinear Bell inequalities for quantum networks. Phys. Rev. Lett. 120, 140402 (2018).
  * (7) Almeida, M. L., et al. Guess your neighbor’s input: A multipartite nonlocal game with no quantum advantage. Phys. Rev. Lett. 104, 230404 (2010).