What are the vertices of the no-signalling set $\mathcal{NS}$?

Consider the standard 2-2 Bell scenario, with two parties each one choosing between two measurement settings, with each measurement setting leading to one of two possible measurement outcomes. Consider the space of possible corresponding behaviours, that is, conditional probability distributions $$(p(ab|xy))_{a,b,x,y\in\{0,1\}}$$.

As also discussed here, it is standard in this context to distinguish between different classes of behaviours. I'll mention in particular the set $$\mathcal L$$ of local behaviours, the set $$\mathcal Q$$ of quantum behaviours, and the set $$\mathcal{NS}$$ of no-signalling behaviours.

These are all clearly convex sets. In particular, $$\mathcal L$$ can be easily characterised via its vertices, which are bound to be the local deterministic behaviours of the form $$\boldsymbol{e}_{a_0 a_1 b_0 b_1}\in\mathbb R^{16}$$, which are ($$16$$) behaviours whose only 4 nonzero elements are $$(\boldsymbol{e}_{a_0 a_1 b_0 b_1})_{a_x b_y,xy}=1$$, for all $$x,y\in\{0,1\}$$. One way to further clarify what these vectors are is representing them as 4x4 matrices with columns representing measurement choices and rows measurement outcomes (sorted in the standard way as binary numbers). Explicitly, these are $$\tiny \boldsymbol{e}_{0000}=\begin{pmatrix}1&1&1&1\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{0011}=\begin{pmatrix}0&0&0&0\\1&1&1&1\\0&0&0&0\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{1100}=\begin{pmatrix}0&0&0&0\\0&0&0&0\\1&1&1&1\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{1111}=\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\1&1&1&1\end{pmatrix}, \\\tiny \boldsymbol{e}_{0001}=\begin{pmatrix}1&0&1&0\\0&1&0&1\\0&0&0&0\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{0010}=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&0&0&0\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{0100}=\begin{pmatrix}1&1&0&0\\0&0&0&0\\0&0&1&1\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{0101}=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}, \\\tiny \boldsymbol{e}_{0110}=\begin{pmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}, \quad \boldsymbol{e}_{0111}=\begin{pmatrix}0&0&0&0\\1&1&0&0\\0&0&0&0\\0&0&1&1\end{pmatrix}, \quad \boldsymbol{e}_{1000}=\begin{pmatrix}0&0&1&1\\0&0&0&0\\1&1&0&0\\0&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{1001}=\begin{pmatrix}0&0&1&0\\0&0&0&1\\1&0&0&0\\0&1&0&0\end{pmatrix}, \\\tiny \boldsymbol{e}_{1010}=\begin{pmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{pmatrix}, \quad \boldsymbol{e}_{1011}=\begin{pmatrix}0&0&0&0\\0&0&1&1\\0&0&0&0\\1&1&0&0\end{pmatrix}, \quad \boldsymbol{e}_{1101}=\begin{pmatrix}0&0&0&0\\0&0&0&0\\1&0&1&0\\0&1&0&1\end{pmatrix}, \quad \boldsymbol{e}_{1110}=\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&1&0&1\\1&0&1&0\end{pmatrix}.$$

For example, $$\boldsymbol{e}_{0000}$$ represents the situation where both outcomes are $$0$$ regardless of the measurement choices, whereas $$\boldsymbol{e}_{0001}$$ the one where Bob gets the outcome "1" whenever he uses the measurement setting "1", and any other outcome is "0". A recognisable feature is that these have a tensor product structure, representing the locality of the behaviours: $$(\boldsymbol{e}_{a_0 a_1 b_0 b_1})_{ab,xy} = (\boldsymbol{e}_{a_0 a_1})_{a,x}(\boldsymbol{e}_{b_0 b_1})_{b,y} = (\boldsymbol{e}_{a_0 a_1}\otimes \boldsymbol{e}_{b_0 b_1})_{ab,xy},$$ where $$\boldsymbol{e}_{a_0 a_1}\in\mathbb R^2$$ represents a possible behaviour representing a deterministic outcome assignment with $$a_0$$ observed whenever the measurement choice is $$0$$, and $$a_1$$ observed whenever the measurement choice is $$1$$. The set $$\mathcal L$$ can then be characterised as the convex hull of these 16 vectors.

Which brings me to my question: can a similarly simple characterisation be done for the no-signalling set, $$\mathcal{NS}$$? In other words, assuming $$\mathcal{NS}$$ can also be characterised as the convex hull of a finite number of vectors, what are these vertices?

• I think in the 2 input 2 output case they are given by the PR boxes but beyond that I don't know of a compact description. Nov 25, 2021 at 15:16
• @Rammus I'm not familiar with those. Is that a way to define non-quantum correlations? Anyway, I tried to just list all 256 possible 4x4 matrices representing valid behaviours, and selecting those satisfying the no-signaling condition, and it turns out those are exactly the 16 local ones listed in the post. So I might have been wrong in assuming $\mathcal{NS}$ can be given a simple description as convex hull of some finite number of points. Or at least, some vertices of $\mathcal{NS}$ are not vertices of the full space of behaviours (like those of ${\cal L}$ turn out to be)
– glS
Nov 25, 2021 at 17:26
• Sorry you are right, 16 of the NS vertices are the deterministic distributions. There are 8 more which correspond to variants of the PR box. For example, the original PR box is the NS distribution that achieves the algebraic maximum of the CHSH inequality. I.e., $p(a,b|x,y) = \frac12 \delta_{xy, a \oplus b}$. The rest of them come from the other 7 CHSH-like inequalities. Which can be derived via relabelings. Nov 25, 2021 at 18:44
• @Rammus I'm not familiar with PR boxes. Can you point to a good reference?
– glS
Nov 25, 2021 at 18:47
• I believe the "PR" comes from this paper: Quantum nonlocality as an axiom. This all falls under the umbrella of generalizing probabilistic theories -- I think the notes of Markus Muller are a good place to start mpmueller.net/vl.html Nov 25, 2021 at 19:03

Let me try to explain the (2,2,2) setting -- 2 parties, 2 inputs and 2 outputs. Firstly we consider a distribution as a vector $$p \in \mathbb{R}^{16}$$. The set of all conditional distributions (call this $$\mathcal{P}$$) may be characterized as follows: $$\mathcal{P} = \{p \in \mathbb{R}^{16}: p\geq 0, \sum_{ab} p_{ab|xy} = 1 \, \forall xy\}.$$ This is a bounded set characterized by an intersection of a finite number of half-spaces i.e., $$\mathcal{P} = \{p:p_{00|00}\geq 0\} \cap \dots \cap \{p : \sum_{ab} p_{ab|00} \geq 1\} \cap \{p : \sum_{ab} p_{ab|00} \leq 1\} \cap \dots$$ and hence is a convex polytope.

Well the no signalling set $$\mathcal{NS}$$ is just $$\mathcal{P}$$ intersected with a few more halfspaces, namely those corresponding to the no-signalling constraints. Hence, $$\mathcal{NS} = \mathcal{P} \cap \{p: \sum_{a}(p_{a0|00} - p_{a0|10}) \geq 0\} \cap \{p: \sum_{a}(p_{a0|00} - p_{a0|10}) \leq 0\} \cap \dots$$

We now know $$\mathcal{NS}$$ is a convex polytope and we have a nice description of the halfspaces defining the set. We can use an algorithm called vertex enumeration to convert from the halfspace representation to the extremal point representation.

The vertex representation

I'll use Tsirelson notation for conditional probability distributions, where we use a $$4\times 4$$ matrix with $$2 \times 2$$ blocks corresponding to different input pairs, namely $$\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}$$

The standard PR box, which achieves the maximal violation of the CHSH inequality is given by $$\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}\,$$ and the "minimum" violation by $$\begin{pmatrix} 0& 1/2 & 0 & 1/2 \\ 1/2 &0 & 1/2 &0 \\ 0 & 1/2 & 1/2& 0 \\ 1/2 & 0 & 0 & 1/2 \end{pmatrix}\,.$$

