# Advantages of multi-copy nonlocality distillation and its application to
minimizing communication complexity

Giorgos Eftaxias<EMAIL_ADDRESS>Quantum Engineering Centre
for Doctoral Training, University of Bristol, Bristol BS8 1FD, United Kingdom
Department of Mathematics, University of York, York YO10 5DD, UK  Mirjam
Weilenmann<EMAIL_ADDRESS>Institute for Quantum Optics and
Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3,
1090 Vienna, Austria  Roger Colbeck<EMAIL_ADDRESS>Department of
Mathematics, University of York, York YO10 5DD, UK

###### Abstract

Nonlocal correlations are a central feature of quantum theory, and
understanding why quantum theory has a limited amount of nonlocality is a
fundamental problem. Since nonlocality also has technological applications,
e.g., for device-independent cryptography, it is useful to understand it as a
resource and, in particular, whether and how different types of nonlocality
can be interconverted. Here we focus on nonlocality distillation which
involves using several copies of a nonlocal resource to generate one with more
nonlocality. We introduce several distillation schemes which distil an
extended part of the set of nonlocal correlations including quantum
correlations. Our schemes are based on a natural set of operational procedures
known as wirings that can be applied regardless of the underlying theory. Some
are sequential algorithms that repeatedly use a two-copy protocol, while
others are genuine three-copy distillation protocols. In some regions we prove
that genuine three-copy protocols are strictly better than two-copy protocols.
By applying our new protocols we also increase the region in which nonlocal
correlations are known to give rise to trivial communication complexity. This
brings us closer to an understanding of the sets of nonlocal correlations that
can be recovered from information-theoretic principles, which, in turn,
enhances our understanding of what is special about quantum theory.

## Introduction

A bound on the strength of correlations realisable between pairs of
measurement inputs and outputs in any local theory was first shown by Bell
Bell (1964). This bound is exceeded in quantum theory and there are even
stronger correlations theoretically possible without enabling signalling
Cirel’son (1980); Popescu and Rohrlich (1994). One way to better understand
quantum theory is to consider it in light of possible alternative theories,
which can be compared in terms of the correlations they can create, and the
implications access to such correlations would have. For instance, it is known
that theories that permit strong enough correlations have trivial
communication complexity Brassard  _et al._ (2006). Furthermore, non-local
correlations have found applications in cryptography, where they form a
necessary resource for device-independent quantum key distribution Ekert
(1991); Mayers and Yao (1998); Barrett  _et al._ (2005); Pironio  _et al._
(2009) and randomness expansion Colbeck (2007); Pironio  _et al._ (2010);
Colbeck and Kent (2011), for example. Since non-local correlations serve as
resources for information processing, it is natural to ask about their
interconvertability. In this work we look at non-locality distillation Forster
_et al._ (2009), i.e., whether with access to several copies of some non-local
resource we can generate stronger ones, which would have implications for the
study of device-independent tasks in noisy regimes, for instance.

Non-locality distillation is often analysed in terms of _wirings_ Forster  _et
al._ (2009); Brunner and Skrzypczyk (2009); Allcock  _et al._ (2009); Høyer
and Rashid (2010), which means interacting with systems by choosing inputs and
receiving and processing outcomes from those systems. This has the advantage
that, firstly, the distillation procedures apply to non-local quantum
correlations no matter how complicated the system these have been obtained
from and, secondly, these procedures are applicable beyond quantum theory. A
general theory will prescribe various different ways to measure systems (in
quantum theory, for instance, a measurement is described by a POVM). Wirings
form an operationally natural sub-class that can be performed in any
generalized probabilistic theory (GPT) Barrett (2007) (including quantum
theory).

Previous work on non-locality distillation has focused on specific protocols
for the distillation of 2 copies of a non-local resource (see e.g., Forster
_et al._ (2009); Brunner and Skrzypczyk (2009); Allcock  _et al._ (2009)). The
case of more copies remains largely open, with only few specific results Høyer
and Rashid (2010). In part, this is because analysing non-locality
distillation is challenging: distillation protocols perform non-linear
operations on the correlations and hence cannot be easily optimised.
Furthermore, applying a successful 2-copy protocol twice often decreases the
non-locality again (see e.g. Brunner and Skrzypczyk (2009) for an exception).
Hence, understanding 2-copy protocols provides little insight into the
$n$-copy case.

In this Letter we describe a sequential adaptive algorithm that uses wirings
to distil non-locality. We use this algorithm to explore the distillable
region within the set of non-local correlations, and the amount of
distillation possible. We demonstrate new wirings that allow distillation of
correlations that cannot be distilled with any 2-copy wiring protocol.

Our results have implications for communication complexity. In this problem,
Alice with input $x$ and Bob with input $y$ want to enable Alice to compute
$f(x,y):\\{0,1\\}^{k}\times\\{0,1\\}^{m}\to\\{0,1\\}$. We ask how much
communication from Bob to Alice is required to do so. Communication complexity
is said to be trivial if any such function (no matter how large $k$ and $m$)
can be computed using only one bit of communication. Shared maximally non-
local resources are known to make communication complexity trivial in this
sense van Dam (2005). A probabilistic notion of trivial communication
complexity was introduced in Brassard  _et al._ (2006) in which for any $f$ we
require the existence of $p>1/2$ such that Alice can obtain the correct value
of $f(x,y)$ with probability at least $p$ for all $x$ and $y$. In this paper,
when we talk about trivial communication complexity we mean it in this
probabilistic sense. A larger set of shared states that render communication
complexity trivial were found in Refs. Brassard  _et al._ (2006); Brunner and
Skrzypczyk (2009). Our results further enlarge this set, demonstrating
advantages of wirings beyond the 2-copy case.

In the following, we will first introduce the necessary background on non-
locality distillation by wiring operations. We then go on to introduce our
first result: a sequential algorithm that allows us to prove that extended
sets of non-local correlations trivialise communication complexity. Following
this we provide our genuine 3-copy protocols and demonstrate their advantages
over existing protocols. Lastly we will present our conclusions.

