# Does the CHSH inequality fully characterise the local polytope?

Consider the standard two-party CHSH scenario. Each party can perform one of two measurements (denoted with $$x,y\in\{0,1\}$$) and observe one of two outcomes (denoted with $$a,b\in\{0,1\}$$).

Let $$P(ab|xy)$$ be the probability of observing outcomes $$a,b$$ when choosing the measurements settings $$x,y$$. Local realistic theories are those that, for some probability distribution over some hidden variable $$\lambda$$, satisfy $$P(ab|xy)=\sum_\lambda q(\lambda)P_\lambda(a|x)P_\lambda(b|y).\tag1$$ Define the local polytope $$\mathcal L$$ as the set of theories that can be written as in (1). Note that we identify here a theory with its set of conditional probabilities: $$\boldsymbol P\equiv (P(ab|xy))_{ab,xy}$$.

Denote with $$E_{xy}$$ the expectation values $$E_{xy}=\sum_{ab}(-1)^{a+b}P(ab|xy)$$. We then know that all local realistic theories $$\boldsymbol P\in\mathcal L$$ satisfy the CHSH inequality: $$\Big|\sum_{xy}(-1)^{xy} E_{xy}\Big| = |E_{00}+ E_{01} + E_{10} - E_{11}| = \left|\sum_{abxy}(-1)^{a+b+xy}P(ab|xy)\right| \le 2.\tag2$$ Is the opposite true? In other words, do all theories satisfying (2) admit local realistic explanations?

Not quite. Consider the following no-signalling distribution $$PR_1$$ which I will write in the form

$$\begin{pmatrix} p(00|00) & p(01|00) & p(00|01) & p(01|01) \\ p(10|00) & p(11|00) & p(10|01) & p(11|01) \\ p(00|10) & p(01|10) & p(00|11) & p(01|11) \\ p(10|10) & p(11|10) & p(10|11) & p(11|11) \\ \end{pmatrix},$$ $$PR_1 = \begin{pmatrix} 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 1/2 & 1/2 & 0\\ \end{pmatrix}.$$ This distribution has $$E_{00} = E_{01} = E_{10} = - E_{11} = 1$$ and so achieves the algebraic maximum of $$4$$ of the CHSH expression as you write it in the question. Now consider another no-signalling distribution $$PR_2$$, derived from $$PR_1$$ by relabelling the inputs of Alice ($$x \mapsto x + 1 \mod 2$$), i.e. $$PR_2 = \begin{pmatrix} 1/2 & 0 & 0 & 1/2 \\ 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0 & 1/2 \\ \end{pmatrix}.$$ $$PR_2$$ is another no-signalling distribution that is not local $$PR_2 \notin \mathcal{L}$$ -- (sketch) the local set is closed under relabellings of inputs/outputs, $$PR_2$$ is a relabelling of $$PR_1$$ (and vice versa) and $$PR_1 \notin \mathcal{L}$$. Now $$PR_2$$ results in the expectation values $$E_{00} = 1, E_{01} = -1, E_{10} = 1, E_{11} = 1$$ and so $$E_{00} + E_{01} + E_{10} - E_{11} = 0$$. Therefore, we have found a distribution that cannot be explained by a local model but nevertheless satisfies the CHSH inequality.

We can however still get a converse statement by including relabelled versions of the CHSH inequality. Suppose a no-signalling distribution $$p$$ satisfies all of the following inequalities \begin{aligned} |E_{00} + E_{01} + E_{10} - E_{11}| &\leq 2 \\ |E_{10} + E_{11} + E_{00} - E_{01}| &\leq 2 \\ |E_{01} + E_{00} + E_{11} - E_{10}| &\leq 2 \\ |E_{11} + E_{10} + E_{01} - E_{00}| &\leq 2 \end{aligned} then $$p \in \mathcal{L}$$. In other words $$\mathcal{L}$$ has $$8$$ non-trivial facets.

• very nice! Is there an easy way to see why the last statement holds? Or do you have a reference for it? – glS May 24 '20 at 12:59
• As far as I am aware this is done computationally via a vertex enuneration algorithm. (Which converts between vertex and hyperplane descriptions of a polytope). I believe the first reference to state that there are 8 nontrivial facets if the 222 polytope is link.springer.com/article/10.1007/BF02903286. – Rammus May 24 '20 at 13:48
• the best reference is a 1981 paper written in English, Italian and Russian (or at least with intros translated in those languages??) published on an Italian journal? Wow, that's something.. – glS May 24 '20 at 15:38
• I find it weird that this can/is only shown numerically though. We can write explicitly the vectors making up the vertices of $\mathcal L$, so the inequalities, if tight, should be nothing but the convex closure of this finite number of vectors, thus in principle characterisable ab-initio. I guess working geometrically in such high-dimensional spaces is rather unwieldy though – glS May 24 '20 at 16:07
• You're right, by computationally I meant that there is an algorithm to compute all of the facets from the vertices. In principle one could do this by hand but it is probably quite tedious. Also for more complex nonlocality scenarios (more inputs/outputs/parties) the number of facets grows very quickly. – Rammus May 24 '20 at 18:07