Note that the local set in the (2,2,2) setting has 8 nontrivial facets corresponding to the two standard CHSH inequalities and 3 permutations of them. You can generate these by the equivalent algorithm to vertex enumeration but for the halfspace representation. The permutations correspond to symmetries of local polytope. Namely we can relabel outputs and inputs and parties (this will preserve the local set and its extremal points). For instance consider the correlator $$\langle A_x B_y\rangle = p_{00|xy} + p_{11|xy} - p_{01|xy} - p_{10|xy}$$. If Alice relabels her inputs $$0\mapsto 1$$ and $$1 \mapsto 0$$ then this transforms this correlator to $$\langle A_x B_y \rangle \mapsto \langle A_{x\oplus 1} B_y \rangle$$. Writing the two "standard" CHSH inequalities as $$-2 \leq \langle A_0 B_0 \rangle + \langle A_0 B_1 \rangle + \langle A_1 B_0 \rangle - \langle A_1 B_1 \rangle \leq 2$$ applying this symmetry gives us two more inequalities $$-2 \leq \langle A_1 B_0 \rangle + \langle A_1 B_1 \rangle + \langle A_0 B_0 \rangle - \langle A_0 B_1 \rangle \leq 2$$ and the other four are found similarly to be $$-2 \leq \langle A_1 B_1 \rangle + \langle A_1 B_0 \rangle + \langle A_0 B_1 \rangle - \langle A_0 B_0 \rangle \leq 2 \\ -2 \leq \langle A_0 B_1 \rangle + \langle A_0 B_0 \rangle + \langle A_1 B_1 \rangle - \langle A_1 B_0 \rangle \leq 2.$$ The corresponding extremal points of the $$\mathrm{NS}$$ set can be generated by applying the symmetries to the 2 PR boxes above (generating the $$\mathrm{NS}$$ distributions that achieve the algebraic maxima of the various CHSH permutations). Altogether the 8 PR boxes are $$\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} \qquad \begin{pmatrix} 0& 1/2 & 0 & 1/2 \\ 1/2 &0 & 1/2 &0 \\ 0 & 1/2 & 1/2& 0 \\ 1/2 & 0 & 0 & 1/2 \end{pmatrix} \\ \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} \qquad \begin{pmatrix} 0& 1/2 & 1/2 & 0 \\ 1/2 &0 & 0 & 1/2 \\ 0 & 1/2 & 0& 1/2 \\ 1/2 & 0 & 1/2 & 0 \end{pmatrix} \\ \begin{pmatrix} 1/2 & 0 & 1/2 & 0 \\ 0 &1/2 &0 & 1/2 \\ 0& 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0& 1/2 \end{pmatrix} \qquad \begin{pmatrix} 0& 1/2 & 0 & 1/2 \\ 1/2 &0 & 1/2 &0 \\ 1/2 & 0& 0 & 1/2 \\ 0 & 1/2 & 1/2 & 0 \end{pmatrix} \\ \begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 &0 & 1/2 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/2 & 0& 1/2 \end{pmatrix} \qquad \begin{pmatrix} 1/2 & 0 & 0 & 1/2 \\ 0 & 1/2 & 1/2 &0 \\ 0 & 1/2& 0 & 1/2 \\ 1/2 & 0 & 1/2 & 0 \end{pmatrix}$$ Together with the deterministic distributions you found these form the vertices of $$\mathcal{NS}$$ in the (2,2,2) setting.

• This is a great answer to the question.
– R.W
Mar 24, 2022 at 9:32

In addition to Rammus's answer, see Barrett, Linden, Massar, Pironio, Popescu and Roberts (2004) for an analytical proof of why PR boxes are the vertices of the no-signalling polytope in the (2,2,2)-setting, as well as a generalisation to more than two outcomes per party.