## Non-locality and wirings

Correlations of inputs $x,y$ and outputs $a,b$ are described by conditional
probability distributions $P(ab|xy)$, and we refer to these as a _box_ or a
_behaviour_. In the context of non-locality, we usually imagine these
correlations as generated by two parties, Alice and Bob, who each choose an
input ($x$ and $y$ respectively) and obtain an output ($a$ and $b$
respectively). The correlations they can generate according to any theory that
is consistent with special relativity have to be _non-signalling_ , meaning

$\sum_{b}P(ab|xy)=\sum_{b}P(ab|xy^{\prime})\quad\forall\ a,x,y,y^{\prime},$

and the same holds with the roles of Alice and Bob (i.e. $a,x$ and $b,y$)
exchanged. A box is called _local_ if it can be written

$P(ab|xy)=\sum_{\lambda}P(a|x\lambda)P(b|y\lambda)P(\lambda)\quad\forall\
a,b,x,y\,.$

In the language of Bell inequalities, there is a variable $\Lambda$ that takes
the value $\lambda$ with probability $P(\lambda)$. Boxes that cannot be
written in this form are _non-local_.

In the case of two binary inputs and outputs, i.e., $a,b,x,y\in\\{0,1\\}$, the
set of all local boxes is the convex hull of $16$ local deterministic boxes
$P^{\rm L}_{i}(ab|xy)=\delta_{a,\mu x\oplus\nu}\,\delta_{b,\sigma
y\oplus\tau}$ for $\mu,\nu,\sigma,\tau\in\\{0,1\\}$,
$i=1+\tau+2\sigma+4\nu+8\mu$, and the set of all non-signalling boxes is the
convex hull of these local boxes and $8$ extremal no-signalling boxes
Tsirelson (1993); Popescu and Rohrlich (1994) $P^{\rm
NL}_{i}(ab|xy)=\frac{1}{2}\delta_{a\oplus b,xy\oplus\mu x\oplus\nu
y\oplus\sigma}$ for $\mu,\nu,\sigma\in\\{0,1\\}$, $i=1+\sigma+2\nu+4\mu$. Up
to symmetry, the Clauser-Horne-Shimony-Holt (CHSH) inequality Clauser  _et
al._ (1969) is the only one that restricts the set of local boxes. Non-
locality can hence be quantified in terms of the CHSH value
$\operatorname{CHSH}(P(ab|xy))=E_{00}+E_{01}+E_{10}-E_{11}$, with
$E_{xy}=P(a=b|xy)-P(a\neq b|xy)$.

Because we work in a black-box picture, the most general operation we consider
for each party is a wiring. We describe here the deterministic wirings; the
most general wirings are convex combinations of these. Consider a party with
access to $n$-boxes with inputs $x_{j}$ and outputs $a_{j}$ with
$j=1,\ldots,n$. They “wire” these together to form a new box with input $x$
and output $a$. The most general deterministic wiring comprises choosing a box
to make the first input to and then making a chosen input, then using the
output of that box to choose the second box and the input to that second box
and so on. We label the $i^{\text{th}}$ box chosen
$j_{i}(x,a_{j_{1}},\ldots,a_{j_{i-1}})$ and its input
$x_{j_{i}}(x,a_{j_{1}},\ldots,a_{j_{i-1}})$. The final outcome is chosen
depending on the overall input and all previous outcomes
$a(x,a_{j_{1}},\ldots,a_{j_{n}})$. Thus, if Alice and Bob each do wirings on
shares of $n$ boxes, they generate a new box $P(ab|xy)$.

Our main question is then: _given several copies of a non-local box, are there
wirings for Alice and for Bob such that the resulting box is more non-local
than the original?_ In the case of two non-signalling boxes with binary inputs
and outputs each, the possible wirings have been fully characterised Short and
Barrett (2010). Nevertheless, even in this case, deciding whether these can
result in more non-locality for a specific box is computationally intensive:
there are $82$ deterministic wirings that each party can perform for each
input Short and Barrett (2010), leading to a total of $82^{4}$ possibilities
(one of the $82$ for each input of each party). However, to make the
computation more tractable, we optimise the wirings of one party with a linear
program, while iterating over $82^{2}$ wirings for the other (see Appendix A
for more detail). We use this linear programming technique to illustrate the
regions in which distillation is possible for various 2-dimensional cross-
sections (CSs) of the no-signalling polytope in Figure I. In this work we
consider three regions:

$\displaystyle\mathrm{CS~{}I:}$ $\displaystyle\ \omega
P^{\mathrm{NL}}_{1}+\frac{\eta}{2}(P^{\mathrm{L}}_{1}+P^{\mathrm{L}}_{6})+(1-\omega-\eta)P^{\mathrm{O}}$
$\displaystyle\mathrm{CS~{}II:}$ $\displaystyle\ \omega
P^{\mathrm{NL}}_{1}+\eta P^{\mathrm{L}}_{1}+(1-\omega-\eta)P^{\mathrm{O}}$
$\displaystyle\mathrm{CS~{}III:}$ $\displaystyle\ \omega
P^{\mathrm{NL}}_{1}+\frac{\eta}{2}(P^{\mathrm{L}}_{1}+P^{\mathrm{L}}_{9})+(1-\omega-\eta)P^{\mathrm{O}}\,,$
(1)

where $P^{\mathrm{O}}=3/4P^{\mathrm{NL}}_{1}+1/4P^{\mathrm{NL}}_{2}$ is local
and $\eta,\omega\geq 0$ with $\eta+\omega\leq 1$.

Figure I: Protocols sufficient to characterise the two-copy distillability
(both the distillable region and the strongest amplification) for two CSs (cf.
Eq. (1)). The optimal two-copy protocols for CS II are the two protocols from
Allcock  _et al._ (2009) (ABL+1,2), while for CS I the protocol of Forster
_et al._ (2009) (FWW) is optimal in some cases. The shading indicates where
the corresponding protocol is optimal, with the boundary indicated by the
black line (see Appendix A for detail of the protocols). The dotted curve
indicates the set of correlations realisable in quantum theory (computed using
the conditions in Cirel’son (1980); Masanes (2003)).

