# Algebra of Nonlocal Boxes and the Collapse of Communication Complexity

Pierre Botteron, Anne Broadbent, Reda Chhaibi, Ion Nechita, Clément Pellegrini

► To cite this version:

Pierre Botteron, Anne Broadbent, Reda Chhaibi, Ion Nechita, Clément Pellegrini. Algebra of Nonlocal Boxes and the Collapse of Communication Complexity. Quantum, 2024, 8, pp.1402. 10.22331/q-2024-07-10-1402. [https://arxiv.org/abs/2407.07140](https://arxiv.org/abs/2407.07140). [arXiv:2407.07140](https://arxiv.org/abs/2407.07140)

HAL Id: hal-04687878

https://hal.science/hal-04687878v1

Submitted on 5 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Algebra of Nonlocal Boxes and the Collapse of Communication Complexity

Pierre Botteron Ⓟ¹, Anne Broadbent Ⓟ²,³, Reda Chhaibi Ⓟ¹,⁴, Ion Nechita Ⓟ⁵, and Clément Pellegrini¹

¹Institut de Mathématiques de Toulouse, Université de Toulouse, France.

²Nexus for Quantum Technologies, University of Ottawa, Canada.

³Department of Mathematics and Statistics, University of Ottawa, Canada.

⁴Institut Universitaire de France (IUF), France.

⁵Laboratoire de Physique Théorique, Université de Toulouse, CNRS, France.

Communication complexity quantifies how difficult it is for two distant computers to evaluate a function $f(X, Y)$, where the strings $X$ and $Y$ are distributed to the first and second computer respectively, under the constraint of exchanging as few bits as possible. Surprisingly, some nonlocal boxes, which are resources shared by the two computers, are so powerful that they allow to collapse communication complexity, in the sense that any Boolean function $f$ can be correctly estimated with the exchange of only one bit of communication. The Popescu-Rohrlich (PR) box is an example of such a collapsing resource, but a comprehensive description of the set of collapsing nonlocal boxes remains elusive.

In this work, we carry out an algebraic study of the structure of wirings connecting nonlocal boxes, thus defining the notion of the “product of boxes” $P \otimes Q$, and we show related associativity and commutativity results. This gives rise to the notion of the “orbit of a box”, unveiling surprising geometrical properties about the alignment and parallelism of distilled boxes. The power of this new framework is that it allows us to prove previously-reported numerical observations concerning the best way to wire consecutive boxes, and to numerically and analytically recover recently-identified noisy PR boxes that collapse communication complexity for different types of noise models.

Nonlocal boxes (NLBs) were introduced by Popescu and Rohrlich in 1994 as a theoretical generalization of quantum correlations [41]. When Alice and Bob share a pair of entangled states $|\Psi\rangle$, each of them can choose to measure their state in a certain basis depending on some “instructions” $x, y \in \{0, \dots, p\}$, and then each of them can encode their outcomes in respectively $a, b \in \{0, \dots, q\}$. Similarly, a two-party NLB is a “black box” shared between Alice and Bob, with some inputs $x, y$ and some outputs $a, b$, and with the rule that Alice has access only to the left part and Bob only to the right part, see Figure 1. This way, we only study the statistics produced by the “hidden state” inside of the box and not the physical theory describing that state, which is the reason why nonlocal boxes are said to be *device-independent*. In this work, we consider one of the simplest scenarios, the CHSH scenario named after Clauser, Horne, Shimony, and Holt [16], where $p = q = 1$ and with two parties Alice and Bob (for more general scenarios, see [4, 5, 14, 20, 44]).

Generally, nonlocal boxes are non-signalling, meaning that they respect the relativistic constraint of no faster-than-light communication between parties (although there is a recent interest for partially-signalling scenarios [44]). These *non-signalling boxes* form a set $\mathcal{N}\mathcal{S}$ defined by the

Pierre Botteron Ⓟ: pierre.botteron@math.univ-toulouse.fr

Anne Broadbent Ⓟ: abroadbe@uottawa.ca

Reda Chhaibi Ⓟ: reda.chhaibi@math.univ-toulouse.fr

Ion Nechita Ⓟ: ion.nechita@univ-tlse3.fr

Clément Pellegrini: clement.pellegrini@math.univ-toulouse.fr
<figure><img src="image_2.png" /><figcaption>Figure 1: Representation of a nonlocal box.</figcaption></figure>

following non-negativity and normalization equations, which ensure $\mathbf{P}$ is a well-defined conditional probability distribution:

$$ \forall a, b, x, y \in \{0, 1\}, \quad \mathbf{P}(a, b | x, y) \ge 0 \quad \text{and} \quad \sum_{a,b} \mathbf{P}(a, b | x, y) = 1, \qquad (1) $$

together with the conditions that the marginals of each party are independent of the other party's question:

$$ \forall a, x \in \{0, 1\}, \quad \sum_{b \in \{0, 1\}} \mathbf{P}(a, b | x, 0) = \sum_{b \in \{0, 1\}} \mathbf{P}(a, b | x, 1) =: \mathbf{P}(a | x), \qquad (2) $$

$$ \forall b, y \in \{0, 1\}, \quad \sum_{a \in \{0, 1\}} \mathbf{P}(a, b | 0, y) = \sum_{a \in \{0, 1\}} \mathbf{P}(a, b | 1, y) =: \mathbf{P}(b | y). \qquad (3) $$

The physical interpretation of Equations (2) and (3) is that Alice and Bob are space-like separated, so it would take more time for a light ray to move from Bob to Alice than the time needed for Alice to do her protocol and to receive her output of the box, and therefore Alice's marginal does not depend on Bob's input.

The best-known example of a non-signalling box is the PR box, named after Popescu and Rohrlich [41]. This box is designed to perfectly win at the CHSH-game [16], i.e. the box produces outputs $a, b$ such that $a \oplus b = xy$ with probability 1, where the symbol “$\oplus$” stands for the sum modulo 2.<fnref n="1" /> More precisely, given an input pair $(x, y)$, there are two possibilities for the outputs: either $(a = 0, b = xy)$ or $(a = 1, b = xy \oplus 1)$, each being output with probability 1/2 by the PR box. In fact, it is possible to show that the PR box thus defined is the only box of $\mathcal{N}\mathcal{S}$ that perfectly wins at the CHSH-game. Let us give two other examples of boxes: (i) the fully mixed box $\mathbf{I}$, which outputs purely random bits $a$ and $b$; and (ii) the deterministic boxes $\mathbf{P}_0, \mathbf{P}_1$ that always output $(0, 0), (1, 1)$ independently of the inputs. All these boxes are in $\mathcal{N}\mathcal{S}$ and can be written as conditional probability distributions:

$$ \begin{aligned} \mathbf{PR}(a, b | x, y) &:= \frac{1}{2} \mathbb{1}_{a \oplus b = xy}, & \mathbf{I}(a, b | x, y) &:= \frac{1}{4}, \\ \mathbf{P}_0(a, b | x, y) &:= \mathbb{1}_{a=b=0}, & \mathbf{P}_1(a, b | x, y) &:= \mathbb{1}_{a=b=1}, \end{aligned} \qquad (4) $$

where the symbol “$\mathbb{1}$” stands for the indicator function. Two other important classes of correlations are the local set $\mathcal{L}$ and the quantum (tensor) set $\mathcal{Q}$, with strict inclusions $\mathcal{L} \subsetneq \mathcal{Q} \subsetneq \mathcal{N}\mathcal{S}$, defined as:

$$ \begin{aligned} \mathcal{L} &= \left\{ \mathbf{P}(a, b | x, y) = \int_{\lambda} \mathbb{P}_{A}(a | x, \lambda) \mathbb{P}_{B}(b | y, \lambda) \mu(\lambda) : \mathbb{P}_{A}, \mathbb{P}_{B}, \mu \text{ are probability distributions} \right\}, \\ \mathcal{Q} &= \left\{ \mathbf{P}(a, b | x, y) = \langle \Psi | (E_a^x \otimes F_b^y) | \Psi \rangle : \begin{array}{l} \{E_a^x\}_a, \{F_b^y\}_b \text{ are POVMs over Hilbert spaces } \mathcal{H}_A, \mathcal{H}_B, \\ |\Psi\rangle \text{ is a vector of } \mathcal{H}_A \otimes \mathcal{H}_B \text{ of norm 1} \end{array} \right\}. \end{aligned} $$

For more details on correlation sets and their separation, see [29].

Interestingly, some nonlocal boxes collapse what is called communication complexity (CC), a notion introduced by Yao in [48] and reviewed in [30, 43] that quantifies the difficulty of performing

<footnote n="1">¹From a computing perspective, the PR box turns a distributed AND ($xy$) into a distributed XOR ($a \oplus b$), where “distributed” means that the computation requires both parties (Alice knows $x$ and $a$, and Bob knows $y$ and $b$).</footnote>
a distributed computation. Say we want to evaluate a Boolean function $f : \{0,1\}^n \times \{0,1\}^m \to \{0,1\}$ using two distant computers, where the first computer receives as input $X \in \{0,1\}^n$, and the other computer receives as input $Y \in \{0,1\}^m$. The CC of $f$ is then defined as the minimal number of bits that the computers need to communicate in order for the first computer to output the value $f(X,Y)$. For instance, when $n=m=2$, $X = (x_1, x_2)$, $Y = (y_1, y_2)$, the CC of $f_1 := x_1 \cdot (y_1 \oplus y_2)$ equals 1, using the communication bit $y_1 \oplus y_2$, whereas it is possible to show that the CC of $f_2 := x_1 \cdot y_1 \oplus x_2 \cdot y_2$ equals 2, using communication bits $y_1$ and $y_2$; therefore $f_2$ is more complex than $f_1$ in the sense of CC. Yao also introduced in [48] a probabilistic version of CC, in which the computers can access shared randomness, and where for all $X,Y$ the first computer has to output the correct value $f(X,Y)$ with probability at least $p > 1/2$ ($p$ being independent of $X$ and $Y$). Now, if a nonlocal box $\mathcal{P}$ is used in the protocol to compute the value $f(X,Y)$, we say that the box $\mathcal{P}$ *collapses* communication complexity if there exists a fixed $p > 1/2$ for which any Boolean function $f$, with arbitrary input size, can be correctly computed with only one bit of communication and probability $p$. In this definition, an arbitrary number of copies of the box $\mathcal{P}$ can be used in the protocol. Such a collapse is strongly believed to be unachievable in Nature since it would imply the absurdity that a single bit of communication is sufficient to distantly estimate any value of any Boolean function $f$ [6, 10, 13, 18]. For more details on the link between nonlocal boxes and communication complexity, see [7].

**Open question.** Among the four examples of boxes listed in Equation (4), only the PR box collapses communication complexity [18], meaning that this box is very “powerful”. We also know that some noisy versions of the PR box collapse CC for different types of noise [8, 10, 11, 13, 23]. On the other hand, we know that quantum correlations do *not* collapse communication complexity [17], and neither does a slightly wider set named “almost quantum correlations” [36]. To this day, the question is still open whether the remaining non-signalling boxes are collapsing, meaning that there is still a gap to be filled. We refer to [8, Fig. 2] for a figure that summarizes the situation.

**Recent results.** Two recent papers make progress on the question above. In [11] Brito, Moreno, Rai, and Chaves study correlation distillation in *quantum voids* [42], which are subsets of a face of $\mathcal{NS}$ where all nonlocal points are non-quantum. They prove strong distillation properties in 1- and 2- dimensional quantum voids and deduce that these regions collapse communication complexity, which partially answers the open question. More recently, in [23], Eftaxias, Weilenmann, and Colbeck propose a *sequential algorithm* to find a suitable sequence of wirings to collapse communication complexity, where a *wiring* is defined as a connection between boxes that allows the creation of a new box out of copies of a box (see Section 1). This allows us to numerically determine a collapsing region of nonlocal boxes, which is again a partial answer to the open question.

**Our Results.** We provide a new mathematical framework and algorithms in working towards addressing the open question. The ideas are based in part on the M.Sc. thesis of one of the authors [7].

(i) We introduce a new framework that we call the *algebra of boxes*. After recalling the definition of a wiring $\mathcal{W}$, we use it to introduce a *product of boxes* $\mathcal{P} \boxtimes_W \mathcal{Q}$. This leads to a natural embedding of the non-signalling set $\mathcal{NS}$ in an algebra, which we call an *algebra of boxes* and for which we characterize associativity and commutativity (see Proposition 7). This gives an algebraic perspective on protocols for correlation distillation—for instance, the non-associativity of the algebra of boxes tells us that the order in which the boxes are wired matters.

(ii) This framework gives rise to the fascinating notion of what we call the *orbit of a box*. The orbit of $\mathcal{P} \in \mathcal{NS}$ is roughly the set of all possible boxes that can be produced by wiring arbitrarily many copies of $\mathcal{P}$. This allows interesting visualizations of the hidden structure of boxes (see Figure 7), and surprisingly we observe that these orbits satisfy strong alignment and parallelism properties as shown in Theorem 10 and Corollary 11. Moreover, we derive the expression of the highest CHSH-valued box of the (tilted) orbit in Theorem 13, which explains the numerical observation reported in [23, Supplementary Material, II], and for which we derive an insightful linear-time algorithm that is exponentially more efficient compared to the
naive exponential-time computation of the entire orbit. In addition, we recover in Theorem 16 a similar result as in [23] stating that those methods lead to finding collapsing boxes via the recursive application of the multiplication $\boxtimes P$ on the right.

(iii) We provide algorithms in our GitHub page [9] for the following task: given a box $P$ that we want to show is collapsing, find an appropriate wiring $W$ such that the orbit contains a collapsing box. The idea is to repeat several times in parallel a variant of the Gradient Descent Algorithm in order to find the most appropriate wiring $W$. These algorithms allow us to recover in Figure 10 similar new collapsing areas as in [23, Figure 3].

(iv) In Theorems 23 and 29, we show that our framework also allows us to recover some analytical results with a new proof based on the algebra of boxes: some triangles in the boundary of $\mathcal{N}S$ are collapsing [11]. To that end, algorithms of (iii) above were performed in order to identify a convenient wiring. Moreover, in Corollary 27, we recover a result from [42] with a new proof, based on communication complexity, showing that the triangle joining $\mathbf{PR}, \mathbf{P}_0, \mathbf{P}_1$ is a "quantum void".

**Further Comparison with Recent Results.** A contribution of our work is in providing a new algebraic framework for a unified perspective on three recent results [11, 23, 42]. Compared to [23], our work concurrently and independently<fnref n="2" /> derives the existence of new collapsing boxes using right multiplication (Theorem 16) and we report a similar numerical result (Figure 10). However, as detailed in Remark 19, we note that the methods complement each other: as the authors of [23], we implement an algorithm finding a non-constant sequence of wirings, but we also implement an algorithm finding a constant sequence of wirings for analytical purposes. Moreover, as mentioned above, our Theorem 13 analytically proves a numerical observation reported in [23, Supplementary Material, II]. As for [11], we recover some of their results in Theorems 23 and 29, and although our proof reproduces previously-known analytical collapsing areas, we view our contribution as a new approach based on the algebra of boxes. Regarding [42], we recover one of their result in Corollary 27 with a new proof, based on communication complexity, showing that the triangle joining $\mathbf{PR}, \mathbf{P}_0, \mathbf{P}_1$ is a "quantum void". In summary, our new algebraic viewpoint unifies the results of [23] (see Subsection 4.1), [11] (see Subsection 4.2), and [42] (see Subsection 4.2).

**Structure.** This work is divided into four sections, a conclusion, and some appendices:

* Section 1: given a wiring $W$, we introduce the product of nonlocal boxes $P \boxtimes_W Q$ and we study the new framework of algebra of boxes.

* Section 2: we define the notion of the orbit of a box $P$, which consists of all boxes produced using copies of $P$ and the product $\boxtimes$ previously defined, and we investigate its surprising geometric structure.

* Section 3: we present algorithms for the following task: given a box $P$ that we want to show is collapsing, find an appropriate wiring $W$ such that the orbit contains a collapsing box. These algorithms are based on Gradient Descents methods and are entirely accessible via our GitHub page [9].

* Section 4: we find collapsing boxes in two different ways: (i) numerically, using the algorithms of the previous section, and (ii) analytically, using the algebra of boxes and the orbit of a box.

* **Conclusion:** we conclude with some discussion, open problems, and avenues for future work.

* **Appendices:** we complete this work with supplementary figures and proofs.

# 1 Algebra of Boxes

The set of non-signalling boxes $\mathcal{N}S$ is the compact convex subset of the vector space $\mathcal{B} = \{P : \{0,1\}^4 \to \mathbb{R}\}$ satisfying Equations (1), (2), (3). In this section, we propose to endow the vector

<footnote n="2">²Our results were first reported in the M.Sc. thesis of one of the authors [7], which appeared in the same month (June 2022) as the arXiv version of [23].</footnote>
space $\mathcal{B}$ with a multiplication $\otimes_W$, so that $\mathcal{B}$ becomes an algebra that we call *algebra of boxes* and
that we denote $\mathcal{B}_W$. To that end, we recall the notion of *wiring W* (deterministic then mixed),
which, for the sake of simplicity, we define for only *two* boxes being connected — see Remark 6 for
more generality. Then we provide some typical examples of wirings from the literature, and we
finally introduce the algebra of boxes and characterize its associativity and commutativity.

1.1 Intuition Behind Wirings

Given two non-signalling boxes P and Q, it is possible to build a new box by *wiring* them together.
This notion of wiring has found a great interest in the last two decades, especially with the following
two goals: (i) attempting nonlocality distillation, *i.e.* we want to build a box that is “strongly
nonlocal” starting from some boxes that are “weakly nonlocal” [6, 11, 13, 19, 21, 23, 24, 25, 27,
35]; (ii) finding sets that are closed under wirings, because it is argued that a consistent physical
theory should, in principle, be closed under natural simple operations as wirings [1, 6, 31, 36, 37].

As one might guess, a wiring simply connects some outputs to some inputs under some rules,
and it applies some pre- and post- processing operations to the carried bits. An example of wiring
is presented in Figure 2 (a), where the wiring indeed connects some outputs to some inputs, but
is counter-intuitive at first, since Alice and Bob do not use their share of the boxes in the same
order: while Alice uses P then Q, Bob uses Q then P. This independence on the choice of the
box order for each player generalizes quantum mechanics, in the sense that if Alice and Bob were
sharing two entangled pairs instead of two nonlocal boxes, Alice would be able to measure her first
particle and then the second one, while Bob would be able to do the converse, and they would
still receive the outputs “instantaneously”. Now, as in the quantum case, Alice receives an answer
from the box P instantaneously even if Bob has not yet inputted a bit in his side of P, and she
can use the output $a_1$ as a parametrization for the input $x_2$ of the box Q; similarly for Bob. This
“instantaneous-answer” property of a box is typical of non-signalling correlations, as modelled by
Equations (2) and (3) saying that Alice’s marginal is independent of Bob’s input, and vice-versa.
Note that a wiring cannot link Alice’s side to Bob’s side, nor the opposite, since otherwise it could
create a signalling box: there would be communication between parties.

<figure><img src="image_3.png" /><figcaption>Figure 2: (a) Example of wiring between two boxes P and Q. (b) General wiring between two boxes P and Q.</figcaption></figure>

1.2 Deterministic Wirings

Two boxes P and Q can be wired as in Figure 2 (b), using functions $f_i$ and $g_j$ depending on the
global entries $x$ and $y$ and on the outputs $a_k$ and $b_\ell$ of the boxes. Nevertheless, to be a valid wiring,
the inputs on Alice's side must be in a valid order: the input $x_2$ of Q can depend on the output $a_1$
of P only if the input $x_1$ of P does not depend on the output $a_2$ of Q; the same should also hold on
Bob's side. In other words, the functions $f_1(x, a_2)$ and $f_2(x, a_1)$ cannot both depend on $a_2$ and $a_1$ respectively for the same value of $x$, and similarly for $g_1(y, b_2)$ and $g_2(y, b_1)$. These conditions are formalized in (5) and (6) of the following definition:

**Definition 1 (Deterministic wiring).** A deterministic wiring W between two boxes P, Q ∈ $\mathcal{NS}$ consists in six Boolean functions $f_1, f_2, g_1, g_2 : \{0,1\}^2 \to \{0,1\}$ and $f_3, g_3 : \{0,1\}^3 \to \{0,1\}$ satisfying the non-cyclicity conditions:

$$ \forall x, \quad (f_1(x, 0) - f_1(x, 1))(f_2(x, 0) - f_2(x, 1)) = 0, \qquad (5) $$

$$ \forall y, \quad (g_1(y, 0) - g_1(y, 1))(g_2(y, 0) - g_2(y, 1)) = 0. \qquad (6) $$

Given a wiring W and two boxes P, Q ∈ $\mathcal{NS}$, we obtain a new box that we denote $P \boxtimes_W Q$. Formally, this new box is defined as the following conditional probability distribution:

$$ P \boxtimes_W Q(a, b | x, y) := \sum_{a_1, a_2, b_1, b_2} P(a_1, b_1 | f_1(x, a_2), g_1(y, b_2)) \times Q(a_2, b_2 | f_2(x, a_1), g_2(y, b_1)) \times 1_{a=f_3(x, a_1, a_2)} \times 1_{b=g_3(y, b_1, b_2)}, \quad (7) $$

where the symbol $1$ stands for the indicator function, taking value 1 if the indexed condition is satisfied, and 0 otherwise. It is important to specify the condition P, Q ∈ $\mathcal{NS}$, since in that case $P \boxtimes_W Q$ is indeed a conditional probability distribution as shown in the proof of Fact 3; otherwise, if one requires only the condition on P, Q to be conditional probability distributions (not necessarily lying in $\mathcal{NS}$), then it might happen that the product $P \boxtimes_W Q$ is not a well-defined probability distribution: consider for example $P = Q = 1_{a=y}1_{b=x}$ and the deterministic wiring $W = (f_1 = x, f_2 = a_1, g_1 = b_2, g_2 = y, f_3 = 0, g_3 = 0)$.

**Definition 2 (Closed under wirings).** A set $X \subseteq \mathcal{NS}$ is said to be closed under wirings if for all boxes P, Q in X and all wirings W, the new box $P \boxtimes_W Q$ is in X as well.<fnref n="3" />

For the sake of completeness, we recall the fact that the non-signalling polytope $\mathcal{NS}$ is an example of a set that is closed under wirings.

**Fact 3.** [1] $\mathcal{NS}$ is closed under deterministic wirings.

*Proof.* We need to show that the box $P \boxtimes_W Q$ given in (7) is a well-defined conditional probability distribution that satisfies the non-signalling conditions (2) and (3). First, by non-negativity of P and Q, the new box $P \boxtimes_W Q$ is non-negative as well. Now, fix $x, y \in \{0,1\}$. The non-cyclicity conditions (5) and (6) tell us that $f_1$ or $f_2$ is constant in the second variable, and similarly for $g_1$ and $g_2$. Without loss of generality, up to changing the roles of both $f_1, g_1$ with respectively $f_2, g_2$, we only need to consider the following two non-exclusive cases:

* Case 1: the functions $f_1(x, a_2)$ and $g_1(y, b_2)$ are constant in the second variable, and we denote them $f_1(x)$ and $g_1(y)$;

* Case 2: the functions $f_2(x, a_1)$ and $g_1(y, b_2)$ are constant in the second variable, and we denote them $f_2(x)$ and $g_1(y)$.

In Case 1, we see that coefficients sum to one by normalization of P and Q:

$$ \sum_{a,b} P \boxtimes_W Q(a, b | x, y) = \sum_{a_1,b_1} P(a_1, b_1 | f_1(x), g_1(y)) \times \underbrace{\left( \sum_{a_2,b_2} Q(a_2, b_2 | f_2(x, a_1), g_2(y, b_1)) \right)}_{=1} = 1. $$

<footnote n="3">³Notice that there exists as well a more general definition involving $k$ boxes and $m$ parties, but our manuscript is restricted to the simpler case of $k = m = 2$, which is the reason why we give a simpler definition here. In the general framework, many sets are known to be closed under wirings [1, 6, 31, 36, 37].</footnote>
In Case 2, using the non-signalling conditions on P and Q, we see that coefficients sum to one again:

$$ 
\begin{aligned}
\sum_{a,b} \mathbf{P} \boxtimes_W \mathbf{Q}(a,b|x,y) &= \sum_{a_2,b_1} \underbrace{\left( \sum_{a_1} \mathbf{P}(a_1, b_1|f_1(x,a_2), g_1(y)) \right)}_{= \mathbf{P}(b_1|g_1(y))} \underbrace{\left( \sum_{b_2} \mathbf{Q}(a_2, b_2|f_2(x), g_2(y,b_1)) \right)}_{= \mathbf{Q}(a_2|f_2(x))} \\
&= \left( \sum_{b_1} \mathbf{P}(b_1|g_1(y)) \right) \left( \sum_{a_2} \mathbf{Q}(a_2|f_2(x)) \right) = 1.
\end{aligned}
$$

Hence $\mathbf{P} \boxtimes_W \mathbf{Q}$ is a conditional probability distribution. It only remains to check that $\mathbf{P} \boxtimes_W \mathbf{Q}$ satisfies the non-signalling conditions (2) and (3). Fix $x, a \in \{0, 1\}$. In Case 1, we have for all $y \in \{0, 1\}$:

$$ \sum_b \mathbf{P} \boxtimes_W \mathbf{Q}(a,b|x,y) = \sum_{a_1,a_2} \mathbf{P}(a_1|f_1(x)) \mathbf{Q}(a_2|f_2(x,a_1)) \mathbf{1}_{a=f_3(x,a_1,a_2)} =: \mathbf{P} \boxtimes_W \mathbf{Q}(a|x), $$

i.e. the result does not depend on $y$, which means that the marginal in $b$ is well-defined. This is similar in Case 2, changing $f_1(x)$ into $f_1(x, a_2)$ and $f_2(x, a_1)$ into $f_2(x)$. Hence the first non-signalling condition (2) is satisfied, and the other one (3) follows in a similar way. $\square$

## 1.3 Mixed Wirings

Using local randomness, one can generalize the class of deterministic wirings to the one of mixed wirings. The difference is that the functions $f_i$ and $g_j$ take values in $[0, 1]$ instead of $\{0, 1\}$. For instance, if $f_1(x, a_1) = p \in [0, 1]$ for some fixed bits $x$ and $a_1$, it means that Alice uses a Bernoulli distribution $\mathcal{B}(p)$ to input the bit 1 with probability $p$, or the bit 0 with probability $1-p$. In other words, we have 32 Bernoulli variables ($B_1, \dots, B_{32}$), whose parameters are stored in $W = (f_1(0, 0), f_1(0, 1), \dots, g_3(1, 1, 1)) \in \mathbb{R}^{32}$, and the box product $\mathbf{P} \boxtimes \mathbf{Q}$ becomes the expected value of the deterministic wirings:

$$ \mathbf{P} \boxtimes_W \mathbf{Q} = \mathbb{E} \left[ \mathbf{P} \boxtimes_{\{B_i\}} \mathbf{Q} \right]. \qquad (8) $$

Note that this generalization of wirings does not change the definition of nonlocal boxes: the inputs and outputs of a box are still classical bits, not any real number between 0 and 1. In order to ensure a well-defined local order for both Alice and Bob, we will need to add a dependence relation between the variables $B_i$, namely the non-cyclicity condition, as for the deterministic wirings:

**Definition 4 (Mixed wiring).** A mixed wiring $W$ between two boxes $\mathbf{P}, \mathbf{Q} \in \mathcal{NS}$ consists in six functions $f_1, f_2, g_1, g_2 : \{0, 1\}^2 \to [0, 1]$ and $f_3, g_3 : \{0, 1\}^3 \to [0, 1]$ satisfying the non-cyclicity conditions (5) and (6). Mixed wirings form a set that we denote $W$.

The set of mixed wirings $W$ is not convex because non-cyclicity conditions (5) and (6) are non-affine equalities. For instance, consider the wirings $W, W'$ with all coefficients 0 except the one corresponding to respectively $f_1(0, 0) = 1$, $f_2'(0, 0) = 1$; each of these wirings satisfies the non-cyclicity conditions (5) and (6), but the mean $W'' = (W + W')/2$ does not:

$$ (f_1''(0,0) - f_1''(0,1))(f_2''(0,0) - f_2''(0,1)) = (1/2 - 0)(1/2 - 0) \neq 0, $$

hence the non-convexity of $W$. The expression of $\mathbf{P} \boxtimes_W \mathbf{Q}$ is the same as before, with the convention that $\mathbf{P}(a, b|\alpha, \beta)$ with $\alpha, \beta \in [0, 1]$ means $(1 - \alpha)(1 - \beta)\mathbf{P}(ab|00) + (1 - \alpha)\beta\mathbf{P}(ab|01) + \alpha(1 - \beta)\mathbf{P}(ab|10) + \alpha\beta\mathbf{P}(ab|11)$, which gives:
$$ \begin{aligned} & \mathbf{P} \boxtimes_W \mathcal{Q}(a, b | x, y) \\ &= \sum_{a_1, a_2, b_1, b_2 \in \{0,1\}} \left[ \begin{aligned} & \mathbf{P}(a_1, b_1 | 0, 0)(1 - f_1(x, a_2))(1 - g_1(y, b_2)) + \mathbf{P}(a_1, b_1 | 0, 1)(1 - f_1(x, a_2))g_1(y, b_2) \\ & + \mathbf{P}(a_1, b_1 | 1, 0)f_1(x, a_2)(1 - g_1(y, b_2)) + \mathbf{P}(a_1, b_1 | 1, 1)f_1(x, a_2)g_1(y, b_2) \end{aligned} \right] \\ & \times \left[ \begin{aligned} & \mathcal{Q}(a_2, b_2 | 0, 0)(1 - f_2(x, a_1))(1 - g_2(y, b_1)) + \mathcal{Q}(a_2, b_2 | 0, 1)(1 - f_2(x, a_1))g_2(y, b_1) \\ & + \mathcal{Q}(a_2, b_2 | 1, 0)f_2(x, a_1)(1 - g_2(y, b_1)) + \mathcal{Q}(a_2, b_2 | 1, 1)f_2(x, a_1)g_2(y, b_1) \end{aligned} \right] \\ & \times \left[ (1 - f_3(x, a_1, a_2)) \mathbb{1}_{a=0} + f_3(x, a_1, a_2) \mathbb{1}_{a=1} \right] \times \left[ (1 - g_3(y, b_1, b_2)) \mathbb{1}_{b=0} + g_3(y, b_1, b_2) \mathbb{1}_{b=1} \right]. \end{aligned} \quad (9) $$

Using the probabilistic point of view of Equation (8), we see that a mixed wiring is a convex combination of deterministic wirings (the realization of Bernoulli variables being either 0 or 1). Hence, by linearity of the expectation $\mathbb{E}$, we deduce from Fact 3 that the set $\mathcal{NS}$ is closed under mixed wirings:

**Fact 5.** $\mathcal{NS}$ is closed under mixed wirings. $\square$

<figure><img src="image_4.png" /></figure>

*Remark 6.* Note that the formalism presented here is deliberately not the most general one, since this simpler version is enough to state our results in the next sections. For a more general framework, see [6]. For instance, here we require a deterministic local box order: knowing $x$, Alice perfectly knows which box she will use first, and similarly for Bob knowing $y$, but a more general mixed wiring would consist in setting a probability distribution on the different permutations of Alice's boxes and another one on Bob's boxes. In addition, here we only defined wirings of depth 2, but it is possible to have more complex wirings using $k$ nonlocal boxes, thus obtaining a wirings of depth $k$, which play a significant role in the context of trivial communication complexity [23].

## 1.4 Typical Examples of Wirings

We now review typical wirings that are studied in the literature. See Figure 3 for an illustration of these wirings. Note that all of these wirings are deterministic wirings.

*Example 0.* The trivial wiring $W_{\text{triv}}$ is defined as the wiring that does “nothing”, in the sense that it outputs exactly the global inputs: $(a, b) = (x, y)$. Similarly, the linear wiring $W_{\text{lin}}$ simply connects the output of a box to the input of the box immediately below.

*Example 1.* In [25], Forster et al. introduce a wiring $W_\oplus$ in order to distill nonlocality. It consists in setting boxes in parallel and in taking the sum mod 2 of the outputs.

*Example 2.* In [13], Brunner and Skrzypczyk enhance the wiring from Example 1 in order to obtain a better distillation protocol of nonlocality. Their wiring $W_{\text{BS}}$ is adaptive, in the sense that boxes are no longer in parallel: the second box's inputs $a_2, b_2$ are not simply equal to the previous box's outputs $a_1, b_1$, but they equal the latter multiplied by the general inputs $x, y$. Their new protocol is so powerful that it allows to arbitrarily reduce the noise of any correlated box (defined as convex combinations of PR and SR) so that the PR box is almost perfectly simulated. As a consequence, communication complexity collapses; see the next section for more details.

*Example 3.* In [1], Allcock et al. study two variants of the previous wirings. First, their “distillation wiring” $W_{\text{dist}}$ is similar to the one in Example 2: it is also adaptive and it also distills all correlated boxes. Second, their “AND wiring” $W_\land$ resembles the one in Example 1: boxes are set in parallel, but we take the product of the outputs instead of the sum.
<figure><img src="image_5.png" /><figcaption>Figure 3: Typical examples of wirings. Wirings with the same color have similar internal structures. The overline bar is the NOT gate: $\bar{x} = x \oplus 1$. The symbol (*) stands for $xa_2 \lor x\bar{a}_1 \lor \overline{xa_2a_1}$, and (**) for $yb_2 \lor y\bar{b}_1$, and (***) for $a_3a_2 \lor a_3\bar{a}_1 \lor \overline{a_3\bar{a}_2a_1}$, and (****) for $b_3b_2 \lor b_3\bar{b}_1 \lor \overline{b_3b_2b_1}$.</figcaption></figure>

**Example 4.** In [27], Høyer and Rashid study the depth-k generalizations of the wirings from Examples 1 and 2 and 3: they wire k boxes instead of only two. They also give an example of a depth-3 protocol that extends the known region of distillable boxes. In [23] this idea is improved upon, by constructing genuine depth-3 protocols, such as $W_{\text{depth3}}$ drawn above. These protocols are strictly better than depth-2 protocols in terms of the collapse of CC, in the sense that they prove the existence of nonlocal boxes that are shown to collapse CC using this wiring but that cannot be distilled using any depth-2 wiring. To do so, they use their algorithm to single out the area of nonlocal boxes that are distillable by means of depth-2 wirings, and they show that their example $W_{\text{depth3}}$ is out of this region.<fnref n="4" /> Note that in our work, the study is limited to depth-2 wirings.

**Example 5.** More recently, in [35], Naik et al. defined the “OR-AND wiring” $W_{\lor\land}$ in order to distill the nonlocality of quantum correlations. That wiring is a mix of the ones in Examples 1 and 3: it consists in setting boxes in parallel and in taking the maximum (the “OR”) of Alice’s outputs and the minimum (the “AND”) of Bob’s outputs.

## 1.5 Algebra of Boxes Induced by a Wiring

Let $\mathcal{B}$ be the vector space of all the functions $\{0,1\}^4 \to \mathbb{R}$, and consider a mixed wiring $W$. As defined in Equation (9), the operation $\otimes_W$ is bilinear, so the vector space $\mathcal{B}$ equipped with

<footnote n="4">⁴We thank Mirjam Weilenmann for feedback and for pointing out that [12] states that the wirings $W \oplus$ and $W_{\text{dist}}$ are sufficient to characterize the distillable region of the slice PR-SR-I.</footnote>
the product $\boxtimes_W$ is actually an algebra, which we denote by $B_W$ for that specific wiring $W \in W$. Its dimension is $\dim B_W = 2^4 = 16$. Note that the (affine) dimension of the non-signalling polytope $\mathcal{NS} \subseteq B_W$ is $\dim \mathcal{NS} = 16 - 8 = 8$ because there are 8 dependent variables in the affine conditions (1), (2), (3); see [3] for a more general expression.

**Multiplication Table.** In order to better understand the behavior of the box product $\boxtimes$, it is interesting to compute the product of some basic boxes: for instance the boxes $PR, P_0, P_1, I$ defined in Equation (4). In Figure 4, we present the multiplication table for the wiring $W_{BS}$ from [13]. By bilinearity of the box multiplication, this table shows that the convex hull $\text{Conv}\{PR, P_0, P_1\}$ is stable under $\boxtimes$. On the contrary, observe that the convex hull $\text{Conv}\{PR, P_0, P_1, I\}$ is not stable under $\boxtimes$: the product $I \boxtimes PR$ gives $Q_1 := \frac{1}{4}PR - \frac{1}{8}(P_0 + P_1) + I$ which is out of the convex hull (nevertheless the affine hull $\text{Aff}\{PR, P_0, P_1, I\}$ is stable under $\boxtimes$). Notice that we show in Proposition 22 that actually $\text{Conv}\{PR, P_0, P_1\} = \mathcal{NS} \cap \text{Aff}\{PR, P_0, P_1\}$. From this table, one may postulate that $P_0$ is a right identity in the sense that $P \boxtimes P_0 = P$ for all $P$ in $\mathcal{NS}$, and it is indeed true as a simple consequence of formula (7). One may similarly verify that $I$ is a right fixed point, in the sense that $P \boxtimes I = I$ for all $P$ in $\mathcal{NS}$, as it is possible to guess from the table. See all the multiplication tables of the typical depth-2 wirings in Appendix C.

<table><caption>Figure 4: Multiplication table of the operation $\boxtimes_{W_{BS}}$ induced by the wiring from [13]. Each cell displays the result of $P \boxtimes Q$. The box $Q_1$ at the bottom left is $Q_1 := \frac{1}{4}PR - \frac{1}{8}(P_0 + P_1) + I$. Further multiplication tables are available in Appendix C.</caption><thead><tr><th>Q<br>P</th><th>PR</th><th>P<sub>0</sub></th><th>P<sub>1</sub></th><th>I</th></tr></thead><tbody><tr><th>PR</th><th>PR</th><th>PR</th><th>PR</th><th>I</th></tr><tr><th>P<sub>0</sub></th><td><sup>1</sup>&frasl;<sub>2</sub>(P<sub>0</sub> + P<sub>1</sub>)</td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>I</td></tr><tr><th>P<sub>1</sub></th><td>PR</td><td>P<sub>1</sub></td><td>P<sub>0</sub></td><td>I</td></tr><tr><th>I</th><td>Q<sub>1</sub></td><td>I</td><td>I</td><td>I</td></tr></tbody></table>

**Non-Commutativity and Non-Associativity.** A direct consequence of the multiplication table in Figure 4 is that the algebra $B_{W_{BS}}$ induced by the wiring $W_{BS}$ is non-commutative ($P_0 \boxtimes PR \neq PR \boxtimes P_0$) and non-associative (($P_0 \boxtimes P_1) \boxtimes PR \neq P_0 \boxtimes (P_1 \boxtimes PR)$). This non-associativity is at the root of interesting remarks, see drawings of the orbit of a box in the next section, Figure 7. Similarly, the algebra induced by the wiring $W_{dist}$ is both non-commutative and non-associative, but on the contrary, the algebras induced by $W \in \{W_{\text{triv}}, W_{\oplus}, W_{\wedge}, W_{\vee\wedge}\}$ are both commutative and associative. One may wonder if there exist induced algebras that are associative but not commutative, and the converse. To that end, here is a characterization of commutativity and associativity in a simple case where boxes are set in parallel and with the same input functions:

**Proposition 7 (Characterization of commutativity and associativity).** Assume $W$ is a wiring such that $f_1 = f_2 = f(x)$ and $g_1 = g_2 = g(y)$. Then:

(i) $B_W$ is commutative if and only if the functions $f_3(x, a_1, a_2)$ and $g_3(y, b_1, b_2)$ are “symmetric” in the last two variables, in the sense that $f_3(x, a_1, a_2) = f_3(x, a_2, a_1)$ for all $x, a_1, a_2$, and similarly for $g_3$.

If in addition $f(x) = x$ and $g(y) = y$:

(ii) $B_W$ is associative if and only if the functions $f_3(x, a_1, a_2)$ and $g_3(y, b_1, b_2)$ are “associative” in the last two variables, in the sense that $f_3(x, a_1, f_3(x, a_2, a_3)) = f_3(x, f_3(x, a_1, a_2), a_3)$ for all $x, a_1, a_2, a_3$, and similarly for $g_3$.

*Proof.* (i) First, from the expression (7), see that for all bits $a, b, x, y$ and any boxes $P, Q$ in $B_W$, we
have:

$$ \begin{aligned} & \mathbb{P}_{\mathbb{W}} \boxtimes \mathbb{Q}(a, b | x, y) - \mathbb{Q}_{\mathbb{W}} \boxtimes \mathbb{P}(a, b | x, y) \\ &= \sum_{a_1, a_2, b_1, b_2} \mathbb{P}(a_1, b_1 | f(x), g(y)) \times \mathbb{Q}(a_2, b_2 | f(x), g(y)) \times \left[ \mathbb{1}_{a=f_3(x, a_1, a_2)} \mathbb{1}_{b=g_3(y, b_1, b_2)} \right. \\ & \qquad \left. - \mathbb{1}_{a=f_3(x, a_2, a_1)} \mathbb{1}_{b=g_3(y, b_2, b_1)} \right]. \end{aligned} $$

Hence, if $f_3$ and $g_3$ are both symmetric in the last two variables, then the difference is null and the algebra is commutative. Conversely, suppose that $\mathcal{B}_W$ is commutative, so that the left-hand side is null. Taking probability distributions $\mathbb{P}$ and $\mathbb{Q}$ that are always positive (such as $\mathbb{I}$), we have that the difference in the right-hand side has to be null for all $x, y, a, b, a_1, a_2, b_1, b_2$. Fix $x, a_1, a_2$ and consider $a := f_3(x, a_1, a_2)$, and similarly fix $y, b_1, b_2$ and consider $b := g_3(y, b_1, b_2)$. We obtain $1 - \mathbb{1}_{a=f_3(x, a_2, a_1)} \mathbb{1}_{b=g_3(y, b_2, b_1)} = 0$, which means that both indicator functions are equal to 1, and therefore both subscript equalities hold. Hence, this being true for any fixed $x, a_1, a_2$ and $y, b_1, b_2$, we obtain that $f_3$ and $g_3$ are symmetric as wanted.

(ii) From (7) again, we have for all bits $a, b, x, y$ and any boxes $\mathbb{P}, \mathbb{Q}, \mathbb{R}$ in $\mathcal{B}_W$:

$$ \begin{aligned} & \mathbb{P}_{\mathbb{W}} \boxtimes (\mathbb{Q}_{\mathbb{W}} \boxtimes \mathbb{R})(a, b | x, y) - (\mathbb{P}_{\mathbb{W}} \boxtimes \mathbb{Q}) \boxtimes \mathbb{R}(a, b | x, y) \\ &= \sum_{a_1, a_2, a_3, b_1, b_2, b_3} \mathbb{P}(a_1, b_1 | x, y) \times \mathbb{Q}(a_2, b_2 | x, y) \times \mathbb{R}(a_3, b_3 | x, y) \times \left[ \mathbb{1}_{a=f_3(x, a_1, f_3(x, a_2, a_3))} \mathbb{1}_{b=g_3(y, b_1, g_3(y, b_2, b_3))} \right. \\ & \qquad \left. - \mathbb{1}_{a=f_3(x, f_3(x, a_1, a_2), a_3)} \mathbb{1}_{b=g_3(y, g_3(y, b_1, b_2), b_3)} \right]. \end{aligned} $$

A similar proof with double implication as in (i) applies, hence the associativity criterion follows. $\square$

<figure><img src="image_6.png" /></figure>

Now, it is easier to build an associative non-commutative induced algebra $\mathcal{B}_{W'}$. Consider the wiring $W'$ given by $f_1(x, a_2) = f_2(x, a_1) = x$, and $g_1(y, b_2) = g_2(y, b_1) = y$, and $f_3(x, a_1, a_2) := a_1$, and $g_3(y, b_1, b_2) := b_1$. This wiring satisfies the condition (ii) of the proposition and does not satisfy the condition (i), hence it is as wanted. Conversely, with similar arguments, a commutative non-associative algebra $\mathcal{B}_{W''}$ is induced by the wiring $W''$ defined by the same $f_1, f_2, g_1, g_2$ and $f_3(x, a_1, a_2) := a_1 a_2 \oplus 1$ and $g_3(y, b_1, b_2) := b_1 b_2 \oplus 1$. Therefore, we obtain the table in Figure 5.

<table><caption>Figure 5: Associativity and commutativity of the induced algebra $\mathcal{B}_W$, depending on the wiring $W$ displayed in the table cell.</caption><thead><tr><th></th><th>Associativity</th><th>Non-associativity</th></tr></thead><tbody><tr><th>Commutativity</th><td>$W_{\text{triv}}, W_{\oplus}, W_{\wedge}, W_{\vee\wedge}$</td><td>$W^{\prime\prime\prime}$</td></tr><tr><th>Non-commutativity</th><td>$W^{\prime}$</td><td>$W_{\text{BS}}, W_{\text{dist}}$</td></tr></tbody></table>

## 2 Orbit of a Box

In this section, we study the set of all boxes that can be generated given many copies of a starting box $\mathbb{P}$ and a wiring $\mathbb{W}$. After introducing the *orbit* of a box, we provide some consequences to communication complexity. Subsequently, we study a particular example, $W_{\text{BS}}$, with which we find collapsing boxes in Subsection 4.2, and then we give some general remarks about other orbits. Finally, we conclude this section by giving the technical proof of the theorem stating that the “best” parenthesization is the multiplication on the right.

### 2.1 Definition

Given multiple copies of a non-signalling box $\mathbb{P} \in \mathcal{N}\mathcal{S}$ and of a (mixed) wiring $\mathbb{W}$, Alice and Bob can produce many other boxes, e.g. $(\mathbb{P} \boxtimes_{\mathbb{W}} \mathbb{P}) \boxtimes_{\mathbb{W}} \mathbb{P}$ or $\mathbb{P} \boxtimes_{\mathbb{W}} (\mathbb{P} \boxtimes_{\mathbb{W}} \mathbb{P})$. All of these new boxes are
again non-signalling because $\mathcal{N}\mathcal{S}$ is closed under wirings, see Lemma 5. We call orbit of the box P (induced by the wiring W) the set of all of these possible new boxes:

$$ \text{Orbit}_W(\mathbf{P}) := \left\{ \text{boxes } \mathcal{Q} \in \mathcal{N}\mathcal{S} \text{ that can be produced by using finitely many times the box P and the wiring W} \right\} \\ = \bigcup_{k \ge 1} \text{Orbit}_W^{(k)}(\mathbf{P}) \subseteq \mathcal{N}\mathcal{S}, $$

where $\text{Orbit}^{(k)}(\mathbf{P})$ is called the orbit of depth $k$ of P (or simply $k$-orbit), defined as:

$$ \text{Orbit}_W^{(k)}(\mathbf{P}) := \left\{ \text{all possible products with } k \text{ times the term P, using the multiplication } \boxtimes_W \right\}. $$

When the context is clear, we overload the notation and write $\text{Orbit}$ and $\text{Orbit}^{(k)}$ respectively. In general, these $k$-orbits are not singletons for $k \ge 3$ since the algebra $\mathcal{B}_W$ induced by W is not necessarily associative and commutative (see Figure 5). Actually, up to multiplicity, the cardinal $\#\text{Orbit}^{(k)}$ is exactly the number of parenthesizations with $k$ terms, which is the Catalan number $\frac{1}{k} \binom{2k-2}{k-1}$, which grows exponentially fast. Here are the 3- and 4- orbits:

$$ \text{Orbit}^{(3)}(\mathbf{P}) = \left\{ (\mathbf{P} \boxtimes \mathbf{P}) \boxtimes \mathbf{P}, \mathbf{P} \boxtimes (\mathbf{P} \boxtimes \mathbf{P}) \right\}, $$

$$ \text{Orbit}^{(4)}(\mathbf{P}) = \left\{ ((\mathbf{P} \boxtimes \mathbf{P}) \boxtimes \mathbf{P}) \boxtimes \mathbf{P}, (\mathbf{P} \boxtimes (\mathbf{P} \boxtimes \mathbf{P})) \boxtimes \mathbf{P}, (\mathbf{P} \boxtimes \mathbf{P}) \boxtimes (\mathbf{P} \boxtimes \mathbf{P}), \mathbf{P} \boxtimes ((\mathbf{P} \boxtimes \mathbf{P}) \boxtimes \mathbf{P}), \mathbf{P} \boxtimes (\mathbf{P} \boxtimes (\mathbf{P} \boxtimes \mathbf{P})) \right\}. $$

Note that a $k$-orbit ($k \ge 2$) can be inductively computed using orbits with lower depth:

$$ \text{Orbit}^{(k)} = \bigcup_{1 \le l \le k-1} \text{Orbit}^{(l)} \boxtimes \text{Orbit}^{(k-l)}, $$

which is the same recurrence relation as that of Catalan numbers.

## 2.2 Consequences to Communication Complexity

Assume Alice and Bob are given infinitely many copies of a nonlocal box P, and assume they want to distantly compute (in finite time) the value of a Boolean function $f(X, Y)$, where $X, Y \in \{0, 1\}^n$ are strings that are known by Alice and Bob respectively. Among all the possible protocols they can try to do in order to succeed, they can wire their copies of P in order to produce a “better” box. For example, starting from a noisy box P, Alice and Bob can try to produce a box that is closer to the “perfect box” PR which satisfies $a \oplus b = xy$ without noise. Such a protocol is called a *distillation protocol* [13]. We call *collapsing box* a nonlocal box that collapses CC.

*Find Collapsing Boxes Using the Orbit.* Imagine Alice and Bob are able to produce a collapsing box $\mathcal{Q}$ after applying wirings to copies of a starting box P. Then they can use that new box $\mathcal{Q}$ to distantly compute the value $f(X, Y)$, which means that they have a protocol to collapse communication complexity and therefore that P is collapsing. This point of view is particularly interesting since it implies that it is sufficient to find a single collapsing box in the union $\bigcup_W \text{Orbit}_W(\mathbf{P})$ to deduce that P is collapsing as well. See an illustration in Figure 6 (a).

*Find Collapsing Boxes Using a Cone.* Once we find a collapsing box P, we can deduce many other collapsing boxes: there is a convex cone taking origin at P that is collapsing as well. More precisely, given a box P, denote $C_P$ the convex cone of boxes R for which there exists a local correlation $L \in \mathcal{L}$ such that $P = \lambda R + (1 - \lambda) L$, with $\lambda \in [0, 1]$. We claim that if P is collapsing, then any $R \in C_P$ is collapsing as well. Indeed, assume Alice and Bob are given copies of a box R. Then, they can use shared randomness to produce the wanted box L and the wanted convex coefficient $\lambda$, so that they can generate the box P with the relation $P = \lambda R + (1 - \lambda) L$. Now, as P is collapsing, they have a protocol that collapses communication complexity, hence R is collapsing as well. See an illustration in Figure 6 (b). In the study of collapsing boxes, notice that it is standard to assume that shared randomness is a “free” resource; for instance Brassard et. al. made that choice in [10] in their collapsing protocol.
Combining arguments from these last two paragraphs and by the fact that Alice and Bob can make a convex combination of boxes using shared randomness, we deduce a sufficient criterion for a box to collapse communication complexity:

**Proposition 8 (Collapsing orbit).** Let P be a box in $\mathcal{N}S$. If there exists a box $Q \in \text{Conv}(\mathcal{L} \cup \bigcup_W \text{Orbit}_W(P))$ that collapses communication complexity, then P is collapsing as well. See Figure 6 (c).

<figure><img src="image_7.png" /><figcaption>Figure 6: Orbits that collapse communication complexity.</figcaption></figure>

## 2.3 Case Study: Orbit of $W_{BS}$

In this subsection, we focus our attention on the wiring $W_{BS}$ inspired by Brunner and Skrzypczyk [13]. Denote $\boxtimes$ the corresponding box multiplication. Define the shared randomness box as $\text{SR} := (P_0 + P_1)/2$; it is designed to output a couple $(a, b)$ such that $a = b$ uniformly and independently of the inputs. From the multiplication table in Figure 4, one can see that the 2-dimensional affine space $\mathcal{A} := \text{Aff}\{\text{PR}, \text{SR}, \text{I}\}$ is stable under $\boxtimes$. As a consequence, the orbit $\text{Orbit}(P)$ of any box P in $\mathcal{A}$ is itself included in $\mathcal{A}$, and as $\mathcal{A}$ is two-dimensional, it is particularly easy to draw the orbit of a box in that case. We represent an orbit in Figure 7.

By definition of the affine space $\mathcal{A}$, any box $A \in \mathcal{A}$ can be uniquely written as $A = c_1(A)\text{PR} + c_2(A)\text{SR} + c_3(A)\text{I}$ for some real coefficients $c_i(A)$ that sum to 1, called convex coordinates of A in the affine basis $\{\text{PR}, \text{SR}, \text{I}\}$. An interesting aspect of considering convex coordinates is that it gives a simple characterization of the parallelism property of lines:

$$ \forall A, B \in \mathcal{A}, \quad \text{Aff}\{A, B\} \parallel \text{Aff}\{\text{PR}, \text{SR}\} \iff c_3(A) = c_3(B). \quad 5 \qquad (10) $$

Moreover, in our case, we have an additional interesting property of the third convex coordinate:

**Lemma 9.** The function $1 - c_3(\cdot)$ is multiplicative:

$$ \forall A, B \in \mathcal{A}, \quad 1 - c_3(A \boxtimes B) = (1 - c_3(A))(1 - c_3(B)). $$

<footnote n="5">⁵Indeed, for $A \neq B \in \mathcal{A}$ whose convex coefficients are respectively $a_1, a_2, a_3$ and $b_1, b_2, b_3$, saying that the line $\text{Aff}\{A, B\}$ is parallel to the line $\text{Aff}\{\text{PR}, \text{SR}\}$ is equivalent to knowing that there exists a scalar $\lambda \in \mathbb{R}^*$ such that $A - B = \lambda(\text{PR} - \text{SR})$, i.e. there exists $\lambda \in \mathbb{R}^*$ such that $a_1 - b_1 = \lambda$ and $a_2 - b_2 = -\lambda$ and $a_3 - b_3 = 0$, i.e. we have two equations: $a_1 + a_2 = b_1 + b_2$ and $a_3 = b_3$. Finally, using the normalization condition $\sum_i a_i = \sum_j b_j = 1$, we see that these two equations are equivalent to simply imposing $a_3 = b_3$, as claimed.</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 7: Example of a box orbit, drawn for depth up to $k = 12$. The quantum area $Q$ (in pink) is drawn using formulas from [33]. Dark green represents the collapsing area that was found by Brassard et. al. in [10], which consists of all the boxes with CHSH-value higher than $\frac{3+\sqrt{6}}{6} \approx 0.91$. The orbit is drawn in yellow and orange dots — observe that it intersects the collapsing area in dark green, so Proposition 8 tells us that the starting box $P$ is collapsing. The black circles represent the boxes that were studied in [13], doing “pairwise” multiplications: $P, P \boxtimes P, (P \boxtimes P) \boxtimes (P \boxtimes P), \text{etc...}$ Each iteration is the wiring of two copies of the previous iteration, it gives a subset of our orbit. As displayed in the drawing and detailed in the proof of Proposition 16, our method allows us to find a larger set of boxes $P$ that are collapsing.</figcaption></figure>

*Proof.* The multiplication table induced by the wiring $W_{BS}$ [13] is:

$$ \begin{array}{|c|c|c|c|} \hline \begin{array}{c} Q \\ \parallel P \end{array} & \text{PR} & \text{SR} & \text{I} \\ \hline \text{PR} & \text{PR} & \text{PR} & \text{I} \\ \hline \text{SR} & \frac{1}{2}\text{PR} + \frac{1}{2}\text{SR} & \text{SR} & \text{I} \\ \hline \text{I} & \frac{1}{4}\text{PR} - \frac{1}{4}\text{SR} + \text{I} & \text{I} & \text{I} \\ \hline \end{array}, \qquad (11) $$

where each cell displays the result of $P \boxtimes Q$. For $A, B \in \mathcal{A}$ whose coefficients $c_i$ are denoted $a_1, a_2, a_3$ and $b_1, b_2, b_3$ for the sake of readability, we use the bilinearity of the product $\boxtimes$ and we get:

$$ A \boxtimes B = \left[ a_1 b_1 + a_1 b_2 + \frac{1}{2} a_2 b_1 + \frac{1}{4} a_3 b_1 \right] PR + \left[ \frac{1}{2} a_2 b_1 + a_2 b_2 - \frac{1}{4} a_3 b_1 \right] SR \\ + \left[ a_1 b_3 + a_2 b_3 + a_3 b_1 + a_3 b_2 + a_3 b_3 \right] I. $$

Hence, using the normalization property of coefficients $\sum_i a_i = \sum_j b_j = 1$, the third coefficient simplifies as $b_3 + a_3(1 - b_3)$, which is equal to $1 - (1 - a_3)(1 - b_3)$ as wanted. $\square$

Now, interestingly, we observe that the points of a given $k$-orbit are all aligned, and we even know the equation of the line:

**Theorem 10 (Alignment).** For any $k \ge 1$ and $P \in \mathcal{A}$, the points of $\text{Orbit}^{(k)}(P)$ are all aligned on a line $\mathcal{L}_k$ whose expression in convex coordinates is given by:

$$ \mathcal{L}_k := \{ A \in \mathcal{A} : c_3(A) = 1 - (1 - c_3(P))^k \}. $$

*Proof.* We prove by induction on $k \ge 1$ that $\text{Orbit}^{(k)} \subseteq \mathcal{L}_k$. For $k = 1$, the 1-orbit contains only one element, namely $P$, which obviously satisfies $c_3(P) = 1 - (1 - c_3(P))$, so $P$ indeed belongs to $\mathcal{L}_1$.
Now, assume the result holds until some integer $k \ge 1$, and let $\mathbb{Q} \in \text{Orbit}^{(k)}$. By definition, the box $\mathbb{Q}$ decomposes as $\mathbb{Q} = \mathbb{Q}_1 \boxtimes \mathbb{Q}_2$, for some $\mathbb{Q}_1 \in \text{Orbit}^{(\ell)}$ and $\mathbb{Q}_2 \in \text{Orbit}^{(k-\ell)}$ for some $1 \le \ell \le k-1$. By the induction hypothesis, we know that $c_3(\mathbb{Q}_1) = 1 - (1-c_3(\mathbb{P}))^{\ell}$ and $c_3(\mathbb{Q}_2) = 1 - (1-c_3(\mathbb{P}))^{k-\ell}$. Then using Lemma 9, we obtain:

$$ 
\begin{aligned}
c_3(\mathbb{Q}) &= 1 - (1 - c_3(\mathbb{Q}_1)) (1 - c_3(\mathbb{Q}_2)) \\
&= 1 - (1 - c_3(\mathbb{P}))^{\ell} (1 - c_3(\mathbb{P}))^{k-\ell} \\
&= 1 - (1 - c_3(\mathbb{P}))^{k},
\end{aligned}
$$

which means that $\mathbb{Q}$ belongs to the line $\mathcal{L}_k$.

□

As a consequence, we see that all the points of the $k$-orbit have the same third convex coefficient, so using the equivalence given in Equation (10), we obtain:

**Corollary 11 (Parallelism).** The supporting line $\mathcal{L}_k$ of all the orbits $\text{Orbit}^{(k)}$ are parallel to the diagonal line $\mathcal{L}_D := \text{Aff}\{\text{PR}, \text{SR}\}$:

$$ \forall k \ge 1, \quad \text{Orbit}^{(k)} \parallel \mathcal{L}_D. $$

In particular, all the orbits are parallel to each other:

$$ \forall k, \ell \ge 1, \quad \text{Orbit}^{(k)} \parallel \text{Orbit}^{(\ell)}. $$

□

Moreover, looking closely at the sequence of coefficients $1 - (1 - c_3(\mathbb{P}))^k$ and noticing that the diagonal line $\mathcal{L}_D$ is defined by the equation $c_3(\mathbb{A}) = 0$, we see that:

**Corollary 12 (Orbits move to the left).** Assume $\mathbb{P} \notin \mathcal{L}_D$. Then the orbits are more and more distant from the diagonal line as $k$ grows. Moreover, the sequence of lines $(\mathcal{L}_k)_k$ tends to the line $\mathcal{L}_\infty$ defined by the equation $c_3(\mathbb{A}) = 1$, which is exactly the line passing through $\mathbb{I}$ and parallel to the diagonal $\mathcal{L}_D$.

□

It takes a lot of computational time to draw $k$-orbits of a box $\mathbb{P}$ as $k$ grows, since it requires to compute $\frac{1}{k} \binom{2k-2}{k-1}$ elements (Catalan number), which grows exponentially. However, our goal is not to compute the whole orbit, but simply to determine whether or not the orbit intersects the known collapsing area (dark green). To that end, one may notice that it is enough to compute the “highest” box of each $k$-orbit in the $y$-coordinate (see Figure 7) and to check whether those “highest” boxes intersect the collapsing area (dark green area). This is the purpose of the following proposition, which displays a simple expression of the “highest” box of each $k$-orbit, and which allows much faster tests of a box $\mathbb{P}$ being collapsing or not without computing all the points of the orbit. We prove this result only in a subset of the orbit, that we call *tilted orbit*, which is easier to manipulate in inductions, and which is defined by $\widetilde{\text{Orbit}}^{(1)}(\mathbb{P}) := \{\mathbb{P}\}$ and for $k \ge 2$:

$$ \widetilde{\text{Orbit}}^{(k)} := (\mathbb{P} \boxtimes \widetilde{\text{Orbit}}^{(k-1)}) \cup (\widetilde{\text{Orbit}}^{(k-1)} \boxtimes \mathbb{P}) = \bigcup_{\ell \in \{1, k-1\}} \widetilde{\text{Orbit}}^{(\ell)} \boxtimes \widetilde{\text{Orbit}}^{(k-\ell)} \subseteq \widetilde{\text{Orbit}}^{(k)}. $$

Note that the cardinality of that set is $\#\widetilde{\text{Orbit}}^{(k+1)} = 2^k$, up to multiplicity. We call CHSH-value the $y$-coordinate, indicating how “high” is a box:

$$ \text{CHSH}(\mathbb{P}) := \mathbb{P}(\text{win at CHSH}) = \frac{1}{4} \sum_{a \oplus b = xy} \mathbb{P}(a, b | x, y). $$

We say that a tilted orbit *distills the CHSH-value* if it contains a box $\mathbb{Q}$ such that $\text{CHSH}(\mathbb{Q}) \ge \text{CHSH}(\mathbb{P})$. In the following theorem, we present the expression of the best parenthesization in terms of CHSH-value, which explains the numerical observation reported in [23, Supplementary Material, II]:
**Theorem 13 (Highest box).** Let $P \in \tilde{A}$ be a box, and let $k \ge 2$ an integer such that the tilted $(k-1)$-orbit distills the CHSH-value. Then the highest CHSH-value of $\text{Orbit}^{(k)}(P)$ is achieved at a box whose expression is the product of $k$ times $P$ on the right:

$$P^{\boxtimes k} := \left( ((P \boxtimes P) \boxtimes P) \cdots \right) \boxtimes P \in \underset{Q \in \text{Orbit}^{(k)}(P)}{\operatorname{argmax}} \text{CHSH}(Q).$$

*Proof.* See Subsection 2.5. □

<figure><img src="image_9.png" /></figure>

*Remark 14.* In the Ph.D. thesis of Giorgos Eftaxias [22], the author presents three types of architectures of wirings in Subsection 5.5.1: the exponential architecture, that we call here pairwise multiplication, used in [13]; the linear architecture, that is the same as the one used in the theorem above; and the Fibonacci architecture. They present some subsets of $\mathcal{N}S$ for which the linear architecture seems to be the best one among the three (Remark 1), and some other subsets of $\mathcal{N}S$ for which it is the Fibonacci architecture (Subsection 5.F.2).

**Conjecture 15 (Dyck paths).** We conjecture that the same result actually holds without the tilde, i.e. the right multiplication $P^{\boxtimes k}$ gives the highest CHSH-value of $\text{Orbit}^{(k)}(P)$, as observed numerically. An idea of the proof could be to use Dyck paths. Each time we open/close a parenthesis, the path goes up/down respectively, which produces a certain Dyck path. The statement to be proved is that each time we convert $a \lor a$ into $a \land a$, the CHSH-value is non-decreasing. Then, we would have that the best Dyck path is necessarily the one that always goes up first and then always goes down, which corresponds to the multiplication of boxes on the right.

As previously mentioned, the next theorem is concurrent and independent of the work of [23]:

**Theorem 16 (New collapsing boxes).** The techniques described in Subsection 2.2 allow the discovery of new collapsing boxes. See new collapsing areas in Figure 10.

*Proof.* See Figure 7 for an intuition of the proof. Take the starting box $P$ with coordinates $(0.627, 0.862)$ in the affine plane $\mathcal{A} = \text{Aff}\{\text{PR}, \text{SR}, \text{I}\}$, where the coordinate system is given by the CHSH'- and CHSH- values of $P$. On the one hand, the tilted orbit of $P$ intersects the collapsing area that was found in [10] (in dark green), since for instance $\text{CHSH}(P^{\boxtimes 5}) \approx 0.913 > 0.908 \approx \frac{3+\sqrt{6}}{6}$, so $P$ is collapsing by Proposition 8. On the other hand, this box $P$ does not lie in any of the previously-known collapsing areas from [8, 10, 11, 13, 18] (to the best of our knowledge, these five references are the only previous results showing a collapse of communication complexity, in addition to [23] which concurrently and independently found a similar result to ours as mentioned before). Indeed, it is not in the collapsing areas from [10, 18] since $\text{CHSH}(P) = 0.862 < 0.908$, nor is it in the collapsing area from [8] since $A+B \approx 14.13 < 16$ (using the authors' notation). The box $P$ neither is in any of the collapsing regions found in [11] since it does not belong to the boundary $\partial \mathcal{N}S$ of the non-signalling set. The last area to check is the one from [13], which was numerically found. From a box $P$, they define a sequence of boxes using “pairwise” multiplications: $Q_1 := P$ and $Q_{n+1} := Q_n \boxtimes Q_n$ for $n \ge 1$, and they check whether or not there exists an integer $n$ such that $\text{CHSH}(Q_n) > \frac{3+\sqrt{6}}{6}$. But, for our starting box $P$, none of the $Q_n$ satisfy this inequality: indeed, for $1 \le n \le 5$, it is possible to check it by hand, for $n=6$ we have $Q_6 \in \mathcal{L}$, and for $n \ge 7$ we also have $Q_n \in \mathcal{L}$ since $\mathcal{L}$ is closed under wirings [1]. Hence our example $P$ is a new collapsing box. □

<figure><img src="image_10.png" /></figure>

## 2.4 Some Other Orbits

In the previous subsection, we studied specifically the orbit of the wiring $W_{BS}$ in the slice of $\mathcal{N}S$ passing through the boxes PR, SR, I. Here we comment on some examples of other orbits in three different ways: (i) it is possible to study the same wiring $W_{BS}$ but in different slices of $\mathcal{N}S$; (ii) it is possible to study another wiring than $W_{BS}$ but to keep the same slice as in the previous subsection; (iii) it is possible to change both the wiring and the slice. See Appendix A for many drawings.
(i) We keep the wiring $W_{BS}$ and we consider the slice of $\mathcal{N}S$ passing through $PR, P_0, P_1$. Notice that we prove in Proposition 22 that this slice is actually precisely the convex combination of the three points. We draw two examples of such an orbit in Figure 8, with two different starting boxes. We observe that both of them seem to recover the alignment and parallelism properties that we showed in Theorem 10 and its corollary. Again, these lines seem all parallel to what we called previously the diagonal line $\mathcal{L}_D$, which is defined as the line passing through $PR$ and $SR = \frac{1}{2}(P_0 + P_1)$. Notice that we show in Theorem 23 that all the boxes of this triangle are actually collapsing, except the ones in the segment $\text{Conv}\{P_0, P_1\}$, drawn in pink.

<figure><img src="image_11.png" /><figcaption>Figure 8: Orbit of $W_{BS}$ in a different slice than in Subsection 2.3: here we consider the slice of $\mathcal{N}S$ passing through $PR, P_0$, and $P_1$. We represent the orbit with two different starting boxes. Each orbit is drawn with depth going until $k = 12$. The game $G$ is defined by the winning rule $a = 0$ and $b = y$. Notice that we give a proof based on CC that this triangle $\text{Conv}\{PR, P_0, P_1\}$ is a quantum void in Corollary 27, which is why the only quantum boxes in this triangle are actually local boxes.</figcaption></figure>

(ii) Among the “typical” wirings defined in Subsection 1.4, the only ones that stabilize the plane $\text{Aff}\{PR, SR, I\}$ are $W_\oplus$ and $W_{BS}$, see Appendix C. This is why, for these two wirings, we can conveniently draw the orbits in a plane. The orbit of $W_\oplus$ is drawn in Appendix A (a). We observe that each $k$-orbit contains only one element, which is not surprising since we know from Figure 5 that its induced algebra is associative, meaning that the choice of parenthesization does not lead to a different result. In the same appendix, we also draw the orbit for three other wirings. Surprisingly, we observe that the three new orbits look the same as the orbit of $W_{BS}$.

(iii) We add the slice $PR, P_0, P_1$ for each wiring of Appendix A. We observe that the alignment and parallelism properties seem to still hold in those cases, as before. Moreover, we see that the example (d) distills the CHSH-value better than the other examples in that slice.

## 2.5 Proof of Theorem 13

Recall that $\text{SR} := (P_0 + P_1)/2$ is the shared randomness box. Given a non-signalling box $P \in \mathcal{N}S$, its CHSH- and CHSH'- values are defined as follows:

$$ \text{CHSH}(P) := \frac{1}{4} \sum_{a \oplus b = xy} P(a, b | x, y), \quad \text{and} \quad \text{CHSH}'(P) := \frac{1}{4} \sum_{\substack{a \oplus b \\ (x \oplus 1)(y \oplus 1)}} P(a, b | x, y). $$

For example, we have $\text{CHSH}(PR) = 1$ and $\text{CHSH}(SR) = \frac{3}{4}$ and $\text{CHSH}(I) = \frac{1}{2}$. Denote $\mathcal{A}$ the affine space $\mathcal{A} := \text{Aff}\{PR, SR, I\}$, and denote $\tilde{\mathcal{A}} \subseteq \mathcal{A}$ the set of boxes $P$ in the convex hull $\text{Conv}\{PR, SR, I\}$ whose CHSH-value is $\ge 3/4$. We will prove our results in $\tilde{\mathcal{A}}$; by the symmetry of the problem, similar results also hold in other areas, such as $2I - \tilde{\mathcal{A}}$ the symmetric of $\tilde{\mathcal{A}}$ by $I$.

**Lemma 17 (Multiplying by $P$ preserves the CHSH-value order).** Let $P \in \tilde{\mathcal{A}}$, and let $Q \neq R \in \mathcal{A}$ such that the line $\text{Aff}\{Q, R\}$ is parallel to the diagonal line $\mathcal{L}_D := \text{Aff}\{PR, SR\}$. We have:

$$ \text{CHSH}(Q) \ge \text{CHSH}(R) \quad \Rightarrow \quad \left\{ \begin{array}{l} \text{CHSH}(Q \boxtimes P) \ge \text{CHSH}(R \boxtimes P), \\ \text{CHSH}(P \boxtimes Q) \ge \text{CHSH}(P \boxtimes R). \end{array} \right. $$
Proof. As the box P lies in $\tilde{\mathcal{A}}$, it is of the form $P = p_1PR + p_2SR + (1 - p_1 - p_2)I$ for some coefficients $p_1, p_2 \ge 0$ such that $p_1 + p_2 \le 1$. Rewrite it as $P = (\frac{p_1}{p_2})$, and similarly denote $Q = (\frac{q_1}{q_2})$ and $R = (\frac{r_1}{r_2})$ for some coefficients $q_i, r_j \in \mathbb{R}$. By the parallelism assumption, vectors $Q - R$ and $PR - SR$ have to be colinear, i.e. there must exist some $\lambda \in \mathbb{R}^*$ such that $Q - R = \lambda(PR - SR) = \lambda(\frac{1}{-1})$, so we may rewrite the second coefficient of R as $r_2 = q_1 + q_2 - r_1$. With this notation, we can use the linearity of the function CHSH(·) to see that condition CHSH(Q) ≥ CHSH(R) simplifies to $(q_1 - r_1) \ge 0$:

$$ 
\begin{aligned}
\mathrm{CHSH}(\mathbf{Q}) - \mathrm{CHSH}(\mathbf{R}) &= (q_1 - r_1) \times \mathrm{CHSH}(\mathrm{PR}) + (q_2 - r_2) \times \mathrm{CHSH}(\mathrm{SR}) + ((1 - q_1 - q_2) - (1 - r_1 - r_2)) \times \mathrm{CHSH}(\mathrm{I}) \\
&= (q_1 - r_1) \times 1 - (q_1 - r_1) \times \frac{3}{4} + 0 \times \frac{1}{2} \\
&= \frac{1}{4}(q_1 - r_1).
\end{aligned}
$$

Now, using the multiplication table from Figure 4 and bilinearity of $\otimes$, we may compute the following expressions:

$$ 
\begin{aligned}
\mathrm{CHSH}(\mathbf{Q} \otimes \mathbf{P}) - \mathrm{CHSH}(\mathbf{R} \otimes \mathbf{P}) &= \frac{1}{8}(p_1 + 2p_2)(q_1 - r_1) \ge 0, \\
\mathrm{CHSH}(\mathbf{P} \otimes \mathbf{Q}) - \mathrm{CHSH}(\mathbf{P} \otimes \mathbf{R}) &= \frac{1}{16}(1 - p_1 + p_2)(q_1 - r_1) \ge 0,
\end{aligned}
$$

which gives the desired result.

□

**Lemma 18 (Right multiplication gives better CHSH-value).** For any $P \in \tilde{\mathcal{A}}$ and $Q \in \widetilde{\mathrm{Orbit}}(P)$, we have:

$$ \mathrm{CHSH}(\mathbf{Q}) \ge \mathrm{CHSH}(\mathbf{P}) \implies \mathrm{CHSH}(\mathbf{Q} \otimes \mathbf{P}) \ge \mathrm{CHSH}(\mathbf{P} \otimes \mathbf{Q}). $$

Proof. Use the coordinate system $(x, y)$ given by the CHSH'- and CHSH- values respectively in order to write P and Q as taking coordinates $(x_P, y_P)$ and $(x_Q, y_Q)$. For instance we have $PR : (\frac{1}{2}, 1)$ and $SR : (\frac{3}{4}, \frac{3}{4})$ and $I : (\frac{1}{2}, \frac{1}{2})$. Use the multiplication table from Equation (11) and apply the bilinearity of $\otimes$ in order to obtain the following expression:

$$ \mathrm{CHSH}(\mathbf{Q} \otimes \mathbf{P}) - \mathrm{CHSH}(\mathbf{P} \otimes \mathbf{Q}) = \frac{1}{8}(12x_P y_Q - 12y_P x_Q - 7x_P + 7y_P + 7x_Q - 7y_Q) =: f_P(x_Q, y_Q). $$

For any fixed $P \in \tilde{\mathcal{A}}$, we want to show that $f_P(x_Q, y_Q) \ge 0$. By construction, we know that $P \in \mathcal{L}_1$ and $Q \in \mathcal{L}_k$ for some $k \ge 1$, so by Corollary 12 we have $x_Q + y_Q \le x_P + y_P$, which we may rewrite as $x_Q \le x_P + y_P - y_Q$. As P lies in $\tilde{\mathcal{A}}$, we have $y_P \ge \frac{3}{4}$, so the first partial derivative is non-positive: $\frac{\partial}{\partial x_Q} f_P(x_Q, y_Q) = \frac{1}{8}(7 - 12y_P) \le -1/4 \le 0$, which means that the function $f_P(\cdot, y_Q)$ is decreasing over $\mathbb{R}$ for any fixed $y_Q$. It yields the following inequalities:

$$ f_P(x_Q, y_Q) \ge f_P(x_P + y_P - y_Q, y_Q) = \frac{3}{2}(y_Q - y_P)(x_P + y_P - \frac{7}{6}) \ge 0, $$

since both factors are non-negative: the first one is non-negative using the hypothesis CHSH(Q) ≥ CHSH(P), and the second one is non-negative using $x_P \ge 1/2$ and $y_P \ge 3/4$ since $P \in \tilde{\mathcal{A}}$. Hence $f_P$ is non-negative and we obtain the wanted result.

Recall that the set $\widetilde{\mathrm{Orbit}}^{(k)}(P)$ is called the tilted $k$-orbit of the box P and contains some boxes Q that are generated by applying a wiring to copies of P. We say that this tilted $k$-orbit *distills the CHSH-value* if it contains a box Q such that CHSH(Q) ≥ CHSH(P). In that distilling scenario, we can compute the expression of a box achieving the best CHSH-value:

**Statement (Theorem 13).** Let $P \in \tilde{\mathcal{A}}$ be a box, and let $k \ge 2$ be an integer such that the tilted $(k-1)$-orbit distills the CHSH-value. Then the highest CHSH-value of $\widetilde{\mathrm{Orbit}}^{(k)}(P)$ is achieved at a box whose expression is the product of $k$ times P on the right:

$$ P^{\otimes k} := ((P \otimes P) \otimes P) \cdots \otimes P \in \underset{Q \in \widetilde{\mathrm{Orbit}}^{(k)}(P)}{\operatorname{argmax}} \mathrm{CHSH}(Q). $$
Proof. We prove the result by induction on $k \ge 2$. It is obviously true for $k = 2$ since $\tilde{\text{Orbit}}^{(2)}(P)$ only contains $P \boxtimes P$. Now, fix $k \ge 2$ and assume $\text{CHSH}(P^{\boxtimes k}) \ge \text{CHSH}(Q)$ for any $Q$ in the tilted $k$-orbit (induction hypothesis). Assume as well that $\text{CHSH}(P^{\boxtimes k}) \ge \text{CHSH}(P)$ (distillation hypothesis). We want to show that:

$$ \text{CHSH}(P^{\boxtimes k+1}) \ge \text{CHSH}(Q \boxtimes P) \quad \text{and} \quad \text{CHSH}(P^{\boxtimes k+1}) \ge \text{CHSH}(P \boxtimes Q), $$

for all $Q$ in the tilted $k$-orbit. The first inequality follows from Lemma 17 using the relation $P^{\boxtimes k+1} = P^{\boxtimes k} \boxtimes P$ and the induction assumption. For the other inequality, start from $\text{CHSH}(P^{\boxtimes k+1}) = \text{CHSH}(P^{\boxtimes k} \boxtimes P)$ and apply Lemma 18 in order to get $\ge \text{CHSH}(P^{\boxtimes k} \boxtimes P)$. Then conclude using Lemma 17 and the induction hypothesis in order to obtain $\ge \text{CHSH}(P \boxtimes Q)$ for any $Q$ in the tilted $k$-orbit. $\square$

## 3 Numerical Optimization on the Set of Wirings

We saw in the previous section that, given a non-signalling box $P$, there may exist a wiring $W$ that sufficiently distills the box $P$ in order to collapse communication complexity. The question we address in this section is the following: if the box $P$ is fixed, how to find a wiring $W$ good enough to collapse communication complexity (when it is possible)? The difficulty is that, for each input $x, y \in \{0, 1\}$, there are 82 possible deterministic wirings [45], leading to a total number of $82^4 \approx 10^8$ possible deterministic wirings. So a naive discrete optimization over deterministic wirings seems inefficient. To that end, we present two optimization algorithms: (i) an algorithm that tests many different combinations of wirings and that is suitable for numerical simulations, and (ii) another one that finds a “uniform” collapsing wiring $W$ in a whole region of boxes, which is appropriate for deriving an analytical proof (see the next section). This section might be skipped at first reading as it is more technical. See our GitHub page for the details of the algorithms [9].

Remark 19 (Comparison with [11, 23]). We now compare and contrast our methods with two recent works that also study optimization over wirings:

(i) In [11], the authors suggest reducing the $82^4$ possible deterministic wirings for Alice and Bob to only 3152 by simply considering the ones that preserve the PR box, i.e. wirings $W$ such that $\text{PR} \boxtimes_W \text{PR} = \text{PR}$, and then doing a discrete optimization over that smaller set. This smaller set encompasses for instance the wirings $W_{BS}$, $W_{dist}$ but discards $W_\oplus$, $W_\wedge$, $W_{\vee\wedge}$ (see definitions in Subsection 1.4); see also [23, Supplementary Material, I] which mentions that even some optimal wirings are discarded. This technique allows them to analytically prove that many new areas of boxes are collapsing.

(ii) In [23], the authors use a mix of exhaustive search and linear programming. For each of Bob's $82^2$ extremal half-wirings, they apply linear programming to optimize Alice's half-wiring, and then they select the best pair of half-wirings. This allows them to numerically find optimal wirings for any pair of boxes, which leads them to discover new collapsing boxes.

(iii) In our work, we use an efficient variant of the Gradient Descent algorithm, based on Line Search methods, frequent resets, and parallel descents. A limitation in the method from [11] could come from the fact that many wirings are discarded; this is why we choose to take our feasible set to be the entire set of mixed wirings $W \subseteq [0, 1]^{32}$. In [23, Supplementary Material, II], the authors implement a sequence of different optimal wirings, which we do similarly in what we call later Task A, but we also implement a uniform version of it in Task B, which allows us to find a single optimal wiring for a whole region of boxes (instead of a sequence of wirings) and then to prove by hand the collapse of communication complexity for those boxes. In this manner, we recover both the numerical results of [23] (see details in Subsection 4.1) and the analytical results of [11] (see details in Subsection 4.2).
## 3.1 Goals of the Algorithms

Task A. To prove that a box P is collapsing, a particular case of Proposition 8 says that it is enough to find a finite sequence of wirings ($W_1, \dots, W_N$) such that the following box is collapsing:

$$P_{N+1} := ((P \boxtimes_{W_1} P) \boxtimes_{W_2} P) \boxtimes_{W_3} \dots \boxtimes_{W_N} P.$$

Note that we need to specify the parenthetization because the different products $\boxtimes_{W_i}$ are potentially non-associative. Among the numerous possibilities, we choose the parenthesization on the left because it is easy to implement and because it is the best one when the wiring is $W_{BS}$, see Theorem 13. This algorithm will consist in an iterative construction of the sequence $(W_i)_i$: first, find a wiring $W_1$ such that the CHSH-value of the box $P_2 := P \boxtimes_{W_1} P$ is the highest possible, then find $W_2$ such that the CHSH-value of the box $P_3 := P_2 \boxtimes_{W_2} P$ is the highest possible, so on and so forth until the N-th iteration. If the CHSH-value of the box $P_{N+1}$ is above the threshold $\frac{3+\sqrt{6}}{6} \approx 0.91\%$, we know that communication complexity collapses [10], so the starting box P is collapsing as well. Otherwise, we cannot conclude whether P is collapsing or not.

Task B. The goal of this algorithm is essentially the same as the first one, but we add a strong constraint: we want all the $W_i$ to be the same wiring W:

$$((P \boxtimes_{W} P) \boxtimes_{W} P) \boxtimes_{W} \dots) \boxtimes_{W} P := P^{\boxtimes_{W} N+1}.$$

In that sense, this is a “uniform” version of the first algorithm. The interest of this algorithm is that it helps to give analytical proofs (see Section 4): if the value CHSH($P^{\boxtimes_{W} N}$) is above the threshold $\frac{3+\sqrt{6}}{6} \approx 0.91\%$ for some N, then by continuity of $\boxtimes_{W}$, there is an open neighborhood around P such that for any Q close enough to P we also have that CHSH($Q^{\boxtimes_{W} N}$) is above the threshold, and therefore the whole neighborhood of P is collapsing. This technique will help to discover wide collapsing areas and to provide analytical proofs by hand.

## 3.2 Toy Example ($N = 1$)

In this subsection, we treat the case when there is only one product $\boxtimes_{W}$ between two boxes Q, P $\in \mathcal{N}S$. We detail the maximization algorithm we use: a Projected Gradient Descent. The optimization problem consists in finding $W^*$ as follows:

$$W^* = \underset{W \in \mathcal{W}}{\operatorname{argmax}} \Phi(W). \qquad (12)$$

where the objective function is $\Phi(W) := \text{CHSH}(Q \boxtimes_{W} P)$ for some fixed non-signalling boxes Q, P, and where W is the set of mixed wirings introduced in Definition 4, which we recall below.

The Constraint $W \in \mathcal{W}$. Recall that a mixed wiring W between two boxes Q, P $\in \mathcal{N}S$ is the data of six functions $f_1, f_2, g_1, g_2 : \{0, 1\}^2 \to [0, 1]$ and $f_3, g_3 : \{0, 1\}^3 \to [0, 1]$ satisfying the following non-cyclicity conditions:

$$\forall x, \quad (f_1(x, 0) - f_1(x, 1))(f_2(x, 0) - f_2(x, 1)) = 0, \qquad (13)$$

$$\forall y, \quad (g_1(y, 0) - g_1(y, 1))(g_2(y, 0) - g_2(y, 1)) = 0. \qquad (14)$$

Recall that the corresponding diagram can be found in Figure 2 (b), and that mixed wirings form a set that we denote W. In our algorithms, we view W a real vector with $4 \times 2^2 + 2 \times 2^3 = 32$ variables. This vector stores each value of each function:

$$W = [f_1(0, 0) \ f_1(0, 1) \ f_1(1, 0) \ f_1(1, 1) \ g_1(0, 0) \ \dots]^\top \in \mathbb{R}^{32}. \qquad (15)$$

To satisfy the normalization constraint that the $f_i, g_j$ take value in $[0, 1]$, and the non-cyclicity conditions (13) and (14) (which are non-linear conditions), we implement a projection function $\text{proj} : \mathbb{R}^{32} \to \mathbb{R}^{32}$ in Algorithm 1. Notice that our real code is written in a vectorized fashion
**Algorithm 1:** Projection function proj on the feasible set W. Vectorized version in our GitHub page [9].

**Data:** W = [w₁ ... w₃₂] = [f₁(0, 0) f₁(0, 1) f₁(1, 0) f₁(1, 1) g₁(0, 0) ... g₃(1, 1, 1)] ∈ ℝ³².

**Result:** proj(W) ∈ W.

W ← [max{w₁, 0} ... max{w₃₂, 0}];

W ← [min{w₁, 1} ... min{w₃₂, 1}];

for x ∈ {0, 1} do

if |f₁(x, 0) - f₁(x, 1)| ≤ |f₂(x, 0) - f₂(x, 1)| then f₁(x, 0), f₁(x, 1) ← (f₁(x, 0) + f₁(x, 1))/2;
else f₂(x, 0), f₂(x, 1) ← (f₂(x, 0) + f₂(x, 1))/2;

end

for y ∈ {0, 1} do

if |g₁(y, 0) - g₁(y, 1)| ≤ |g₂(y, 0) - g₂(y, 1)| then g₁(y, 0), g₁(y, 1) ← (g₁(y, 0) + g₁(y, 1))/2;
else g₂(y, 0), g₂(y, 1) ← (g₂(y, 0) + g₂(y, 1))/2;

end

return W

and is difficult to read as such, so we only present the idea here. Moreover, we use the package PyTorch [39] for automatic differentiation.

The Objective Function Φ(W) := CHSH(Q⊠W P). In our algorithms, we view a box P as a 2×2×2×2-tensor: P[a, b, x, y] := P(a, b | x, y) with a, b, x, y ∈ {0, 1}, whose entries are float numbers between 0 and 1. Two things need to be computed separately: Q⊠W P and then CHSH(·). On the one hand, the product P ⊠W P is computed using Equation (9), which we vectorized in our algorithm using five types of operations: tensor transposition T, tensor sum +, tensor product ⊗, contraction of tensors ·, and entry-wise multiplication *; see details in the pdf document of our GitHub page [9]. On the other hand, the function CHSH(·) is a linear function that computes the CHSH-value of a box, implemented with a dot product as follows:

$$ \mathrm{CHSH}(\mathbf{R}) := \frac{1}{4} \sum_{a \oplus b = xy} \mathbf{R}(a, b | x, y) = \langle \mathbf{R}, \mathbf{T} \rangle, $$

where T is the 2 × 2 × 2 × 2-tensor defined as T[a, b, x, y] = 1/4 if a ⊕ b = xy, and = 0 otherwise.

### 3.2.1 Naive Gradient Descent

To gain insight into the complexity of the optimization problem, we begin by studying a basic algorithm, the Projected Gradient Descent, with a small learning rate (α ≪ 1) and a lot of iterations (K ≫ 1). We will obtain a histogram of the frequency of the different results we obtain, see Figure 9 (a).

Projected Gradient Descent. We implement a “projected” version of the Gradient Descent algorithm in order to satisfy the constraint W ∈ W at each step. It simply means that each iteration is projected on the feasible set:

$$ W^{k+1} = \mathrm{proj}(W^k + \alpha \nabla \Phi(W^k)), $$

where α ∈ ℝ is the learning rate. Our implementation can be found in Algorithm 2. We compute the gradient of the objective function using the automatic differentiation Python package `torch.autograd` that provides us with the commands `backward` and `grad`. As we do not have a good intuition of what could be a good wiring W in W to start with given a fixed box P, we take a random initialization: W⁰ is uniformly generated in the hypercube [0, 1]³². As such, the vector W⁰ is not necessarily a well-defined mixed wiring since it does not necessarily satisfy the non-cyclicity conditions (13) and (14), but this problem is fixed after one iteration in the Projected Gradient
**Algorithm 2:** Projected Gradient Descent. More details on our GitHub page [9].

**Data:** $\Phi: \mathbb{R}^{32} \to \mathbb{R}$ objective function, $\alpha \in \mathbb{R}$ learning rate, $K \in \mathbb{N}$ number of iterations, $\varepsilon > 0$ tolerance.

**Result:** $W_{\text{out}} \approx \operatorname{argmax}_{W} \Phi(W) \in W \subseteq \mathbb{R}^{32}$.

$W \sim \mathcal{U}([0, 1]^{32})$;

for $k \in \{0, \dots, K-1\}$ do

<figure><img src="image_12.png" /></figure>

$W_{\text{old}} \leftarrow W$;

$W \leftarrow \text{proj}(W + \alpha \nabla\Phi(W))$ using Algorithm 1;

if $\|W - W_{\text{old}}\|_{\infty} < \varepsilon$ then break;

end

return $W_{\text{out}} := W \in \mathbb{R}^{32}$.

<figure><img src="image_13.png" /><figcaption>Figure 9: Histogram of the evaluations of the objective function $\Phi$ applied at the output $W_{\text{out}}$ of (a) Algorithm 2 and (b) Algorithm 3. As expected, we observe that the latter is more efficient than the former in maximizing $\Phi$, for equivalent computation duration.</figcaption></figure>

Descent algorithm since the wiring is then projected. Otherwise, one can also directly apply **proj** to $W^0$. The notation $W \sim \mathcal{U}(X)$ means that we uniformly generate $W$ in the set $X$.

*Estimating the Proportion of “Good” Outputs.* We use Algorithm 2 with a learning rate $\alpha = 0.01$, a number of iterations of $K = 10^6$, a tolerance of $\varepsilon = 10^{-6}$, and we obtain the histogram presented in Figure 9 (a). Recall that the objective function is $\Phi(W) := \text{CHSH}(Q \otimes_W P)$; this histogram is drawn with $Q = P = pPR + qSR + (1-p-q)I$, where $p = 0.39$ and $q = 0.6$. The number of reruns is $m = 10^3$, done simultaneously in parallel, which is faster than doing $m$ descents one after another$^6$. We observe that the results concentrate on certain discrete values. These values correspond to different attractive points in different basins of attraction (recall that the initial $W$ is taken uniformly at random in $[0, 1]^{32}$). As we want to maximize $\Phi$, we are interested in the highest concentrated value $\approx 0.87$. In that example, we observe that the proportion of starting wirings such that $W_{\text{out}}$ is only $\chi \approx 2/10^3 = 0.2\%$ using this basic Gradient Descent algorithm. This information tells us that the function $\Phi$ is difficult to maximize, which is why we present a more efficient algorithm in the following subsection.

### 3.2.2 More Efficient Algorithm: Line Search with Resets

In this subsection, we present a variant of the Gradient Descent algorithm called Line Search, which we enhance with frequent resets of bad outcomes. See [38] for a standard reference book in numerical optimization. The idea of this algorithm is, instead of always keeping the same $\alpha$, to

<footnote>$^6$In order to do $m$ gradient descents in parallel efficiently, we “parallelize” Algorithm 2: instead of viewing $W$ as a 32-vector, we view it as a $(32 \times m)$-matrix, where each column represents a different wiring. Comparing this method with a naive FOR loop, we observe a factor of 100 in the speed gain. Notice that when the descent is done, one can post-select the best wiring among the $m$ columns of $W_{\text{out}}$. See our GitHub page [9].</footnote>
estimate the best coefficient $\alpha_k$ at each step of the descent:

$$ \left\{ \begin{array}{l} \alpha_k = \underset{\alpha \in \mathbb{R}}{\operatorname{argmax}} \Phi(W^k + \alpha \nabla\Phi(W^k)), \\ W^{k+1} = \operatorname{proj}(W^k + \alpha_k \nabla\Phi(W^k)). \end{array} \right. $$

As we observed in the previous subsection, the proportion $\chi$ of “good” starting wirings is very weak, which is why we apply frequent resets: we do $m = 10^3$ descents in parallel but only $K_{reset} = 100$ steps, then we keep only the best $m \cdot \chi$ wirings and we reset all the others to a new random initialization. Then we repeat that procedure but we reset fewer wirings (say, at the j-th repetition, keep for instance the best $j \cdot m \cdot \chi$ wirings), and we repeat this procedure $1/\chi$ times. In the end, most of the wirings should be in the good basin of attraction, so we can apply one final run of line search, with many more steps so that it converges to the attractor. See Algorithm 3, and we obtain results of Figure 9 (b).

**Algorithm 3:** Line Search with Resets. More details on our GitHub page [9].

**Data:** $\Phi: \mathbb{R}^{32} \to \mathbb{R}$ objective function, $K_{reset} \in \mathbb{N}$ number of iterations before reset, $\chi \in [0, 1]$ proportion of “good” random wirings, $m \in \mathbb{N}$ number of descents in parallel, $M \in \mathbb{N}$ number of iterations to compute the best learning rate $\alpha^*$.

**Result:** $W_{out} \in \mathbb{R}^{32 \times m}$, where each column is $\approx \operatorname{argmax}_W \Phi(W)$.

$W = (32 \times m$ null matrix), whose columns are denoted $W_i$;

for $j \in \{0, \dots, \lfloor 1/\chi \rfloor - 1\}$ do

$W \leftarrow$ among the $m$ columns of $W$, keep the $j \cdot m \cdot \chi$ ones giving the highest values for the objective function $\Phi$, and reset all the other columns randomly with $\mathcal{U}([0, 1]^{32})$;

if $j = \lfloor 1/\chi \rfloor - 1$ then $K_{reset} \leftarrow 10 \cdot K_{reset}$;

for $k \in \{0, \dots, K_{reset} - 1\}$ do

for $i \in \{0, \dots, m-1\}$ do $\alpha_i^* \leftarrow \operatorname{argmax}_{\alpha>0} \Phi(W_i + \alpha \nabla\Phi(W_i))$ using $M$ iterations;

$W \leftarrow [\operatorname{proj}(W_i + \alpha_i^* \nabla\Phi(W_i))]_i$ using Algorithm 1;

end

end

return $W_{out} = W \in \mathbb{R}^{32 \times m}$.

### 3.3 Task A

Algorithm A is presented in Algorithm 4; it simply consists in applying the toy case $Q \boxtimes P$ from the previous subsection recursively $N$ times. We want to find a sequence of wirings $W_1, \dots, W_N$ such that the CHSH-value is above the following threshold:

$$ \mathrm{CHSH} \left( \underbrace{\left( \left( (P \boxtimes P) \boxtimes P) \boxtimes \dots \boxtimes P \right) \right)}_{=: P_{N+1}} \right) > \frac{3 + \sqrt{6}}{6}. $$

A consequence is that the box P collapses communication complexity [10]. Notice that for some boxes $P \in \mathcal{NS}$, it might not be possible to find such a sequence of wirings because it is impossible to distill them by any means. This algorithm is used in Subsection 4.1 in order to plot the new regions of collapsing nonlocal boxes.

**Remark 20.** Going further, once we find $(W_1^*, \dots, W_N^*)$, it is possible to do a “backward” process: for all $i \in \{1, \dots, N\}$, fix $W_j^*$ for $j \neq i$, optimize the function $W_i \mapsto \mathrm{CHSH}(P_{N+1})$ and update $W_i^*$. It is also possible to use neural network methods to optimize all the $W_i$ “at the same time”.
**Algorithm 4:** Task A. More details on our GitHub page [9].

**Data:** $P \in [0, 1]^{2+2+2+2}$ box, $N \in \mathbb{N}$ number of box products, ($K_{\text{reset}}, \chi, m, M$) parameters for Algorithm 3.

**Result:** $[W_1^*, \dots, W_n^*] \in \mathcal{W}^n$ for some $n \le N$.

$P_1 \leftarrow P$;

for $n \in \{1, \dots, N\}$ do

$W_n^* \in [0, 1]^{32} \leftarrow \operatorname*{argmax}_W \operatorname{CHSH}(P_n \otimes_W P)$ by picking the best column among the $m$ columns of the output $W_{\text{out}} \in \mathbb{R}^{32 \times m}$ of Algorithm 3;

$P_{n+1} \leftarrow P_n \otimes_{W_n^*} P$;

if $\operatorname{CHSH}(P_{n+1}) > \frac{3+\sqrt{6}}{6}$ then return $[W_1^*, \dots, W_n^*]$;

end

return "Nothing found."

## 3.4 Task B

Task B is a “uniform” version of task A, in the sense that we want all the $W_i$'s to be the same. In order words, we want to find a wiring $W$ and an integer $N$ such that:

$$ \operatorname{CHSH} \left( \underbrace{(( (P \otimes_W P) \otimes_W P) \otimes_W \dots) \otimes_W P}_{=: P \otimes_{W(N+1)}} \right) > \frac{3+\sqrt{6}}{6}. $$

This algorithm is used in the proof of Theorem 29 in order to find appropriate collapsing wirings for the analytical proof.

*Idea of the Algorithm.* First, find a wiring $W_1^* = \operatorname*{argmax}_W \operatorname{CHSH}(P \otimes_W P)$ with a Gradient Descent algorithm, and then evaluate the powers of $P$ with that wiring $W_1^*$ until $N+1$, i.e. compute $\operatorname{CHSH}(P^{\otimes W_1^*})$ for $n=1, \dots, N+1$. If one of those evaluations is greater than the threshold $(3+\sqrt{6})/6$ from [10], then we can stop the algorithm, it means that the wiring $W_1^*$ achieves the goal. Otherwise, compute $W_2^* = \operatorname*{argmax}_W \operatorname{CHSH}(P^{\otimes W_2^*})$ and repeat the same evaluation process of the powers of $P$ as in the previous step. Proceed like this until computing $W_M^*$, where $M \in \mathbb{N}$ is some hyper-parameter. Typically, we take $M \le N$ because it is a lot faster to evaluate the $N$-th power of $P$ than to optimize the $N$-th power of $P$. See the details in Algorithm 5.

**Algorithm 5:** Task B. More details on our GitHub page [9].

**Data:** $P \in [0, 1]^{2+2+2+2}$ box, $N \in \mathbb{N}$ maximal tested box power, $L \in \mathbb{N}$ maximal optimized box power, ($K_{\text{reset}}, \chi, m, M$) parameters for Algorithm 3.

**Result:** $W^* \in \mathcal{W}$.

for $\ell \in \{1, \dots, L\}$ do

$W_\ell^* \leftarrow \operatorname*{argmax}_W \operatorname{CHSH}(P^{\otimes W_\ell+1})$ using Algorithm 3;

for $n \in \{1, \dots, N+1\}$ do

| if $\operatorname{CHSH}(P^{\otimes W_\ell^*}) > \frac{3+\sqrt{6}}{6}$ then return $W_\ell^*$;

end

end

return "Nothing found."

## 4 New Collapsing Boxes

In this section, we present collapsing boxes found in two different ways. (i) First with a numerical approach, using the algorithms (Section 3). (ii) Then with an analytical approach, using the algebra of boxes (Section 1) and the orbit of a box (Section 2).
## 4.1 Numerical Results

Using Algorithm 4 that addresses Task A, we obtain many collapsing boxes. Some samples are drawn in Figure 10 on some slices of the non-signalling set $\mathcal{NS}$, but note that this algorithm also applies more generally to any desired slice. As previously mentioned, this work is concurrent and independent of the work of [23]. In the drawings, some boxes are denoted $P_L$ and $P_{NL}$, let us recall their definition here. The local set $\mathcal{L}$ and the non-signalling set $\mathcal{NS}$ are polytopes, i.e. the convex hull of a finite number of extremal points. The first set $\mathcal{L}$ admits exactly 16 extremal points, called local extreme points and denoted $P_L^{\mu,\nu,\sigma,\tau}$, where $\mu, \nu, \sigma, \tau \in \{0,1\}$. These 16 points are as well extremal points of $\mathcal{NS}$, together with 8 additional extremal points, called non-local extreme points and denoted $P_{NL}^{\mu,\nu,\sigma}$. They are defined as follows [2, 3]:

$$ \bullet \text{ Local extremal points: } P_L^{\mu,\nu,\sigma,\tau}(a, b | x, y) := \begin{cases} 1 & \text{if } a = \mu x \oplus \nu \text{ and } b = \sigma y \oplus \tau, \\ 0 & \text{otherwise,} \end{cases} \tag{16} \\ \bullet \text{ Nonlocal extremal points: } P_{NL}^{\mu,\nu,\sigma}(a, b | x, y) := \begin{cases} 1/2 & \text{if } a \oplus b = xy \oplus \mu x \oplus \nu y \oplus \sigma, \\ 0 & \text{otherwise.} \end{cases} $$

Note that $P = P_{NL}^{000}$ and $P_0 = P_L^{0000}$ and $P_1 = P_L^{0101}$ (we remove the commas in the superscripts for the sake of simplicity of notations).

<figure><img src="image_14.png" /><figcaption>Figure 10: In orange are drawn the collapsing boxes outputted by Algorithm 4. Each drawing represents a different slice of $\mathcal{NS}$; the extreme points of the triangles indicate which slice is drawn and the definition of the boxes $P_{NL}$ can be found in Equation (16). The three graphs have the same color legend, displayed at the center, and they are all configured with the same algorithm parameters ($K_{reset}$, $\chi$, $m$, $M$, $N$), detailed at the top. We adopt the following convention: (i) boxes that are numerically determined are drawn with dots, (ii) boxes that are analytically determined are drawn in plain regions (there exist explicit equations describing those regions). Notice that the left drawing is similar to [23, Figure 3], which was found using a different algorithm as detailed in Remark 19. The quantum set $\mathcal{Q}$ (in pink) is drawn using formulas from [33]. References: $[BBLMTU06]=[10]$, $[BS09]=[13]$, $[BBP23]=[8]$.</figcaption></figure>

Observe in Figure 10 that, depending on the chosen slice, the collapsing area does not always have the same “shape” nor the same “area”. Moreover, notice in the graphs that there seems to exist a collapsing area in the neighborhood below the diagonal segments joining PR and respectively SR, $P_0$, $P_1$. This is actually true. Indeed, we analytically show below in Theorem 23 that those three segments are collapsing, and we also know that the box product $P \boxtimes_W \mathcal{Q}$ is continuous in $P$ and $\mathcal{Q}$ for any $W$ (it is even bilinear, recall the expression in (9)), so distillation protocols are continuous and in some sense the orbits are also “continuous”, hence there exists an open neighborhood below these diagonal segments that collapses communication complexity.

*Remark 21 (Continuous extension of a finite collapsing set).* The algorithm only provides us with
finitely many collapsing boxes, but we can still deduce a continuous “extension” of that collapsing set. Indeed, as explained in Subsection 2.2, if we know that a box $P \in \mathcal{NS}$ collapses communication complexity, then we also know that the cone $C_P$ is collapsing, where $C_P$ denotes a certain cone taking origin at $P$ represented in Figure 6 (b). As a consequence, if we list the collapsing boxes $\{P_k\}_{1 \le k \le K}$ obtained by numerical means, we can deduce what follows:

The union of cones $\bigcup_{k=1}^K C_{P_k}$ is a collapsing set.

## 4.2 Analytical Results

### 4.2.1 The Triangle $PR, P_0, P_1$ is Collapsing

In this subsection, we extend the result [13] from Brunner and Skrzypczyk, who showed that any box in the segment joining the boxes $PR$ and $SR := (P_0 + P_1)/2$ is collapsing (except the box $SR$, which is classical). In the following theorem, we recover a result from [11] stating that any box in the triangle joining the boxes $PR, P_0, P_1$ is collapsing (except the boxes in the segment joining $P_0$ and $P_1$, which are classical), with a new proof, based on the algebra of boxes. Recall that $PR$ is the non-signalling box that outputs $(a, b)$ such that $a \oplus b = xy$ when $(x, y)$ is inputted, and $P_0$ and $P_1$ are respectively the deterministic boxes that output $(0, 0)$ and $(1, 1)$ independently of the inputs. Recall also that the convex hull of a set $\{Q_1, \dots, Q_N\}$ is the set of all possible convex combinations of these $Q_i$:

$$ \mathrm{Conv}\{Q_1, \dots, Q_N\} := \left\{ \sum_{i=1}^{N} q_i Q_i \text{ such that } q_i \ge 0 \text{ and } \sum_i q_i = 1 \right\}, $$

and the affine hull of $\{Q_1, \dots, Q_N\}$ has the same definition but without the non-negativity constraint:

$$ \mathrm{Aff}\{Q_1, \dots, Q_N\} := \left\{ \sum_{i=1}^{N} q_i Q_i \text{ such that } q_i \in \mathbb{R} \text{ and } \sum_i q_i = 1 \right\} \supset \mathrm{Conv}\{Q_1, \dots, Q_N\}. $$

**Proposition 22.** The triangle $C := \mathrm{Conv}\{PR, P_0, P_1\}$ is a face on the boundary of $\mathcal{NS}$.

*Proof.* First, we prove the equality between the sets $C$ and $A := \mathcal{NS} \cap \mathrm{Aff}\{PR, P_0, P_1\}$, meaning that the convex hull $C$ is actually a slice of $\mathcal{NS}$. The first inclusion $C \subseteq A$ is trivial because the three points $PR, P_0, P_1$ are in $\mathcal{NS}$ and because $\mathcal{NS}$ is a polytope so it is stable under taking convex combination. Conversely, recall that by definition $\mathrm{CHSH}(P) := \frac{1}{4} \sum_{a \oplus b = xy} P(a, b | x, y)$, and $\mathrm{CHSH}'(\cdot)$ and $\mathrm{CHSH}''(\cdot)$ are defined similarly but with respective summand conditions $a \oplus b = (x \oplus 1) \cdot (y \oplus 1)$ and $a \oplus b = x \cdot (y \oplus 1)$. As these three functions are linear, they preserve alignment and convexity. It means that if a box $P$ is of the form $P = \sum_i q_i Q_i$ for some reals $q_i$ and boxes $Q_i$, then $\mathrm{CHSH}(P) = \sum_i q_i \mathrm{CHSH}(Q_i)$, and similarly with $\mathrm{CHSH}'$ and $\mathrm{CHSH}''$. We apply the preservation of alignment in Figure 11 representing the 24 extremal points of $\mathcal{NS}$ [3], and we obtain the following inclusions:

$$ (a) \quad A \subseteq \mathrm{Conv}\{PR, P_0, P_1, P_L^{1011}, P_L^{1110}, P_{NL}^{111}\}; $$

$$ (b) \quad A \subseteq \mathrm{Conv}\{PR, P_0, P_1, P_L^{1000}, P_L^{1101}, P_{NL}^{100}\}. $$

Now, taking the intersection, we obtain $A \subseteq C$, which yields the wanted equality $A = C$, and $C$ is indeed a slice of $\mathcal{NS}$.

It remains to show that the slice $C$ is included in the boundary $\partial \mathcal{NS}$, so that it is indeed a face. Assume that there is a point $P$ in $C$ of the form $P = qQ_1 + (1-q)Q_2$ with $q > 0$ and $Q_1, Q_2 \in \mathcal{NS}$. Applying the convexity preservation property of $\mathrm{CHSH}(\cdot)$, $\mathrm{CHSH}'(\cdot)$, $\mathrm{CHSH}''(\cdot)$ in Figure 11, we obtain the following two necessary conditions:

$$ (a) \quad Q_1, Q_2 \in \mathrm{Conv}\{PR, P_0, P_1, P_L^{1011}, P_L^{1110}, P_{NL}^{111}\}; $$

$$ (b) \quad Q_1, Q_2 \in \mathrm{Conv}\{PR, P_0, P_1, P_L^{1000}, P_L^{1101}, P_{NL}^{100}\}. $$
<figure><img src="image_15.png" /><figcaption>Figure 11: Computation of the CHSH-, CHSH'- and CHSH''- values of the 24 extremal points of $\mathcal{NS}$ [3], where by definition $\text{CHSH}(P) := \frac{1}{4} \sum_{a \oplus b = xy} P(a, b | x, y)$, and $\text{CHSH}'$ and $\text{CHSH}''$ are defined similarly but with respective summand conditions $a \oplus b = (x \oplus 1) \cdot (y \oplus 1)$ and $a \oplus b = x \cdot (y \oplus 1)$.</figcaption></figure>

Then, taking the intersection, we get $Q_1, Q_2 \in C$ and therefore $C \subseteq \partial \mathcal{NS}$ as wanted. $\square$

**Theorem 23.** The face $C$ of $\mathcal{NS}$ is collapsing, except in the segment $\text{Conv}\{P_0, P_1\}$.

<figure><img src="image_16.png" /><figcaption>Figure 12: Illustration of Theorem 23.</figcaption></figure>

*Proof.* Denote $T := \text{Conv}\{\text{PR}, P_0, P_1\} \setminus \text{Conv}\{P_0, P_1\}$, and consider a convex combination of the form $P_{\alpha, \beta} := \alpha \text{PR} + \beta P_0 + (1 - \alpha - \beta) P_1 \in T$ with $\alpha, \beta \ge 0$ and $\alpha \ne 0$ and $\alpha + \beta \le 1$. Similarly fix other convex coefficients $(\alpha_0, \beta_0) := u_0$ with the same conditions. We want to build a sequence $(u_k)_k = ((\alpha_k, \beta_k))_k$ such that $(P_{u_k})_k$ tends to the PR box. Denote $\boxtimes$ the box product induced by the wiring $W_{BS}$ (see definition in Subsection 1.4). By bilinearity of $\boxtimes$ and using the multiplication table in Figure 4, computations lead to $P_{\alpha, \beta} \boxtimes P_{\alpha_0, \beta_0} = P_{\tilde{\alpha}, \tilde{\beta}}$ where:

$$ \begin{bmatrix} \tilde{\alpha} \\ \tilde{\beta} \end{bmatrix} = A \begin{bmatrix} \alpha \\ \beta \end{bmatrix} + b, \quad A := \begin{bmatrix} 1 - \alpha_0 & -\alpha_0 \\ -1 + \alpha_0 + \beta_0 & -1 + \frac{3}{2}\alpha_0 + 2\beta_0 \end{bmatrix}, \quad b := \begin{bmatrix} \alpha_0 \\ 1 - \alpha_0 - \beta_0 \end{bmatrix}. $$

From this remark, we define the following sequence:

$$ u_0 := (\alpha_0, \beta_0), \quad u_{k+1} = A u_k + b. $$

We easily identify that $\ell := (1, 0)$ is a fixed point of $x \mapsto Ax + b$, so it yields:

$$ u_{k+1} - \ell = (A u_k + b) - (A \ell + b) = A(u_k - \ell) = A^{k+1}(u_0 - \ell), $$

where the last equality follows from an induction on $k$. But the matrix $A$ admits exactly two distinct$^7$ eigenvalues $\lambda_1 = 1 - a/2$ and $\lambda_2 = -1 + a + 2b$. So $A$ is diagonalizable, and its power

<footnote>$^7$The eigenvalues $\lambda_1$ and $\lambda_2$ are distinct because otherwise we would have $2 = \frac{3}{2}(a+b) + \frac{b}{2}$, which is achieved only if both $a+b=1$ and $b=1$, which is equivalent to $a=0$ and $b=1$ and which contradicts the assumption $a \ne 0$.</footnote>
$A^k = P[\begin{matrix} \lambda_1^k & 0 \\ 0 & \lambda_2^k \end{matrix}]P^{-1}$ tends to the null matrix because $|\lambda_1|, |\lambda_2| < 1$, where $P$ is an invertible matrix. Hence, from the above equation, the sequence $(u_k)_k$ tends to $\ell$, and by continuity we have that the sequence of boxes $(P_{u_k})_k \subseteq \mathbb{R}^{16}$ converges to $P_\ell = \text{PR}$. But Brassard et al. showed that there is an open neighbor around PR that collapses communication complexity [10]. Therefore, we know that the sequence $(P_{u_k})_k$ reaches this collapsing neighbor for some $k$ large enough, and using Proposition 8 we conclude that any starting box $P_{u_0} \in \mathcal{T}$ is indeed collapsing. $\square$

**Remark 24** (Why is $\text{Conv}\{\mathbf{P}_0, \mathbf{P}_1\}$ non-collapsing?). It is not surprising that the boundary segment $\text{Conv}\{\mathbf{P}_0, \mathbf{P}_1\}$ of $\mathcal{T}$ is not in the collapsing area because this segment is included in the local set $\mathcal{L}$, which is itself included in the quantum set $\mathcal{Q}$, for which it is known that communication complexity does not collapse [17].

**Remark 25** (Left multiplication does not give the same result). In the proof, we defined our sequence of boxes $(P_{u_k})_k$ based on right multiplication. One could instead try to do the left multiplication: $P_{u_{k+1}} = P_{u_0} \otimes P_{u_k}$. In that case, similar computations lead to:

$$u_{k+1} = A'u_k + b', \quad A' := \begin{bmatrix} 1 - \alpha_0 - \beta_0 & 0 \\ -1 + \alpha_0 + \frac{3}{2}\beta_0 & -1 + \alpha_0 + 2\beta_0 \end{bmatrix}, \quad b' := \begin{bmatrix} \alpha_0 \\ 1 - \alpha_0 - \beta_0 \end{bmatrix}.$$

The map $x \mapsto A'x + b'$ admits a unique fixed point $\ell' := (\frac{\alpha_0}{\alpha_0+\beta_0}, \frac{\beta_0}{2(\alpha_0+\beta_0)})$ (no division by 0 since $\alpha_0 > 0$). The matrix $A'$ is already in the triangular form, its eigenvalues are $\lambda'_1 := 1 - \alpha_0 - \beta_0$ and $\lambda'_2 := -1 + \alpha_0 + 2\beta_0$, and again $|\lambda'_1|, |\lambda'_2| < 1$ so $P_{\alpha_k, \beta_k} \to P_{\ell'}$. But in that case $P_{\ell'}$ is not the PR box, so we cannot apply Ref. [10] to build a collapsing protocol from any starting box.

**Remark 26** (Pairwise multiplication gives the same result). It is also possible to try the pairwise multiplication: $P_{u_{k+1}} = P_{u_k} \otimes P_{u_k}$, which is the way the authors of [13] originally proved that the segment $\text{Conv}\{\text{PR}, \text{SR}\} \setminus \{\text{SR}\}$ is collapsing. But this pairwise multiplication does not behave as well as with the right multiplication, iterations $u_k = (\alpha_k, \beta_k)$ are non-affine here:

$$u_{k+1} = \begin{bmatrix} -1 & -1 & 0 \\ 1 & 5/2 & 2 \end{bmatrix} \begin{bmatrix} \alpha_k^2 \\ \alpha_k \beta_k \\ \beta_k^2 \end{bmatrix} + \begin{bmatrix} 2 & 0 \\ -2 & -2 \end{bmatrix} u_k + \begin{bmatrix} 0 \\ 1 \end{bmatrix}.$$

Nevertheless, the result still holds using this pairwise multiplication, but the proof we found is much more technical, see Appendix B.

The intersection of the quantum set $\mathcal{Q}$ with the boundary $\partial\mathcal{NS}$ of the non-signalling set was recently studied in [15]. Moreover, the notion of the quantum void was introduced and studied in [11, 42], which consist in a subset of $\partial\mathcal{NS}$ for which all quantum correlations are actually local. A direct corollary of the previous theorem allows us to single out the quantum correlations of the face $C = \text{Conv}\{\text{PR}, \mathbf{P}_0, \mathbf{P}_1\}$: they are exactly the ones in the segment $\text{Conv}\{\mathbf{P}_0, \mathbf{P}_1\}$. Indeed, on the one hand, it is known that quantum correlations do not collapse communication complexity [17], and on the other hand, local correlations are particular cases of quantum correlations, so we recover the following statement from [42] with a new proof, based on communication complexity:

**Corollary 27.** The face $C = \text{Conv}\{\text{PR}, \mathbf{P}_0, \mathbf{P}_1\} \subseteq \partial\mathcal{NS}$ is a quantum void:

$$\mathcal{Q} \cap C = \text{Conv}\{\mathbf{P}_0, \mathbf{P}_1\}. \quad \square$$

### 4.2.2 Other Collapsing Triangles

The fact that the triangle $\mathcal{T} := \text{Conv}\{\text{PR}, \mathbf{P}_0, \mathbf{P}_1\} \setminus \text{Conv}\{\mathbf{P}_0, \mathbf{P}_1\}$ is collapsing induces many further collapsing triangles. In this subsection, we give some examples of such collapsing triangles, thus recovering some results of [11] with a new proof, based on the algebra of boxes.
**Proposition 28.** Let P, Q, R be three boxes. If there exists a wiring $W \in W$ that induces the multiplication table below, then the triangle $\text{Conv}\{P, Q, R\} \setminus \text{Conv}\{Q, R\}$ is collapsing.

<table><thead><tr><th></th><th>P</th><th>Q</th><th>R</th></tr></thead><tbody><tr><th>P</th><td>P</td><td>P</td><td>P</td></tr><tr><th>Q</th><td><sup>1</sup>&frasl;<sub>2</sub>(Q + R)</td><td>Q</td><td>R</td></tr><tr><th>R</th><td>P</td><td>R</td><td>Q</td></tr></tbody></table>

*Proof.* For any $\alpha, \beta \in \mathbb{R}$, consider the convex combination $P_{\alpha,\beta} := \alpha P + \beta Q + (1-\alpha-\beta)R$. We have the equality $P_{\alpha,\beta} \boxtimes P_{\alpha_0,\beta_0} = P_{\tilde{\alpha},\tilde{\beta}}$, with the same coefficients $(\tilde{\alpha}, \tilde{\beta})$ as in the proof of Theorem 23. Then, applying the same proof gives the desired result. □

**Theorem 29.** All the triangles drawn in Figure 13 are collapsing.

<figure><img src="image_17.png" /><figcaption>Figure 13: Examples of collapsing triangles, together with wirings that can be used in Proposition 28 to show a collapse of communication complexity. The definition of the boxes $P_L$ and $P_{NL}$ can be found in Equation (16).</figcaption></figure>

*Proof.* The proof follows directly from Proposition 28 applied to what follows:

<table><thead><tr><th>Triangle</th><th>P</th><th>Q</th><th>R</th><th>Wiring W ∈ W ⊆ ℝ<sup>32</sup></th></tr></thead><tbody><tr><th>T</th><td>PR</td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>W<sub>BS</sub> = [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0]</td></tr><tr><th>T<sub>1</sub></th><td>PR</td><td>P<sub>L</sub><sup>0111</sup></td><td>P<sub>0</sub></td><td>W<sub>1</sub> = [1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0]</td></tr><tr><th>T<sub>2</sub></th><td>PR</td><td>P<sub>0</sub></td><td>P<sub>L</sub><sup>1101</sup></td><td>W<sub>2</sub> = [0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]</td></tr><tr><th>T<sub>3</sub></th><td>PR</td><td>P<sub>L</sub><sup>0010</sup></td><td>P<sub>L</sub><sup>1011</sup></td><td>W<sub>3</sub> = [0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1]</td></tr><tr><th>T<sub>4</sub></th><td>PR</td><td>P<sub>L</sub><sup>1000</sup></td><td>P<sub>L</sub><sup>1110</sup></td><td>W<sub>4</sub> = [0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]</td></tr></tbody></table>

where the notation $W \in \mathbb{R}^{32}$ comes from Equation (15). See a representation of these wirings in Figure 13, bottom row. □

The wirings of Figure 13 are arbitrary examples of collapsing wirings that were obtained using Algorithm 5; many more wirings can be found in other triangles of $\mathcal{N}S$ using the same algorithm, which is accessible via our GitHub page [9]. Notice that these wirings are all different from the ones used in the proof of [11]. Now, an interesting problem would be to understand better the structure of the set $W$ so that, given a triangle in $\mathcal{N}S$, we know how to construct a collapsing wiring $W$ without using a search algorithm.
Conclusion

Our new algebraic perspective on nonlocal boxes allowed us to discover a surprising structure of
what we called the orbit of a box, with some strong alignment and parallelism properties (see
Figure 7). As a consequence, this deeper understanding of the algebraic structure of nonlocal
boxes enabled us to recover in Section 4 some collapsing regions of $\mathcal{NS}$ that were recently also
found in [11, 23]—for instance boxes in the triangle joining $\mathbf{PR}, \mathbf{P}_0, \mathbf{P}_1$ (except boxes in the segment
$\mathbf{P}_0, \mathbf{P}_1$). The importance of our results is emphasized by considering the many known impossibility
results [6, 34, 46]. Note also that according to our present intuition of Nature [6, 10, 13, 18], a
direct consequence is that the collapsing boxes we presented are unlikely to exist in Nature.

We made advances towards answering the open question of determining which nonlocal boxes
do indeed collapse communication complexity, but there is still a gap to be filled: for instance, as
plotted in light blue in Figure 10, there are still regions of $\mathcal{NS}$ for which it is unknown whether
there is a collapse of communication complexity.

Further work includes the study of the “square root” of a box: here we introduced and studied
the properties of the product $P \boxtimes P$, but one might be interested in finding all the boxes $Q$ such
that $Q \boxtimes_W Q = P$ for some fixed wiring $W \in W$. If one knows that $P$ is collapsing, then the wiring
$W$ yields a collapsing protocol, thus all the square roots $Q$ are also collapsing.

Another interesting problem is the one mentioned at the end of Section 4. Given a triangle of
boxes in $\mathcal{NS}$, we already provided in Section 3 and in our GitHub page [9] an algorithm that intends
to find a wiring $W$ that makes this triangle collapse communication complexity. Now, it would be
interesting to address the question of how to construct such a collapsing wiring $W$ without using a
search algorithm, simply by knowing the target triangle of $\mathcal{NS}$. This can then help to understand
better the structure of the set $W$ and importantly to better understand protocols for correlation
distillation.

In Subsection 4.2, we give examples of collapsing sets of dimension $d = 2$ (triangles). An open
question from [11] consists in finding higher-dimensional sets of boxes that are all distillable to the
PR box, which therefore collapses CC. For dimension $d = 3$, the authors provide explicit examples
of distillable sets, but it is still unknown whether these sets are collapsing. For dimensions $d \ge 4$,
they prove that distillable quantum voids are impossible due to the presence of isotropic boxes.

Another interesting problem would be to generalize and study the notion of “product of boxes”
with more than two boxes. Indeed, our study is limited to wirings connecting two boxes, but it is
possible to consider more general wirings, connecting *n* boxes, which are known to be strictly more
powerful: for instance, some genuine depth-3 wirings have significance in the context of trivial
communication complexity [23]. As a consequence, it may be that the multi-product of boxes
$W(P_1, \dots, P_n)$ gives rise to similar structures of orbits as the one we found in Figure 7, which would
be useful in the study of *n*-box distillation protocols.

In this work, we chose to study the principle of communication complexity. Although this
principle alone cannot rule out the quantum set [36], a clever idea would be to combine it with
other principles, such as *nonlocal computation* [32], *information causality* [28, 40], *macroscopic
locality* [37], *local orthogonality* [26], *nonlocality swapping* [47], *many-box locality* [49], in working
towards a comprehensive information-based description of Quantum Mechanics.

Acknowledgements

We thank Mirjam Weilenmann for the many helpful comments during the finalization process of the
manuscript. We also thank Giorgos Eftaxias for comments on a preliminary version of this work. We
acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC),
[funding reference number ALLRP 580876 - 22]. This work was also supported by the MITACS grant
FR113029, and by the ANR projects ESQuisses, grant number ANR-20-CE47-0014-01. P.B. was supported
by the Institute for Quantum Technologies in Occitanie. A.B. acknowledges the support of the Air Force
Office of Scientific Research under award number FA9550-20-1-0375. R.C. recognizes support from the
ANR-3IA Artificial and Natural Intelligence Toulouse Institute. I.N. was supported by STARS, grant
number ANR-20-CE40-0008, and by the PHC program Star (Applications of random matrix theory and
abstract harmonic analysis to quantum information theory). C.P. was supported by the ANR projects
Q-COAST ANR- 19-CE48-0003, “Quantum Trajectories” ANR-20-CE40-0024-01, and “Investissements
d’Avenir” ANR-11-LABX-0040 of the French National Research Agency.
References

[1] Jonathan Allcock, Nicolas Brunner, Noah Linden, Sandu Popescu, Paul Skrzypczyk, and Tamás Vértesi. “Closed sets of nonlocal correlations”. In: *Phys. Rev. A* 80 (6 Dec. 2009), p. 062107. doi: 10.1103/Phys-RevA.80.062107.

[2] Jonathan Allcock, Nicolas Brunner, Marcin Pawlowski, and Valerio Scarani. “Recovering part of the boundary between quantum and nonquantum correlations from information causality”. In: *Phys. Rev. A* 80 (4 Oct. 2009), p. 040103. doi: 10.1103/PhysRevA.80.040103.

[3] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, and David Roberts. “Non-local correlations as an information-theoretic resource”. In: *Phys. Rev. A* 71 (2 Feb. 2005), p. 022101. doi: 10.1103/PhysRevA.71.022101.

[4] Jonathan Barrett and Stefano Pironio. “Popescu-Rohrlich Correlations as a Unit of Nonlocality”. In: *Phys. Rev. Lett.* 95 (14 Sept. 2005), p. 140401. doi: 10.1103/PhysRevLett.95.140401.

[5] Mohammad Bavarian and Peter W. Shor. “Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH”. In: *Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science*. ITCS ’15. Rehovot, Israel: Association for Computing Machinery, 2015, pp. 123–132. ISBN: 9781450333337. doi: 10.1145/2688073.2688112.

[6] Salman Beigi and Amin Gohari. “Monotone Measures for Non-Local Correlations”. In: *IEEE Transactions on Information Theory* 61.9 (2015), pp. 5185–5208. doi: 10.1109/TIT.2015.2452253.

[7] Pierre Botteron. “Nonlocal Boxes and Communication Complexity”. Under the supervision of Anne Broadbent, Ion Nechita and Clément Pellegrini. MA thesis. Université Paul Sabatier (Toulouse), June 2022. URL: https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf.

[8] Pierre Botteron, Anne Broadbent, and Marc-Olivier Proulx. “Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity”. In: *Phys. Rev. Lett.* 132 (7 2024), p. 070201. doi: 10.1103/Phys-RevLett.132.070201.

[9] Pierre Botteron and Réda Chhaibi. *GitHub page*. [Accessed: November 2023]. URL: https://github.com/Pierre-Botteron/Algebra-of-Boxes-code.

[10] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp, and Falk Unger. “Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial”. In: *Phys. Rev. Lett.* 96 (25 June 2006), p. 250401. doi: 10.1103/PhysRevLett.96.250401.

[11] Samurá Brito, George Moreno, Ashutosh Rai, and Rafael Chaves. “Nonlocality distillation and quantum voids”. In: *Phys. Rev. A* 100 (1 July 2019), p. 012102. doi: 10.1103/PhysRevA.100.012102.

[12] Nicolas Brunner, Daniel Cavalcanti, Alejo Salles, and Paul Skrzypczyk. “Bound Nonlocality and Activation”. In: *Phys. Rev. Lett.* 106 (2 Jan. 2011), p. 020402. doi: 10.1103/PhysRevLett.106.020402.

[13] Nicolas Brunner and Paul Skrzypczyk. “Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity”. In: *Physical Review Letters* 102.16 (Apr. 2009). ISSN: 1079-7114. doi: 10.1103/phys-revlett.102.160403.

[14] Harry Buhrman and Serge Massar. “Causality and Tsirelson’s bounds”. In: *Phys. Rev. A* 72 (5 Nov. 2005), p. 052103. doi: 10.1103/PhysRevA.72.052103.

[15] Kai-Siang Chen, Gelo Noel M. Tabia, Chellasamy Jebarathinam, Shiladitya Mal, Jun-Yi Wu, and Yeong-Cherng Liang. “Quantum correlations on the no-signaling boundary: self-testing and more”. In: *Quantum* 7 (July 2023), p. 1054. ISSN: 2521-327X. doi: 10.22331/q-2023-07-11-1054.

[16] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. “Proposed Experiment to Test Local Hidden-Variable Theories”. In: *Phys. Rev. Lett.* 23 (15 Oct. 1969), pp. 880–884. doi: 10.1103/Phys-RevLett.23.880.

[17] Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp. *Quantum Entanglement and the Communication Complexity of the Inner Product Function*. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 61–74. ISBN: 978-3-540-49208-5. doi: 10.1007/3-540-49208-9+4.

[18] Wim van Dam. “Nonlocality & Communication Complexity”. Ph.D. thesis. Departement of Physics: University of Oxford, 1999. URL: https://sites.cs.ucsb.edu/~vandam/oxford_thesis.pdf.

[19] Dejan D. Dukaric and Stefan Wolf. *A Limit on Non-Locality Distillation*. 2008. arXiv: 0808.3317 [quant-ph].

[20] Frédéric Dupuis, Nicolas Gisin, Avinatan Hasidim, André Allan Méthot, and Haran Pilpel. “No nonlocal box is universal”. In: *Journal of Mathematical Physics* 48.8 (2007), p. 082107. doi: 10.1063/1.2767538.

[21] Helen Ebbe and Stefan Wolf. “Multi-User Non-Locality Amplification”. In: *IEEE Transactions on Information Theory* 60.2 (2014), pp. 1159–1167. doi: 10.1109/TIT.2013.2292515.

[22] Giorgos Eftaxias. “Theory-independent topics towards quantum mechanics: ψ-ontology and nonlocality distillation”. PhD thesis. University of Bristol (Quantum Engineering Centre for Doctoral Training), Mar. 2022. URL: https://research-information.bris.ac.uk/en/studentTheses/theory-independent-topics-towards-quantum-mechanics.

[23] Giorgos Eftaxias, Mirjam Weilenmann, and Roger Colbeck. “Advantages of Multicopy Nonlocality Distillation and Its Application to Minimizing Communication Complexity”. In: *Phys. Rev. Lett.* 130 (10 Mar. 2023), p. 100201. doi: 10.1103/PhysRevLett.130.100201.
[24] Giorgos Eftaxias, Mirjam Weilenmann, and Roger Colbeck. "Multisystem measurements in generalized probabilistic theories and their role in information processing". In: *Phys. Rev. A* 108 (6 2023), p. 062212. doi: 10.1103/PhysRevA.108.062212.

[25] Manuel Forster, Severin Winkler, and Stefan Wolf. "Distilling Nonlocality". In: *Phys. Rev. Lett.* 102 (12 Mar. 2009), p. 120401. doi: 10.1103/PhysRevLett.102.120401.

[26] Tobias Fritz, Ana Belén Sainz, Remigiusz Augusiak, Jonatan Bohr Brask, Rafael Chaves, Anthony Leverrier, and Antonio Acín. "Local orthogonality as a multipartite principle for quantum correlations". In: *Nature Communications* 4.1 (Aug. 2013), p. 2263. doi: 10.1038/ncomms3263.

[27] Peter Hoyer and Jibran Rashid. "Optimal protocols for nonlocality distillation". In: *Phys. Rev. A* 82 (4 Oct. 2010), p. 042118. doi: 10.1103/PhysRevA.82.042118.

[28] Prabhav Jain, Mariami Gachechiladze, and Nikolai Miklin. *Information causality as a tool for bounding the set of quantum correlations*. 2023. arXiv: 2308.02478 [quant-ph].

[29] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. *MIP\*=$RE$. 2022. arXiv: 2001.04383 [quant-ph].

[30] Eyal Kushilevitz and Noam Nisan. *Communication Complexity*. Cambridge University Press, 1996. doi: 10.1017/CBO9780511574948.

[31] Ben Lang, Tamás Vértesi, and Miguel Navascués. "Closed sets of correlations: answers from the zoo". In: *Journal of Physics A: Mathematical and Theoretical* 47.42 (Oct. 2014), p. 424029. doi: 10.1088/1751-8113/47/42/424029.

[32] Noah Linden, Sandu Popescu, Anthony J. Short, and Andreas Winter. "Quantum Nonlocality and Beyond: Limits from Nonlocal Computation". In: *Phys. Rev. Lett.* 99 (18 Oct. 2007), p. 180502. doi: 10.1103/PhysRevLett.99.180502.

[33] Lluis Masanes. *Necessary and sufficient condition for quantum-generated correlations*. 2003. arXiv: quant-ph/0309137 [quant-ph].

[34] Ryuhei Mori. "Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes". In: *Phys. Rev. A* 94 (5 Nov. 2016), p. 052130. doi: 10.1103/PhysRevA.94.052130.

[35] Sahil Gopalkrishna Naik, Govind Lal Sidhardh, Samrat Sen, Arup Roy, Ashutosh Rai, and Manik Banik. "Distilling Nonlocality in Quantum Correlations". In: *Phys. Rev. Lett.* 130 (22 June 2023), p. 220201. doi: 10.1103/PhysRevLett.130.220201.

[36] Miguel Navascués, Yelena Guryanova, Matty J. Hoban, and Antonio Acín. "Almost quantum correlations". In: *Nature Communications* 6.1 (May 2015), p. 6288. doi: 10.1038/ncomms7288.

[37] Miguel Navascués and Harald Wunderlich. "A glance beyond the quantum model". In: *Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences* 466.2115 (2009), pp. 881–890. doi: 10.1098/rspa.2009.0453.

[38] Jorge Nocedal and Stephen J. Wright, eds. *Numerical Optimization*. en. Springer Series in Operations Research and Financial Engineering. New York: Springer-Verlag, 1999. ISBN: 9780387987934. DOI: 10.1007/b98874.

[39] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. "Automatic differentiation in PyTorch". In: *OpenReview* (2017). URL: https://openreview.net/forum?id=BJJsrmfCZ.

[40] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski. "Information causality as a physical principle". In: *Nature* 461.7267 (Oct. 2009), pp. 1101–1104. doi: 10.1038/nature08400.

[41] Sandu Popescu and Daniel Rohrlich. "Quantum nonlocality as an axiom". In: *Foundations of Physics* 24.3 (Mar. 1994), pp. 379–385. doi: 10.1007/BF02058098.

[42] Ashutosh Rai, Cristhiano Duarte, Samuraí Brito, and Rafael Chaves. "Geometry of the quantum set on no-signaling faces". In: *Phys. Rev. A* 99 (3 Mar. 2019), p. 032106. doi: 10.1103/PhysRevA.99.032106.

[43] Anup Rao and Amir Yehudayoff. *Communication Complexity: and Applications*. Cambridge University Press, 2020. doi: 10.1017/9781108671644.

[44] Denis Rosset, Amin Baumeler, Jean-Daniel Bancal, Nicolas Gisin, Anthony Martin, Marc-Olivier Renou, and Elie Wolfe. *Algebraic and geometric properties of local transformations*. 2020. arXiv: 2004.09405 [quant-ph].

[45] Anthony J. Short, Sandu Popescu, and Nicolas Gisin. "Entanglement swapping for generalized nonlocal correlations". In: *Phys. Rev. A* 73 (1 Jan. 2006), p. 012101. doi: 10.1103/PhysRevA.73.012101.

[46] Noah Shutty, Mary Wootters, and Patrick Hayden. "Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise". In: *2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)*. 2020, pp. 206–217. doi: 10.1109/FOCS46700.2020.00028.

