## Abstract

We describe a new technique for obtaining Tsirelson bounds, which are upper bounds on the quantum value of a Bell inequality. Since quantum correlations do not allow signalling, we obtain a Tsirelson bound by maximizing over all no-signalling probability distributions. This maximization can be cast as a linear programme. In a setting where three parties, A, B and C, share an entangled quantum state of arbitrary dimension, we (i) bound the trade-off between AB's and AC's violation of the Clauser–Horne–Shimony–Holt inequality and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities, relevant for interactive proof systems and cryptography.

## 1. Introduction

One of the remarkable properties of quantum entanglement is that it is monogamous: if Alice (A), Bob (B) and Charlie (C) each have a qubit, and A and B are maximally entangled, then C's qubit must be completely uncorrelated with either A's or B's. This property is inherently non-classical: if A, B and C have bits instead of qubits, and A's bit is always the same as B's bit, then there is no restriction on how A's bit is correlated with C's bit. In this work, we consider the correlations that result from making local measurements on a multipartite quantum system. Some such quantum correlations violate Bell (1964) inequalities. We show how these correlations, termed *non-local*, can also be monogamous.

Consider, for example, the well-known Clauser–Horne–Shimony–Holt (CHSH) inequality (Clauser *et al.* 1969). Two parties, A and B, share a quantum state *ρ*, and each chooses one of two observables to measure on their component of the state. Define the *CHSH operator*(1.1)where *A*_{1} and *A*_{2} (*B*_{1} and *B*_{2}) are A's (B's) observables and are Hermitian operators with spectrum in [−1,+1]. Then the CHSH inequality states that , for all local hidden variable (LHV) models. There are, however, *entangled* states, e.g. the singlet state of two qubits , such that . Thus the correlations arising from measuring this state cannot be described by any LHV model. In fact, it is true that for all observables *A*_{1}, *A*_{2}, *B*_{1} and *B*_{2}, and all states *ρ*. Such a bound on the maximum entangled value of a Bell inequality is termed a Tsirelson bound (Cirel'son 1980). Although we do not yet know how to calculate the best such bound for an arbitrary Bell inequality, a number of ad hoc techniques have been developed (Cirel'son 1980; Tsirelson 1987; Buhrman & Massar 2004; Cleve *et al.* 2004; Masanes 2005; Navascués *et al.* 2007, 2008; Doherty *et al.* 2008).

In this paper, we introduce a new technique for obtaining Tsirelson bounds. Since local measurements on spatially separated components of a multipartite quantum system can be carried out simultaneously, such measurements cannot be used to send a signal from one party to another. The outcomes of local measurements on an entangled quantum state are therefore described by a *no-signalling* probability distribution. Maximization over all no-signalling probability distributions can be cast as a linear programme, and so we obtain an upper bound by solving this linear programme. This gives an efficient algorithm for obtaining Tsirelson bounds.

We use this new technique to study the monogamy of quantum and no-signalling correlations. Suppose that three parties, A, B and C, share an entangled quantum state of arbitrary dimension. We start by bounding the trade-off between AB's and AC's violation of the CHSH inequality. Thus, we prove an analogue for quantum correlations of the famous theorem of Coffman *et al.* (2000), which describes the trade-off between how entangled A is with B, and how entangled A is with C.

In our second application, we illustrate a way to *prevent* A and B from violating a Bell inequality, even if they can share an arbitrary entangled state. We do this by introducing an extra party C, and forcing one of the parties, say B, to be classically correlated with C. For the odd-cycle Bell inequality of Cleve *et al.* (2004), we prove that the presence of C prevents A and B from violating the Bell inequality *at all*. Finding methods to prevent entangled parties from violating Bell inequalities is important because it allows us to extend results about the computational hardness of computing the classical value of a Bell inequality to the quantum domain. Indeed, subsequent to the work described in this paper, Kempe *et al.* (in press) have used the same idea (but entirely different proof techniques) to show that it is NP-hard to calculate, or even to approximate to exponential precision, the entangled value of a three-player Bell inequality.