We analysed the distillability within these cross sections. Among the optimal
protocols we recovered several that were previously known Brunner  _et al._
(2011); Allcock  _et al._ (2009). The protocols of Allcock  _et al._ (2009)
(called ABL${}^{+}1,2$) are sufficient to characterise the two-copy
distillability in CS II (see Fig. I), and CS III is two-copy non-distillable.
The observation that ABL+2 achieves no distillation in CS I shows that optimal
protocols depend on the cross-section.

The above analysis is generally not useful for analysing whether repeated
distillation of a box can lead to a certain CHSH-value. Applying a wiring that
works for two boxes to two copies of the generated box often does not give a
further increase in non-locality but maps outside of the distillable region of
that protocol, in which case a switch of wirings is needed to distil further.
While there are boxes that cannot be distilled at all with wirings (e.g.
isotropic boxes Beigi and Gohari (2015)), the maximal CHSH value can be
distilled using multiple copies of a specific resource box is open.

This means that we do not know how resourceful (multiple copies of) most non-
local boxes are for information processing. For instance, shared boxes render
communication complexity trivial if their initial CHSH value is greater than
$\operatorname{CHSH}(P(ab|xy))=4\sqrt{\frac{2}{3}}$ Brassard  _et al._ (2006).
The complete set of boxes that render commuication complexity trivial is
unknown, although an additional region was found with the protocol of Brunner
and Skrzypczyk (2009).

## Sequential algorithms for non-locality distillation and reduction of
communication complexity

While a repeated application of a successful 2-copy protocol often does not
increase the non-locality further, there are various ways to combine different
2-copy wirings (see Appendix B). Here, we focus on the specific structure
illustrated in Figure II.

Figure II: A serial architecture for combining nonlocal resources (gray) in a
sequential manner. The first step on the left depicts the usual two-copy
distillation scheme. Each subsequent iteration uses another copy of the
original box and the previously generated one. Our sequential algorithm
optimises the protocol at each round. See Appendix B for details.

Our serial algorithm consists in optimising the wiring to be applied in every
step, which is done in terms of a hybrid procedure of iterating over wirings
and linear programming (see Appendix B for a detailed description of the
algorithm). Applying our serial algorithm, we are able to extend the region of
non-local boxes known to trivialise communication complexity, see Figure III.

Figure III: Region of trivial communication complexity in CS I. The light-gray
part was identified in Brassard  _et al._ (2006). The dark-gray region
includes boxes that trivialise communication complexity through (up to 4)
iterations of ABL+1\. The red points (and everything on their right) collapse
communication complexity using our serial algorithm. The black solid chord is
that of Figure I (left) and indicates a change in protocol for the red points
– see Appendix B for details, including the black points in the figure which
are analysed in more detail.

Our algorithm furthermore provides us with a way to systematically derive new
non-locality distillation protocols for multi-copy non-locality distillation.
When performing two-steps of the serial algorithm, the following three-copy
protocol appears particularly successful:

In the first step, a box is created from two copies of a box $P$ with inputs
(outputs) labelled $x_{1},y_{1}$ ($a_{1},b_{1}$) and $x_{2},y_{2}$
($a_{2},b_{2}$) respectively (first step in Figure II). Then this is wired to
another copy of $P$, $P(a_{3}b_{3}|x_{3}y_{3})$, using the functions

$\displaystyle x_{1}$ $\displaystyle=x=x^{\prime},\ x_{2}=x\oplus\bar{a}_{1},\
a=a_{1}\oplus a_{2},\ x_{3}=x\bar{a}$ $\displaystyle y_{1}$
$\displaystyle=y=y^{\prime},\ y_{2}=yb_{1},\ b=b_{1}\oplus b_{2},\
y_{3}=y\oplus b,$ (2) $\displaystyle a^{\prime}$ $\displaystyle=a\oplus
a_{3},\ b^{\prime}=b\oplus b_{3},$

where $\oplus$ is the logical xor and $\bar{z}=z\oplus 1$. In Figure IV, we
illustrate that this new protocol distils in CS II a strict superset of non-
local boxes than the previously known 3-copy distillation protocol of Høyer
and Rashid (2010) (in contrast to CS I where the protocol of Høyer and Rashid
(2010) is superior). For completeness we introduce the protocol from Høyer and
Rashid (2010) in Appendix C and we refer to it as HR.

Figure IV: Comparison of our new protocol (Sequential algorithms for non-
locality distillation and reduction of communication complexity), displayed
with the purple boundary, to the 3-copy protocol HR from Høyer and Rashid
(2010), displayed in gray for CS II. The protocol of Eq. (Sequential
algorithms for non-locality distillation and reduction of communication
complexity) distils a strict superset of the boxes that HR distils and the
non-locality increase at each point is also stronger than that of HR.

## Genuine three-copy distillation protocols

When considering 3-copy distillation, the variety of possible protocols is
vastly increased. In this case we can derive new protocols that outperform the
previous ones in terms of the boxes for which they offer distillation. For
this, we introduce a _genuine three-copy distillation protocol_ , which is one
that cannot be reduced to a concatenation of 2-copy protocols. Consider the
following wiring, where $\lor$ denotes the logical or operation:

$\displaystyle x_{1}=x_{2}=\bar{x},\ x_{3}=\bar{x}a_{1}\lor\bar{x}a_{2},\
a=a_{1}a_{3}\lor a_{2}a_{3}\lor\bar{a}_{1}\bar{a}_{2}\bar{a}_{3},$
$\displaystyle y_{1}=y_{2}=y,\ y_{3}=yb_{1}\lor
yb_{2}\lor\bar{y}\bar{b}_{1}\bar{b}_{2},$ (3) $\displaystyle
b=\bar{y}b_{1}b_{3}\lor\bar{y}b_{2}b_{3}\lor yb_{1}\bar{b}_{3}\lor
yb_{2}\bar{b}_{3}\lor\bar{y}\bar{b}_{1}\bar{b}_{2}\bar{b}_{3}\lor
y\bar{b}_{1}\bar{b}_{2}b_{3}.$