[47] Paul Skrzypczyk, Nicolas Brunner, and Sandu Popescu. "Emergence of Quantum Correlations from Nonlocality Swapping". In: *Phys. Rev. Lett.* 102 (11 Mar. 2009), p. 110402. doi: 10.1103/PhysRevLett.102.110402.

[48] Andrew Chi-Chih Yao. "Some Complexity Questions Related to Distributive Computing (Preliminary Report)". In: *Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing*. STOC '79. Atlanta, Georgia, USA: Association for Computing Machinery, 1979, pp. 209–213. ISBN: 9781450374385. doi: 10.1145/800135.804414.

[49] Yuqian Zhou, Yu Cai, Jean-Daniel Bancal, Fei Gao, and Valerio Scarani. "Many-box locality". In: *Phys. Rev. A* 96 (5 Nov. 2017), p. 052108. doi: 10.1103/PhysRevA.96.052108.
<figure><img src="image_18.png" /></figure>

## B An Alternative Proof of Theorem 23, using Pairwise Multiplication

**Lemma 30 (Convergence sufficient conditions).** Let $\mathcal{K} \subseteq \mathbb{R}^2$ be a compact convex set, and let $F$, $f_\beta$, $g_\alpha$ be functions such that:

$$F: \begin{cases} \mathcal{K} & \to \mathcal{K} \\ (\alpha, \beta) & \mapsto (f_\beta(\alpha), g_\alpha(\beta)). \end{cases}$$