Our second result also has a cryptographic interpretation. Suppose that A and B are trying to share a secret key, and that C is eavesdropping on them. If A and B observe correlations that would cause them to win the two-player odd-cycle game with a probability greater than 1−1/2*n*, then this limits how correlated C can be with B. Barrett *et al.* (2005) have presented a key distribution protocol along these lines, which is provably secure against no-signalling eavesdroppers (see also Acín *et al.* 2006).

The rest of this paper is structured as follows. After defining our framework in §2, we describe the linear programme in §3. We then present our applications: in §4, we study the monogamy of the CHSH inequality, while in §5 we study the odd-cycle Bell inequality.

## 2. Framework

### (a) Non-local games

We cast our results in the language of *non-local games*, also known as *cooperative games of incomplete information* (see Cleve *et al.* 2004). Let be a function and let *π* be a probability distribution on . Then, *V* and *π* define an *m*-player non-local game *G*(*V*, *π*) as follows: a referee chooses a set of questions randomly, according to *π*, and sends question *q*_{i} to player *i*. Each player must answer with a bit *a*_{i}. The players are not permitted to communicate after receiving the questions, but they may agree on a strategy before receiving them. They win with probability (where the ‘|’ in *V*(.|.) separates answers from questions). The *classical value* of a game *G*(*V*, *π*), denoted *ω*_{c}(*G*), is the maximum probability with which the players can win, assuming they use purely classical strategies. The *quantum value*, denoted *ω*_{q}(*G*), is the supremum of the winning probabilities obtained using strategies where the players are allowed to share an entangled quantum state. The *no-signalling value*, denoted *ω*_{ns}(*G*), is the maximum winning probability, assuming the players are allowed (black box) access to any no-signalling probability distribution. It is clear that .

### (b) The CHSH game

We describe how to interpret the CHSH inequality within this framework. The CHSH game *G*_{CHSH} is defined by setting *m*=*n*=2, letting *π* be the uniform distribution on and letting , where *a*_{1}⊕*a*_{2} is the exclusive-or of bits *a*_{1} and *a*_{2}, *q*_{1}∧*q*_{2} is the and of bits *q*_{1} and *q*_{2}, and [*ϕ*] is 1 if *ϕ* is true and 0 otherwise. Then, the winning probability of a particular strategy is , where is the CHSH operator of equation (1.1) and 〈.〉 is the appropriate expectation value for the strategy, classical, quantum or no-signalling. It follows that , and .

### (c) Classical correlation restricts Bell inequality violation

Consider a two-player game *G*(*V*, *π*) that is played by A and B_{0}. Here, we review the work of Masanes *et al.* (2006), who show how forcing B_{0} to be *classically* correlated with additional players B_{1}, B_{2}, …, B_{N} restricts the advantage that A and B_{0} can gain by sharing entanglement.

For *N*≥1, define the *N*th *extension* of a two-player game *G*(*V*, *π*) to be the (*N*+2)-player game *G*_{N}(*V*_{N}, *π*_{N}), with *π*_{N} defined by choosing (*q*_{1}, *q*_{2}) according to *π* and setting *q*_{2}=*q*_{3}=*q*_{4}=⋯=*q*_{N+2}, and(2.1)

We also set *G*_{0}=*G*. The idea is that we send B_{0}'s question to the other B_{i} and the players win if (i) the answers A and B_{0} satisfy the winning condition of *G*(*V*, *π*) and (ii) all the B_{i} agree.

*Let G*(*V*, *π*) *be a two-player game*. *Then,* *the values of its extensions satisfy*

*ω*_{c}(*G*_{N})=*ω*_{c}(*G*)*for all N and**ω*_{ns}(*G*_{N})*is a non-increasing sequence in N*,*with ω*_{ns}(*G*_{n−1})=*ω*_{c}(*G*)*,**where n is the number of possible questions for B*_{0}*in G*.