We find larger regions of distillable boxes as compared to the two-copy case,
see Figure V.

Figure V: Region of distillation by means of the 3-copy wiring Eq. (3) bounded
by the green lines. The blue and orange lines show the region of optimal
2-copy distillation in CS I, as in Figure I (left). The green shaded area in
CS I depicts where our protocol leads to higher CHSH values than all
previously known protocols (i.e., 2-copy and 3-copy FWW, ABL+1, HR). In CS III
no 2-copy non-locality distillation is possible and the ability to distil is
unlocked only when given access to at least 3 copies of a non-local box where
use of a genuine 3-copy protocol is imperative. The dotted curve indicates the
set of quantum-realizable correlations.

In CS III no 2-copy distillation is possible, while with 3 copies it is.
Furthermore, the increase in the region of boxes that allow for distillation
is considerably larger than that of HR (which is nearly indistinguishable from
ABL+1, see also Figure IV).

Additionally we find 3-copy protocols that increase the region where
communication complexity is trivial. In particular

$\displaystyle x_{1}=x_{2}=x,\ x_{3}=xa_{2}\lor
x\bar{a}_{1}\lor\bar{x}\bar{a}_{2}a_{1},$ $\displaystyle a=a_{3}a_{2}\lor
a_{3}\bar{a}_{1}\lor\bar{a}_{3}\bar{a}_{2}a_{1},\ y_{1}=y_{2}=y,\
y_{3}=yb_{2}\lor\bar{b}_{1},$ $\displaystyle b=b_{3}b_{2}\lor
b_{3}\bar{b}_{1}\lor\bar{b}_{3}\bar{b}_{2}b_{1}.$ (4)

We illustrate the use of this protocol for trivialising communication
complexity in Figure VI. We observe, that as compared to using 2-copy
protocols (even sequentially), 3-copy protocols provide further advantages.

Figure VI: Regions of trivial communication complexity with various protocols.
The green region is from repeated use of our genuine 3-copy protocol of Eq.
(4), the blue bounded region is from repeated use of ABL+1 and the dashed gray
bounded region is from repeated use of HR. In the magnified view (right) we
see a small region where our new 3-copy protocol outperforms HR and any
possible 2-copy protocol.

## Conclusions

We have found a genuine 3-copy protocol that distils nonlocality for boxes in
which distillation with two copies is impossible and shown that there are
3-copy protocols that outperform _all_ 2-copy protocols (and sequential
applications thereof). For the latter we employed an optimization technique
for 2-copy wiring protocols. Although this optimization furthers our
understanding, it remains limited to cases with small numbers of inputs and
outputs and there remains much more to discover about nonlocality
distillation.

Whether the principle of non-trivial communication complexity Brassard  _et
al._ (2006) defines a closed set of correlations Lang  _et al._ (2014) that
allows for a simple characterisation and lies well between quantum and non-
signalling sets is an open question of interest for the foundations of quantum
theory. Indeed, finding a sensible generalised probabilistic theory that leads
to a set of correlations between the non-signalling and quantum set with a
simple geometric description has been a conundrum. The present work suggests
that a better understanding of multi-copy non-locality distillation may give
us insights into such a set, namely that of a GPT whose only restriction is
imposed by the principle of non-trivial communication complexity. This would
further advance the recent research program of experimentally ruling out
generalised probabilistic theories due to the correlations they produce in
networks Weilenmann and Colbeck (2020a, b).

Some of our distillation protocols work within the set of quantum correlations
(see Figure V). There is a well studied theory of entanglement distillation
Bennett  _et al._ (1996), which could be used as part of a non-locality
distillation protocol. The results here indicate that in some cases the non-
locality of quantum states can be distilled using a simple wiring protocol and
without first distilling the entanglement, and it would be interesting to
explore applications of this for information processing, e.g., in device-
independent protocols.

###### Acknowledgements.

GE is supported by the EPSRC grant EP/LO15730/1. MW is supported by the Lise
Meitner Fellowship of the Austrian Academy of Sciences (project number M
3109-N).