where $f_\beta: I_\beta \to I_\beta$ and $g_\alpha: J_\alpha \to J_\alpha$, where $I_\beta := \mathcal{K} \cap (\mathbb{R} \times \{\beta\})$ and $J_\alpha := \mathcal{K} \cap (\{\alpha\} \times \mathbb{R})$ are viewed as intervals of $\mathbb{R}$. Suppose that:

(i) The function $F$ is continuous;

(ii) The $f_\beta$'s are strictly increasing and uniformly bounded in the “left part” of the interior of $\mathcal{K}$:

$$\exists \mu_*, \forall (\alpha, \beta) \in \mathrm{Int}(\mathcal{K}), \alpha < \mu_* \implies \alpha < f_\beta(\alpha) < \mu_*; \qquad (17)$$

(iii) For all boundary element $(\alpha, \beta) \in \partial \mathcal{K}$ such that $\alpha < \mu_*$, either the resulting inequalities of (17) are satisfied, or $\alpha = f_\beta(\alpha)$ and the image $F(\alpha, \beta)$ lies in the interior $\mathrm{Int}(\mathcal{K})$ of $\mathcal{K}$.

Then the sequence defined by $(\alpha_0, \beta_0) \in \mathcal{K}$, $\alpha_0 < \mu_*$, and $(\alpha_{k+1}, \beta_{k+1}) = F(\alpha_k, \beta_k)$ ($k \ge 0$), satisfies:

$$\alpha_k \xrightarrow{k \to +\infty} \mu_*.$$

*Proof.* A proof by induction based on (ii) and (iii) shows that the sequence $(\alpha_k)_k$ is increasing and bounded from above by $\mu_*$, so it converges to some $\alpha_\infty \le \mu_*$. Let us show that $\alpha_\infty = \mu_*$. As $\mathcal{K}$ is compact, Bolzano-Weierstrass' Theorem tells us that the sequence $(\beta_k)_k$ admits a converging subsequence $(\beta_{\varphi(k)})_k$, whose limit is $\beta_\infty$. Then, by continuity of $F$, we have:

$$(\alpha_{\varphi(k)+1}, \beta_{\varphi(k)+1}) = F(\alpha_{\varphi(k)}, \beta_{\varphi(k)}) \xrightarrow{k \to +\infty} F(\alpha_\infty, \beta_\infty) = (f_{\beta_\infty}(\alpha_\infty), g_{\alpha_\infty}(\beta_\infty)).$$

Therefore the sequence $(\alpha_{\varphi(k)+1})_k$ tends to $f_{\beta_\infty}(\alpha_\infty)$, but we know from before that it also tends to $\alpha_\infty$, so the limits coincide:

$$f_{\beta_\infty}(\alpha_\infty) = \alpha_\infty.$$