Terhal *et al.* (2003), building on the work of Werner (1989), earlier proved a similar result for *ω*_{q}(*G*_{N}).

## 3. Tsirelson bounds by linear programming

An *m*-party no-signalling probability distribution is a set of probabilities(3.1)subject to

*Positivity*. For all {*a*_{i}} and all {*q*_{i}},*p*({*a*_{i}}|{*q*_{i}})≥0,*Normalization*. For all {*q*_{i}}, , and*No-signalling*. For each subset of the*m*parties, the marginal probability distribution on must be independent of the inputs of the parties in*S*. In particular, must be independent of {*q*_{i}:*i*∈*S*} for all {*a*_{i}:*i*∉*S*} and for all {*q*_{i}:*i*∉*S*}.

The no-signalling value of *G* is given bywhere the maximization is performed over all conditional probability distributions , subject to the three sets of linear constraints enumerated above. We observe that *ω*_{ns}(*G*) is the solution to a linear programme in variables *p*({*a*_{i}}|{*q*_{i}}). Solving this programme for *ω*_{ns}(*G*) gives an upper bound on *ω*_{q}(*G*). Moreover, even if we cannot solve the linear programme, we can obtain an upper bound on *ω*_{ns}(*G*) by constructing a solution to the dual programme (see Boyd & Vandenberghe (2004) for an introduction to convex optimization).

Note that for the CHSH game, the no-signalling value *ω*_{ns}(*G*_{CHSH})=1 (Popescu & Rohrlich 1994), so the linear-programming technique provides only a trivial bound on *ω*_{q}(*G*_{CHSH}).

## 4. An analogue of the Coffmann–Kundu–Wootters theorem for non-local quantum correlations

Suppose three parties, A, B and C, each have a qubit. There is a well-known theorem of Coffman *et al.* (2000) that describes the trade-off between how entangled A is with B and how entangled A is with C. It states that , where is the concurrence between A and B; is the concurrence between A and C; and *ρ*_{A} is the reduced density matrix of A.

To derive a similar expression for correlations, we consider a generalization of the CHSH game to three players, suggested by Michael Nielsen (see also Scarani & Gisin 2001). In the new game, , the referee sends bits chosen uniformly at random to each of the three players, and with probability 1/2 checks if *a*_{1}⊕*a*_{2}=*q*_{1}∧*q*_{2} and with probability 1/2 checks if *a*_{1}⊕*a*_{3}=*q*_{1}∧*q*_{3}. Formally, *π* is uniform on and(4.1)Then, the winning probability of a particular strategy is(4.2)where the superscripts denote on which parties the CHSH operator acts. It is easy to see that (a strategy where everyone always answers 0 achieves this, and this strategy is the best possible, by the CHSH inequality applied to AB and BC separately). It turns out that too, as is easily verified using linear-programming software, which implies the following theorem.

*Suppose three parties*, *A*, *B* *and C*, *share any quantum state ρ* (*of arbitrary dimension*) *and each chooses to measure one of two observables*. *Then,*(4.3)

Theorem 4.1 establishes a trade-off between AB's and AC's violation of the CHSH inequality. In particular, CHSH correlations are monogamous: if AB violates the CHSH inequality, then AC cannot, as has already been shown for no-signalling correlations by Masanes *et al.* (2006). Note that if AB and AC each share an EPR pair, there are measurements such that either or is , which at first appears to contradict theorem 4.1. It does not: in theorem 4.1, we insist that A's observables are the *same* in and . This is in the same spirit as the requirement of Coffmann–Kundu–Wootters that B and C are entangled with the same qubit of A. In the following corollary we generalize this result.

*Suppose that N*+2 *parties A*, *B*_{0}, *B*_{1}, …, *B*_{N} *share a quantum state and each chooses to measure one of two observables*. *Then,* *A violates the CHSH inequality with at most one of the B*_{i}.