## References

  * Bell (1964) J. S. Bell, “On the Einstein-Podolsky-Rosen paradox,” Physics Physique Fizika 1, 195–200 (1964).
  * Cirel’son (1980) B. Cirel’son, “Quantum generalizations of bell’s inequality,” Letters in Mathematical Physics 4, 93–100 (1980).
  * Popescu and Rohrlich (1994) S. Popescu and D. Rohrlich, “Quantum nonlocality as an axiom,” Foundations of Physics 24, 379–385 (1994).
  * Brassard  _et al._ (2006) G. Brassard, H. Buhrman, N. Linden, A. A. Méthot, A. Tapp, and F. Unger, “Limit on nonlocality in any world in which communication complexity is not trivial,” Physical Review Letters 96, 250401 (2006).
  * Ekert (1991) A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Physical Review Letters 67, 661–663 (1991).
  * Mayers and Yao (1998) D. Mayers and A. Yao, “Quantum cryptography with imperfect apparatus,” in  _Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS-98)_ (IEEE Computer Society, Los Alamitos, CA, USA, 1998) pp. 503–509.
  * Barrett  _et al._ (2005) J. Barrett, L. Hardy, and A. Kent, “No signalling and quantum key distribution,” Physical Review Letters 95, 010503 (2005).
  * Pironio  _et al._ (2009) S. Pironio, A. Acin, N. Brunner, N. Gisin, S. Massar, and V. Scarani, “Device-independent quantum key distribution secure against collective attacks,” New Journal of Physics 11, 045021 (2009).
  * Colbeck (2007) R. Colbeck,  _Quantum and Relativistic Protocols For Secure Multi-Party Computation_ , Ph.D. thesis, University of Cambridge (2007), also available as arXiv:0911.3814.
  * Pironio  _et al._ (2010) S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, “Random numbers certified by Bell’s theorem,” Nature 464, 1021–4 (2010).
  * Colbeck and Kent (2011) R. Colbeck and A. Kent, “Private randomness expansion with untrusted devices,” Journal of Physics A: Mathematical and Theoretical 44, 095305 (2011).
  * Forster  _et al._ (2009) M. Forster, S. Winkler, and S. Wolf, “Distilling nonlocality,” Physical Review Letters 102, 120401 (2009).
  * Brunner and Skrzypczyk (2009) N. Brunner and P. Skrzypczyk, “Nonlocality distillation and postquantum theories with trivial communication complexity,” Physical Review Letters 102, 160403 (2009).
  * Allcock  _et al._ (2009) J. Allcock, N. Brunner, N. Linden, S. Popescu, P. Skrzypczyk, and T. Vértesi, “Closed sets of nonlocal correlations,” Physical Review A 80, 062107 (2009).
  * Høyer and Rashid (2010) P. Høyer and J. Rashid, “Optimal protocols for nonlocality distillation,” Physical Review A 82, 042118 (2010).
  * Barrett (2007) J. Barrett, “Information processing in generalized probabilistic theories,” Physical Review A 75, 032304 (2007).
  * van Dam (2005) W. van Dam, “Implausible consequences of superstrong nonlocality,” e-print quant-ph/0501159 (2005).
  * Tsirelson (1993) B. S. Tsirelson, “Some results and problems on quantum Bell-type inequalities,” Hadronic Journal Supplement 8, 329–345 (1993).
  * Clauser  _et al._ (1969) J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, “Proposed experiment to test local hidden-variable theories,” Physical Review Letters 23, 880–884 (1969).
  * Short and Barrett (2010) A. J. Short and J. Barrett, “Strong nonlocality: a trade-off between states and measurements,” New Journal of Physics 12, 033034 (2010).
  * Masanes (2003) L. Masanes, “Necessary and sufficient condition for quantum-generated correlations,” e-print arXiv:quant-ph/0309137 (2003).
  * Brunner  _et al._ (2011) N. Brunner, D. Cavalcanti, A. Salles, and P. Skrzypczyk, “Bound nonlocality and activation,” Physical Review Letters 106, 020402 (2011).
  * Beigi and Gohari (2015) S. Beigi and A. Gohari, “Monotone measures for non-local correlations,” IEEE Transactions on Information Theory 61, 5185–5208 (2015).
  * Lang  _et al._ (2014) B. Lang, T. Vértesi, and M. Navascués, “Closed sets of correlations: answers from the zoo,” Journal of Physics A: Mathematical and Theoretical 47, 424029 (2014).
  * Weilenmann and Colbeck (2020a) M. Weilenmann and R. Colbeck, “Self-testing of physical theories, or, is quantum theory optimal with respect to some information-processing task?” Physical Review Letters 125, 060406 (2020a).
  * Weilenmann and Colbeck (2020b) M. Weilenmann and R. Colbeck, “Toward correlation self-testing of quantum theory in the adaptive Clauser-Horne-Shimony-Holt game,” Physical Review A 102, 022203 (2020b).
  * Bennett  _et al._ (1996) C. H. Bennett, H. J. Bernstein, S. Popescu, and B. Schumacher, “Concentrating partial entanglement by local operations,” Phys. Rev. A 53, 2046–2052 (1996).
  * Short  _et al._ (2006) A. J. Short, S. Popescu, and N. Gisin, “Entanglement swapping for generalized nonlocal correlations,” Physical Review A 73, 012101 (2006).
  * Brito  _et al._ (2019) S. G. d. A. Brito, M. Moreno, A. Rai, and R. Chaves, “Nonlocality distillation and quantum voids,” Physical Review A 100, 012102 (2019).
  * Eftaxias (2022) G. Eftaxias,  _Theory-independent topics towards quantum mechanics: $\psi$-ontology and nonlocality distillation_, Ph.D. thesis (2022), in preparation.

##  Appendix A Optimising over all two-copy non-locality distillation
protocols

In order to establish whether a non-local box is amenable to 2-copy non-
locality distillation, it is convenient (and due to the large number of
possible protocols even necessary) to find ways to search and optimise over
all such protocols. This can be achieved using Linear Programming.
Specifically, while iterating over the extremal wirings of one party, we can
optimise the operations of the other this way.

To see how this is possible, notice that the correlations obtained from wiring
two boxes $Q_{1}(a_{1}b_{1}|x_{1}y_{1})$, $Q_{2}(a_{2}b_{2}|x_{2}y_{2})$ are

$P(ab|xy)=\sum_{x_{i},y_{i},a_{i},b_{i}}Q_{1}(a_{1}b_{1}|x_{1}y_{1})Q_{2}(a_{2}b_{2}|x_{2}y_{2})\chi_{x}(ax_{1}x_{2}|a_{1}a_{2})\xi_{y}(by_{1}y_{2}|b_{1}b_{2}),$

where $\chi_{x}(ax_{1}x_{2}|a_{1}a_{2})$ and $\xi_{y}(by_{1}y_{2}|b_{1}b_{2})$
describe Alice’s and Bob’s wirings upon receiving input $x$ and $y$
respectively. For a deterministic wiring,
$\chi_{x}(ax_{1}x_{2}|a_{1}a_{2})\in\\{0,1\\}$ for all
$a,\,a_{1},\,a_{2},\,x_{1},\,x_{2}$, and the wiring $x_{1}=0$, $x_{2}=a_{1}$
and $a=a_{1}\oplus a_{2}$ would correspond to
$\chi(ax_{1}x_{2}|a_{1}a_{2})=\delta_{x_{1},0}\delta_{x_{2},a_{1}}\delta_{a,a_{1}\oplus
a_{2}}$, for example.