In other words, we showed that $\alpha_\infty$ is a fixed point of $f_{\beta_\infty}$. Now, by contradiction if $\alpha_\infty$ were different from $\mu_*$, i.e. if $\alpha_\infty < \mu_*$, then (ii) and (iii) would imply either the contradiction $\alpha_\infty < f_{\beta_\infty}(\alpha_\infty)$, or the inclusion $(f_{\beta_\infty}(\alpha_\infty), g_{\alpha_\infty}(\beta_\infty)) \in \mathrm{Int}(\mathcal{K})$, but then (ii) would give $f_{\beta_\infty}(\alpha_\infty) < f_{\beta_\infty} \circ f_{\beta_\infty}(\alpha_\infty)$, which is again the contradiction $\alpha_\infty < f_{\beta_\infty}(\alpha_\infty)$. Hence $\alpha_\infty = \mu_*$ and we obtain the wanted result. $\square$

**Theorem 31 (Alternative proof of Theorem 23).** The set $T := \mathrm{Conv}\{\mathbf{P}\mathbf{R}, \mathbf{P}_0, \mathbf{P}_1\} \setminus \mathrm{Conv}\{\mathbf{P}_0, \mathbf{P}_1\}$ is collapsing.

*Proof.* Consider boxes of the form $\mathbf{P}_{\alpha, \beta} := \alpha \mathbf{P}\mathbf{R} + \beta \mathbf{P}_0 + (1 - \alpha - \beta)\mathbf{P}_1$, where $\alpha, \beta \ge 0$ and $\alpha \ne 0$ and $\alpha + \beta \le 1$. Denote $\Delta$ the set of all such $\alpha$'s and $\beta$'s, so that $T = \{\mathbf{P}_{\alpha, \beta} : (\alpha, \beta) \in \Delta\}$. The triangle $\Delta$ is not compact but it can be written as a union of compact convex sets:

$$\Delta = \bigcup_{n \ge 1} \mathcal{K}_n,$$

where $\mathcal{K}_n := \Delta \cap \{\alpha \ge 1/n\}$. Denote $\boxtimes$ the box product induced by the wiring $W_{\mathbf{B}\mathbf{S}}$ inspired from [13]. Fix $(\alpha_0, \beta_0) \in \Delta$, and fix an integer $n \ge 1$ large enough so that $(\alpha_0, \beta_0) \in \mathcal{K}_n$. We want to build a protocol
that collapses communication complexity using the starting box $P_{\alpha_0, \beta_0}$ as a resource. To do so, we will define a sequence of boxes $(P_{\alpha_k, \beta_k})_k$ that are eventually collapsing for $k$ large enough. First, see that the closure $\bar{T}$ of the triangle $T$ is stable under $\boxtimes$, because $\bar{T}$ equals $\mathcal{NS} \cap \text{Aff}\{\text{PR}, P_0, P_1\}$ (see Proposition 22) and the two intersected sets are stable under $\boxtimes$ $^8$. Moreover, by bilinearity of $\boxtimes$ and using the multiplication table in Figure 4, we obtain:

$$P_{\alpha, \beta} \boxtimes P_{\alpha, \beta} = P_{\tilde{\alpha}, \tilde{\beta}}, \qquad (18)$$