Yes. As you've effectively said, all cases satisfying (2) are in a polytope and therefore convex. All the vertices of that polytope are deterministic strategies, and so every point inside the polytope can be described as a convex combination of these, and that gives you (at least) one such local realistic explanation.

• this means that the local polytope has exactly two nontrivial (nontrivial meaning excluding the faces of the form $P(ab|xy)\ge0$) facets, correct? One for $S=2$ and the other one for $S=-2$. I ask because this paper seems to state that the only facet is $S=2$ (see eq. 2) – glS Mar 23 '20 at 9:50
• I'd have said so. Certainly the statement from that paper doesn't seem entirely mathematically consistent. However, have you looked at ref 6 in that paper? It's been a while since I looked at it, but they thought a lot about uniqueness/equivalence of different facets, which may be relevant... Either that or it's a typo and he left out the modulus sign. – DaftWullie Mar 23 '20 at 10:11
• I was thinking back about this, and there is something that I'm not quite clear about. I can see why all local deterministic behaviours are vertices. But how do you see that all vertices of (2) are local deterministic behaviours? I mean (2) is satisfied by vectors which are not even physical probabilities. E.g. the vector with $P(00|00)=P(11|00)=1$ and zero everywhere else satisfies (2), but doesn't correspond to a physical scenario. What's there to prevent the existence of a nonclassical behaviour that satisfies (2), making (2) not tight, i.e. not the convex hull of local determin behaviours? – glS May 13 '20 at 10:58
• Sure, you can give non-physical scenarios that satisfy the bound. That's irrelevant. The issue is whether there is ever any point which satisfies the bound for which there is no local realistic theory. But you can explicitly enumerate the vertices of (2) and verify that there is a deterministic model for each of them. – DaftWullie May 13 '20 at 12:16
• but you have to list the vertices of the intersection of the region defined by (2) with the region containing vectors which are physical behaviours. How do you do that? – glS May 13 '20 at 12:40

I will here spell out more explicitly what the vertices of the local polytope look like.

## The local polytope is generated by local deterministic behaviours

The local polytope is, by definition, comprised of behaviours $$p(ab|xy)$$ such that $$p(ab|xy)=\sum_\lambda p_\lambda p_\lambda(a|x) p_\lambda(b|y).$$ Moreover, for each $$\lambda$$ and $$x$$, we can always decompose $$p_\lambda(a|x)$$ as a convex combination of local deterministic assignments. For example, if $$p_\lambda(0|x)=q_{\lambda,0x}$$ and $$p_\lambda(1|x)=1-q_{\lambda,0x}$$, then we can write $$p_\lambda(a|x) = q_{\lambda,0x} \delta_{a,0} + (1-q_{\lambda,0x})\delta_{a,1}.$$

As a vector, this reads \begin{align}\mathbf p_\lambda &= (q_{\lambda,00}\mathbf e_{0} + (1-q_{\lambda,00})\mathbf e_{1}) \oplus (q_{\lambda,01}\mathbf e_{0} + (1-q_{\lambda,01})\mathbf e_{1}) \\ &= (q_{\lambda,00},1-q_{\lambda,00},q_{\lambda,01},1-q_{\lambda,01}) \\ &= (p_\lambda(0|0), p_\lambda(1|0), p_\lambda(0|1), p_\lambda(1|1)), \end{align} for $$q_{\lambda,00},q_{\lambda,01}\in\{0,1\}$$. All such vectors are generated by the basis vectors $$\mathbf e_{ij}\equiv \mathbf e_i\oplus\mathbf e_j$$, representing behaviours in which $$x=0$$ corresponds to $$a=i$$ and $$x=1$$ to $$a=j$$. Explicitly, these are spanned by the four length-four vectors: $$(1,0,1,0),\quad (1,0,0,1),\quad (0,1,1,0), \quad (0,1,0,1).$$

(Behaviours in full space) Now, what about the actual behaviours corresponding to the full conditional probabilities $$p(ab|xy)$$? To accommodate any such distribution, these must be vectors with $$(2^2)^{2^2}=2^8=256$$ elements. The deterministic behaviours in such space are the vectors of the form $$\underbrace{\mathbf e_{ij}}_{x=0,y=0}\otimes \underbrace{\mathbf e_{k\ell}}_{x=0,y=1}\otimes \underbrace{\mathbf e_{mn}}_{x=1,y=0}\otimes\underbrace{\mathbf e_{pq}}_{x=1,y=1},$$ with each $$\mathbf e_{ij}$$ characterising the outputs $$ab$$ associated with a given pair of inputs $$xy$$. Clearly, however, such vectors do not always correspond to local behaviours. For example, the vector $$\mathbf e_{00}\otimes \mathbf e_{10}\otimes \mathbf e_{\bullet\bullet}\otimes \mathbf e_{\bullet\bullet}$$ is not local, as it gives $$(a,b)=(0,0)$$ for $$(x,y)=(0,0)$$ but $$(a,b)=(1,0)$$ for $$(x,y)=(0,1)$$.