A wiring on Alice’s side is made up of $|x|\cdot|a|$ vectors
$\chi_{x}(a)=(\chi_{x}(ax_{1}x_{2}|a_{1}a_{2}))_{a_{1}a_{2}x_{1}x_{2}}$. In
the case of 2-inputs and 2-outputs, these are straightforward to characterise
since the wirings there are exactly the allowed measurements in a generalised
probabilistic theory of non-local boxes Short  _et al._ (2006). Specifically,
to have a valid wiring in this case, it is necessary and sufficient that the
output distribution on any 2-input 2-output non-signalling box returns a valid
probability distribution, i.e., for any $Q\in\\{P^{\rm L}_{i},P^{\rm
NL}_{j}\\}_{i,j}$

$\displaystyle
0\leq\sum_{a_{1},a_{2},x_{1},x_{2}}\chi_{x}(x_{1}x_{2}a|a_{1}a_{2})Q(a_{1}a_{2}|x_{1}x_{2})$
$\displaystyle\leq 1\qquad\forall x,a,$ (5)
$\displaystyle\sum_{a,a_{1},a_{2},x_{1},x_{2}}\chi_{x}(x_{1}x_{2}a|a_{1}a_{2})Q(a_{1}a_{2}|x_{1}x_{2})$
$\displaystyle=1\qquad\forall x.$ (6)

These are linear constraints on the vectors $\chi_{x}(a)$.

Furthermore, $\operatorname{CHSH}(P(ab|xy))$ as defined in the main text is a
linear function of the $P(ab|xy)$, which in turn is linear in $\chi_{x}(a)$.
Thus, we can optimise the distilled non-locality over Alice’s wirings with a
linear program. Although this procedure works well when Alice and Bob each
hold halves of two 2-input 2-output systems, going beyond this case presents
several challenges:

  1. 1.

With more than two systems the number of wirings on Bob’s side significantly
increases.

  2. 2.

Sticking with two systems but increasing the number of inputs and outputs for
each system significantly increases the number of wirings.

  3. 3.

With more than two systems it is possible that the linear program optimizing
over Alice’s operations outputs a vector $\chi_{x}$ that is not a wiring.

The presence of such _non-wirings_ for three systems was first noticed in
Short and Barrett (2010). In the main text we motivated the use of wirings
based on maintaining validity of the results in any GPT. Allowing the non-
wirings that come from such a linear program does not significantly alter the
theory-independence in the sense that Eq. (5) and Eq. (6) are minimal
requirements hence if no additional restrictions are placed on the theory any
$\chi_{x}$ output by the linear program should be valid. Nevertheless it may
be unnatural to allow non-wirings for Alice while restricting to wirings for
Bob. Hence one would either like to add all the non-wirings valid in _any_
theory to the set of Bob’s possibilities, or remove non-wirings from the set
of possible operations of Alice.

In the case of 2 copies of a box, in order to optimise the distilled non-
locality over all wirings of Alice _and_ Bob, we iterate over the $82^{2}$
extremal wirings of Bob, as found in Short  _et al._ (2006) and displayed in
Table 1, while optimizing Alice’s wiring for each such choice with a linear
program as described above.

Wiring class |  Number of wirings in class |  Elements $\chi(a,a_{1},a_{2},x_{1},x_{2})=1$ if the following holds: (otherwise zero) |  Label of wiring for each $\mu,\nu,\sigma,\delta,\epsilon\in\\{0,1\\}$
---|---|---|---
Constant |  2 |  $x_{1}=x_{2},\hskip 5.69046pta=\mu$ |  $\mu+1$
One-sided |  8 |  $x_{1}=x_{2}=\mu,\hskip 5.69046pta=a_{\nu+1}\oplus\sigma$ |  $(4\mu+2\nu+\sigma+1)+2$
XOR-gated |  8 |  $x_{1}=\mu,\hskip 5.69046ptx_{2}=\nu,\hskip 5.69046pta=a_{1}\oplus a_{2}\oplus\sigma$ |  $(4\mu+2\nu+\sigma+1)+10$
AND-gated |  32 |  $x_{1}=\mu,\hskip 5.69046ptx_{2}=\nu,$
$a=(a_{1}\oplus\sigma)(a_{2}\oplus\delta)\oplus\epsilon$ |  $(16\mu+8\nu+4\sigma+2\delta+\epsilon+1)+18$
Sequential |  32 |  $x_{\mu+1}=\nu,\hskip 5.69046ptx_{(\mu\oplus 1)+1}=a_{\mu+1}\oplus\sigma,$
$a=a_{(\mu\oplus 1)+1}\oplus\delta a_{\mu+1}\oplus\epsilon$ |  $(16\mu+8\nu+4\sigma+2\delta+\epsilon+1)+50$
Table 1: Labelling of 2-copy wirings. To iterate over all extremal wirings for
Bob, we consider all combinations of $\xi_{0}(b)$, $\xi_{1}(b)$ from the above
list, i.e., $82^{2}$ wirings.

Using this technique we can find whether there is a successful protocol for
2-copy non-locality distillation for any non-local box with two inputs and two
outputs. In the following we illustrate this on CSs I and II from the main
text. In both cases, the full optimisation shows that two protocols are
sufficient for characterising the region of 2-copy distillation in a CS. None
of the points that are not distillable with either of these protocols can be
distilled with any other 2-copy wiring there. In both CSs, we can choose non-
locality distillation protocols from the literature to achieve this, i.e.,
known protocols are among the optimal ones when considering the region of
distillation. Specifically, the region of distillation of CS I can be
characterised in terms of the protocol from Forster  _et al._ (2009), which we
call _FWW_ here, as well as a protocol from Allcock  _et al._ (2009), called
_ABL +1_ here, which are both given in the Tables 2 and 3. The parameters
$\omega$ and $\eta$ are chosen like in Figure I of the main text. Since the
boundary of this region can be established as those boxes $P$ for which 2-copy
distillation leads to a box $P^{\prime}$ such that
$\operatorname{CHSH}(P(ab|xy))=\operatorname{CHSH}(P^{\prime}(ab|xy))$, this
region can be characterised analytically.

protocol name |  wiring |  analytic boundary of the region of distillation ($\omega$ as a function of $\eta$) |  CHSH value of the distilled box
---|---|---|---
FWW Forster  _et al._ (2009) |  $x_{1}=x_{2}=x$
$y_{1}=y_{2}=y$
$a=a_{1}\oplus a_{2}$
$b=b_{1}\oplus b_{2}$ |  $\omega=1-3\eta+2\sqrt{1-3\eta+3\eta^{2}}$