with $\tilde{\alpha} := 2\alpha - \alpha^2 - \alpha\beta$ and $\tilde{\beta} := 1 - 2\alpha + \alpha^2 + \frac{5}{2}\alpha\beta - 2\beta + 2\beta^2$. We then consider the function $F: \mathcal{K}_n \subseteq \mathbb{R}^2 \to \mathbb{R}^2$ such that $F(\alpha, \beta) := (\tilde{\alpha}, \tilde{\beta})$ and we define the sequence $(\alpha_{k+1}, \beta_{k+1}) := F(\alpha_k, \beta_k)$ for $k \ge 0$. Let us show that the conditions of Lemma 30 are satisfied. Due to the stability of $\bar{T}$ under $\boxtimes$, we have the inclusion $F(\mathcal{K}_n) \subseteq \bar{\Delta}$, and as

$$\tilde{\alpha} = 2\alpha - \alpha(\alpha + \beta) \ge \alpha \ge 1/n, \qquad (19)$$

we obtain the inclusion $F(\mathcal{K}_n) \subseteq \mathcal{K}_n$, where we used $\alpha + \beta \le 1$. (i) The function $F$ is polynomial so continuous. (ii) Condition (17) is satisfied for $\mu_* := 1$: on the one hand $f_\beta$ is strictly increasing due to (19) applied with $\alpha + \beta < 1$ in the interior $\text{Int}(\mathcal{K}_n)$; on the other hand, by strict growth of $f_\beta$ we have $f_\beta(\alpha) = \tilde{\alpha} < f_\beta(\tilde{\alpha})$, which is $\le 1$ because $F(\mathcal{K}_n) \subseteq \mathcal{K}_n$. Hence we indeed have $\alpha < f_\beta(\alpha) < 1$ in the interior of $\mathcal{K}_n$. (iii) Let $(\alpha, \beta) \in \partial\mathcal{K}_n = \{\beta = 0\} \cup \{\alpha = 1/n\} \cup \{\alpha + \beta = 1\}$ such that $\alpha < 1$. If $\beta = 0$ or $\alpha = 1/n$, then inequalities of Condition (17) hold. Otherwise we have $\alpha + \beta = 1$ and in that case:

$$\left\{ \begin{array}{l} \tilde{\alpha} = \alpha \in (\frac{1}{n}, 1), \\ \tilde{\beta} = \frac{1}{2}(1-\alpha)(1+\beta) > 0, \\ \tilde{\alpha} + \tilde{\beta} = 1 - \frac{1}{2}(1-\alpha)(1-\beta) < 1, \end{array} \right.$$

which implies that $(\tilde{\alpha}, \tilde{\beta}) \in \text{Int}(\mathcal{K}_n)$. Finally, we may assume that $\alpha_0 < 1$ (otherwise $\alpha_0 = 1$ and then $P_{\alpha_0, \beta_0} = \text{PR}$, which is collapsing) and all the conditions of Lemma 30 are satisfied. The lemma tells that the sequence $(\alpha_k)_k$ tends to $\mu_* = 1$, so $(P_{\alpha_k, \beta_k})_k \subseteq \mathbb{R}^{16}$ tends to $\text{PR}$. But we know from [10] that there is a non-empty open set around $\text{PR}$ that is collapsing. So there exists a finite $k$ for which the box $P_{\alpha_k, \beta_k}$ is collapsing and we obtain the wanted collapsing protocol. $\square$

## C Some Multiplication Tables

Find below the multiplication tables of $\boxtimes_W$ for different wirings $W$. Each cell displays the result of $P \boxtimes_W Q$, where $P$ lies in the first column and $Q$ lies in the first line. $P_{10} := P_L^{0100}$. $P_{01} := P_L^{0001}$. $Q_1 := -\frac{1}{8}(P_0 + P_1) + \frac{1}{4}\text{PR} + \text{I}$. $Q_2 := \frac{1}{4}(\text{PR} + P_{\text{NL}}^{011}) + \frac{1}{2}\text{I}$. $Q_3 := \frac{1}{4}\text{PR} + \frac{1}{2}\text{I} + \frac{3}{8}P_0 - \frac{1}{8}P_1$. $Q_4 := \frac{3}{8}P_0 - \frac{1}{8}P_1 + \frac{3}{4}\text{I}$. $Q_5 := \frac{1}{4}\text{PR} + \frac{1}{8}(P_0 + P_1) + \frac{1}{2}P_{10}$. $Q_6 := \frac{3}{16}(P_0 + P_1) + \frac{9}{16}P_{10}$. Find an algorithm to compute a multiplication table in our GitHub page [9]. Recall the definitions of $P_L$ and $P_{\text{NL}}$ in Equation (16).

<table><tbody><tr><th colspan="5">W<sub>triv</sub></th><th colspan="5">W<sub>⊕</sub> [25]</th></tr><tr><td>PR</td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>PR</td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>I</td></tr><tr><td>P<sub>0</sub></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>I</td></tr><tr><td>P<sub>1</sub></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>1</sub></td><td>P<sub>1</sub></td><td>P<sub>0</sub></td><td>I</td></tr><tr><td>I</td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>P<sub>L</sub><sup>1010</sup></td><td>I</td><td>I</td><td>I</td><td>I</td></tr><tr><th colspan="5">W<sub>BS</sub> [13]</th><th colspan="5">W<sub>dist</sub> [1]</th></tr><tr><td>PR</td><td>PR</td><td>PR</td><td>PR</td><td>I</td><td>PR</td><td>PR</td><td>PR</td><td>I</td></tr><tr><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>I</td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>I</td></tr><tr><td>P<sub>1</sub></td><td>PR</td><td>P<sub>1</sub></td><td>P<sub>0</sub></td><td>I</td><td>P<sub>1</sub></td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>I</td></tr><tr><td>I</td><td>Q<sub>1</sub></td><td>I</td><td>I</td><td>I</td><td>I</td><td>I</td><td>I</td><td>I</td></tr><tr><th colspan="5">W<sub>Λ</sub> [1]</th><th colspan="5">W<sub>ΛΛ</sub> [35]</th></tr><tr><td>PR</td><td>P<sub>0</sub>+P<sub>1</sub><br>2</td><td>P<sub>0</sub></td><td>PR</td><td>Q<sub>3</sub></td><td>PR</td><td>P<sub>0</sub>+P<sub>10</sub><br>2</td><td>P<sub>0</sub>+P<sub>10</sub><br>2</td><td>P<sub>1</sub>+P<sub>10</sub><br>2</td><td>Q<sub>5</sub></td></tr><tr><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>0</sub></td><td>P<sub>0</sub>+P<sub>10</sub><br>2</td><td>P<sub>0</sub></td><td>P<sub>10</sub></td><td>P<sub>0</sub>+P<sub>10</sub><br>2</td><td>P<sub>1</sub>+P<sub>10</sub><br>2</td></tr><tr><td>P<sub>1</sub></td><td>PR</td><td>P<sub>0</sub></td><td>P<sub>1</sub></td><td>I</td><td>P<sub>1</sub>+P<sub>10</sub><br>2</td><td>P<sub>10</sub></td><td>P<sub>1</sub></td><td>P<sub>1</sub>+P<sub>10</sub><br>2</td><td>P<sub>1</sub>+P<sub>10</sub><br>2</td></tr><tr><td>I</td><td>Q<sub>3</sub></td><td>P<sub>0</sub></td><td>I</td><td>Q<sub>4</sub></td><td>I</td><td>Q<sub>5</sub></td><td>P<sub>0</sub>+P<sub>10</sub><br>2</td><td>P<sub>1</sub>+P<sub>10</sub><br>2</td><td>Q<sub>6</sub></td></tr></tbody></table>

<footnote>$^8$Indeed, (i) the set $\mathcal{NS}$ is stable under $\boxtimes$ because it is closed under wirings [1], (ii) the affine plane $\text{Aff}\{\text{PR}, P_0, P_1\}$ is stable under $\boxtimes$ as a consequence of the multiplication table in Figure 4 and by bilinearity of $\boxtimes$.</footnote>