Suppose A violates the CHSH inequality with both B_{j} and B_{k}, then *j*≠*k*. Trace out the rest of the B_{i}'s. We obtain a contradiction with theorem 4.1.

For no-signalling probability distributions, we also have a converse of theorem 4.1: for any pair consistent with inequality (4.3), there is a no-signalling probability distribution with these expectation values. This is because we can write as a convex combination of (4, 0), (0, 4) and (0, 0), each of which is achieved by a no-signalling probability distribution. Thus, inequality (4.3) establishes precisely which values of are allowed. For quantum theory, Toner & Verstraete (2006) have subsequently shown that the allowed region is described by .

## 5. The odd-cycle game

Our second example illustrates how violation of a Bell inequality can preclude classical correlation with another party. We start with a two-player game based on an interactive proof for graph colourability. Imagine that the two players, A and B, are trying to convince the referee that an odd cycle of length *n* is two-colourable (which it is not, as *n* is odd). The referee sends them each the name of a vertex, such that the two vertices are either the same or adjacent. A and B each send one of two colours back to the referee. The referee requires that, when the vertices are the same, the two colours should agree and, when the vertices are adjacent, the colours should differ. Formally, we define a two-player game *G*_{OC} as follows: let *n*≥3 be an odd integer, let *π* be uniform over the set and let *V* be defined by , . It is established by Braunstein & Caves (1990) and Cleve *et al.* (2004) that and .

Now consider the first extension of this game, which we denote . Formally, is defined by using the same distribution as *G*_{OC} on (*q*_{1}, *q*_{2}), and setting *q*_{2}=*q*_{3}. The function *V* is defined by(5.1)(5.2)Theorem 2.1 implies that . We show that sharing entanglement (or indeed no-signalling correlations) gives no advantage for.

*For the first extension of the odd-cycle game,*(5.3)

This result is remarkable because it establishes that adding just one additional player is sufficient to prevent A and B from gaining advantage by sharing entanglement, rather than the *n*−1 additional players required in theorem 2.1. In the context of interactive proof systems, we can interpret the fact that in the two-player game as saying that sharing entanglement allows the provers to cheat, because it increases the probability with which they are able to convince the referee that the odd cycle is two-colourable. Theorem 5.1 shows that we can counter this by adding an extra prover, and forcing B to be classically correlated with this prover. This placed no extra burden on classical provers, because an optimal classical strategy is deterministic, but it prevents quantum provers from gaining any advantage by sharing entanglement.

Recently, Raz (in press) studied how the classical value of the odd-cycle game behaves under parallel repetition. A parallel repetition of an *m*-player game *G*(*V*, *π*) is, roughly speaking, a game where the *m*-players try to win *k*>1 instances of the game simultaneously. More formally, for each *j*=1, …, *k*, the referee samples questions (*q*_{1,j}, …, *q*_{m,j}) according to *π*. (Questions with different values of *j* are independent.) The referee then sends questions *q*_{i,1}, …, *q*_{i,k} to player *i*. Player *i* is expected to return *k* answers, labelled *a*_{i,1}, …, *a*_{i,k}. The players win if for all *j*=1, …, *k* it is true that . We write *G*^{k} for the *k*-fold parallel repetition of a game *G*. It is immediately clear that(5.4)because the players can just play each instance of the game independently, using an optimal strategy for each instance.

Specializing now to the odd-cycle game, for the quantum value, the inequality in equation (5.4) is actually tight: Cleve *et al.* (2007) have proved that(5.5)a result known as a *strong parallel repetition theorem*. What is surprising is that equation (5.4) is *not* tight for the classical value: Raz (in press) has shown that equation (5.4) can be improved to(5.6)whereas equation (5.4) gives only . (We note that equation (5.6) is itself almost tight, up to logarithmic factors; Feige *et al*. 2007.) This is a counterexample to strong parallel repetition in the classical case.