(Local behaviours in full space) Local behaviours have the form $$\mathbf e_{a_0b_0}\otimes \mathbf e_{a_0b_1} \otimes \mathbf e_{a_1b_0} \otimes \mathbf e_{a_1b_1} \simeq \mathbf e_{a_0 a_1}\otimes\mathbf e_{b_0b_1},$$ for some choice of $$a_i,b_j\in\{0,1\}$$. There are therefore only $$(2^2)^2=16$$ such basic vectors, whose convex combinations draw the subset of local behaviours in the bigger $$256$$-dimensional space of general behaviours.

## Show that all local deterministic behaviours are vertices

Suppose $$\left|\sum_{abxy} (-1)^{a+b+xy} P(ab|xy)\right|= 2.$$ Explicitly, this amounts to the following two equations (I'll use $$P_{ab,xy}\equiv P(ab|xy)$$ for notational brevity): $$(P_{00,00} + P_{11,00} - P_{01,00} - P_{10,00}) + (P_{00,01} + P_{11,01} - P_{01,01} - P_{10,01}) + (P_{00,10} + P_{11,10} - P_{01,10} - P_{10,10}) - (P_{00,11} + P_{11,11} - P_{01,11} - P_{10,11}) = \pm2.$$ Taking into account the normalisation condition for each $$(x,y)$$, we can simplify this to $$(\underbrace{P_{00,00} + P_{11,00}}_{\equiv a_{00}}) + (\underbrace{P_{00,01} + P_{11,01}}_{\equiv a_{01}}) + (\underbrace{P_{00,10} + P_{11,10}}_{\equiv a_{10}}) - (\underbrace{P_{00,11} + P_{11,11}}_{\equiv a_{11}}) \in \{0,2\}. \tag X$$ Consider the possible deterministic assignments. Any such assignment corresponds to a choice of each of the above four terms on the LHS $$-$$ here denoted with $$a_{xy}$$ $$-$$ equaling one (if $$P_{00,xy}=1$$ or $$P_{11,xy}=1$$) or zero (if $$P_{01,xy}=1$$ or $$P_{10,xy}=1$$). In other words, $$a_{xy}\in\{0,1\}$$ for all $$x,y$$. The possible combinations are thus seen to be $$\begin{array}{c|c|c|c|c} a_{00} & a_{01} & a_{10} & a_{11} & S\\\hline 1 & 0 & 0 & 1 & 0\\\hline 0 & 1 & 0 & 1 & 0 \\\hline 0 & 0 & 1 & 1 & 0 \\\hline 1 & 1 & 1 & 1 & 2 \\\hline 0 & 0 & 0 & 0 & 0 \\\hline 1 & 1 & 0 & 0 & 2 \\\hline 1 & 0 & 1 & 0 & 2 \\\hline 0 & 1 & 1 & 0 & 2 \\\hline \end{array}$$ Each of these rows corresponds to $$2^4=16$$ deterministic behaviours. However, this does not take into account the locality constraint. To see this, focus for example on the first row. A compatible behaviour corresponding to this row is: $$\mathbf e_{00}\otimes\mathbf e_{01}\otimes\mathbf e_{10}\otimes\mathbf e_{00}.$$ This is nonlocal: the fourth assignment shouldn't be possible, as the first three established that $$a=x$$ and $$b=y$$, but here we get that $$(1,1)\to(0,0)$$.

More generally, a local deterministic behaviour must be factorisable: $$P(ab|xy)=p(a|x)q(b|y)\equiv p_{a|x}q_{b|y}=\delta_{a,a_x}\delta_{b,b_y},$$ for some deterministic probability distributions $$p$$ and $$q$$. There are $$(2^2)^2=16$$ such assignments, and the proper way to list them is via each possible assignment of four bits to the four variables $$(a_0, a_1, b_0, b_1)$$.

Let us rewrite (X) embedding the locality constraint in the expression. We get $$(p_{00} + p_{01}) q_{00} + (p_{00} - p_{01}) q_{01} + (p_{10} + p_{11}) q_{10} + (p_{10} - p_{11}) q_{11} \in \{0,2\}.$$ One can verify directly that each one of the possible $$16$$ assignments satisfies this equation, meaning that all possible deterministic local behaviours are vertices on the local polytope. Half of these are vertices for the polytope corresponding to $$S=2$$, and the remaining $$8$$ for the $$S=0$$ polytope.