$\eta\in[1/2,1]$ |  $\frac{1}{2}\Big{[}(1+\omega)^{2}-3\eta^{2}+6\eta(1+\omega)\Big{]}$
ABL+1 Allcock  _et al._ (2009) |  $x_{1}=x$
$y_{1}=y$
$x_{2}=x\oplus a_{1}\oplus 1$
$y_{2}=yb_{1}$
$a=a_{1}\oplus a_{2}\oplus 1$
$b=b_{1}\oplus b_{2}\oplus 1$ |  $\omega=-\eta+\frac{1}{\sqrt{3}}\sqrt{3-4\eta+4\eta^{2}}$

$\eta\in[0,1]$ |  $\frac{1}{4}\Big{[}3\omega^{2}+8\omega-\eta^{2}+\eta(4+6\omega)+5\Big{]}$
Table 2: Optimal 2-copy distillation protocols for CS I. protocol name |  wiring |  analytic boundary of the region of distillation ($\omega$ as a function of $\eta$) |  CHSH value of the distilled box
---|---|---|---
ABL+2 Allcock  _et al._ (2009) |  $x_{1}=x_{2}=x$
$y_{1}=y_{2}=y$
$a=a_{1}a_{2}$
$b=b_{1}b_{2}$ |  $\omega=3-11\eta+2\sqrt{3-18\eta+31\eta^{2}}$

$\eta\in[1/3,1]$ |  $\frac{1}{8}\Big{[}\omega^{2}+10\omega-3\eta^{2}+\eta(6+22\omega)+13\Big{]}$
ABL+1 Allcock  _et al._ (2009) |  $x_{1}=x$
$y_{1}=y$
$x_{2}=x\oplus a_{1}\oplus 1$
$y_{2}=yb_{1}$
$a=a_{1}\oplus a_{2}\oplus 1$
$b=b_{1}\oplus b_{2}\oplus 1$ |  $\omega=-\frac{4}{3}\eta+\frac{1}{3}\sqrt{9-18\eta+25\eta^{2}}$

$\eta\in[0,1]$ |  $\frac{1}{4}\Big{[}3\omega^{2}+8\omega-3\eta^{2}+\eta(6+8\omega)+5\Big{]}$
Table 3: Optimal 2-copy distillation protocols for CS II.

The two CSs are displayed in Figure I of the main text. The black line where
the two protocols work equally well is analytically characterised as

$\displaystyle\omega=5\eta-3,\hskip
14.22636pt\frac{1}{2}(1+\frac{1}{\sqrt{13}})\leq\eta\leq\frac{2}{3}$ (7)

in CS I and

$\displaystyle\omega=-\frac{2\sqrt{6}-3}{5}(\eta-1),\hskip
19.91684pt\frac{1}{25}(9+\sqrt{6})\leq\eta\leq 1$ (8)

in CS II.

We remark here that previously, heuristics to simplify the optimisation over
two-copy protocols have been proposed. For instance, the method in Brito  _et
al._ (2019) suggests to reduce the search over $82^{4}$ protocols to a
manageable number of only $3152$, by only considering protocols that preserve
the PR-box, $P^{\rm NL}_{1}$. Using linear programming, as proposed here, has
the advantage that it takes all distillation protocols into account. In
contrast, the heuristic from Brito  _et al._ (2019) discards various
protocols, e.g., FWW and ABL+2, that despite not preserving $P^{\rm NL}_{1}$,
are useful for non-locality distillation—they are even among the optimal
2-copy distillation protocols in CS I—so this shortcoming is pertinent.

##  Appendix B Sequential non-locality distillation into the region of trivial
communication complexity

In some situations we would like to distil non-locality up to a certain value
that is useful for a specific task, e.g. because a particular CHSH score is
needed in a device-independent scenario, or because we want to draw
conclusions about the properties of those correlations, e.g. that they are
unnatural since they imply that communication complexity is trivial. For this
purpose, 2 copies of a non-local box are usually not sufficient. Since the
repeated application of a fixed protocol is generally not successful in this
respect either, it is natural to combine _different_ protocols instead. There
are various “architectures” that such combinations can take, two of which are
displayed in Figure VII.

Figure VII: Two architectures for combining an arbitrary number of resource
boxes (gray) in a sequential manner. In each case, the purpose of our
sequential algorithm is to find new optimal wirings in each round. Thus, the
serial architecture on the left represents the serial algorithm of the main
text, Figure II. Similarly, the parallel architecture on the right will
represent the parallel algorithm.

Analysing all of the wirings that are possible in such a multi-round procedure
is computationally infeasible. We thus propose a sequential algorithm to
(partially) optimise these procedures. This algorithm (in either version of
Figure VII, serial or parallel or some alternatives, analysed more carefully
in Eftaxias (2022)) proceeds as follows:

  1. (1)

Optimise the wiring step by step using the procedure outlined in Appendix A.
As figure of merit to be optimised we use the CHSH value here.

  2. (2)

Stop the procedure when either a certain round number is reached or when the
CHSH value does not increase any further.

When applying the serial algorithm to the black points from Figure III,
choosing the serial architecture turned out to be more effective than the
parallel (in terms of distilled CHSH values). The tables below compare the
findings of the serial algorithm with repeated iterations of other protocols.