Theorem 5.1 gives rise to a similar counterexample for the quantum (and no-signalling) values of three-player games. Consider the first extension of the odd-cycle game, . Observe that(5.7)where the first two inequalities are obvious, the equality follows from theorem 2.1(i), and the second inequality is equation (5.6). Comparing this to , as established in theorem 5.1, we observe that is a counterexample to strong parallel repetition in the quantum case. The same remarks apply in the no-signalling case.

Throughout this proof, the addition of elements in is understood to be taken modulo *n*. There are a number of symmetries we can use to simplify the problem. Without changing the probability of winning:

all parties can flip the binary value of their outputs, and/or

all parties can add an integer to their inputs, and/or

B and C can exchange roles.

For a given no-signalling strategy, let be the probability that (A, B, C) answer (*a*, *b*, *c*) when asked (*i*, *j*, *k*). Then, we can take to be symmetric under these three symmetries. In particular, symmetry (i) implies we can restrict attention to *a*=0 and symmetry (ii) to *i*=0. Therefore, let . We shall use symmetry (iii) to give extra constraints, rather than to reduce the number of parameters.

We rewrite the primary linear programme in these variables, labelling the constraints to facilitate writing down the dual programme. Our goal is to maximize(5.8)subject to

(normalization)

*n*(*j*,*k*),(5.9)for 0≤*j*,*k*<*n*,(symmetry)

*s*(*b*,*c*|*j*,*k*),(5.10)for*b*,*c*∈{0,1}, 0≤*j*,*k*<*n*; note that, when*b*=*c*and*j*=*k*, this constraint is trivial,(no-signalling conditions, A to BC)

*y*(*d*|*j*,*k*),(5.11)for*d*∈{0,1}, 1≤*j*<*n*, 0≤*k*<*n*,(no-signalling conditions, B to AC)

*z*(*d*|*j*,*k*),(5.12)for*d*∈{0,1}, 1≤*j*<*n*, 0≤*k*<*n*.

We omit the no-signalling conditions in the other directions (BC to A and AC to B), which do not further constrain the solution.

Each constraint in the primary linear programme corresponds to a variable in the dual, as labelled above. The objective of the dual programme is to minimize(5.13)subject to the constraints *μ*(0, 0|0, 0), *μ*(1, 1|1, 1)≥*n*, *μ*(*b*, *c*|*j*, *k*)≥0, for all *b*, *c*∈{0,1}, 0≤*j*, *k*<*n*, where(5.14)

We now give an explicit solution to the dual. This solution was constructed by numerically solving the linear programme for small *n*, iteratively converting the inequality constraints into a consistent set of equality conditions by generalizing from the small *n* solutions, and then inverting these constraints to yield the solution. While we used numerical methods to obtain the solution, we emphasize that the final solution can be checked analytically, without any need for numerical computation. The non-zero variables are(5.15)

(5.16)

(5.17)

(5.18)

(5.19)

(5.20)

(5.21)

(5.22)

(5.23)

(5.24)

(5.25)

(5.26)

(5.27)

(5.28)

(5.29)

(5.30)

(5.31)

(5.32)

(5.33)

(5.34)

(5.35)

(5.36)

(5.37)

All other variables are zero.

For this solution, it is tedious but straightforward to establish the following: , , , for *j*=1, 2,…,*n*−1; for *k*=1, 2,…,*n*−1; and , otherwise. Thus, our solution satisfies the constraints. Substituting into equation (5.13), we find that , which proves theorem 5.1. ▪

## Acknowledgments

I thank Richard Cleve, John Preskill, Graeme Smith, Frank Verstraete and John Watrous for their useful suggestions, and Michael Nielsen for suggesting theorem 4.1. This work was supported in part by the NSF under grant no. PHY-456720, the ARO under grant no. W911NF-05-1-0294, the EU FP6-FET Integrated Project QAP CT-015848, NWO VICI project 639-023-302 and the Dutch BSIK/BRICKS project.

## Footnotes

- Received April 8, 2008.
- Accepted July 30, 2008.

- © 2008 The Royal Society