Document 1 (368 KB) - DROPS - Series

Graph-theoretical Bounds on the Entangled Value
of Non-local Games
André Chailloux1 , Laura Mančinska2 , Giannicola Scarpa3 , and
Simone Severini4
SECRET Project Team, INRIA Paris-Rocquencourt,Paris, France
[email protected]
Center for Quantum Technologies, Singapore
[email protected]
Universitat Autònoma de Barcelona, Barcelona, Spain
[email protected]
University College London, London, United Kingdom
[email protected]
We introduce a novel technique to give bounds to the entangled value of non-local games. The
technique is based on a class of graphs used by Cabello, Severini and Winter in 2010. The upper
bound uses the famous Lovász theta number and is efficiently computable; the lower one is based
on the quantum independence number, which is a quantity used in the study of entanglementassisted channel capacities and graph homomorphism games.
1998 ACM Subject Classification G.2.3 Applications
Keywords and phrases Graph theory, non-locality, entangled games
Digital Object Identifier 10.4230/LIPIcs.TQC.2014.67
In non-local games, two non-communicating players cooperate in order to achieve a task.
Each player receives an input and produces an output, and they must satisfy the task’s
In physics, this class of games is also known as “entangled games”. They are mostly used
to investigate the power of entanglement, by designing intuitive Bell inequalities. One designs
a non-local game and proves an upper bound on the winning probability of the classical
players (the Bell inequality). Later, one shows that there exists a quantum strategy that
by using entanglement can beat that winning probability. Two famous examples of such
approach are the CHSH game (based on [3]) and the magic square game (based on [14]).
Non-local games are also important in computer science, where they are usually called
“two-prover one-round games”. Their intuitive nature has been used in complexity theory to
approach the difficult problem of P vs. NP, by defining probabilistically checkable proofs
and ultimately leading to the famous unique games conjecture [9, 10].
Estimating or bounding the value of a game given its description is an important task,
and much effort has been devoted to the question. For example, the entangled value for the
class of XOR games has been shown to be easy to compute with a semidefinite program by
Cirel’son [4]. Also the entangled value of unique games turns out to be easy to compute,
therefore falsifying the unique games conjecture in the quantum world [11].
© André Chailloux, Laura Mančinska, Giannicola Scarpa, and Simone Severini;
licensed under Creative Commons License CC-BY
9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC’14).
Editors: Steven T. Flammia and Aram W. Harrow; pp. 67–75
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
Graph-theoretical Bounds on the Entangled Value of Non-local Games
Here, we propose a general approach to bound the value of a non-local game based on
graph theory. Given the description of a game, we construct a graph that contains all the
information about the game, and we call it the “game graph”. The construction is based on
the techniques in [7]. Such techniques have also been extended and used in [1].
We first show that the classical value of any game is equal to the independence number
of its game graph (renormalized). This reflects the fact that computing exactly the classical
value of a game is NP-hard. We then show an efficiently computable upper bound on the
quantum value of a game (and therefore on the classical value), given by the celebrated
Lovász theta number. We then give lower bound for the games on the uniform distribution
given by the quantum independence number, a graph parameter introduced in [5] and futher
discussed in [13, 15]. To conclude, we give a class of games for which this upper bound is
We believe this graph-theoretical approach is an important and a fertile field for improvements. We discuss these in the conclusions section.
Non-local games
We now briefly describe the setting of a non-local game G.
Alice and Bob are separated and forbidden to communicate. They receive inputs x and y
from some input sets X and Y , according to some fixed and known probability distribution π,
and are required to produce outputs a and b from output sets A and B, respectively. The
game rules are encoded in a predicate λ : X × Y × A × B → {0, 1}, which specifies which
outputs a, b are correct on inputs x, y. In other words, players win the game on inputs x, y if
they output some a, b such that λ(x, y, a, b) = 1. The goal of the players is to maximize the
winning probability.
A classical strategy for the game is without loss of generality a pair of functions, fA :
X → A for Alice and fB : Y → B for Bob. (Shared randomness between the two players
is easily seen not to be beneficial.) The winning probability of a strategy is calculated as
π(x, y)λ(x, y, fA (x), fB (y)).
The classical value ω(G) of the game is the maximum winning probability among all classical
In entangled strategies (a.k.a. quantum strategies), players share a fixed (i.e., independent
of the inputs) entangled state |ψi. For each input x, Alice has a projective measurement
{Pax }a∈A , and for each input y, Bob has a projective measurement {Qyb }b∈B . Upon receiving
the inputs, they apply the corresponding measurements to their parts of the entangled state
and produce classical outputs a and b, respectively. The winning probability of a strategy is
calculated as follows:
π(x, y)λ(x, y, a, b)hψ|Pax ⊗ Qyb |ψi.
The entangled value ω ∗ (G) of the game is the supremum of the winning probability, taken
over all entangled strategies.
A Bell inequality for a game is an upper bound on its classical value. We have a Bell
inequality violation for a game G if the entangled value is strictly larger than the classical
one. The violation is quantified by the ratio ω ∗ (G)/ω(G).
A. Chailloux, L. Mančinska, G. Scarpa, and S. Severini
The CHSH game is one particularly famous example [3]. Here, the inputs x ∈ {0, 1} and
y ∈ {0, 1} are uniformly distributed, and Alice and Bob win the game if their respective
outputs a ∈ {0, 1} and b ∈ {0, 1} satisfy a ⊕ b = x ∧ y; in other words, a should equal b
unless x = y = 1. The classical value of this game is√easily seen to be ω(G) = 3/4, while the
entangled value is known to be ω ∗ (G) = 1/2 + 1/(2 2) ≈ 0.85.
A non-local game is said to be a pseudo-telepathy game if the quantum value is 1 while
the classical value is strictly less than 1.
Notions of graph theory
A simple graph G = (V, E) consists of a finite vertex set V and its edge set E ( V × V (the
inclusion here is strict because there are no edges of the form (v, v)). Two vertices (v, w) ∈ E
are “adjacent” or equivalently “form an edge”. All graphs considered here are simple graphs.
For a graph G = (V, E), we also denote its vertex set with V (G) and its edge set with E(G)
whenever confusion has to be avoided.
An independent set of a graph is a subset I of V (G) such that no two elements of I are
adjacent. The independence number of a graph G, denoted by α(G), is the maximum size of
an independent set of G.
A d-dimensional orthogonal representation of G = (V, E) is a map φ : V → Cd such
that for all (v, w) ∈ E, hφ(v)|φ(w)i = 0. (If all the vectors have unit norm, this is called
orthonormal representation.)
We finally introduce an important graph parameter: the theta number (a.k.a. Lovász
number or theta function). It was originally defined by Lovász [12] to solve a long-standing
problem posed by Shannon [16]: computing the Shannon capacity of the five-cycle. There
are many equivalent formulations of the theta number (see [8] for a detailed survey). The
one that we use in this paper is the following:
ϑ(G) = max
|hψ|ψv i|2 ,
v∈V (G)
where the maximum is over unit vectors ψ and orthonormal representations {ψv }v∈V (G) .
Lovász [12] proved that α(G) ≤ ϑ(G) holds (this inequality is part of the so-called “sandwich
theorem” [8]). The theta number can be approximated to within arbitrary precision in
polynomial time, hence it gives a tractable and in many cases useful bound for α.
Quantum Independence Number
In this section we define the quantum independence number and state some of its properties.
First, let us briefly give some historical background. In [13] the concept of quantum
independence number is presented in the context of zero-error information theory. This
quantity is usually called in literature “one-shot zero-error entanglement-assisted channel
capacity” and denoted as α∗ . A new definition of quantum independence number, denoted
as αq , came in [15], in the context of graph homomorphisms. As of today, it is not known if
the two quantities are equal for all graphs. In this paper we use the second quantity, but for
simplicity we omit the details about homomorphisms and provide a direct definition.
As with the quantum chromatic number (see [6]), the quantum independence number
can be defined in terms of a non-local game. Informally, the independent set game with
parameter t for a graph G = (V, E) is as follows. Two players, Alice and Bob, claim that
they know an independent set I of G consisting of t vertices. A referee wants to test this
claim with a non-local game. He forbids communication between the players, generates two
Graph-theoretical Bounds on the Entangled Value of Non-local Games
uniformly random numbers x, y ∈ [t] and separately asks Alice to provide the x-th vertex
of I and Bob to provide the y-th vertex of I. The players are required to output the same
vertex if x = y, and to output non-adjacent vertices if x 6= y. A formal definition follows.
I Definition 1. The independent set game with parameter t on the graph G = (V, E) is
a non-local game with input sets X = Y = [t], output sets A = B = V . The probability
distribution π is the uniform distribution on the input pairs. Alice gets input x and outputs
v, Bob gets input y and outputs w. The players lose the game in the following two cases:
1. x = y and v 6= w
2. x 6= y and (v, w) ∈ E or v = w
A classical strategy consists w.l.o.g. of two deterministic functions fA : [t] → V for Alice
and fB : [t] → V for Bob. Shared randomness, as seen for the coloring game, is not beneficial.
A little thought will show that to win with probability 1, we must have fA = fB (to avoid
the first losing condition) and that {fA (1), . . . , fA (t)} must be a valid independent set of the
graph of size t (to avoid the second losing condition). It follows that the classical players
cannot win the game with probability 1 when t > α(G).
It is proven in [15] that w.l.o.g. quantum strategies for the independent set game consist of
projective measurements on a maximally entangled state, that the projective measurements
of Alice and Bob are the same and that all the projectors can be real-valued. Therefore we
can define a quantum independent set of size t as a collection of t projective measurements
{Pvx }v∈V for all x ∈ [t] that have the whole vertex set as outputs, with the following
consistency condition:
for all (u, v) ∈ E or u = v and for all x 6= x0 ,
Pux Pvx = 0.
I Definition 2. For all graphs G, the quantum independence number αq (G) is the maximum
number t such that there exists a quantum independent set of G of size t.
Game graphs
Definition and relation to ω(G)
Consider a non-local game G with input sets X, Y , output sets A, B, predicate λ : X × Y ×
A × B → {0, 1} and uniform distribution on the inputs.
I Definition 3. A graph G = (V, E) associated to the game G has:
1. V = {xyab | x ∈ X, y ∈ Y, a ∈ A, b ∈ B and λ(x, y, a, b) = 1},
2. E = {{xyab, x0 y 0 a0 b0 } | (x = x0 ∧ a 6= a0 ) ∨ (y = y 0 ∧ b 6= b0 )}.
This definition is inspired by a construction in [7] in the framework of contextuality of
physical theories. The authors used something similar to Definition 3 for the special case of
the CHSH game. Here we generalize to all games.
For simplicity, we prove the results in this section for the case where the game has the
uniform distribution on the inputs and λ is a boolean function. It is straightforward to
generalize to games with real-valued predicate and any probability distribution π of the
inputs, as follows. Consider the (vertex) weighted graph with all the quadruples xyab in the
vertex set, labelled with weight(xyab) = λ(x, y, a, b) · π(x, y), and the same edge set as before.
The classical bound and the Lovász theta bound that we will prove later can be adapted
by considering the weighted versions of these parameters. However, we do not know how to
generalize our last result because we do not define the quantum independence number for a
weighted graph.
A. Chailloux, L. Mančinska, G. Scarpa, and S. Severini
Now we prove that that the classical value of a game can be expressed in terms of the
independence number of its game graph.
I Theorem 4. Let G be a non-local game with input sets X and Y , uniform input distribution
and associated graph G. Then
ω(G) =
|X × Y |
Proof. Let k = |X × Y |. We begin by proving that ω(G) ≥ α(G)/k. Namely, we show that
given a maximal independent set I ⊆ V of size `, we can exhibit a strategy for G that answers
correctly to at least ` of the k questions. By the structure of G, the independent set I cannot
contain vertices xyab and xy 0 a0 b0 such that a 6= a0 . Similarly, I cannot contain vertices xyab
and x0 ya0 b0 such that b 6= b0 . Hence, we have the following strategy: on input x, Alice outputs
the unique a determined by the vertices in the independent set I. Bob behaves similarly.
Since V contains only winning quadruples xyab, the size ` of the independent set means
Alice and Bob answer correctly to at least ` input pairs. Hence, ω(G) ≥ `/k.
Now we show that ω(G) ≤ α(G)/k, i.e., if there exists a strategy that wins on ` of the k
input pairs, then there exists an independent set with weight `. We have that w.l.o.g. classical
strategies consist of a pair of functions. Fix Alice and Bob’s functions fA and fB that win
on ` input pairs. Now take the set of quadruples S = {(x, y, fA (x), fB (y))}x∈X,y∈Y . We
have that I = S ∩ V is a set of ` vertices of G. Since fA and fB are deterministic, I cannot
contain vertices xyab and xy 0 a0 b0 such that a 6= a0 nor vertices xyab and x0 ya0 b0 such that
6 b0 . Therefore, there cannot be an edge between any pair of the elements of I and we have
that I is an independent set of G of size `. Hence, α(G) ≥ `. Combining the two directions
proves the theorem.
Bounds on the entangled value of a game
Cabello, Severini and Winter [7] observe that the quantum value of the CHSH game is equal
to the theta number of its associated graph divided by the number of questions. We have
found by direct calculation that this is not always true for general games, for example in the
case of the 2-fold parallel repetition of CHSH. The same conclusion follows from the results
of Acín et al. in [1]. Here we prove the upper bound directly for our specific constructions.
I Theorem 5. Let G be a non-local game with input sets X and Y , uniform input distribution
and associated graph G = (V, E). Then
ω ∗ (G) ≤
|X × Y |
Proof. Let k = |X × Y |. Consider a quantum strategy for G that achieves the value ω ∗ (G).
It consists of a shared entangled state |ψi and a collection of projective measurements
{Pax }, {Qyb }, such that
X 1
1 X
λ(x, y, a, b)hψ|Pax ⊗ Qyb |ψi =
hψ|Pax ⊗ Qyb |ψi = ω ∗ (G).
For each quadruple xyab let |ψxyab i = Pax ⊗ Qyb |ψi. This is an orthogonal representation
of G, since for every edge (xyab, x0 y 0 a0 b0 ) either Pax Pax0 = 0 or Qyb Qyb0 = 0. Now for each
xyab consider the normalized vector
|ψxyab i
|ψxyab i
= p
||ψxyab ||
hψ|Pax ⊗ Qyb |ψi
Graph-theoretical Bounds on the Entangled Value of Non-local Games
}xyab∈V and ψ are a feasible solution for the formulation (1) of ϑ(G).
We have that {ψxyab
We conclude
ϑ(G) ≥
|hψ|ψxyab i|2
X hψ|ψxyab i 2
||ψxyab || xyab∈V
X hψ|P x ⊗ Qy |ψi2
hψ|Pax ⊗ Qyb |ψi
hψ|Pax ⊗ Qyb |ψi
= k · ω ∗ (G).
We now have the following lower bound in terms of the quantum independence number.
I Theorem 6. Let G be a non-local game with input sets X and Y , uniform input distribution
and associated graph G = (V, E). Then
ω ∗ (G) ≥
αq (G)
|X × Y |
To prove the theorem, we will use the following lemma.
I Lemma 7. Let M, N be positive semidefinite matrices. Then for any vector |vi, we have
hv| supp(M + N )|vi ≥ hv| supp(M )|vi,
where supp(M ) denotes the projector onto the support ( i.e., the column space) of M .
Proof. If P is a projector onto a subspace Π then hv|P |vi is the squared length of the
projection of |vi into Π. Hence, to prove the lemma it suffices to show that supp(M ) ⊆
supp(M + N ), where by abusing the notation we use supp to denote the support itself (rather
than the projection onto it).
For contradiction, suppose that supp(M ) 6⊆ supp(M + N ). Then the orthogonal complement of supp(M ) (i.e. the nullspace Null(M )) does not contain Null(M + N ). Hence we can
pick a vector |wi such that (M + N )|wi = 0 but M |wi =
6 0. This further implies that
hw|N |wi = hw|(M + N )|wi − hw|M |wi = −hw|M |wi < 0,
since M is positive semidefinite and M |wi =
6 0. This completes the proof as we have reached
a contradiction with the initial assumption that N is positive semidefinite.
Proof of Theorem 6. Given a quantum strategy {Pxyab
} for the independent set game on
G with parameter t, we construct a strategy to win the game G with probability at least
t/|X × Y |, as follows.
Players share a maximally entangled state with local dimension d (which is the dimension
of the projectors above). On input x, Alice measures her half of the state using the projective
measurement{Pax }a∈A {I − a Pax }, where the individual elements are defined as follows:
 X X i 
Pax = supp 
Pxayb 
A. Chailloux, L. Mančinska, G. Scarpa, and S. Severini
where we use supp(M ) to denote the projector onto the image of M . We show that this
is a valid projective measurement. For all y, b, y 0 , b0 there is an edge (xyab, xy 0 a0 b0 ) ∈ E.
Therefore in the strategy for the independent set game we have that for all i, j each projector
is orthogonal to Pxy
0 a0 b0 . Hence, for all a 6= a we have Pa · Pa0 = 0. Bob constructs
projectors Pb similarly.
Now we lower bound the quantum value of G as follows:
|X × Y | · ω ∗ (G) ≥
hψ|Pax ⊗ Pby |ψi
hψ| supp
y 0 b0
x0 a0
0 b0 ⊗ P 0 0
x a yb |ψi,
xay 0 b0 ∈V x0 a0 yb∈V
where we have used the fact that supp(M ⊗ N ) = supp(M ) ⊗ supp(N ) for all matrices M, N
to obtain the last equality. Now by applying Lemma 7, we drop all the terms except the
ones with i = j, a = a0 , b = b0 , x = x0 and y = y 0 , and we have that
|X × Y | · ω ∗ (G) ≥
hψ| supp
⊗ Pxayb
⊗ Pxayb
X X1
Tr(Id )
= αq (G).
In the above we have observed that supp(P + Q) = P + Q for mutually orthogonal projectors
P and Q to get Expression (4). We have used properties of |ψi = √1d i |i, ii to obtain
Expression (5). We have used the fact that, for all i, {Pxayb
: λ(x, a, y, b) = 1} forms a
measurement to obtain Expression (6).
Tightness of the lower bound
Here we obtain an equality relation between the value of the game and the quantum
independence number of the game graph, for a class of pseudo-telepathy games.
I Theorem 8. Let G be a pseudo-telepathy game with a 0-1 valued predicate λ, admitting
a quantum strategy consisting of a maximally entangled state |ψi and pairwise commuting
projectors. Let G be the corresponding game graph. Then,
ω ∗ (G) =
αq (G)
= 1.
|X × Y |
Proof. From Theorem 6 we have αq (G) ≤ |X × Y | · ω ∗ (G). We need to prove the other
Let {Pax }, {Qyb } be the strategies that win the game G on |ψi. We have:
π(x, y)
hψ|Pax ⊗ Qyb |ψi = 1,
so for all (x, y) we must have
Graph-theoretical Bounds on the Entangled Value of Non-local Games
hψ|Pax ⊗ Qyb |ψi = 1
and for all quadruples (x, y, a, b) such that λ(xyab) = 0 we have Pax Qyb = 0.
Let Πxyab = Pax Qyb . These are projectors thanks to the commutativity assumption. We
1. For all (x, y) we have
X y
Qb = I,
Pax Qyb =
Pax Qyb =
Qyb Qyb0
where the second equality follows from
= δbb0 .
0 0 0 0
2. For each edge (x, y, a, b), (x , y , a , b ) we have a collection of t real-valued projective
measurements {Pvx }v∈V for all x ∈ [t] that have the whole vertex set as outputs,
Πxyab Πx0 y0 a0 b0 = 0,
because if x = x0 and a 6= a0 then Pax Pax0 = 0, and if y = y 0 and b 6= b0 then Qyb Qyb0 = 0.
Therefore, we can construct |X × Y | projective measurements that are a winning strategy
for the independent set game with t = |X × Y | as follows. For each pair (x, y) consider the
projective measurement {Πxyab }a,b:λ(xyab)=1 (and zero matrices for the other vertices of the
graph). The first observation above proves that those are valid projective measurements; the
second observation shows that they respect the consistency condition (2).
Concluding remarks and open problems
We have formalized and discussed a novel approach for the study of non-local game in a
combinatorial fashion. Work in progress on this approach relate to the easy generalization to
more than 2 players, and the less-easy computation of graphs for the parallel repetition of
Our approach has ample room for improvement. Open questions include:
1. Can we find a tighter lower bound for the entangled value of all games by using some
variant of the quantum independence number, such as the one in [2]? Alternatively, can
we prove tightness of the current lower bound?
2. Can we find better lower bounds, for example using one of the variants of Lovász theta
3. Can we characterize the class of games for which the Lovász bound is tight? We know that
the value of CHSH is exactly the theta number of its game graph (see [7]). Is this true
for all the XOR games? This would reflect the fact that their value is easy to compute.
4. Are there other graph parameters related to the classical and entangled values of specific
classes of games, for example unique games?
5. We have shown that for a class of pseudo-telepathy games that quantum players can win
using commutative projective measurements on maximally entangled state, this bound is
tight. A similar class of games is shown in [13] to be in one-to-one correspondence with a
generalization of Kochen-Specker sets. It is not clear to us if those two results together
could be used to prove something stronger. Perhaps the whole class could be interpreted
as pseudo-telepathy games based on some graph parameter (maybe the homomorphism
games in [15]) and the relationship to the quantum independence number would be a
consequence of this.
A. Chailloux, L. Mančinska, G. Scarpa, and S. Severini
Acknowledgements. The authors thank the referees of TQC 2014 for useful comments.
Laura Mančinska is supported by the MOE Tier 3 Grant “Random numbers from quantum
processes” (MOE2012-T3-1-009). G. Scarpa is supported by the European Commission. Part
of this work was done while G. Scarpa was a PhD student at CWI, supported by Ronald de
Wolf’s VIDI grant from NWO. S. Severini is supported by the Royal Society and EPSRC.
Antonio Acín, Tobias Fritz, Anthony Leverrier and Ana Belén Sainz. A Combinatorial
Approach to Nonlocality and Contextuality. December 2012. arXiv:1212.4084.
Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan, and Giannicola Scarpa.
Zero-error source-channel coding with entanglement. In The Seventh European Conference
on Combinatorics, Graph Theory and Applications, volume 16 of CRM Series, pages 157–
162. Scuola Normale Superiore, 2013.
John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed
experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880–884,
B.S. Cirel’son. Quantum generalizations of bell’s inequality. Letters in Mathematical
Physics, 4(2):93–100, 1980.
T. S. Cubitt, D. Leung, W. Matthews, and A. Winter. Improving zero-error classical
communication with entanglement. Phys. Rev. Lett., 104:230503–230506, 2010.
P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter. On the quantum
chromatic number of a graph. Electr. J. Comb., 14(1), 2007.
Adán Cabello, Simone Severini, and Andreas Winter. Graph-theoretic approach to quantum
correlations. Phys. Rev. Lett., 112:040401, January 2014. Full version on arXiv:1010.2163.
D. E. Knuth and Stanford University. Computer Science Dept. The sandwich theorem.
Stanford University, Dept. of Computer Science, 1993.
Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the
Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC’02, pages 767–775,
New York, NY, USA, 2002. ACM.
Subhash Khot. In Proceedings of IEEE 25th Annual Conference on Computational Complexity, pages 99–121, June 2010.
Julia Kempe, Oded Regev, and Ben Toner. Unique games with entangled provers are easy.
SIAM Journal on Computing, 39(7):3207–3229, 2010. Preliminary version in FOCS’08.
L. Lovász. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory, 25(1):1–7, 1979.
L. Mančinska, G. Scarpa, and S. Severini. New separations in zero-error channel capacity
through projective Kochen-Specker sets and quantum coloring. IEEE Trans. Inf. Theory,
59(6):4025–4032, 2013.
A. Peres. Two simple proofs of the Kochen-Specker theorem. J. Phys. A, 24:L175–L178,
D. E. Roberson and L. Mancinska. Graph Homomorphisms for Quantum Players. December
2012. arXiv:1212.1724.
Claude E. Shannon. The zero error capacity of a noisy channel. IT-2(3):8–19, September