CS I, point $(\eta,\omega)=(0.888,0.1)$, $\text{CHSH}_{init}=2.2$
---
$\text{CHSH}_{final}$ , after # iterations | Serial Algorithm STRATEGIES
iter # |  two-copy ABL+1, blindly repetitive |  two-copy FWW, blindly repetitive |  two-copy
BS, blindly repetitive |  Serial Algorithm |  Alice’s wiring $(\chi_{x=0}\hskip 2.84544pt,\hskip 2.84544pt\chi_{x=1})$ |  Bob’s wiring $(\chi_{y=0}\hskip 2.84544pt,\hskip 2.84544pt\chi_{y=1})$
1 |  2.2815 |  2.3525 |  2.2812 |  2.3525 |  (12, 18) |  (12, 18)
2 |  2.3837 |  2.5546 |  2.3823 |  2.4681 |  (12, 18) |  (12, 18)
3 |  2.4964 |  2.7191 |  2.4918 |  2.5546 |  (12, 18) |  (12, 18)
4 |  2.5885 |  |  2.5749 |  2.6186 |  (12, 18) |  (12, 18)
5 |  2.5927 |  |  |  2.6729 |  (12, 78) |  (74, 78)
6 |  |  |  |  2.7236 |  (70, 82) |  (12, 82)
7 |  |  |  |  2.7706 |  (12, 78) |  (74, 78)
8 |  |  |  |  2.8143 |  (70, 82) |  (12, 82)
9 |  |  |  |  … |  $\circlearrowleft$ |  $\circlearrowleft$
10 |  |  |  |  … |  $\circlearrowright$ |  $\circlearrowright$
36 |  |  |  |  3.2683 |  (70, 82) |  (12, 82)
41 |  |  |  |  3.2730 |  (12, 78) |  (74, 78)
Table 4: Data about the lower black point of Figure III. The wirings are
described using the labellings of the last column of Table 1. The circular
arrows denote the continued switching between the two strategies appearing on
each side after the 4th iteration. The distilled CHSH values are recorded here
as long as they increase. The yellow shaded entries compare final-CHSH values
when each scheme has used 8 identical resource boxes. We observe that (37
copies of) the initial box trivializes communication complexity, a fact that
only the serial algorithm reveals. Figure VIII: Visualization of the data of
Table 4 (plus some further iterations that decrease the final-CHSH value).
Here, the superiority of the serial algorithm – as opposed to the independent
repetition of a fixed protocol– makes the initial box surpass the trivial
communication complexity threshold (dashed line). The horizontal axis shows
CHSH${}_{2}=E_{00}-E_{01}+E_{10}+E_{11}$. CS I, point
$(\eta,\omega)=(0.575,0.375)$, $\text{CHSH}_{init}=2.75$
---
$\text{CHSH}_{final}$ , after # iterations | Serial Algorithm STRATEGIES
iter # |  two-copy ABL+1, blindly repetitive |  two-copy FWW, blindly repetitive |  two-copy
BS, blindly repetitive |  Serial Algorithm |  Alice’s wiring $(\chi_{x=0}\hskip 2.84544pt,\hskip 2.84544pt\chi_{x=1})$ |  Bob’s wiring $(\chi_{y=0}\hskip 2.84544pt,\hskip 2.84544pt\chi_{y=1})$
1 |  2.9212 |  2.8212 |  2.9162 |  2.9212 |  (12, 78) |  (74, 78)
2 |  3.0294 |  |  3.0096 |  3.0452 |  (70, 82) |  (12, 82)
3 |  |  |  |  3.1327 |  $\circlearrowleft$ |  $\circlearrowleft$
4 |  |  |  |  3.1930 |  $\circlearrowright$ |  $\circlearrowright$
5 |  |  |  |  3.2324 |  $\circlearrowleft$ |  $\circlearrowleft$
6 |  |  |  |  3.2562 |  $\circlearrowright$ |  $\circlearrowright$
7 |  |  |  |  3.2683 |  (12, 78) |  (74, 78)
8 |  |  |  |  3.2718 |  (70, 82) |  (12, 82)
Table 5: Data for the higher black point of Figure III. The wirings are
described using the labellings of the last column of Table 1. The circular
arrows denote the continued switching between the two strategies appearing on
each side after the 4th iteration. The distilled CHSH values are recorded here
as long as they increase. The yellow shaded entries compare final CHSH values
when each scheme has used 4 identical resource boxes. We observe that (8
copies of) the initial box trivializes communication complexity, and again,
this is only revealed using the serial algorithm.

We can furthermore compare the different types of procedure. While we find
that in CSs I and II, the serial procedure is more successful with respect to
the increase in non-locality that is achieved, we have found other CSs where
the parallel is favourable. For more details and the analysis of further types
of procedures we refer to Eftaxias (2022).

##  Appendix C 3-copy distillation in the literature

So far, the 3-copy non-locality distillation protocol that was so far known in
the literature was introduced in Høyer and Rashid (2010). This is specified by
the following functions that make up the protocol HR:

Alice’s side |  Bob’s side
---|---
$x_{1}=x$ |  $y_{1}=y$
$x_{2}=x\oplus a_{1}$ |  $y_{2}=y\overline{b}_{1}$
$x_{3}=a_{2}\overline{a}_{1}\oplus x(a_{1}\oplus a_{2}\oplus a_{1}a_{2})$ |  $y_{3}=\overline{b}_{1}\oplus b_{2}\overline{b}_{1}\oplus y(\overline{b}_{2}\oplus b_{1}b_{2})$
$a=a_{1}\oplus a_{2}\oplus a_{3}$ |  $b=b_{1}\oplus b_{2}\oplus b_{3}$

In CS I, this protocol outperforms the 2-copy distillation protocol ABL+1 as
displayed in Figure IX around an indicated point. Our results show that for
that particular point HR can distill non-locality while _no_ 2-copy protocol
can. However, we also find that the region around that point where this is
possible is extremely small (see Figure IX). This is different for our genuine
3-copy protocols presented in the main text, for which this increase is
considerable.

Figure IX: The blue (gray) boundary includes the boxes that are distillable by
the ABL+1 (HR). The gray region depicts the set where HR achieves higher
distilled CHSH-values than ABL+1\. The bullet point corresponds to a box that
is distillable by ABL+1 but not by HR. Interestingly, the star (coordinates
$(\eta,\omega)=(\frac{3}{32},\frac{1}{32}(2\sqrt{227}-3))$) corresponds to a
box that is not distillable by ABL+1 (so, not distillable by any two-copy
protocol) but it can be distilled by HR.