# Expanding bipartite Bell inequalities for maximum multi-partite randomness

Lewis Wooltorton<EMAIL_ADDRESS>Department of Mathematics,
University of York, Heslington, York, YO10 5DD, United Kingdom  Quantum
Engineering Centre for Doctoral Training, H. H. Wills Physics Laboratory and
Department of Electrical & Electronic Engineering, University of Bristol,
Bristol BS8 1FD, United Kingdom  Peter Brown<EMAIL_ADDRESS>Télécom Paris, LTCI, Institut Polytechnique de Paris, 19 Place Marguerite
Perey, 91120 Palaiseau, France  Roger Colbeck<EMAIL_ADDRESS>Department of Mathematics, University of York, Heslington, York, YO10 5DD,
United Kingdom

($14^{\text{th}}$ August 2023)

###### Abstract

Nonlocal tests on multipartite quantum correlations form the basis of
protocols that certify randomness in a device-independent (DI) way. Such
correlations admit a rich structure, making the task of choosing an
appropriate test difficult. For example, extremal Bell inequalities are tight
witnesses of nonlocality, however achieving their maximum violation places
constraints on the underlying quantum system, which can reduce the rate of
randomness generation. As a result there is often a trade-off between maximum
randomness and the amount of violation of a given Bell inequality. Here, we
explore this trade-off for more than two parties. More precisely, we study the
maximum amount of randomness that can be certified by correlations exhibiting
a violation of the Mermin-Ardehali-Belinskii-Klyshko (MABK) inequality. We
find that maximum quantum violation and maximum randomness are incompatible
for any even number of parties, with incompatibility diminishing as the number
of parties grow, and conjecture the precise trade-off. We also show that
maximum MABK violation is not necessary for maximum randomness for odd numbers
of parties. To obtain our results, we derive new families of Bell inequalities
certifying maximum randomness from a technique for randomness certification,
which we call “expanding Bell inequalities”. Our technique allows one to take
a bipartite Bell expression, known as the seed, and transform it into a
multipartite Bell inequality tailored for randomness certification, showing
how intuition learned in the bipartite case can find use in more complex
scenarios.

##  I Introduction

Distant measurements on a shared quantum system can display correlations
inaccessible to any locally realistic model Bell (1987); Brunner  _et al._
(2014). Such correlations are termed nonlocal and provide a device-independent
(DI) witness of useful quantum characteristics, opening up a new paradigm of
information processing Barrett  _et al._ (2005a). Tasks such as randomness
expansion (DIRE) Colbeck (2007); Pironio  _et al._ (2010); Colbeck and Kent
(2011); Miller and Shi (2014, 2017), amplification Colbeck and Renner (2012)
and key distribution Ekert (1991); Barrett  _et al._ (2005b); Acin  _et al._
(2007); Pironio  _et al._ (2009); Vazirani and Vidick (2014); Arnon-Friedman
_et al._ (2018) can all be achieved in the DI regime, where security is proven
based on the observed correlations and without trusting the inner workings of
the devices. Moreover, nonlocal correlations can be used to prove the presence
of a particular state or sets of measurements, known as self-testing Mayers
and Yao (2004); McKague  _et al._ (2012); Yang and Navascués (2013);
Coladangelo  _et al._ (2017); Šupić  _et al._ (2022); Šupić and Bowles (2020).

Certification of randomness typically uses a Bell inequality and different
Bell inequalities give different amounts of certified randomness. Extremal
Bell inequalities are a natural set constituting the minimal set separating
local and non-local correlations. However, the set of correlations compatible
with high violation is tightly constrained and it is natural to ask how these
constraints affect the certification of randomness. For example, in the
simplest bipartite scenario, correlations with higher violation of the only
extremal Bell inequality, the Clauser-Horne-Shimony-Holt (CHSH) inequality,
cannot certify maximal DI randomness , while those with a lower violation can
Acín  _et al._ (2012); Wooltorton  _et al._ (2022). Further complications
arise when scarios with more inputs, outputs or parties are considered because
the number of different classes of extremal Bell inequalities grows and it
becomes more difficult to navigate the trade-offs between extremal Bell
violation and maximum certifiable randomness. Alongside foundational interest,
this question is also motivated practically, in finding more robust DIRE
protocols Wooltorton  _et al._ (2022).

In this work we study the family of multipartite Bell inequalities due to
Mermin, Ardehali, Belinskii, and Klyshko (MABK) Mermin (1990); Ardehali
(1992); Belinskiĭ and Klyshko (1993) and their usefulness for DIRE. These all
have two inputs and two outputs per party. The one and two sided randomness
given a tripartite MABK violation was bounded in Woodhead  _et al._ (2018);
Grasselli  _et al._ (2021), and compared to other tripartite inequalities in
Grasselli  _et al._ (2022). Considering global randomness, reference Bamps
_et al._ (2018) gave a bipartite construction for certification of $N$ bits of
randomness using $N$ copies of almost unentangled states.

Reference Dhara  _et al._ (2013) showed how, for an odd number of parties $N$,
maximum MABK violation can certify $N$ bits of DI randomness, whilst reference
de la Torre  _et al._ (2015) provided an alternative family of Bell
inequalities certifying $N$ bits in the even case. This leaves the open the
following questions: is MABK suitable for maximum randomness generation when
$N$ is even, and if not, what is the compatibility trade-off between MABK
violation and maximum randomness for arbitrary $N$? Are there correlations
with lower MABK that achieve maximal randomness when $N$ is odd?

To analyse multipartite nonlocality, we require tools to construct
multipartite Bell tests. To do so, one approach is to generalize intuition
from the well understood CHSH scenario; this has been done to extend the
number of measurements per party Braunstein and Caves (1990); Š upić  _et al._
(2016), or the number of parties Curchod  _et al._ (2019), where it was shown
how to construct multipartite Bell inequalities from a bipartite seed. Self-
testing results using projections onto bipartite subsystems Šupić  _et al._
(2018); Zwerger  _et al._ (2019); Li  _et al._ (2018) suggest stronger
capabilities of the technique presented in reference Curchod  _et al._ (2019),
prompting the question: can it be leveraged for multipartite randomness
certification?

Our work seeks to answer these questions. We show maximum MABK violation
certifies $N+1/2-\log_{2}(1+\sqrt{2})/\sqrt{2}\approx N-0.4$ bits of global
randomness when $N$ is even, and find a new family of constructions, for
arbitrary $N$, that certify $N$ bits. For the even case, our constructions
simultaneously achieve any MABK violation up to a non-maximal value, beyond
which, using a second construction, randomness necessarily trades off for
higher violation. Our results lower bound the randomness versus MABK trade-
off, and we provide a numerical upper bound which suggests tightness.
Additionally, we show that in the asymptotic limit our constructions achieve
arbitrarily close to the maximum quantum MABK value, whilst certifying maximal
DI randomness. We also use our first construction to conjecture that maximum
MABK violation is not necessary to achieve maximum randomness when $N$ is odd,
confirming this for specific values of $N$.

Our constructions are formed from concatenation, following intuition derived
from the bipartite case Wooltorton  _et al._ (2022). Specifically, we extend
the technique presented in reference Curchod  _et al._ (2019), originally
introduced to witness genuinely multipartite nonlocality. Our extension
exploits self-testing properties of the seed to certify randomness.
Specifically, our main technical contribution is a decoupling lemma (see Eq.
12), which shows under certain circumstances that the maximum violation of an
expanded Bell expression implies a decoupling between the honest parties and
Eve. Such decoupling occurs for extremal quantum correlations, and guarantees
security Franz  _et al._ (2011). We envisage this technique to be a useful
tool in multipartite DI cryptography and of independent interest. For the seed
inequality, we introduce a new family of versatile bipartite Bell expressions
(Lemma 8) and prove that they are self-tests, which may also be of independent
interest. This family generalises the families found in Wooltorton  _et al._
(2022).

The paper is structured as followed. In Section II we provide the necessary
background and notation. In Section III we detail our enhancement of the
technique from Curchod  _et al._ (2019), along with the decoupling lemma. In
Section IV we describe our constructions, and apply this technique to certify
$N$ bits of randomness across a broad range of MABK violations, which we
conjecture to be optimal; this result is summarized in Lemma 6. We
additionally show how the conjectured highest value of MABK at which maximum
randomness remains possible tends to the maximum quantum value as the number
of parties increases (see Proposition 4). In Section V we consider MABK values
beyond the conjectured threshold for maximum randomness, up to the maximum
quantum value. Here we give a candidate form for the exact trade-off, which is
summarized in Lemma 9. We conclude with a discussion in Section VI. All
technical proofs can be found in the appendices.

##  II Background

###  II.1 Multiparty DI-scenario

We consider an $N$ party, 2-input 2-output DI scenario, where $N$ isolated
devices are given a random input, labeled $x_{k}\in\\{0,1\\}$, and produce an
output $a_{k}\in\\{0,1\\}$ stored in a classical register $R_{k}$, where
$k\in\\{1,...,N\\}$ indexes the party. We use bold to denote tuples; for
example, $\bm{a}=(a_{1},...,a_{N})$ denotes an $N$ bit string of device
outputs. The behaviour of the devices is then described by the joint
conditional probability distribution $p(\bm{a}|\bm{x})$, which must be no-
signalling following the isolation of the devices.

A behaviour $p(\bm{a}|\bm{x})$ is quantum if there exists (following Naimark’s
dilation theorem Paulsen (2003)) a pure state and sets of orthonormal
projectors that can reproduce the distribution via the Born rule.
Specifically, we consider an adversary Eve, who wishes to guess the device
outputs, and let $|\Psi\rangle_{\tilde{\bm{Q}}E}$ denote the global state in
the Hilbert space $\mathcal{H}_{\tilde{\bm{Q}}}\otimes\mathcal{H}_{E}$, where
$\mathcal{H}_{\tilde{\bm{Q}}}=\bigotimes_{k=1}^{N}\mathcal{H}_{\tilde{Q}_{k}}$.
Throughout the text, tildes will denote elements pertaining to physical
Hilbert spaces $\mathcal{H}_{\tilde{Q}_{k}}$ (whose dimension is unknown),
whilst no tilde will describe qubit Hilbert spaces $\mathcal{H}_{Q_{k}}$. We
let $\\{\tilde{P}_{a_{k}|x_{k}}^{(k)}\\}_{a_{k}}$ be binary-outcome projective
measurements on $\mathcal{H}_{\tilde{Q}_{k}}$, and we denote the corresponding
observables of each party by
$\tilde{A}_{x_{k}}^{(k)}=\tilde{P}_{0|x_{k}}^{(k)}-\tilde{P}_{1|x_{k}}^{(k)}$;
here bracketed superscripts will typically keep track of the party to which
the object belongs. Following measurements $\bm{x}$ by the honest parties, we
obtain the classical quantum state
$\rho_{\bm{R}E|\bm{x}}=\sum_{\bm{a}}|\bm{a}\rangle\\!\langle\bm{a}|_{\bm{R}}\otimes\rho_{E}^{\bm{a}|\bm{x}}$,
where
$\rho_{E}^{\bm{a}|\bm{x}}=\mathrm{Tr}_{\tilde{\bm{Q}}}\big{[}(\tilde{P}_{\bm{a}|\bm{x}}\otimes\mathbb{I}_{E})|\Psi\rangle\\!\langle\Psi|_{\tilde{\bm{Q}}E}\big{]}$
and
$\tilde{P}_{\bm{a}|\bm{x}}=\bigotimes_{k=1}^{N}\tilde{P}_{a_{k}|x_{k}}^{(k)}$.
The behaviour is recovered by
$p(\bm{a}|\bm{x})=\mathrm{Tr}\big{[}\rho_{E}^{\bm{a}|\bm{x}}\big{]}$.

###  II.2 Multiparty Nonlocality

Given an observed distribution $p(\bm{a}|\bm{x})$, what is a suitable way to
quantify its distance from the local boundary? When $N=2$, the CHSH
inequality, as the only non-trivial facet, is a natural choice. The multiparty
scenario is more complex however, and the number of classes of Bell inequality
increases rapidly with $N$ Werner and Wolf (2001). Instead a general way to
quantify this distance for an arbitrary scenario can be used, which is related
to how much the local polytope needs to be diluted to encompass a given non-
local correlation. Computing this can be done using linear programming (see
Section B.5).

In this work, we choose to study one such CHSH generalization and its
relationship to DI randomness; the MABK family Mermin (1990); Ardehali (1992);
Belinskiĭ and Klyshko (1993),

$\langle
M_{N}\rangle=\frac{1}{2}\Bigg{(}\frac{1-i}{2}\Bigg{)}^{N-1}\Big{\langle}\prod_{k=1}^{N}(\tilde{A}_{0}^{(k)}+i\tilde{A}_{1}^{(k)})\Big{\rangle}\\\
+\frac{1}{2}\Bigg{(}\frac{1+i}{2}\Bigg{)}^{N-1}\Big{\langle}\prod_{k=1}^{N}(\tilde{A}_{0}^{(k)}-i\tilde{A}_{1}^{(k)})\Big{\rangle}\\\
=2^{\frac{1-N}{2}}\sum_{\bm{x}}\cos\Big{[}\frac{\pi}{2}\Big{(}\frac{N-1}{2}-\sum_{k=1}^{N}x_{k}\Big{)}\Big{]}\langle\tilde{A}_{\bm{x}}\rangle,$
(1)

where
$\langle\tilde{A}_{\bm{x}}\rangle=\sum_{\bm{a}}(-1)^{\sum_{k=1}^{N}a_{k}}p(\bm{a}|\bm{x})=\langle\Psi|\tilde{A}_{x_{1}}^{(1)}\otimes\cdots\otimes\tilde{A}_{x_{N}}^{(N)}\otimes\mathbb{I}_{E}|\Psi\rangle$
when the behaviour is quantum. [In effect the prefactor
$(-1)^{\sum_{k=1}^{N}a_{k}}$ corresponds to relabelling the outcomes $0\mapsto
1$ and $1\mapsto-1$ to match the usual formulation of observables with
eigenvalues $\pm 1$.] The local bound is given by $\langle M_{N}\rangle\leq
1$, and the maximum quantum value is $2^{(N-1)/2}$.

###  II.3 Self-testing

It is known that maximum quantum violation of the MABK family is uniquely
achieved, up to local isometries, by the GHZ state and pairs of maximally
anticommuting observables Kaniewski (2016, 2017). This form of uniqueness
arising from a Bell expression is known as self-testing. In this work, we take
the choice $|\psi_{\mathrm{GHZ}}\rangle=(|0\rangle^{\otimes
N}+i|1\rangle^{\otimes N})/\sqrt{2}$,
$A_{0}^{(k)}=\cos\theta_{N}^{+}\,\sigma_{X}+\sin\theta_{N}^{+}\,\sigma_{Y}$,
and
$A_{1}^{(k)}=\cos\theta_{N}^{-}\,\sigma_{X}+\sin\theta_{N}^{-}\,\sigma_{Y}$,
where $\theta_{N}^{\pm}=(\pi/4)(1/N\pm 1)$.

Whilst self-testing statements can be formally defined between $N$ parties
(see, e.g. Šupić  _et al._ (2018, 2022)), in our formulation it will only be
necessary to use a bipartite definition of self-testing.

######  Definition 1 (Bipartite self-test).

Let $k,l\in\\{1,...,N\\}$ index two distinct parties. Define the sets of
target qubit projectors $\\{P_{a_{k}|x_{k}}^{(k)}\\}_{a_{k}}$,
$\\{P_{a_{l}|x_{l}}^{(l)}\\}_{a_{l}}$, and a target two qubit state
$|\Phi\rangle_{Q_{k}Q_{l}}$. Let $I^{(k,l)}$ be a Bell operator between
parties $k$ and $l$, with maximum quantum value $\eta^{\mathrm{Q}}$. The
inequality $\langle I^{(k,l)}\rangle\leq\eta^{\text{Q}}$ _self-tests_ the
target state and measurements if, for all physical quantum strategies
$(\tilde{\rho}_{\tilde{Q}_{k}\tilde{Q}_{l}},\tilde{P}_{a_{k}|x_{k}}^{(k)},\tilde{P}_{a_{l}|x_{l}}^{(l)})$
that satisfy $\langle I^{(k,l)}\rangle=\eta^{\mathrm{Q}}$, there exists a
local isometery
$V:\mathcal{H}_{\tilde{Q}_{k}}\otimes\mathcal{H}_{\tilde{Q}_{l}}\otimes\mathcal{H}_{E}\rightarrow\mathcal{H}_{Q_{k}}\otimes\mathcal{H}_{Q_{l}}\otimes\mathcal{H}_{\mathrm{Junk}}$
and ancillary state $|\xi\rangle_{\mathrm{Junk}}$, such that

$V\Big{(}\tilde{P}_{a_{k}|x_{k}}^{(k)}\otimes\tilde{P}_{a_{l}|x_{l}}^{(l)}\otimes\mathbb{I}_{E}\Big{)}|\Psi\rangle_{\tilde{Q}_{k}\tilde{Q}_{l}E}\\\
=\Big{(}P_{a_{k}|x_{k}}^{(k)}\otimes
P_{a_{l}|x_{l}}^{(l)}\Big{)}|\Phi\rangle_{Q_{k}Q_{l}}\otimes|\xi\rangle_{\mathrm{Junk}}\,,$
(2)

for all $a_{k}$, $a_{l}$, $x_{k}$, $x_{l}$, where $|\Psi\rangle$ is a
purification of $\tilde{\rho}$.

We define the shifted Bell operator as
$\bar{I}^{(k,l)}=\eta^{\mathrm{Q}}\mathbb{I}-I^{(k,l)}$, and we say
$\bar{I}^{(k,l)}$ admits a sum-of-squares (SOS) decomposition if there exists
a set of polynomials, $\\{M^{(k,l)}_{i}\\}_{i}$, of the operators
$\tilde{P}_{a_{k}|x_{k}}^{(k)},\tilde{P}_{a_{l}|x_{l}}^{(l)}$, satisfying

$\bar{I}^{(k,l)}=\sum_{i}M^{(k,l)\dagger}_{i}M^{(k,l)}_{i}.$ (3)

SOS decompositions can be used to enforce algebraic constraints on any quantum
state $\tilde{\rho}$, and measurements
$\tilde{P}_{a_{k}|x_{k}}^{(k)},\tilde{P}_{a_{l}|x_{l}}^{(l)}$, satisfying
$\langle\bar{I}^{(k,l)}\rangle=\eta^{\mathrm{Q}}$. For example, when
$\tilde{\rho}=|\psi\rangle\\!\langle\psi|$ is pure, it must satisfy

$M_{i}^{(k,l)}|\psi\rangle=0,\ \forall i,$ (4)

(or $\mathrm{Tr}[(M_{i}^{(k,l)})^{\dagger}M_{i}^{(k,l)}\tilde{\rho}]=0$ more
generally). Typically, we find that constraints of the form in Eq. 4 are only
satisfied by a unique state (up to local isometeries), and when that is the
case we call Eq. 4 the self-testing criteria.

###  II.4 DI randomness certification

We use the conditional von Neumann entropy,
$H(\bm{R}|\bm{X}=\bm{x}^{*},E)_{\rho_{\bm{R}E|\bm{x}^{*}}}$ to measure the DI
randomness generation rate. This is the correct quantity for spot-checking DI
random number generation, where $\bm{x}^{*}$ is a specified measurement choice
used to generate randomness (see Bhavsar  _et al._ (2021) for a discussion of
this and other possibilities). The asymptotic rate of DI randomness generation
is given by

$r=\inf_{\begin{subarray}{c}|\Psi\rangle_{\tilde{\bm{Q}}E},\big{\\{}\\{\tilde{P}_{a_{k}|x_{k}}^{(k)}\\}_{a_{k}}\big{\\}}_{k}\\\
\mathrm{compatible\ with}\
f_{i}(P_{\mathrm{obs}})\end{subarray}}H(\bm{R}|\bm{X}=\bm{x}^{*},E)_{\rho_{\bm{R}E|\bm{x}^{*}}}$
(5)

and we require lower bounds on this quantity over states and measurements
compatible with the observed statistics, $P_{\mathrm{obs}}$, or linear
functions $f_{i}(P_{\mathrm{obs}})$ of them, such as the value of some Bell
expression. We will typically only consider one functional, $f$, which will be
a Bell inequality with observed value $f(P_{\mathrm{obs}})=\omega$; then we
denote the infimum in Eq. 5 as the function $R_{f}(\omega)$. The asymptotic
rate can be used as a basis for rates with finite statistics using tools such
as the entropy accumulation theorem Dupuis  _et al._ (2016); Dupuis and Fawzi
(2019); Metger  _et al._ (2022).

Because we study fundamental limits on certifiable DI randomness we work in
the noiseless scenario, using self-testing statements to certify DI
randomness. Here, $f(P_{\mathrm{obs}})$ is a Bell expression, and we show all
states and measurements that achieve its maximum violation correspond to a
post-measurement state in tensor product with Eve,
$\rho_{\bm{R}E|\bm{x}^{*}}=\rho_{\bm{R}|\bm{x}^{*}}\otimes\rho_{E}$. This
allows us to directly evaluate the conditional entropy
$H(\bm{R}|\bm{X}=\bm{x}^{*},E)=H(\bm{R}|\bm{X}=\bm{x}^{*})$, and the infimum
becomes trivial since all compatible strategies give rise to the same
classical distribution (see Appendix A.3 for details). The Bell expressions we
use are also applicable in the case of noise, following a method analogous to
that used in Wooltorton  _et al._ (2022).

##  III Expanding Bell inequalities

In this section we discuss and enhance the technique presented in Curchod  _et
al._ (2019), which allows us to derive the main results of this work. Ref.
Curchod  _et al._ (2019) introduced a method for building multipartite Bell
inequalities by expanding a bipartite inequality, called the “seed”, which can
be used to witness genuinely multipartite nonlocality. One constructs a new
Bell expression by summing the seed over different subsets of parties, whilst
the remaining parties perform some fixed measurement. The more multipartite
nonlocal the correlations, the more bipartite terms are violated. This
resembles other recent results that enable multipartite self-testing by
projections onto bipartite subsystems Li  _et al._ (2018); Šupić  _et al._
(2018); Zwerger  _et al._ (2019).

In this work we extend this technique to make it suitable for DI cryptographic
purposes. More precisely, we consider cases where the seed is a bipartite
self-test, and use the maximum quantum violation of the expanded Bell
expression, constructed in an equivalent manner to Curchod  _et al._ (2019),
to draw conclusions about the post-measurement state held between the honest
parties and Eve. These conclusions allow us to derive rates for randomness
certification.

###  III.1 Definition

We begin by introducing a generic formulation for expanding Bell expressions
Curchod  _et al._ (2019), shortly followed by an example.

######  Definition 2 (Expanded Bell expressions).

Let $\bm{C}$ be an $N\times N$ nonzero matrix with entries $c_{k,l}$
satisfying $c_{k,l}\in\\{0,1\\}$ if $k<l$, and $c_{k,l}=0$ otherwise. For each
pair $k,l$ for which $c_{k,l}\neq 0$ let
$\\{I^{(k,l)}_{\bm{\mu}}\\}_{\bm{\mu}}$ denote a set of bipartite Bell
expressions between parties $k$ and $l$ where $\bm{\mu}$ indexes over the
$N-2$ measurement outcomes of all parties excluding $k,l$ and each Bell-
inequality is equivalent up to output relabellings, with a local bound
$\eta^{\mathrm{L}}$ strictly less than the maximum quantum value
$\eta^{\mathrm{Q}}$. Then the expanded Bell operator $I$ from the seed
$I^{(k,l)}_{\bm{\mu}}$ is defined as

$I=\sum_{k,l}c_{k,l}\Bigg{(}\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}I^{(k,l)}_{\bm{\mu}}\Bigg{)},$
(6)

where
$\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}=\prod_{k^{\prime}=1,k^{\prime}\neq
k,l}^{N}\tilde{P}_{\mu_{k^{\prime}}|0}^{(k^{\prime})}$ is the projector for
all parties excluding $k$ and $l$, corresponding to the joint setting $\bm{0}$
and joint outcome $\bm{\mu}$111We have written the Bell operator in Eq. 6 in
terms of projectors, which is convenient since we consider quantum strategies.
We can however easily rewrite it in a theory independent way, by taking the
expectation value and making the substitution
$p(\bm{a}|\bm{x})=\langle\tilde{P}_{\bm{a}|\bm{x}}\rangle$. .

Consider the following tripartite example. To ease notation we label the
observables of the three parties $A_{x}=P^{A}_{0|x}-P^{A}_{1|x}$ and similarly
for $B$ and $C$. From reference Wooltorton  _et al._ (2022), observing
saturation of the following Bell expression certifies 2 bits of global
randomness,

$-3\sqrt{3}\leq\langle I^{A,B}\rangle\leq 3\sqrt{3},$ (7)

where $I^{A,B}=A_{0}B_{0}+2\big{(}A_{0}B_{1}+A_{1}B_{0}-A_{1}B_{1}\big{)}$.
The bound $\langle I^{A,B}\rangle=\pm 3\sqrt{3}$ is uniquely achieved, up to
local isometeries, by the bipartite strategy

$\begin{gathered}\rho_{Q_{A}Q_{B}}=|\Phi_{\pm}\rangle\\!\langle\Phi_{\pm}|,\
|\Phi_{\pm}\rangle=\frac{|00\rangle\pm i|11\rangle}{\sqrt{2}},\\\
A_{0}=B_{0}=\sigma_{X},\
A_{1}=B_{1}=\frac{-\sigma_{X}+\sqrt{3}\sigma_{Y}}{2}.\end{gathered}$ (8)

Now consider a tripartite extension of the above strategy,

$\begin{gathered}\rho_{Q_{A}Q_{B}Q_{C}}=|\psi_{\mathrm{GHZ}}\rangle\\!\langle\psi_{\mathrm{GHZ}}|,\\\
A_{0}=B_{0}=C_{0}=\sigma_{X},\
A_{1}=B_{1}=C_{1}=\frac{-\sigma_{X}+\sqrt{3}\sigma_{Y}}{2}.\end{gathered}$ (9)

One can verify that when all three parties measure $x=y=z=0$, their outcomes
are uniformly distributed, resulting in 3 bits of raw randomness; how can we
certify this device-independently? Notice $|\psi_{\mathrm{GHZ}}\rangle$ has
the following property: when a single party, say $A$, measures $\sigma_{X}$,
the leftover state held by $BC$ is $|\Phi_{\pm}\rangle$ where the sign depends
on the parity of $A$’s measurement outcome $\mu\in\\{0,1\\}$. Party $B$ and
$C$ can now saturate one of the bounds $\langle I^{B,C}\rangle=\pm 3\sqrt{3}$
conditioned on $A$’s measurement. By using $I^{A,B}_{\mu}=(-1)^{\mu}I^{A,B}$
as the seed, and choosing the matrix $\bm{C}$ with party indexes
$k,l\in\\{A,B,C\\}$,

$\bm{C}=\begin{bmatrix}0&0&1\\\ 0&0&1\\\ 0&0&0\end{bmatrix},$ (10)

we can construct the expanded Bell expression according to Footnote 1:

$I=\underbrace{P_{\mu=0|y=0}^{A}I^{B,C}-P_{\mu=1|y=0}^{A}I^{B,C}}_{k=A,l=C}\\\
+\underbrace{P_{\mu=0|y=0}^{B}I^{A,C}-P_{\mu=1|y=0}^{B}I^{A,C}}_{k=B,l=C}\\\
=A_{0}I^{B,C}+B_{0}I^{A,C}.$ (11)

Due to the properties of $|\psi_{\mathrm{GHZ}}\rangle$ discussed above, we
find $\langle I\rangle=2\cdot 3\sqrt{3}$ is achieved by the strategy in Eq. 9,
and that $I$ is a nontrivial Bell inequality, i.e., one that can be violated
by quantum theory. In Lemma 1 we prove this claim in full generality, and will
later rigorously prove that this is a sufficient condition for certifying
maximum randomness.

We call $I$ an expanded Bell expression, since it is built from combining a
bipartite seed, $I_{\bm{\mu}}^{(k,l)}$, conditioned on fixed measurement
settings $\bm{0}$ and outcomes $\bm{\mu}$ for the remaining $N-2$ parties. We
then sum over all possible outcomes of this $N-2$ party measurement, changing
the Bell expression accordingly, and over different combinations of parties
$(k,l)$ chosen according to $\bm{C}$. There needs to be a gap between the
local and quantum bounds of $\langle I\rangle$ for $I$ to define a nontrivial
Bell inequality; typically, we find the following upper bound is achievable,
which is strictly greater than the local bound:

######  Lemma 1.

Let $I$ be an expanded Bell expression according to Footnote 1. The maximum
quantum value of $\langle I\rangle$ is upper bounded by
$\eta^{\mathrm{Q}}_{N}:=\sum_{k,l}c_{k,l}\eta^{\mathrm{Q}}$.

Naturally, the only strategy that can achieve $\langle
I\rangle=\eta^{\mathrm{Q}}_{N}$ is the one satisfying
$\big{\langle}\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}I^{(k,l)}_{\bm{\mu}}\big{\rangle}=\eta^{\mathrm{Q}}$
for all pairing combinations $k,l$ with $c_{k,l}>0$, i.e., the reduced state
held between parties $k$ and $l$, following the projection
$\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}$ on the global state, must
achieve the maximum quantum value of $\langle
I^{(k,l)}_{\bm{\mu}}\rangle=\eta^{\mathrm{Q}}$. This explains why we must
include a dependence on $\bm{\mu}$ for the Bell expression, since it should be
tailored to the bipartite state following the outcome $\bm{\mu}$. For
simplicity we assume each bipartite state is equivalent up to local unitaries,
meaning we effectively use a single seed $I_{\bm{\mu}}^{(k,l)}$. In principle
however, one could use different seeds depending on the value of $\bm{\mu}$,
which tailors the construction to non-symmetric states Curchod  _et al._
(2019). For our work we only consider the symmetric case. Additionally, one
could further generalize by choosing specific measurement choices $\bm{y}$
dependent on the choice of non-projecting parties $k,l$, instead of fixing
$\bm{y}=\bm{0}$ as we have done here. A proof of Lemma 1 is given in Section
A.1.

###  III.2 Expanding Bell expressions and entropy evaluation

Next we present the characteristic of expanded Bell expressions that allows us
to certify DI randomness from witnessing its maximum quantum value, forming
the main technical contribution of our work.

######  Lemma 2 (Decoupling lemma).

Let $I$ be an expanded $N$-party Bell expression defined in Footnote 1 with
binary inputs and outputs, and $c_{k,N}=1$ if $k<N$ and zero otherwise.
Suppose for every $I_{\bm{\mu}}^{(k,N)}$, there exists an SOS decomposition
that self-tests the same pure bipartite entangled state $|\Phi\rangle$ between
parties $k$ and $N$, along with some ideal measurements
$P^{(k)}_{a_{k}|x_{k}},P^{(N)}_{a_{N}|x_{N}}$, according to Eq. 2, satisfying
$\langle\Phi|P^{(k)}_{a_{k}|0}\otimes P^{(N)}_{a_{N}|0}|\Phi\rangle>0$ for all
$a_{k},a_{N}$. Then for any strategy
$|\Psi\rangle_{\tilde{\bm{Q}}E},\big{\\{}\\{\tilde{P}_{a_{k}|x_{k}}^{(k)}\\}_{x_{k}}\big{\\}}_{k}$
that achieves $\langle I\rangle=\eta^{\mathrm{Q}}_{N}$, the post-measurement
state $\rho_{\bm{R}E}$, for measurement settings $\bm{x}=\bm{0}$, admits the
tensor product decomposition,

$\rho_{\bm{R}E|\bm{0}}=\rho_{\bm{R}|\bm{0}}\otimes\rho_{E}.$ (12)

Having established that Eve is decoupled it is then straightforward to
evaluate the rate in Eq. 5 conditioned on observing the maximum quantum value
of $I$.

######  Lemma 3.

Let $I,\eta_{N}^{\mathrm{Q}}$ be defined as in Eq. 12. Then

$R_{I}(\eta_{N}^{\mathrm{Q}})=H(\\{p(\bm{a}|\bm{0})\\}),$ (13)

where $H(\\{p_{i}\\})$ is the Shannon entropy of a distribution
$\\{p_{i}\\}_{i}$.

The proof can be found in Section A.3. Eq. 12 allows one to relate observing
the maximum quantum value of the expanded Bell expression $I$, to a condition
on the post-measurement state held by the parties and Eve, namely that it must
be in tensor product with the purifying system $E$. This allows one to
directly evaluate the conditional entropy according to Lemma 3.

##  IV Certifying $N$ bits of DI randomness

We now consider constructions for generating $N$ bits of DI randomness. As
previously mentioned, when $N$ is odd the MABK family can be used Dhara  _et
al._ (2013). For an arbitrary number of parties, we apply the previously
outlined techniques to derive a suitable Bell expression for this task. This
will involve generalizing a one parameter family of quantum strategies,
symmetric under permutation of the parties.

###  IV.1 $N$ odd

Using symmetry arguments, the authors of Ref. Dhara  _et al._ (2013) showed
that maximum violation of the MABK inequality, for $N$ odd, implies maximum
randomness.

######  Proposition 1 (Maximum randomness for $N$ odd Dhara  _et al._ (2013)).

When $N$ is odd, maximum quantum violation of the MABK family of Bell
inequalities, given by Eq. 1, certifies $N$ bits of global DI randomness, i.e.

$R_{M_{N}}(2^{(N-1)/2})=N.$ (14)

From a self-testing point of view, maximum violation of the MABK family can
only be achieved with a GHZ state and maximally anticommuting observables
Kaniewski (2016, 2017). For the form given in Eq. 1, the following strategy
achieves maximum violation for $N$ odd:

$\begin{gathered}\rho_{\bm{Q}}=|\psi_{\mathrm{GHZ}}\rangle\\!\langle\psi_{\mathrm{GHZ}}|\\\
A_{0}^{(k)}=\cos\theta_{N}^{+}\,\sigma_{X}+\sin\theta_{N}^{+}\,\sigma_{Y},\\\
A_{1}^{(k)}=\cos\theta_{N}^{-}\,\sigma_{X}+\sin\theta_{N}^{-}\,\sigma_{Y},\\\
k\in\\{1,...,N\\},\end{gathered}$ (15)

where $\theta_{N}^{\pm}=\pi/(4N)\pm\pi/4$, and satisfies
$A_{0}^{(k)}A_{1}^{(k)}+A_{1}^{(k)}A_{0}^{(k)}=0$ for each $k$. Following this
self-testing property, the infimum in Eq. 14 reduces to a single point up to
symmetries, and the pure state held by the parties implies Eve must be
uncorrelated, i.e.,
$\rho_{\bm{R}E|\bm{x}^{*}}=\rho_{\bm{R}}^{\bm{x}^{*}}\otimes\rho_{\bm{E}}$. By
direct calculation, one can verify for $N=4n-1$, $n=1,2,3,...$,
$p(\bm{a}|\bm{0})=1/2^{N},\forall\bm{a}$, hence $H(\\{p(\bm{a}|\bm{0})\\})=N$.
Similarly for $N=4n+1$, $n=1,2,3,...$,
$p(\bm{a}|\bm{1})=1/2^{N},\forall\bm{a}$, implying
$H(\\{p(\bm{a}|\bm{1})\\})=N$.

Taking $N=3$ in the above construction we have
$M_{3}=\big{(}\langle\tilde{A}_{1}^{(0)}\tilde{A}_{0}^{(1)}\tilde{A}_{0}^{(2)}\rangle+\langle\tilde{A}_{0}^{(0)}\tilde{A}_{1}^{(1)}\tilde{A}_{0}^{(2)}\rangle+\langle\tilde{A}_{0}^{(0)}\tilde{A}_{0}^{(1)}\tilde{A}_{1}^{(2)}\rangle-\langle\tilde{A}_{1}^{(0)}\tilde{A}_{1}^{(1)}\tilde{A}_{1}^{(2)}\rangle\big{)}/2$,
and the strategy in Eq. 15 reaches the algebraic bound of $2$. It turns out
$M_{3}=0$ implies $3$ bits of randomness when all three parties measure $0$.
On the other hand, the correlators in the inequality must take the values $\pm
1$ to reach the algebraic bound, so none of the input settings used in the
inequality can generate more than 2 bits of global randomness (in fact they
give exactly 2 bits when $M_{3}=0$).

###  IV.2 $N$ even

When $N$ is even, all full body correlators must have non-zero weight to
achieve the largest possible quantum value of MABK. This is incompatible with
maximum randomness from one input combination. Hence, achieving the quantum
bound does not certify maximum randomness; we show in Section V that maximum
MABK violation certifies $N+1/2-\log_{2}(1+\sqrt{2})/\sqrt{2}\approx N-0.4$
bits of global DI randomness.

To do so we find a new Bell expression which is tailored to a strategy of the
form in Eq. 15. We use the techniques introduced in Section III to generalize
the $N=2$ case, which was addressed in Wooltorton  _et al._ (2022).

####  IV.2.1 Bipartite self-tests

To begin with, we summarize the results obtained for the $N=2$ case.

######  Lemma 4 ($I_{\theta}$ family of self-tests).

Define the set
$\mathcal{G}=(\pi/4,\pi/2)\cup(\pi/2,3\pi/4)\cup(5\pi/4,3\pi/2)\cup(3\pi/2,7\pi/4)$222Note
that $\mathcal{G}=\left\\{\theta\in[0,2\pi]\mid\cos(2\theta)<0,\
\cos(\theta)\neq 0\right\\}$.. Let $\theta\in\mathcal{G}$, and define the
family of Bell expressions parameterized by $\theta$, for parties
$k,l\in\\{1,...,N\\}$,

$\langle I_{\theta}^{(k,l)}\rangle=\cos\theta\cos 2\theta\langle
A_{0}^{(k)}A_{0}^{(l)}\rangle-\\\ \cos 2\theta\big{(}\langle
A_{0}^{(k)}A_{1}^{(l)}\rangle+\langle
A_{1}^{(k)}A_{0}^{(l)}\rangle\big{)}+\cos\theta\langle
A_{1}^{(k)}A_{1}^{(l)}\rangle.$ (16)

Then we have the following:

  1. (i)

The local bounds are given by $\pm\eta_{\theta}^{\mathrm{L}}$, where

$\eta_{\theta}^{\mathrm{L}}=\mathrm{max}\Big{(}|\cos\theta(1-\cos
2\theta)|,\\\ |\cos\theta\big{(}1+\cos 2\theta\big{)}|+|2\cos
2\theta|\Big{)}.$ (17)

  2. (ii)

The quantum bounds are given by $\pm\eta_{\theta}^{\mathrm{Q}}$, where
$\eta_{\theta}^{\mathrm{Q}}=2\sin^{3}\theta$.

  3. (iii)

Up to local isometries, there exists a unique strategy that achieves $\langle
I_{\theta}\rangle=\eta_{\theta}^{\mathrm{Q}}$:

$\displaystyle\rho_{Q_{k}Q_{l}}$ $\displaystyle=|\psi\rangle\\!\langle\psi|,\
\mathrm{where}\
|\psi\rangle=\frac{1}{\sqrt{2}}\big{(}|00\rangle+i|11\rangle\big{)}$ (18)
$\displaystyle A_{0}^{(k)}$ $\displaystyle=A_{0}^{(l)}=\sigma_{X}$
$\displaystyle A_{1}^{(k)}$
$\displaystyle=A_{1}^{(l)}=\cos\theta\,\sigma_{X}+\sin\theta\,\sigma_{Y}.$

The above lemma is a rewriting of Proposition 1 in Wooltorton  _et al._
(2022), and its proof is deferred to Lemma 7 for which the above claim can be
recovered as a special case. Importantly, the self-testing property implies
both parties measure $\sigma_{X}$ on $|\psi\rangle$, which results in 2 bits
of randomness, $H(\\{p(ab|00)\\})=2$. We also remark that the state
$|\psi^{\prime}\rangle=(|00\rangle-|11\rangle)/\sqrt{2}$ with the same
measurements achieves $\langle I_{\theta}\rangle=-\eta_{\theta}^{\mathrm{Q}}$.
This is a symmetry of the case above, since relabeling the measurement
outcomes of party $k$ yields the new Bell expression
$I_{\theta}^{\prime}=-I_{\theta}$. Therefore $\langle
I_{\theta}\rangle=-\eta_{\theta}^{\mathrm{Q}}$ implies $\langle
I_{\theta}^{\prime}\rangle=\eta_{\theta}^{\mathrm{Q}}$, which self-tests
$|\psi\rangle$ and the negated measurements, or equivalently
$|\psi^{\prime}\rangle$ and the original measurements.

####  IV.2.2 Target strategy

For the $N$ partite case, we generalize the above bipartite strategy. The
target $N$-partite strategy takes a form similar to that in Eq. 15, but with
an added parameter $\theta$ to choose the second measurement:

$\begin{gathered}\rho_{\bm{Q}}=|\psi_{\mathrm{GHZ}}\rangle\\!\langle\psi_{\mathrm{GHZ}}|\\\
A_{0}^{(k)}=\sigma_{X},\\\
A_{1}^{(k)}=\cos\theta\,\sigma_{X}+\sin\theta\,\sigma_{Y},\
k\in\\{1,...,N\\}.\end{gathered}$ (19)

As before, we find $p(\bm{a}|\bm{0})=1/2^{N},\forall\bm{a}$, hence this is a
target strategy for certifying $N$ bits of global randomness. Our objective
now will be to design a tailored Bell inequality that can certify $N$ bits by
witnessing its maximum value, attained by the strategy in Eq. 19.

####  IV.2.3 Constructing an $N$-partite Bell inequality

We use the techniques introduced in Section III to construct the desired Bell
expression by expanding the seed $I_{\theta}$. Studying the strategy in Eq.
19, we notice when $N-2$ parties perform their first measurement,
$\sigma_{X}$, depending on the outcome parity the post-measurement state for
the remaining parties is $(|00\rangle\pm i|11\rangle)/\sqrt{2}$. Now,
performing the measurements in Eq. 19 on that post-measurement state achieves
$\langle I_{\theta}\rangle=\pm\eta_{\theta}^{\mathrm{Q}}$, which, according to
the self-testing properties of $I_{\theta}$, will certify 2 bits of
randomness. Since the strategy is symmetric under party permutations, we can
repeat this argument over different subsets of $N-2$ parties, and conclude
that, when every bipartite self-test is satisfied, the output setting
$\bm{X}=\bm{0}$ must generate uniform DI randomness. The corresponding Bell
inequality is constructed according to the following lemma.

######  Lemma 5 (Bell inequality for maximum randomness).

Let $\bm{\mu}$ be a tuple of $N-2$ measurement outcomes for all parties
excluding $k,l$, and $n_{\bm{\mu}}\in\\{0,1\\}$ be the parity of $\bm{\mu}$.
Let $\theta\in\mathcal{G}$ and $\\{I_{\bm{\mu}}^{(k,l)}\\}_{\bm{\mu}}$ be a
set of bipartite Bell expressions between parties $k,l$, where

$I_{\bm{\mu}}^{(k,l)}=(-1)^{n_{\bm{\mu}}}I_{\theta}^{(k,l)}.$ (20)

Then the expanded Bell expression given by

$I_{\theta}=\sum_{k=1}^{N-1}\Bigg{(}\sum_{\bm{\mu}}\tilde{P}^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}I_{\bm{\mu}}^{(k,N)}\Bigg{)}$
(21)

has quantum bounds $\pm\eta_{N,\theta}^{\mathrm{Q}}$ where
$\eta_{N,\theta}^{\mathrm{Q}}=2(N-1)\sin^{3}\theta$, achieved up to
relabelings by the strategy in Eq. 19, and defines a nontrivial Bell
inequality.

The proof can be found in Section B.1.

We can now state our first main result:

######  Proposition 2 (Maximum randomness certification).

Achieving the maximum quantum value of the Bell inequality in Lemma 5
certifies $N$ bits of global randomness, i.e.

$R_{I_{\theta}}(\eta_{N,\theta}^{\mathrm{Q}})=N.$ (22)

The proof is obtained directly by relating maximimal Bell violation to
decoupling Eve from the post-measurement state, proven in Eqs. 12 and 3.

###  IV.3 MABK value and maximum randomness

Above we gave a new one parameter construction for certifying $N$ bits of
device-independent randomness in any $N$-party 2-input 2-output scenario. Now
we will study some properties of the correlations used to certify maximum
randomness. In particular we’re interested in how maximal randomness and
nonlocality tradeoff against each other. For instance, how nonlocal can
correlations be whilst certifying maximal randomness?

####  IV.3.1 Achievable MABK values with maximum randomness

When $N$ is odd, we have discussed that one can always certify $N$ bits of DI
randomness from maximum MABK violation; for the even case, it is unclear how
large the MABK value can be whilst certifying maximum randomness. Using the
fact that, for the strategy in Eq. 19, $\langle A_{\bm{x}}\rangle=\sin
n\theta$, where $n=\sum_{k=1}^{N}x_{k}$, its MABK value is given by

$\langle
M_{N}(\theta)\rangle=2^{\frac{N-1}{2}}\Big{(}\cos^{N}\big{(}\theta/2+\pi/4\big{)}\sin\big{(}N\theta/2+\pi/4\big{)}\\\
+\cos^{N}\big{(}\theta/2-\pi/4\big{)}\sin\big{(}N\theta/2-\pi/4\big{)}\Big{)}.$
(23)

We begin with the following proposition:

######  Proposition 3.

For $N$ even, let

$\theta^{*}_{N}=\frac{2\pi t_{N}}{N+1},$ (24)

where $t_{N}$ is the $(N/2)^{\mathrm{th}}$ element of the sequence
$1,1,5,7,3,3,11,13,5,5,...$ given by

$t_{N}=\begin{cases}N/4+1/2,\ \mathrm{if}\ N=8n+2,\\\ N/4,\ \mathrm{if}\
N=8n+4,\\\ 3N/4+1/2,\ \mathrm{if}\ N=8n+6,\\\ 3N/4+1,\ \mathrm{if}\ N=8n+8,\
n\in\mathbb{N}_{0}.\end{cases}$ (25)

Then $\theta^{*}_{N}\in\mathcal{G}$.

Proof can be found in Section B.2. This allows us to state the following
technical conjecture, for which we have convincing evidence for:

######  Conjecture 1.

Let $\theta_{N}^{*}$ be defined in Eq. 25, and define the corresponding MABK
violation

$m_{N}^{*}=\langle M_{N}(\theta^{*}_{N})\rangle.$ (26)

Then we have the following for $N$ even.

  1. (i)

For every MABK value $s$ in the range $(1,m_{N}^{*}]$, there exists a
$\theta_{s}\in\mathcal{G}$ that satisfies $s=\langle
M_{N}(\theta_{s})\rangle$.

  2. (ii)

$m_{N}^{*}$ is the maximum MABK value achievable by quantum strategies which
generate maximum randomness, i.e., strategies with $p(\bm{a}|\bm{0})=1/2^{N},\
\forall\bm{a}$.

For $N$ odd we have:

  1. (iii)

For every MABK value $s$ in the range $(1,2^{(N-1)/2})$, there exists a
$\theta_{s}\in\mathcal{G}$ that satisfies $s=\langle
M_{N}(\theta_{s})\rangle$.

Following 1, we can state the range of MABK violations for which maximum DI
randomness can be certified.

######  Lemma 6 (MABK violations achievable with maximum DI randomness).

Suppose 1 holds. Then

  1. (i)

for $N$ even the maximum amount of device-independent randomness that can be
certified for the range of MABK values $(1,m_{N}^{*}]$ is $N$ bits;

  2. (ii)

for $N$ odd the maximum amount of device-independent randomness that can be
certified for the range of MABK values $(1,2^{(N-1)/2}]$ is $N$ bits.

Should part $(i)$ of 1 hold, by varying $\theta\in\mathcal{G}$, the family of
strategies in Eq. 19 achieves every MABK value in the interval
$(1,m_{N}^{*}]$. Since $\theta\in\mathcal{G}$ for all these values, the
corresponding bipartite strategy is self-testable according to Lemma 4; we can
hence apply Lemma 5 to expand the Bell expression to $N$ parties, and it
follows from Lemma 3 that this Bell expression certifies $N$ bits of DI
randomness. We provide evidence for part $(i)$ in Fig. 1, by evaluating the
Mermin value for a given $N$ as a function of $\theta\in\mathcal{G}$, and
showing the full range of violations $(1,m_{N}^{*}]$ is accessible.

Figure 1: Using the family of strategies in (19) for even $N$ we plot the MABK
value renormalized by the maximum quantum value over all strategies (i.e.,
$2^{(N-1)/2}$) in terms of $\theta\in[\pi/4,3\pi/4]$, and
$\theta\in[5\pi/4,7\pi/4]$ respectively. The dashed lines indicate where the
strategy becomes local. All points in this interval, excluding the boundaries
and center point, correspond to strategies that certify $N$ bits of randomness
device-independently using our expanded Bell expressions.

Due to Eq. 25, the MABK value $m_{N}^{*}$ becomes an achievable lower bound on
the maximum MABK value for quantum correlations certifying maximum randomness.
Part $(ii)$ of 1 says this is optimal, in the sense that one cannot achieve a
larger MABK value whilst simultaneously certifying maximum randomness. As
evidence we derive a numerical technique that can generate upper bounds on
this question, and show these upper bounds match the lower bounds for some
specific $N$. See Section B.3 for the details.

Finally, part $(iii)$ of 1 implies that when $N$ is odd, one can always
achieve maximum randomness and any MABK value simultaneously. For the case of
$\langle M_{N}\rangle=2^{(N-1)/2}$, i.e., the maximum quantum value,
randomness can be certified according to Eq. 14. For all other MABK values, we
conjecture maximum randomness can be certified by $I_{\theta}$ for some
$\theta\in\mathcal{G}$. Evidence for this can be found in Fig. 2, where we
plot the MABK value as a function of $\theta$ for different $N$, and see that
maximal randomness is compatible with all nonlocal values of MABK that are
achievable.

Figure 2: A similar plot to that of Fig. 1 for odd $N$ and second measurement
angle of all parties $\theta\in[\pi/4,3\pi/4]$, and $\theta\in[5\pi/4,7\pi/4]$
respectively. All points in this interval, excluding the boundaries,
correspond to strategies that can certify $N$ bits of randomness device-
independently, using our expanded Bell expressions, or using the MABK
inequality for the center points.

The discussion above leads to the further conjecture that, as was proven for
the $N=2$ case Wooltorton  _et al._ (2022); Acín  _et al._ (2012), one can
always achieve maximum randomness device-independently with correlations that
lie arbitrarily close to the MABK facet of the local polytope. There is also a
nontrivial maximal MABK violation for which this randomness is achievable when
$N$ is even, unlike the odd case; as discussed in Section IV.1, this can be
seen as a consequence of the $N$ even MABK expressions containing every $N$
party correlator. When maximum randomness is being certified, one of these
correlators must be zero, which restricts the maximum MABK violation to be
strictly less than the optimal quantum value.

####  IV.3.2 Asymptotic behaviour

We now consider the behaviour of the conjectured maximal MABK value achievable
with maximum randomness, $m_{N}^{*}$ for increasingly large even $N$. We show
that $m_{N}^{*}$ converges to the largest possible quantum value in this
limit. Note this is not based on a conjecture; $m_{N}^{*}$ is an achievable
lower bound, and in the following proposition we show this lower bound tends
towards the global upper bound, namely the maximal quantum MABK value.

######  Proposition 4 (Maximum randomness in the asymptotic limit).

In the limit of large even $N$, one can achieve arbitrarily close to the
maximum quantum violation of the $N$ party MABK inequality, $2^{(N-1)/2}$,
whilst certifying maximum device-independent randomness.

This is proven in Section B.4.

####  IV.3.3 Nonlocality and maximum randomness

Whilst we have studied the MABK values achieved by the strategies in Eq. 19,
we also consider how nonlocal they are, quantified by how much the local set
needs to be “diluted” to contain them. We refer to this measure as the local
dilution, which can be computed via a linear program (LP) for small $N$, and
we give details in Section B.5. Our findings are presented in Fig. 3.

Figure 3: Nonlocality, as measured using local dilution, of the strategies in
Eq. 19, for second measurement angle of all parties $\theta\in[0,\pi]$. All
values of $\theta\in(\pi/4,\pi/2)\cup(\pi/2,3\pi/4)$ correspond to strategies
which can certify $N$ bits of maximum randomness using our technique for
expanding Bell expressions. $\theta=\pi/2$ can also correspond to maximum
randomness when $N$ is odd by testing the MABK inequality.

Interestingly, for $N>2$ the correlations of the strategy in Eq. 19 are not
close to the local boundary for any $\theta\in\mathcal{G}$, even for small
MABK violation; whilst the violation of a given MABK inequality can be made
arbitrarily small, the correlations are still distant from the local boundary.
In fact, by comparing Fig. 3 with Fig. 1 and Fig. 2, one can see how
correlations achieving at or below the maximum local MABK value, $\langle
M_{N}\rangle\leq 1$, can still be nonlocal and certify maximum randomness.
This is because the correlations violate some other Bell inequality,
highlighting the complexity of randomness versus nonlocality in the
multipartite scenario.

##  V Trade-off between DI randomness and MABK violation

In this section, we present an achievable lower bound on the maximum device-
independent randomness that can be generated by correlations achieving any
given MABK violation. Moreover, we conjecture this lower bound to be tight
based on numerical evidence. This is achieved by introducing a new family of
two parameter quantum strategies along with their self-testing Bell
expressions. Using this as the seed, we construct a multipartite Bell
expression which certifies their randomness.

###  V.1 Constructing the Bell expression

####  V.1.1 Bipartite self-tests

We begin by introducing a versatile family of bipartite self-tests which
generalize the results in Wooltorton  _et al._ (2022).

######  Lemma 7 ($J_{\phi,\theta}$ family of self-tests).

Let $(\phi,\theta)\in\mathbb{R}^{2}$ such that $\cos(2\theta)\cos(2\phi)<0$
and $\cos(\theta-\phi)\neq 0$333The reason for this condition is explained in
Section B.6.. Define the family of Bell expressions parameterized by $\phi$
and $\theta$,

$\langle J_{\phi,\theta}^{(k,l)}\rangle=\cos 2\theta\cos(\theta-\phi)\langle
A_{0}^{(k)}A_{0}^{(l)}\rangle\\\ -\cos 2\theta\cos 2\phi\big{(}\langle
A_{0}^{(k)}A_{1}^{(l)}\rangle+\langle A_{1}^{(k)}A_{0}^{(l)}\rangle\big{)}\\\
+\cos 2\phi\cos(\theta-\phi)\langle A_{1}^{(k)}A_{1}^{(l)}\rangle.$ (27)

Then we have the following:

  1. (i)

The local bounds are given by $\pm\eta_{\phi,\theta}^{\mathrm{L}}$, where

$\eta_{\phi,\theta}^{\mathrm{L}}=\max\big{\\{}|\cos(\theta-\phi)(\cos
2\theta-\cos 2\phi)|,\\\ |\cos(\theta-\phi)\big{(}\cos 2\theta+\cos
2\phi\big{)}|+|2\cos 2\phi\cos 2\theta|\big{\\}}.$ (28)

  2. (ii)

The quantum bounds are given by $\pm\eta_{\phi,\theta}^{\mathrm{Q}}$, where
$\eta_{\phi,\theta}^{\mathrm{Q}}=2\sin^{2}(\theta+\phi)\sin(\theta-\phi)$.

  3. (iii)

Up to local isometries, there exists a unique strategy that achieves $\langle
J_{\phi,\theta}^{(k,l)}\rangle=\eta_{\phi,\theta}^{\mathrm{Q}}$:

$\displaystyle\rho_{Q_{k}Q_{l}}$ $\displaystyle=|\psi\rangle\\!\langle\psi|,\
\mathrm{where}\
|\psi\rangle=\frac{1}{\sqrt{2}}\big{(}|00\rangle+i|11\rangle\big{)}$ (29)
$\displaystyle A_{0}^{(k)}$
$\displaystyle=A_{0}^{(l)}=\cos(\phi)\,\sigma_{X}-\sin(\phi)\,\sigma_{Y}$
$\displaystyle A_{1}^{(k)}$
$\displaystyle=A_{1}^{(l)}=\cos(\theta)\,\sigma_{X}+\sin(\theta)\,\sigma_{Y}.$

Note that when $\phi=0$ Lemma 7 reduces to Lemma 4. Moreover, this Bell
expression retains the same symmetry properties of the $I_{\theta}$ family,
namely that $\langle J_{\phi,\theta}\rangle=-\eta^{\mathrm{Q}}_{\phi,\theta}$
for the state $|\psi^{\prime}\rangle$ and the same measurements, and is hence
a self-test. We provide a full self-testing proof in Section B.6.

For future convenience, we define the set
$\mathcal{F}=\Big{[}(-\pi/4,\pi/4)\times\mathcal{G}\Big{]}\cup\Big{[}(-\pi/4,\pi/4)\setminus\\{0\\}\times\\{\pi/2,3\pi/2\\}\Big{]}\subset\mathbb{R}^{2}$.
One can verify that points $(\theta,\phi)\in\mathcal{F}$ satisfy
$\sin^{2}(\theta+\phi)\geq\cos^{2}(\theta-\phi)$, and
$\eta^{\mathrm{L}}_{\phi,\theta}<|\eta^{\mathrm{Q}}_{\phi,\theta}|$; i.e. they
define a valid self-test according to Lemma 7.

####  V.1.2 Target strategy

For the $N$-partite case, we will consider the following strategy:

$\begin{gathered}\rho_{\bm{Q}}=|\psi_{\mathrm{GHZ}}\rangle\\!\langle\psi_{\mathrm{GHZ}}|\\\
A_{0}^{(k)}=\cos\phi\,\sigma_{X}-\sin\phi\,\sigma_{Y},\\\
A_{1}^{(k)}=\cos\theta\,\sigma_{X}+\sin\theta\,\sigma_{Y},\
k\in\\{1,...,N\\}.\end{gathered}$ (30)

Using the fact that $\langle A_{\bm{x}}\rangle=\sin(n\theta-(N-n)\phi)$, where
$n=\sum_{k}x_{k}$, the MABK value, defined in Eq. 1, of the above strategy is
given by

$\langle
M_{N}(\phi,\theta)\rangle=2^{\frac{N-1}{2}}\Big{(}\cos^{N}\big{[}(\theta+\phi)/2+\pi/4\big{]}\\\
\cdot\sin\big{[}N(\theta-\phi)/2+\pi/4\big{]}\\\
+\cos^{N}\big{[}(\theta+\phi)/2-\pi/4\big{]}\sin\big{[}N(\theta-\phi)/2-\pi/4\big{]}\Big{)}.$
(31)

####  V.1.3 Constructing an $N$-partite Bell inequality

Using the previous two building blocks, we construct the following Bell
inequality using the $J_{\phi,\theta}$ expressions as the seed.

######  Lemma 8.

Let $\bm{\mu}$ be a tuple of $N-2$ measurement outcomes for all parties
excluding $k,l$, and $n_{\bm{\mu}}\in\\{0,1\\}$ be the parity of $\bm{\mu}$.
Let $(\phi^{\prime},\theta^{\prime})\in\mathcal{F}$ and
$\\{I_{\bm{\mu}}^{(k,l)}\\}_{\bm{\mu}}$ be a set of bipartite Bell expressions
between parties $k,l$, where

$I_{\bm{\mu}}^{(k,l)}=(-1)^{n_{\bm{\mu}}}J_{\theta^{\prime},\phi^{\prime}}^{(k,l)}.$
(32)

Then the expanded Bell expression given by

$I_{\theta^{\prime},\phi^{\prime}}=\sum_{k=1}^{N-1}\Bigg{(}\sum_{\bm{\mu}}\tilde{P}^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}I_{\bm{\mu}}^{(k,N)}\Bigg{)}$
(33)

has a quantum bound $\pm\eta_{N,\theta^{\prime},\phi^{\prime}}^{\mathrm{Q}}$
where
$\eta_{N,\theta^{\prime},\phi^{\prime}}^{\mathrm{Q}}=2(N-1)\sin^{2}(\theta^{\prime}+\phi^{\prime})\sin(\theta^{\prime}-\phi^{\prime})$,
achieved up to relabelings by the strategy in Eq. 30 by setting
$\phi=-2\phi^{\prime}/(N-2)$ and $\theta=\theta^{\prime}+\phi^{\prime}$, and
defines a nontrivial Bell inequality.

The proof is given in Section B.7. Note that the Bell expressions (33) are
written in terms of the shifted parameters $(\phi^{\prime},\theta^{\prime})$,
instead of the measurement angles $(\phi,\theta)$. This is because the $N-2$
parties performing the projection no longer use $\sigma_{X}$, but use
$\cos(\phi)\,\sigma_{X}-\sin(\phi)\,\sigma_{Y}$. This accumulates a phase
factor on the state of the remaining parties,
$(|00\rangle+i(-1)^{n_{\bm{\mu}}}\exp\\{i(N-2)\phi\\}|11\rangle)/\sqrt{2}$,
which is equivalent to the action of some local unitary $U$ on
$(|00\rangle+i(-1)^{n_{\bm{\mu}}}|11\rangle)/\sqrt{2}$. To correct for this,
we use the Bell expression
$U^{\dagger}J_{\phi,\theta}^{(k,l)}U=J_{\phi^{\prime},\theta^{\prime}}^{(k,l)}$
as the seed. See Section B.7 for the exact calculation.

###  V.2 Randomness versus MABK value

Using the previously derived Bell inequality, we consider the trade-off
between maximum device-independent randomness and MABK violation. Let us
define

$\theta(\phi)=\frac{N-1}{N+1}\phi+\theta^{*}_{N},$ (34)

where $\theta_{N}^{*}$ is defined in Eq. 24 and also

$\phi_{N}^{*}=\mathrm{sgn}[\sin(2\theta_{N}^{*})]\frac{\pi}{4N}.$ (35)

For the strategy in Eq. 30, direct calculation yields

$\langle M_{N}(\phi_{N}^{*},\theta(\phi_{N}^{*}))\rangle=2^{(N-1)/2},$ (36)

and $\langle M_{N}(0,\theta(0))\rangle=m_{N}^{*}$. Hence by varying
$\phi\in[0,\phi_{N}^{*}]$ and choosing $\theta=\theta(\phi)$ one can obtain
the desired range of MABK values $[m_{N}^{*},2^{(N-1)/2}]$, from the
conjectured maximum MABK value with maximum randomness to the maximum quantum
value. Choosing this parameterization, the raw randomness,
$H(\bm{R}|\bm{X}=\bm{x}^{*})=H(\\{p_{\phi}(\bm{a}|\bm{0})\\})$, of the
strategy in Eq. 30, as a function of $\phi$, is given by

$H(\\{p_{\phi}(\bm{a}|\bm{0})\\})\equiv
r(\phi)=N-1+H_{\mathrm{bin}}\Big{[}\frac{1-\sin N\phi}{2}\Big{]},$ (37)

where $H_{\mathrm{bin}}$ is the binary entropy function and $r(\phi)$ is a
smooth, monotonically decreasing function of $\phi$ in the range
$[0,\phi_{N}^{*}]$.

As shown in Section IV, when $\phi=0$ we can certify maximum DI randomness. It
also follows from the self-testing properties of the MABK family that when
$\phi=\phi^{*}_{N}$ we obtain $N-1+3/2-\log_{2}(1+\sqrt{2})/\sqrt{2}\approx
N-0.4$ bits of global DI randomness. What remains then, is to apply the new
Bell expression constructed in Lemma 8 to certify $r(\phi)$ bits of DI
randomness for $\phi\in(0,\phi^{*}_{N})$. To do so, the following proposition
shows that for every $\phi\in[0,\phi_{N}^{*}]$, there exists a valid Bell
expression given by Lemma 8.

######  Proposition 5.

Let $\phi\in[0,\phi_{N}^{*}]$, and define $\phi^{\prime}=-(N-2)\phi/2$,
$\theta^{\prime}=\theta(\phi)-\phi^{\prime}$. Then
$(\phi^{\prime},\theta^{\prime})\in\mathcal{F}$, where $\mathcal{F}$ is
defined in Lemma 7.

This is proven in Section B.8. Proposition 5 implies that, for every $\phi$ in
the range we are interested in, the bipartite expression
$(-1)^{n_{\bm{\mu}}}J_{\phi^{\prime},\theta^{\prime}}$ is a valid self-test of
the strategy

$\displaystyle\rho_{Q_{k}Q_{l}}$
$\displaystyle=|\Phi_{\bm{\mu}}\rangle\\!\langle\Phi_{\bm{\mu}}|,$ (38)
$\displaystyle A_{0}^{(k)}$
$\displaystyle=A_{0}^{(l)}=\cos\phi^{\prime}\,\sigma_{X}-\sin\phi^{\prime}\,\sigma_{Y}$
$\displaystyle A_{1}^{(k)}$
$\displaystyle=A_{1}^{(l)}=\cos\theta^{\prime}\,\sigma_{X}+\sin\theta\,\sigma_{Y}.$

After applying the local unitary $U_{\phi}\otimes U_{\phi}$, where
$U_{\phi}=|0\rangle\\!\langle 0|+e^{-i(N-2)\phi/2}|1\rangle\\!\langle 1|$,
this is equivalent to

$\displaystyle\rho_{Q_{k}Q_{l}}$
$\displaystyle=|\Phi_{\bm{\mu},\phi}\rangle\\!\langle\Phi_{\bm{\mu},\phi}|,$
(39) $\displaystyle A_{0}^{(k)}$
$\displaystyle=A_{0}^{(l)}=\cos\phi\,\sigma_{X}-\sin\phi\,\sigma_{Y}$
$\displaystyle A_{1}^{(k)}$
$\displaystyle=A_{1}^{(l)}=\cos\theta\,\sigma_{X}+\sin\theta\,\sigma_{Y},$

which is exactly the bipartite strategy we wanted to self-test, since it is
the one held by parties $k$ and $N$ after the projector
$\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}$ is applied to the global
state $|\psi_{\mathrm{GHZ}}\rangle$. As a result, the correlations generated
by the strategy in Eq. 30, by setting $\theta=\theta(\phi)$ and varying
$\phi\in[0,\phi_{N}^{*}]$, maximally violate the Bell inequality
$I_{\theta^{\prime},\phi^{\prime}}$ with $\phi^{\prime}=-(N-2)\phi/2$ and
$\theta^{\prime}=\theta(\phi)-\phi^{\prime}$. We can therefore employ the
decoupling lemma to make the rate unconditioned on Eve, $r(\phi)$, device-
independent.

######  Proposition 6.

Achieving the maximum quantum value of the Bell inequality in Lemma 8
certifies $r(\phi)$ bits of randomness, i.e.

$R_{I_{\theta^{\prime},\phi^{\prime}}}(\eta^{\mathrm{Q}}_{N,\theta^{\prime},\phi^{\prime}})=r(\phi).$
(40)

We have established, for every MABK value $s\in[m_{N}^{*},2^{(N-1)/2}]$, that
there exists a $\phi_{s}\in[0,\phi_{N}^{*}]$ which defines a quantum strategy
achieving $s$, for which its generated randomness $r(\phi_{s})$ is device-
independent. We have therefore related every MABK value with a DI rate. We
conjecture the curve $(s,r(\phi_{s}))$ is optimal in terms of raw randomness,
which can then be made device-independent following the above discussion — see
Lemma 9.

######  Conjecture 2.

For $N$ even, the maximum randomness unconditioned on Eve, $r$, that can be
generated by quantum strategies achieving an MABK value, $s$, is given by

$r(s)=\begin{cases}N,\ s\in(1,m_{N}^{*}],\\\ r(\phi_{s}),\
s\in(m_{N}^{*},2^{(N-1)/2}],\end{cases}$ (41)

where $r(\phi)$ is defined in Eq. 37, and

$\phi_{s}=\mathrm{arg\,min}\big{\\{}|\phi|\ :\ \phi\in[0,\phi_{N}^{*}],\langle
M_{N}(\phi,\theta(\phi))\rangle=s\big{\\}}.$ (42)

For the range $s\in(1,m_{N}^{*}]$, and $s\in(m_{N}^{*},2^{(N-1)/2}]$, the rate
$r(s)$ and MABK value $s$ is achieved by the family of quantum strategies in
Eq. 19 and Eq. 30, and certified by the Bell expressions in Lemma 5 and Lemma
8, respectively.

The minimization in the definition of $\phi_{s}$ is included since we have not
shown the set $\\{\ \phi\in[0,\phi_{N}^{*}]\ :\ \langle
M_{N}(\phi,\theta(\phi))\rangle=s\\}$ is unique. Intuitively, the closer
$\phi_{s}$ is to zero the closer we are to maximum randomness; hence we expect
$r(\phi)$ to be monotonically decreasing with $|\phi|$ for
$\phi\in[0,\phi_{N}^{*}]$, and minimisation guarantees the best rate at a
given $s$. For the examples we have computed, the minimization turns out to be
trivial, i.e. over a single point.

######  Lemma 9.

Suppose 1 and Eq. 42 hold. Then the maximum amount of device-independent
randomness that can be certified for the range of Mermin values
$(1,2^{(N-1)/2}]$ is given by Eq. 41.

The above lemma tells us that if the rate in Eq. 41 is optimal without
conditioning on Eve, it will also be optimal conditioned on Eve, i.e., the
rate can be made device-independent. This is because Eqs. 25 and 5 ensure
that, for every MABK value, the corresponding quantum strategy achieving it,
given in Eq. 19 or Eq. 30, can generate certifiable randomness using the
corresponding Bell expression $I_{\theta}$ or
$I_{\theta^{\prime},\phi^{\prime}}$. A rewriting of Lemma 9 without
Conjectures 1 and 42, would say that (41) corresponds to a guaranteed lower
bound on the maximum DI randomness as a function of MABK value. Our results
are summarized in Fig. 4.

Figure 4: The conjectured curves of maximum device-independent randomness
versus MABK value, where the MABK value is normalized by its maximum quantum
value $2^{(N-1)/2}$. When $N$ is odd, maximum global randomness can be
achieved for any MABK value between the local and quantum bound, indicated by
solid lines. The blue crosses indicate the conjectured maximum MABK value for
which maximum randomness can be achieved when $N$ is even, $m_{N}^{*}$, which
tends towards the maximum quantum value as $N\rightarrow\infty$. To the left
of the blue crosses, $N$ bits of randomness can be achieved for MABK values
between the local bound (not shown on this axis) and $m_{N}^{*}$; since this
is the global maximum, it is optimal, indicated by solid lines. To the right
of the blue crosses, dashed lines indicate lower bounds on the trade-off
between maximum randomness and MABK value from $m_{N}^{*}$ to the maximum
quantum value, which are conjectured to be tight. The case of $N=2$ was proven
in Ref Wooltorton  _et al._ (2022), which we reproduce with our results.

We provide evidence for Conjectures 1 and 42 in Section B.9, where we derive a
numerical technique for upper bounding the maximum randomness that can be
generated by quantum strategies achieving a given MABK value $s$. By studying
the numerical results, we find our analytical lower bound closely agrees with
the numerical upper bound.

###  V.3 Other extremal Bell inequalities

In the $N$-partite 2-input 2-output scenario, the MABK family is just one
class of extremal Bell inequalities, and the techniques developed in this
section can be readily applied to others. For example, when $N=3$, there are a
total of 3 non-trivial, new classes, one being the MABK inequality $M_{3}$,
and two being of the form Werner and Wolf (2001)

$\displaystyle S_{1}$
$\displaystyle=\frac{1}{4}\sum_{x,y,z}A_{x}B_{y}C_{z}-A_{1}B_{1}C_{1},$ (43)
$\displaystyle S_{2}$
$\displaystyle=A_{0}B_{0}(C_{0}+C_{1})-A_{1}B_{1}(C_{0}-C_{1}),$ (44)

where we have swapped $A_{x_{1}}^{(1)}$ with $A_{x}$ etc. for legibility.
$S_{1}$ and $S_{2}$ have local bounds of $1$ and $2$, and maximum quantum
values $5/3$ and $2\sqrt{2}$, respectively. We applied our numerical technique
(see Section B.9) to find upper bounds on the maximum amount of randomness
certifiable whilst achieving a given violation of $S_{1}$ and $S_{2}$. A
comparison can be found in Fig. 5, and we provide additional figures and
details in Section B.10.

Figure 5: Upper bounds on the trade-off between asymptotic global DI
randomness and violation of non-trivial extremal Bell inequalities, for the
tripartite scenario with two binary measurements per party. The violation has
been normalized by the maximum quantum value. $S_{1}$ and $S_{2}$ are given by
Eq. 43 and Eq. 44 respectively, and $M_{3}$ is the MABK expression. Note the
above graph does not necessarily imply a weaker trade-off for $S_{1}$, since
the local bounds differ for all expressions once normalized by the maximum
quantum value.

We find both $S_{1}$ and $S_{2}$ exhibit a trade-off for violations close to
the quantum maximum. Due to its structure, $S_{2}$ exhibits identical trade-
off characteristics to the CHSH inequality found in Wooltorton  _et al._
(2022), with the maximum CHSH value achievable with maximum randomness being
numerically close to $3\sqrt{3}/2$. On the other hand, we find more randomness
can be generated from maximum violation of $S_{2}$, which is still strictly
less than the maximum certified by MABK. Exact values are given in Section
B.10.

##  VI Discussion

In this work, we studied how MABK violation constrains the generation of
global DI randomness for an arbitrary number of parties. Whilst there is no
trade-off in the odd case, we conjectured the precise trade-off for the even
case. This conjecture is supported by an analytical lower bound and a
numerical upper bound that agree up to several decimal places and have been
checked for up to $N=12$. We additionally showed that, in the asymptotic
limit, this trade-off vanishes. Our first technical contribution was the
advancement of a recent tool, originally introduced to witness genuinely
multipartite nonlocality, to randomness certification. Our second was the
introduction of a new, versatile family of bipartite Bell expressions which
generalizes some that were previously known.

More precisely, we discussed that odd MABK expressions contain half the full
party correlators; considering input combinations not included in the Bell
expression, we find some of these can be uniform. For even $N$, all
correlators are included and must be non-zero to ascertain maximum violation,
resulting in a trade-off. The number of correlators is $2^{N}$, whereas the
quantum bound is $2^{(N-1)/2}$. Maximum violation is achieved when the product
of all correlators and their MABK coefficients have the same value, which in
this case will be $2^{-(N+1)/2}$. Hence we find the penalty for fixing one
correlator to zero (which is necessary for maximum randomness) diminishes as
$N$ grows, and vanishes in the asymptotic limit.

We also quantified the nonlocality of our constructions for low values of $N$,
calculated via a linear program. Interestingly we found our correlations are
always separated from the local boundary. It would be interesting to find
correlations that lie asymptotically close to the local boundary whilst still
certifying maximum randomness, as was found in the $N=2$ case Acín  _et al._
(2012); Wooltorton  _et al._ (2022). This could entail symmetry breaking
between the second measurements of each party, and the versatility of the
techniques presented here can be easily applied. Moreover, one could hope to
go further and bound the trade-off between randomness and nonlocality in this
setting; however, the challenge becomes finding a suitable measure of
nonlocality that is efficient to work with.

We hope that the results found here will inform future experiments in DIRE;
initial works have already made progress in this direction Seguinard  _et al._
(2023). In such experiments, one should consider the optimal protocol for
DIRE. In this work, we have proposed protocols that rely on spot-checking
Miller and Shi (2014, 2017); Bhavsar  _et al._ (2021), where randomness is
generated by a single input combination. An alternative approach has been
explored in reference Bhavsar  _et al._ (2021), where it was found that
generating randomness from all inputs and averaging the result boosts the rate
when the CHSH inequality is used. For the noiseless scenario, spot-checking
will always be optimal when a specific input combination leads to maximum
randomness, as is the case in this work; having one maximally random setting
necessarily implies that at least one other setting combination will not be
maximally random for the correlations to be nonlocal, hence averaging will
only decrease the overall rate. The noisy case remains an open question
however, and the trade-off between using spot-checking and weighted averaging
for our constructions deserves future investigation, with the aim of further
improving practical rates.

Another interesting direction for future research is to connect expanded Bell
inequalities to multipartite self-testing. Our decoupling result allows the
structure of the post-measurement state to be certified following the maximum
violation of an expanded Bell expression; the open question we pose is if an
expanded Bell inequality can constitute a full self-test, opening up a new
range of useful applications beyond randomness certification. Intuitively, if
each pair of parties can self-test all of their measurements along with a
projected state, one might hope to use the marginal information to make a
statement about the global state. Such a strategy has already been adopted for
self-testing multipartite correlations Šupić  _et al._ (2018). However, there
are subtleties. For example, for three parties with observables
$A_{x},B_{y},C_{z}$, our first Bell expression in Eq. 21 when $\theta=\pi/2$,
reads

$A_{0}\big{(}B_{0}C_{1}+B_{1}C_{0}\big{)}+B_{0}\big{(}A_{0}C_{1}+A_{1}C_{0}\big{)}\leq_{\mathcal{Q}}4\mathbb{I},$
(45)

which is achievable classically. This originates from the classical
achievability of the seed
$I_{\theta=\pi/2}^{(k,l)}=A_{0}^{(k)}A_{1}^{(l)}+A_{1}^{(k)}A_{0}^{(l)}$ in
Eq. 16. Yet, the Bell expression was designed for the strategy

$\begin{gathered}\rho_{Q_{A}Q_{B}Q_{C}}=|\psi_{\mathrm{GHZ}}\rangle\\!\langle\psi_{\mathrm{GHZ}}|,\\\
A_{0/1}=B_{0/1}=C_{0/1}=\sigma_{X/Y},\end{gathered}$ (46)

which maximally violates the $N=3$ MABK inequality, and is known to be self-
testing. In other words, when any party measures $\sigma_{X}$ or $\sigma_{Y}$
on $|\psi_{\mathrm{GHZ}}\rangle$, the resulting bipartite correlations are
classical, even though the global strategy is nonlocal. It is then necessary
to add extra measurements to enable bipartite self-testing. On the other hand,
the $N=3$ MABK expression reads

$A_{0}\big{(}B_{0}C_{1}+B_{1}C_{0}\big{)}+A_{1}\big{(}B_{0}C_{0}-B_{1}C_{1}\big{)}\leq_{\mathcal{Q}}4\mathbb{I},$
(47)

which holds similarities to Eq. 45. Both terms in the sum are achievable
classically, given by a relabeling of the seed $I_{\theta=\pi/2}^{(k,l)}$; the
key difference is the lack of simultaneous classical achievability in Eq. 47.
Clearly this property is sufficient. It would be interesting to understand if
the $N=3$ MABK expression can still be viewed as an expansion of the seed
$I_{\theta=\pi/2}^{(k,l)}$ following an appropriate relabelling, using only
the strategy in Eq. 46 as the starting point. Note however, for $N>3$, we can
use the $N=3$ MABK expression as the self-testing seed, and we do not run into
this situation. Thus, correlations that do not exhibit post-measurement
nonlocality, yet are still nonlocal, could be viewed as a resource to
construct richer correlations.

Finally, whilst we studied the MABK family of inequalities, one could consider
a similar analysis for other families of extremal multipartite Bell
expressions Werner and Wolf (2001). For example, we explored upper bounds on
the trade-offs for all extremal inequalities when $N=3$, and found the MABK
inequality to be optimal for global randomness; it would be interesting to
find out if the upper bounds presented for the other inequalities are
achievable. One might try to find explicit constructions that match these
bounds, and use our techniques to make them device-independent. Analysing
other extremal inequalities will build a more complete picture of how DI
randomness can be generated in the multipartite scenario, better informing the
way forward for future multipartite experiments.

###### Acknowledgements.

This work was supported by the UK’s Engineering and Physical Sciences Research
Council (EPSRC) via the Quantum Communications Hub (Grant No. EP/T001011/1)
and Grant No. EP/SO23607/1.

## References

  * Bell (1987) J. S. Bell,  _Speakable and unspeakable in quantum mechanics_ (Cambridge University Press, 1987).
  * Brunner  _et al._ (2014) N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, “Bell nonlocality,” Reviews of Modern Physics 86, 419–478 (2014).
  * Barrett  _et al._ (2005a) J. Barrett, N. Linden, S. Massar, S. Pironio, S. Popescu, and D. Roberts, “Nonlocal correlations as an information-theoretic resource,” Physical Review A 71, 022101 (2005a).
  * 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. Acin, 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–1024 (2010).
  * Colbeck and Kent (2011) R. Colbeck and A. Kent, “Private randomness expansion with untrusted devices,” Journal of Physics A 44, 095305 (2011).
  * Miller and Shi (2014) C. A. Miller and Y. Shi, “Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices,” in  _Proceedings of the 46th Annual ACM Symposium on Theory of Computing_, STOC ’14 (ACM, New York, NY, USA, 2014) pp. 417–426.
  * Miller and Shi (2017) C. A. Miller and Y. Shi, “Universal security for randomness expansion from the spot-checking protocol,” Siam Journal of Computing 46, 1304–1335 (2017).
  * Colbeck and Renner (2012) R. Colbeck and R. Renner, “Free randomness can be amplified,” Nature Physics 8, 450–454 (2012).
  * Ekert (1991) A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Physical Review Letters 67, 661–663 (1991).
  * Barrett  _et al._ (2005b) J. Barrett, L. Hardy, and A. Kent, “No signalling and quantum key distribution,” Physical Review Letters 95, 010503 (2005b).
  * Acin  _et al._ (2007) A. Acin, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, “Device-independent security of quantum cryptography against collective attacks,” Physical Review Letters 98, 230501 (2007).
  * 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).
  * Vazirani and Vidick (2014) U. Vazirani and T. Vidick, “Fully device-independent quantum key distribution,” Physical Review Letters 113, 140501 (2014).
  * Arnon-Friedman  _et al._ (2018) R. Arnon-Friedman, F. Dupuis, O. Fawzi, R. Renner, and T. Vidick, “Practical device-independent quantum cryptography via entropy accumulation,” Nature communications 9, 459 (2018).
  * Mayers and Yao (2004) D. Mayers and A. Yao, “Self testing quantum apparatus,” (2004), arXiv:quant-ph/0307205 [quant-ph] .
  * McKague  _et al._ (2012) M. McKague, T. H. Yang, and V. Scarani, “Robust self-testing of the singlet,” Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).
  * Yang and Navascués (2013) T. H. Yang and M. Navascués, “Robust self-testing of unknown quantum systems into any entangled two-qubit states,” Physical Review A 87, 050102 (2013).
  * Coladangelo  _et al._ (2017) A. Coladangelo, K. T. Goh, and V. Scarani, “All pure bipartite entangled states can be self-tested,” Nature Communications 8, 15485 (2017).
  * Šupić  _et al._ (2022) I. Šupić, J. Bowles, M.-O. Renou, A. Acín, and M. J. Hoban, “Quantum networks self-test all entangled states,”  (2022).
  * Šupić and Bowles (2020) I. Šupić and J. Bowles, “Self-testing of quantum systems: a review,” Quantum 4, 337 (2020).
  * Acín  _et al._ (2012) A. Acín, S. Massar, and S. Pironio, “Randomness versus nonlocality and entanglement,” Physical Review Letters 108, 100402 (2012).
  * Wooltorton  _et al._ (2022) L. Wooltorton, P. Brown, and R. Colbeck, “Tight analytic bound on the trade-off between device-independent randomness and nonlocality,” Physical Review Letters 129, 150403 (2022).
  * Mermin (1990) N. D. Mermin, “Extreme quantum entanglement in a superposition of macroscopically distinct states,” Physical Review Letters 65, 1838–1840 (1990).
  * Ardehali (1992) M. Ardehali, “Bell inequalities with a magnitude of violation that grows exponentially with the number of particles,” Physical Review A 46, 5375–5378 (1992).
  * Belinskiĭ and Klyshko (1993) A. V. Belinskiĭ and D. N. Klyshko, “Interference of light and bell’s theorem,” Physics-Uspekhi 36, 653 (1993).
  * Woodhead  _et al._ (2018) E. Woodhead, B. Bourdoncle, and A. Acín, “Randomness versus nonlocality in the Mermin-Bell experiment with three parties,” Quantum 2, 82 (2018).
  * Grasselli  _et al._ (2021) F. Grasselli, G. Murta, H. Kampermann, and D. Bruß, “Entropy bounds for multiparty device-independent cryptography,” PRX Quantum 2, 010308 (2021).
  * Grasselli  _et al._ (2022) F. Grasselli, G. Murta, H. Kampermann, and D. Bruß, “Boosting device-independent cryptography with tripartite nonlocality,” e-print arXiv:2209.12828 (2022).
  * Bamps  _et al._ (2018) C. Bamps, S. Massar, and S. Pironio, “Device-independent randomness generation with sublinear shared quantum resources,” Quantum 2, 86 (2018).
  * Dhara  _et al._ (2013) C. Dhara, G. Prettico, and A. Acín, “Maximal quantum randomness in Bell tests,” Physical Review A 88, 052116 (2013).
  * de la Torre  _et al._ (2015) G. de la Torre, M. J. Hoban, C. Dhara, G. Prettico, and A. Acín, “Maximally nonlocal theories cannot be maximally random,” Physical Review Letters 114, 160502 (2015).
  * Braunstein and Caves (1990) S. L. Braunstein and C. M. Caves, “Wringing out better bell inequalities,” Annals of Physics 202, 22–56 (1990).
  * Š upić  _et al._ (2016) I. Š upić, R. Augusiak, A. Salavrakos, and A. Acín, “Self-testing protocols based on the chained Bell inequalities,” New Journal of Physics 18, 035013 (2016).
  * Curchod  _et al._ (2019) F. J. Curchod, M. L. Almeida, and A. Acín, “A versatile construction of Bell inequalities for the multipartite scenario,” New Journal of Physics 21, 023016 (2019).
  * Šupić  _et al._ (2018) I. Šupić, A. Coladangelo, R. Augusiak, and A. Acín, “Self-testing multipartite entangled states through projections onto two systems,” New Journal of Physics 20, 083041 (2018).
  * Zwerger  _et al._ (2019) M. Zwerger, W. Dür, J.-D. Bancal, and P. Sekatski, “Device-independent detection of genuine multipartite entanglement for all pure states,” Physical Review Letters 122, 060502 (2019).
  * Li  _et al._ (2018) X. Li, Y. Cai, Y. Han, Q. Wen, and V. Scarani, “Self-testing using only marginal information,” Physical Review A 98, 052331 (2018).
  * Franz  _et al._ (2011) T. Franz, F. Furrer, and R. F. Werner, “Extremal quantum correlations and cryptographic security,” Physical Review Letters 106, 250502 (2011).
  * Paulsen (2003) V. Paulsen,  _Completely Bounded Maps and Operator Algebras_, Cambridge Studies in Advanced Mathematics (Cambridge University Press, 2003).
  * Werner and Wolf (2001) R. F. Werner and M. M. Wolf, “All-multipartite Bell-correlation inequalities for two dichotomic observables per site,” Physical Review A 64, 032112 (2001).
  * Kaniewski (2016) J. Kaniewski, “Analytic and nearly optimal self-testing bounds for the Clauser-Horne-Shimony-Holt and Mermin inequalities,” Physical Review Letters 117, 070402 (2016).
  * Kaniewski (2017) J. Kaniewski, “Self-testing of binary observables based on commutation,” Physical Review A 95, 062323 (2017).
  * Bhavsar  _et al._ (2021) R. Bhavsar, S. Ragy, and R. Colbeck, “Improved device-independent randomness expansion rates using two sided randomness,” e-print arXiv:2103.07504 (2021).
  * Dupuis  _et al._ (2016) F. Dupuis, O. Fawzi, and R. Renner, “Entropy accumulation,” e-print arXiv:1607.01796 (2016).
  * Dupuis and Fawzi (2019) F. Dupuis and O. Fawzi, “Entropy accumulation with improved second-order term,” IEEE Transactions on Information Theory 65, 7596–7612 (2019).
  * Metger  _et al._ (2022) T. Metger, O. Fawzi, D. Sutter, and R. Renner, “Generalised entropy accumulation,” e-print arXiv:2203.04989 (2022).
  * Seguinard  _et al._ (2023) A. J.-M. Seguinard, A. Piveteau, P. Mironowicz, and M. Bourennane, “Experimental certification of more than one bit of quantum randomness in the two inputs and two outputs scenario,” e-print arXiv:2303.07460 (2023).
  * Jordan (1875) C. Jordan, “Essai sur la géométrie à n dimensions,” Bulletin de la S. M. F. 3, 103–174 (1875).
  * Bamps and Pironio (2015) C. Bamps and S. Pironio, “Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing,” Physical Review A 91, 052111 (2015).
  * Brown  _et al._ (2021) P. Brown, H. Fawzi, and O. Fawzi, “Computing conditional entropies for quantum correlations,” Nature Communications 12, 575 (2021).

##  Appendix A Proofs for expanded Bell expressions

###  A.1 Proof of Lemma 1

Lemma 1. Let $I$ be an expanded Bell expression according to Footnote 1. The
maximum quantum value of $\langle I\rangle$ is upper bounded by
$\eta^{\mathrm{Q}}_{N}:=\sum_{k,l}c_{k,l}\eta^{\mathrm{Q}}$.

###### Proof.

To prove the above, we show that the operator expression
$\bar{I}=\eta^{\mathrm{Q}}_{N}\mathbb{I}-I$ is non-negative. Since each
bipartite expression satisfies $\langle
I_{\bm{\mu}}^{(k,l)}\rangle\leq\eta^{\mathrm{Q}}$ for all $\bm{\mu},k,l$, we
have positive expressions

$\bar{I}_{\bm{\mu}}^{(k,l)}=\eta^{\mathrm{Q}}\mathbb{I}-I_{\bm{\mu}}^{(k,l)}\succeq
0,\ \forall\bm{\mu},k,l.$ (48)

We then have

$\displaystyle\bar{I}_{k,l}$
$\displaystyle=\eta^{\mathrm{Q}}\mathbb{I}-\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}I^{(k,l)}_{\bm{\mu}}$
$\displaystyle=\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}\Big{(}\eta^{\mathrm{Q}}\mathbb{I}-I_{\bm{\mu}}^{(k,l)}\Big{)}$
$\displaystyle=\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}\bar{I}_{\bm{\mu}}^{(k,l)}\succeq
0.$ (49)

Finally it follows from the above that $\bar{I}\succeq 0$, which proves the
upper bound on the maximum quantum value. We can also upper bound the maximum
local value by
$\sum_{k<l}c_{k,l}\eta^{\mathrm{L}}<\sum_{k<l}c_{k,l}\eta^{\mathrm{Q}}=\eta_{N}^{\mathrm{Q}}$
since $\eta^{\mathrm{L}}<\eta^{\mathrm{Q}}$. ∎

###  A.2 Uniqueness of binary distributions with fixed marginals

Before proving Eq. 12, we establish the following fact about classical
distributions of bit strings when their conditional distributions are fixed.
We will later use this result to justify that the distribution used for
randomness achieving the quantum bound of an expanded Bell inequality is
unique when the seed is a self-test.

######  Lemma 10.

Let $\bm{A}=A_{1}...A_{N}$, $N\geq 3$, be a random $N$ bit string which takes
values $\bm{a}\in\\{0,1\\}^{N}$ according to the distribution
$p_{\bm{A}}(\bm{a})$. Let $\bm{B}_{\bar{k}}$ be an $N-2$ bit partition of the
string $\bm{A}$, excluding bits $N$ and $k\in\\{1,...,N-1\\}$, taking values
$\bm{b}_{\bar{k}}\in\\{0,1\\}^{N-2}$. Then the distribution
$p_{\bm{A}}(\bm{a})$ is entirely determined by the set of conditional
distributions
$\\{p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}a_{N}|\bm{b}_{\bar{k}})\\}_{k\in\\{1,...,N-1\\}}$,
provided $p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}a_{N}|\bm{b}_{\bar{k}})>0$ for
all $k,a_{k},a_{N},\bm{b}_{\bar{k}}$.

###### Proof.

Proof can be established using a recursive argument to solve for a set of
marginal terms $p_{\bm{B}_{\bar{l}}}(\bm{b}_{\bar{l}})$, for a fixed
$l\in\\{1,...,N-1\\}$, from which the full distribution can be recovered. Let
us choose another partition $k\in\\{1,...,N-1\\}$ with $k\neq l$. Then we have

$\displaystyle p_{\bm{A}}(\bm{a})$
$\displaystyle=p_{\bm{B}_{\bar{k}}}(\bm{b}_{\bar{k}})p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}a_{N}|\bm{b}_{\bar{k}})$
(50)
$\displaystyle=p_{\bm{B}_{\bar{l}}}(\bm{b}_{\bar{l}})p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|\bm{b}_{\bar{l}}).$

By choosing different values of $a_{k}$, this implies the two sets of
equations

$\displaystyle p_{\bm{B}_{\bar{k}}}(\bm{b}_{\bar{k}})$ $\displaystyle
p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}=0,a_{N}|\bm{b}_{\bar{k}})$ (51)
$\displaystyle=p_{\bm{B}_{\bar{l}}}(a_{k}=0,\bm{b}_{\bar{kl}})p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|a_{k}=0,\bm{b}_{\bar{kl}}),$
$\displaystyle p_{\bm{B}_{\bar{k}}}(\bm{b}_{\bar{k}})$ $\displaystyle
p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}=1,a_{N}|\bm{b}_{\bar{k}})$
$\displaystyle=p_{\bm{B}_{\bar{l}}}(a_{k}=1,\bm{b}_{\bar{kl}})p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|a_{k}=1,\bm{b}_{\bar{kl}}).$

Since $p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}a_{N}|\bm{b}_{\bar{k}})\neq 0$, we
can rearrange both for $p_{\bm{B}_{\bar{k}}}$ and equate:

$\frac{p_{\bm{B}_{\bar{l}}}(a_{k}=0,\bm{b}_{\bar{kl}})p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|a_{k}=0,\bm{b}_{\bar{kl}})}{p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}=0,a_{N}|\bm{b}_{\bar{k}})}\\\
=\frac{p_{\bm{B}_{\bar{l}}}(a_{k}=1,\bm{b}_{\bar{kl}})p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|a_{k}=1,\bm{b}_{\bar{kl}})}{p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}=1,a_{N}|\bm{b}_{\bar{k}})},$
(52)

where we have explicitly written in the $a_{k}$ variable, and $\bar{kl}$
denotes a tuple excluding parties $k$ and $l$. The above equation tells us,
for every choice of $\bm{b}_{\bar{kl}}\in\\{0,1\\}^{N-3}$, the unknowns
$p_{\bm{B}_{\bar{l}}}(a_{k}=0,\bm{b}_{\bar{kl}})$ and
$p_{\bm{B}_{\bar{l}}}(a_{k}=1,\bm{b}_{\bar{kl}})$ are linearly dependent.
Hence we consider the $2^{N-3}$ unknowns
$p_{\bm{B}_{\bar{l}}}(a_{k}=0,\bm{b}_{\bar{kl}})$, since the $a_{k}=1$ terms
can be computed via this linear dependence.

Consider choosing $k^{\prime}\in\\{1,...,N-1\\}\setminus\\{k,l\\}$. We can
find a new set of equations by repeating the above process with $k^{\prime}$
instead of $k$, to find:

$\displaystyle\frac{p_{\bm{B}_{\bar{l}}}(a_{k}=0,a_{k^{\prime}}=0,\bm{b}_{\overline{kk^{\prime}l}})}{p_{A_{k^{\prime}}A_{N}|\bm{B}_{\bar{k^{\prime}}}}(a_{k^{\prime}}=0,a_{N}|a_{k}=0,\bm{b}_{\overline{kk^{\prime}}})}$
(53) $\displaystyle\hskip 22.76228pt\cdot
p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|a_{k}=0,a_{k^{\prime}}=0,\bm{b}_{\overline{kk^{\prime}l}})$
$\displaystyle=\frac{p_{\bm{B}_{\bar{l}}}(a_{k}=0,a_{k^{\prime}}=1,\bm{b}_{\overline{kk^{\prime}l}})}{p_{A_{k^{\prime}}A_{N}|\bm{B}_{\bar{k^{\prime}}}}(a_{k^{\prime}}=1,a_{N}|a_{k}=0,\bm{b}_{\overline{kk^{\prime}}})}$
$\displaystyle\hskip 22.76228pt\cdot
p_{A_{l}A_{N}|\bm{B}_{\bar{l}}}(a_{l}a_{N}|a_{k}=0,a_{k^{\prime}}=1,\bm{b}_{\overline{kk^{\prime}l}}),$

where we have only included the $a_{k}=0$ case, and written
$\overline{kk^{\prime}l}$ to denote a tuple excluding parties
$k,k^{\prime},l$. Notice we have now identified linear dependence between
$p_{\bm{B}_{\bar{l}}}(a_{k}=0,a_{k^{\prime}}=0,\bm{b}_{\overline{kk^{\prime}l}})$
and
$p_{\bm{B}_{\bar{l}}}(a_{k}=0,a_{k^{\prime}}=1,\bm{b}_{\overline{kk^{\prime}l}})$.
None of these equations contain a marginal with $a_{k}=1$, so they relate
pairs of unknowns distinctly to the parings from the previous equations, and
are hence linearly independent. As before, we can proceed with the $2^{N-4}$
unknowns
$p_{\bm{B}_{\bar{l}}}(a_{k}=0,a_{k^{\prime}}=0,\bm{b}_{\overline{kk^{\prime}l}})$
and recover the others by linear dependence.

We can apply the above procedure iteratively a total of $N-2$ times (for every
$k\in\\{1,...,N-1\\}\setminus\\{l\\}$), halving the number of unknowns on
every iteration by establishing linear dependence. Starting with $2^{N-2}$
marginals $p_{\bm{B}_{\bar{l}}}(\bm{b}_{\overline{l}})$, this leaves us with 1
unknown, which can be solved via normalization, completing the proof. ∎

Now we can present a corollary which will be needed for the proof of Eq. 12,
showing the conditional distribution used for randomness, $p(\bm{a}|\bm{0})$,
achieving the quantum bound of an expanded Bell expression is unique.

######  Corollary 1.

Let $I$ be an expanded Bell inequality according to Footnote 1 with
$c_{k,N}=1$ if $k<N$ and zero otherwise, and $\eta_{N}^{\mathrm{Q}}$ defined
in Lemma 1. Let $I$ be constructed using a seed with the self-testing
properties described in Eq. 12, and $p(\bm{a}|\bm{x})$ denote a quantum
behaviour that achieves $\langle I\rangle=\eta^{\mathrm{Q}}_{N}$. Then
provided $p(a_{k}a_{N}|\bm{b}_{\bar{k}},\bm{x}=\bm{0})>0$ for all
$k,a_{k},a_{N},\bm{b}_{\bar{k}}$, the conditional the distribution
$p(\bm{a}|\bm{0})$ is unique.

###### Proof.

If the quantum value $\langle I\rangle=\eta_{N}^{\mathrm{Q}}$ is achieved, we
must have

$\displaystyle\sum_{k=1}^{N-1}\big{\langle}\eta^{\mathrm{Q}}\mathbb{I}-\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}I_{\bm{\mu}}^{(k,N)}\big{\rangle}=0,$
(54)

which implies
$\big{\langle}\eta^{\mathrm{Q}}\mathbb{I}-\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}I_{\bm{\mu}}^{(k,N)}\big{\rangle}=0$
from Eq. 49. Next we apply Hölder’s inequality:

$\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}I_{\bm{\mu}}^{(k,N)}\rangle\\\
\leq\|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\rho_{\bm{Q}E}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\|_{1}\|I_{\bm{\mu}}^{(k,N)}\|_{\infty}=\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\rangle\eta^{\mathrm{Q}},$
(55)

where $\rho_{\bm{Q}E}=|\Psi\rangle\\!\langle\Psi|$, $|\Psi\rangle$ is the
quantum state that realizes the correlations and identities on $E$ are
implicit. Since

$\sum_{\bm{\mu}}\Big{(}\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\rangle\eta^{\mathrm{Q}}-\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}I_{\bm{\mu}}^{(k,N)}\rangle\Big{)}=0$
(56)

we conclude
$\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}I_{\bm{\mu}}^{(k,N)}\rangle=\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\rangle\eta^{\mathrm{Q}}$.
Now we can write

$\langle\Psi^{\prime}|I_{\bm{\mu}}^{(k,N)}|\Psi^{\prime}\rangle=\eta_{Q},$
(57)

where we define the normalized state
$|\Psi^{\prime}\rangle=\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle/\sqrt{\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\rangle}$.
The self-testing properties of $I_{\bm{\mu}}^{(k,N)}$ (see definition in Eq.
12) then determine the unique correlations
$\langle\Psi^{\prime}|\tilde{P}_{a_{k}|0}^{(k)}\tilde{P}_{a_{N}|0}^{(N)}|\Psi^{\prime}\rangle=p^{k,N}_{\bm{\mu}}(a_{k}a_{N}|xy)$.
Using the definition of $|\Psi^{\prime}\rangle$, we find

$\big{\langle}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\tilde{P}_{a_{k}|0}^{(k)}\tilde{P}_{a_{N}|0}^{(N)}\big{\rangle}=\langle\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\rangle
p^{k,N}_{\bm{\mu}}(a_{k}a_{N}|00).$ (58)

We can now directly apply Corollary 1. Explicitly we have
$p_{\bm{A}}(\bm{a})=\big{\langle}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\tilde{P}_{a_{k}|0}^{(k)}\tilde{P}_{a_{N}|0}^{(N)}\big{\rangle}$,
and the $N-1$ fixed conditional distributions
$p_{A_{k}A_{N}|\bm{B}_{\bar{k}}}(a_{k}a_{l}|\bm{b}_{\bar{k}})=p(a_{k}a_{N}|\bm{b}_{\bar{k}},\bm{x}=\bm{0})=p^{k,N}_{\bm{\mu}}(a_{k}a_{N}|00)$,
where we have identified $\bm{\mu}=\bm{b}_{\bar{k}}$.

∎

###  A.3 Proof of Eq. 12

We can now proceed to prove Eq. 12 in the main text, which is restated below:

Lemma 2. Let $I$ be an expanded $N$-party Bell expression defined in Footnote
1 with binary inputs and outputs, and $c_{k,N}=1$ if $k<N$ and zero otherwise.
Suppose for every $I_{\bm{\mu}}^{(k,N)}$, there exists an SOS decomposition
which self-tests the same pure bipartite entangled state $|\Phi\rangle$
between parties $k,N$, along with some ideal measurements
$P^{(k)}_{a_{k}|x_{k}},P^{(N)}_{a_{N}|x_{N}}$, according to Eq. 2, which
satisfy $\langle\Phi|P^{(k)}_{a_{k}|0}\otimes P^{(N)}_{a_{N}|0}|\Phi\rangle>0$
for all $a_{k},a_{N}$. Then for any strategy
$|\Psi\rangle_{\tilde{\bm{Q}}E},\big{\\{}\\{\tilde{P}_{a_{k}|x_{k}}^{(k)}\\}_{x_{k}}\big{\\}}_{k}$
that achieves $\langle I\rangle=\eta^{\mathrm{Q}}_{N}$, the post-measurement
state $\rho_{\bm{R}E}$, for measurement settings $\bm{x}=\bm{0}$, admits the
tensor product decomposition,

$\rho_{\bm{R}E|\bm{0}}=\rho_{\bm{R}|\bm{0}}\otimes\rho_{E}.$ (59)

###### Proof.

We will break this proof up into four steps. First, we will provide an SOS
decomposition for the Bell operator $\bar{I}$, and derive the algebraic
constraints satisfied by any state and measurements that achieves its maximum
value. These turn out to be those implied by the bipartite bell expressions
that build up $I$. Next, we will employ Jordan’s lemma, reducing the problem
to qubits, and show how these constraints self-test the bipartite states.
Finally we write down the global post-measurement state, and show how these
self-tests imply a tensor product with $E$.

####  A.3.1 SOS decomposition

We begin by introducing SOS decompositions for the bipartite Bell operators,

$\bar{I}_{\bm{\mu}}^{(k,N)}=\sum_{i}M_{\bm{\mu},i}^{(k,N)\dagger}M_{\bm{\mu},i}^{(k,N)},$
(60)

where $M_{\bm{\mu},i}^{(k,N)}$ is a polynomial of the operators
$A_{x_{k}}^{(k)}$, $A_{x_{N}}^{(N)}$. We now use this to build an SOS
decomposition for $\bar{I}$,

$\displaystyle\bar{I}$ $\displaystyle=\sum_{k=1}^{N-1}\bar{I}_{k,l}$
$\displaystyle=\sum_{k=1}^{N-1}\sum_{\bm{\mu}}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\bar{I}_{\bm{\mu}}^{(k,N)}$
$\displaystyle=\sum_{k=1}^{N-1}\sum_{\bm{\mu}}\sum_{i}\Big{(}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}M_{\bm{\mu},i}^{(k,N)}\Big{)}^{\dagger}\Big{(}\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}M_{\bm{\mu},i}^{(k,N)}\Big{)}.$
(61)

Now, for some physical state $|\Psi\rangle$ and observables, observation of
the maximum quantum value, $\langle\bar{I}\rangle=0$, immediately implies the
algebraic constraints

$\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}M_{\bm{\mu},i}^{(k,N)}|\Psi\rangle=0,\
\forall k\in\\{1,...,N-1\\},\bm{\mu},i.$ (62)

Since $\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}$ and
$M_{\bm{\mu},i}^{(k,N)}$ commute, we define the post-measurement states

$|\Psi_{\bm{\mu},k}\rangle=\frac{\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}{\sqrt{\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}},$
(63)

and arrive at the set of algebraic constraints, for a fixed $k,\bm{\mu}$,

$M_{\bm{\mu},i}^{(k,N)}|\Psi_{\bm{\mu},k}\rangle=0,\quad\forall i.$ (64)

####  A.3.2 Applying Jordan’s lemma

Next, we employ Jordan’s lemma, which allows us to reduce our analysis to a
convex combination of $N$-qubit systems. We write $\mathcal{H}_{Q_{k}}$ to
denote the qubit Hilbert space of party $k$, and introduce a flag system
$\mathcal{H}_{F_{k}}$ which indicates the block. Then for every party
$\mathcal{H}_{\tilde{Q}_{k}}=\mathcal{H}_{Q_{k}}\otimes\mathcal{H}_{F_{k}}$,
and the purified state takes the form

$|\Psi\rangle_{\tilde{\bm{Q}}E}=\sum_{\bm{f}}\sqrt{p_{\bm{f}}}|\bm{f}\rangle_{\bm{F}}\otimes|\varphi^{\bm{f}}\rangle_{\bm{Q}E}\otimes|\bm{f}\rangle_{E^{\prime}},$
(65)

where
$\rho^{\bm{f}}=\mathrm{Tr}_{E}\big{[}|\varphi^{\bm{f}}\rangle\\!\langle\varphi^{\bm{f}}|\big{]}$
is an $N$-qubit state corresponding to block $\bm{f}=(f_{1},...,f_{N})$, where
$f_{k}$ indexes the block for party $k$ and $p_{\bm{f}}>0$ form a probability
distribution. Tracing out $EE^{\prime}$, the total state received by the
parties is then a convex combination of qubit states, and Eve holds a
purification of the state in register $E$ along with a label in register
$E^{\prime}$ telling her which block it pertains to. Similarly, the projectors
decompose

$\tilde{P}_{a_{k}|x_{k}}^{(k)}=\sum_{f_{k}}|f_{k}\rangle\\!\langle
f_{k}|_{F_{k}}\otimes P_{a_{k}|x_{k}}^{(f_{k})},$ (66)

where $P_{a_{k}|x_{k}}^{(f_{k})}$ is a rank one single qubit projector on
$\mathcal{H}_{Q_{k}}$ corresponding to block $f_{k}$ Jordan (1875); Pironio
_et al._ (2009); Bhavsar  _et al._ (2021).

$\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}=\sum_{\bm{f}_{(\overline{k,N})}}|\bm{f}_{(\overline{k,N})}\rangle\\!\langle\bm{f}_{(\overline{k,l})}|_{\bm{F}_{(\overline{k,N})}}\otimes
P_{\bm{\mu}|\bm{0}}^{(\bm{f}_{(\overline{k,N})})},$ (67)

where the notation $(\overline{k,N})$ is understood to denote a tuple
excluding entries $k,N$, e.g. $\bm{f}_{(\overline{k,N})}$ is a tuple of
indices $f_{k^{\prime}}$ for $k^{\prime}\neq k,N$.
$P_{\bm{\mu}|\bm{0}}^{(\bm{f}_{(\overline{k,N})})}=\bigotimes_{k^{\prime}\neq
k,N}P^{(f_{k^{\prime}})}_{\mu_{k^{\prime}}|0}$ is then a rank one projector on
the $N-2$ qubit Hilbert space shared by all parties excluding $k$ and $N$,
corresponding to the block $\bm{f}_{(\overline{k,N})}$.

We can now apply Jordan’s lemma to the projected states
$|\Psi_{\bm{\mu},k}\rangle$, by computing

$\displaystyle|\Psi_{\bm{\mu},k}\rangle$
$\displaystyle=\sum_{\bm{f}}\sqrt{p_{\bm{f}}}|\bm{f}\rangle_{\bm{F}}$
$\displaystyle\ \ \ \ \otimes\frac{\Big{(}\mathbb{I}_{Q_{k}Q_{N}E}\otimes
P_{\bm{\mu}|\bm{0}}^{(\bm{f}_{(\overline{k,N})})}\Big{)}|\varphi^{\bm{f}}\rangle_{\bm{Q}E}}{\sqrt{\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}}\otimes|\bm{f}\rangle_{E^{\prime}}$
$\displaystyle=\sum_{\bm{f}\in
S_{\bm{\mu}}^{k}}\sqrt{p_{\bm{f}}}|\bm{f}\rangle_{\bm{F}}\otimes|\phi_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\bm{Q}_{(\overline{k,N})}}$
$\displaystyle\ \ \ \ \ \ \ \
\otimes|\psi_{\bm{\mu},k}^{\bm{f}}\rangle_{Q_{k}Q_{N}E}\otimes|\bm{f}\rangle_{E^{\prime}}$
(68)

where $S_{\bm{\mu}}^{k}\ni\bm{f}$ is the set of blocks for which the
projection is non-zero. Here $\bm{f}$ is understood to be the concatenation of
$f_{k},f_{N},\bm{f}_{(\overline{k,N})}$, and we used the fact that the qubit
projectors are rank one to write the state as a tensor product,

$\frac{\Big{(}\mathbb{I}_{Q_{k}Q_{N}E}\otimes
P_{\bm{\mu}|\bm{0}}^{(\bm{f}_{(\overline{k,N})})}\Big{)}|\varphi^{\bm{f}}\rangle_{\bm{Q}E}}{\sqrt{\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}}\\\
=\begin{cases}|\phi_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\bm{Q}_{(\overline{k,N})}}\otimes|\psi_{\bm{\mu},k}^{\bm{f}}\rangle_{Q_{k}Q_{N}E}\
\mathrm{if}\ \bm{f}\in S_{\bm{\mu}}^{k},\\\ 0\ \mathrm{otherwise},\end{cases}$
(69)

where
$|\phi_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle=\bigotimes_{k^{\prime}\neq
k,N}|\phi_{\mu_{k^{\prime}}}^{f_{k^{\prime}}}\rangle$, and
$|\phi_{\mu_{k^{\prime}}}^{f_{k^{\prime}}}\rangle$ spans the support of
$P^{(f_{k^{\prime}})}_{\mu_{k^{\prime}}|0}$.
$|\psi_{\bm{\mu},k}^{\bm{f}}\rangle_{Q_{k}Q_{l}E}$ is then the state held by
parties $k,N$ and Eve following the projection. By writing
$|\tilde{\phi}_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\tilde{\bm{Q}}_{{(\overline{k,N})}}}=|\bm{f}_{(\overline{k,N})}\rangle_{\bm{F}_{(\overline{k,N})}}\otimes|\phi_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\bm{Q}_{{(\overline{k,N})}}}$,
and
$|\tilde{\psi}_{\bm{\mu},k}^{\bm{f}}\rangle_{\tilde{Q}_{k}\tilde{Q}_{N}E}=|f_{k}f_{N}\rangle_{F_{k}F_{N}}\otimes|\psi_{\bm{\mu},k}^{\bm{f}}\rangle_{Q_{k}Q_{N}E}$,
we can re-write the constraints in Eq. 64 as

$\sum_{\bm{f}\in
S_{\bm{\mu}}^{k}}\sqrt{p_{\bm{f}}}|\tilde{\phi}_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\tilde{\bm{Q}}_{{(\overline{k,N})}}}\\\
\otimes
M_{\bm{\mu},i}^{(k,N)}|\tilde{\psi}_{\bm{\mu},k}^{\bm{f}}\rangle_{\tilde{Q}_{k}\tilde{Q}_{N}E}\otimes|\bm{f}\rangle_{E^{\prime}}=0,$
(70)

implying, for a fixed $k,\bm{\mu}$,

$M_{\bm{\mu},i}^{(k,N)}|\tilde{\psi}_{\bm{\mu},k}^{\bm{f}}\rangle_{\tilde{Q}_{k}\tilde{Q}_{N}E}=0,\
\forall i,\forall\bm{f}\in S_{\bm{\mu}}^{k}.$ (71)

####  A.3.3 Applying the bipartite self-tests

For the next part of the proof, we use the self-testing properties of the
bipartite Bell expression $I^{(k,l)}_{\bm{\mu}}$, which are in turn derived
from the SOS polynomials, and the constraints they impose on any state which
achieves the maximum quantum value. Explicitly, for any state which satisfies
the polynomial constraints, there exists a local isometery which transforms
that state into an ideal state in tensor product with some junk. Due to
Jordan’s lemma, the constraints in Eq. 71 certify the the existence of a local
unitary on parties $k$ and $N$, for every measurement outcome $\bm{\mu}$ and
block combination $\bm{f}\in S_{\bm{\mu}}^{k}$, $U_{\bm{\mu},k}^{\bm{f}}$,
that satisfies for some fixed two qubit state $|\Phi\rangle$ and projectors
$P_{a_{k}|x_{k}}^{(k)}$, $P_{a_{N}|x_{N}}^{(N)}$,

$\Big{(}\mathbb{I}_{F_{k}F_{N}}\otimes
U_{\bm{\mu},k}^{\bm{f}}\otimes\mathbb{I}_{E}\Big{)}\Big{(}\tilde{P}_{a_{k}|x_{k}}^{(k)}\otimes\tilde{P}_{a_{N}|x_{N}}^{(N)}\Big{)}|\tilde{\psi}_{\bm{\mu},k}^{\bm{f}}\rangle_{\tilde{Q}_{k}\tilde{Q}_{N}E}\\\
=|f_{k}f_{N}\rangle_{F_{k}F_{N}}\otimes\Big{(}P_{a_{k}|x_{k}}^{(k)}\otimes
P_{a_{N}|x_{N}}^{(N)}\Big{)}|\Phi\rangle_{Q_{k}Q_{N}}\otimes|\lambda_{\bm{\mu},k}^{\bm{f}}\rangle_{E},$
(72)

where $|\lambda_{\bm{\mu},k}^{\bm{f}}\rangle_{E}$ is the junk system left over
in the Eve register, which a priori may depend on $\bm{\mu},k$. Recall we
required that all bipartite expressions self-test the same state up to local
unitaries, hence the above equation holds for all $\bm{\mu}$.

####  A.3.4 Global post-measurement state

Finally, we use the existence of local unitaries $U_{\bm{\mu},k}^{\bm{f}}$ to
analyse the global post-measurement state held by all parties following their
zero measurement, which takes the form

$\rho_{\bm{R}EE^{\prime}|\bm{0}}=\sum_{a_{k},a_{N},\bm{\mu}}|a_{k}a_{N}\bm{\mu}\rangle\\!\langle
a_{k}a_{N}\bm{\mu}|_{\bm{R}}\otimes\\\
\mathrm{Tr}_{\tilde{\bm{Q}}}\Big{[}\Big{(}\tilde{P}_{a_{k}|0}^{(k)}\otimes\tilde{P}_{a_{N}|0}^{(N)}\otimes\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\otimes\mathbb{I}_{EE^{\prime}}\Big{)}|\Psi\rangle\\!\langle\Psi|\Big{]}.$
(73)

We can rewrite the term inside the partial trace

$\displaystyle\Big{(}\tilde{P}_{a_{k}|0}^{(k)}\otimes\tilde{P}_{a_{N}|0}^{(N)}\otimes\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\otimes\mathbb{I}_{EE^{\prime}}\Big{)}|\Psi\rangle$
$\displaystyle=\sqrt{\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}\Big{(}\tilde{P}_{a_{k}|0}^{(k)}\otimes\tilde{P}_{a_{N}|0}^{(N)}\otimes\mathbb{I}_{\tilde{\bm{Q}}_{(\overline{k,N})}}\otimes\mathbb{I}_{EE^{\prime}}\Big{)}|\Psi_{\bm{\mu},k}\rangle$
$\displaystyle=\sqrt{\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}\sum_{\bm{f}\in
S_{\bm{\mu}}^{k}}\sqrt{p_{\bm{f}}}|\tilde{\phi}_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\tilde{\bm{Q}}_{{(\overline{k,N})}}}$
$\displaystyle\ \ \ \ \ \ \ \
\otimes\Big{(}\tilde{P}_{a_{k}|0}^{(k)}\otimes\tilde{P}_{a_{N}|0}^{(N)}\Big{)}|\tilde{\psi}_{\bm{\mu},k}^{\bm{f}}\rangle_{\tilde{Q}_{k}\tilde{Q}_{N}E}\otimes|\bm{f}\rangle_{E^{\prime}}$
$\displaystyle=\sqrt{\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle}\sum_{\bm{f}\in
S_{\bm{\mu}}^{k}}\sqrt{p_{\bm{f}}}|\tilde{\phi}_{\bm{\mu}}^{\bm{f}_{(\overline{k,N})}}\rangle_{\tilde{\bm{Q}}_{{(\overline{k,N})}}}$
$\displaystyle\otimes|f_{k}f_{N}\rangle_{F_{k}F_{N}}\otimes
U_{\bm{\mu},k}^{\bm{f}\dagger}\Big{(}P_{a_{k}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle_{Q_{k}Q_{N}}$ $\displaystyle\ \ \ \ \ \ \
\
\otimes|\lambda_{\bm{\mu},k}^{\bm{f}}\rangle_{E}\otimes|\bm{f}\rangle_{E^{\prime}}.$
(74)

Now, tracing out $\tilde{\bm{Q}}$ equates to tracing out systems
$\bm{F}\bm{Q}$, which yields

$\displaystyle\mathrm{Tr}_{\tilde{\bm{Q}}}\Big{[}\Big{(}\tilde{P}_{a_{k}|0}^{(k)}\otimes\tilde{P}_{a_{N}|0}^{(N)}\otimes\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}\otimes\mathbb{I}_{EE^{\prime}}\Big{)}|\Psi\rangle\\!\langle\Psi|\Big{]}$
$\displaystyle=\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle$ $\displaystyle\ \ \ \ \ \ \ \
\cdot\sum_{\bm{f}\in
S_{\bm{\mu}}^{k}}p_{\bm{f}}|\lambda_{\bm{\mu},k}^{\bm{f}}\rangle\\!\langle\lambda_{\bm{\mu},k}^{\bm{f}}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}}.$
(75)

By employing Corollary 1, we know that, following observation of $\langle
I\rangle=\eta^{\mathrm{Q}}$, the marginals
$\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,l)}}|\Psi\rangle$ are
unique; hence the following equality holds:

$\langle\Psi|\tilde{P}_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle=p(a_{k},a_{N},\bm{\mu}|\bm{0}),$ (76)

where $\\{p(a_{k},a_{N},\bm{\mu}|\bm{0})\\}_{a_{k},a_{N},\bm{\mu}}$ are those
unique correlations needed to achieve $\langle I\rangle=\eta^{\mathrm{Q}}$. We
then find

$\rho_{\bm{R}EE^{\prime}|\bm{0}}=\sum_{a_{k},a_{N},\bm{\mu}}p(a_{k},a_{N},\bm{\mu}|\bm{0})|a_{k}a_{N}\bm{\mu}\rangle\\!\langle
a_{k}a_{N}\bm{\mu}|_{\bm{R}}\\\ \otimes\sum_{\bm{f}\in
S_{\bm{\mu}}^{k}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu},k}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}}.$
(77)

Now notice, Eve can still establish correlations with the $N$ parties
excluding $k$ and $N$, by choosing the sets
$\\{S_{\bm{\mu}}^{k}\\}_{\bm{\mu}}$ to be disjoint. She could then distinguish
the different outcomes $\bm{\mu}$ by a projective measurement on $E^{\prime}$.
She can also establish correlations by making the set
$\\{|\lambda^{\bm{f}}_{\bm{\mu},k}\rangle\\}_{\bm{\mu}}$ distinguishable and
measuring $E$. To show Eve is in fact uncorrelated with all parties, we use
the fact that there are $N-1$ choices of $k$, i.e. one can choose different
combinations of parties to maximally violate the bipartite self-tests.

We now include extra notation $\overline{kN}$,
$\bm{\mu}\rightarrow\bm{\mu}_{\overline{kN}}$, which denotes a tuple of $N-2$
outcomes for all parties excluding $k$ and $N$, and define the following
state, which is just a rewriting of Eq. 77 making the choice $k$ explicit:

$\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k}:=\sum_{a_{k},a_{N},\bm{\mu}_{\overline{kN}}}p(a_{k},a_{N},\bm{\mu}_{\overline{kN}}|\bm{0})\\\
\cdot|a_{k}a_{N}\bm{\mu}_{\overline{kN}}\rangle\\!\langle
a_{k}a_{N}\bm{\mu}_{\overline{kN}}|_{\bm{R}}\\\ \otimes\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{kN}}}^{k}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}}.$
(78)

Now, we could equally define a second state
$\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k^{\prime}}$ where $k^{\prime}\neq k,N$ in
the exact same way, except we chose $k^{\prime}$ instead of $k$ as the self-
testing party. Since both states are a rewriting of the same post measurement
state $\rho_{\bm{R}EE}$ given by Eq. 77, they must be equal, and we establish
the equalities

$\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k}=\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k^{\prime}},\
\forall k,k^{\prime}\in\\{1,...,N-1\\},\ k^{\prime}\neq k.$ (79)

These equalities will allow us to place constraints on the sets
$S_{\bm{\mu}_{\overline{kN}}}^{k}$, and ultimately show they are all equal.
Specifically, Eq. 79 implies444Note that we have implicitly equated the
rewriting of the same outcome string
$\bm{a}=a_{k}a_{N}\bm{\mu}_{\overline{kN}}=a_{k^{\prime}}a_{N}\bm{\mu}_{\overline{k^{\prime}N}}$,
and only considered cases which appear in the summation, i.e. strings with
nonzero probability, $p(\bm{a}|\bm{0})>0$.

$\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{kN}}}^{k}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}}\\\
=\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{kN}}}^{k^{\prime}}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k^{\prime}}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k^{\prime}}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}}$
(80)

Now, since $p_{\bm{f}}\neq 0$, it follows for equality to hold in Eq. 80 that

$\bigcup_{\bm{\mu}_{\overline{kN}}}S_{\bm{\mu}_{\overline{kN}}}^{k}=\bigcup_{\bm{\mu}_{\overline{k^{\prime}N}}}S_{\bm{\mu}_{\overline{k^{\prime}N}}}^{k^{\prime}}\equiv
S.$ (81)

Next we consider the following partial trace equality that is a consequence of
Eq. 79,

$\mathrm{Tr}_{kN}\big{[}\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k}\big{]}=\mathrm{Tr}_{kN}\big{[}\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k^{\prime}}\big{]}.$
(82)

Directly computing, we find

$\mathrm{Tr}_{kN}\big{[}\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k}\big{]}=\sum_{\bm{\mu}_{\overline{kN}}}\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{kN}}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle|\bm{\mu}_{\overline{kN}}\rangle\\!\langle\bm{\mu}_{\overline{kN}}|\\\
\otimes\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{kN}}}^{k}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|\otimes|\bm{f}\rangle\\!\langle\bm{f}|,$
(83)

and

$\mathrm{Tr}_{kN}\big{[}\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k^{\prime}}\big{]}=\sum_{a_{k^{\prime}}}\langle\Phi|\Big{(}P_{a_{k^{\prime}}|0}^{(k^{\prime})}\otimes\mathbb{I}\Big{)}|\Phi\rangle|a_{k^{\prime}}\rangle\\!\langle
a_{k^{\prime}}|\\\
\otimes\sum_{\bm{\mu}_{\overline{k^{\prime}N}}}\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{k^{\prime}N}}|\bm{0}}^{\overline{(k^{\prime},N)}}|\Psi\rangle|\bm{\mu}_{\overline{k^{\prime}Nk}}\rangle\\!\langle\bm{\mu}_{\overline{k^{\prime}Nk}}|\\\
\otimes\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{k^{\prime}N}}}^{k^{\prime}}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}|\otimes|\bm{f}\rangle\\!\langle\bm{f}|,$
(84)

where $\bm{\mu}_{\overline{k^{\prime}Nk}}$ is understood to be the index
$\bm{\mu}_{\overline{k^{\prime}N}}$ without the entry corresponding to party
$k$. By equating Eq. 83 and Eq. 84, we find for every
$\bm{\mu}_{\overline{kN}}=(a_{1},...,a_{k-1},a_{k+1},...,a_{k^{\prime}},...,a_{N-1})$,

$\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{kN}}|\bm{0}}^{\overline{(k,l)}}|\Psi\rangle\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{kN}}}^{k}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|\otimes|\bm{f}\rangle\\!\langle\bm{f}|\\\
=\langle\Phi|\Big{(}P_{a_{k^{\prime}}|0}^{(k^{\prime})}\otimes\mathbb{I}\Big{)}|\Phi\rangle\sum_{a_{k}}\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{k^{\prime}N}}|\bm{0}}^{\overline{(k^{\prime},N)}}|\Psi\rangle\\\
\cdot\sum_{\bm{f}\in
S_{\bm{\mu}_{\overline{k^{\prime}N}}}^{k^{\prime}}}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}|\otimes|\bm{f}\rangle\\!\langle\bm{f}|.$
(85)

In the above equation it is understood that
$\bm{\mu}_{\overline{k^{\prime}N}}=(a_{1},...,a_{k^{\prime}-1},a_{k^{\prime}+1},...,a_{k},...,a_{N-1})$,
i.e. has the same values as $\bm{\mu}_{\overline{kN}}$ for parties excluding
$k,k^{\prime}$, where the $k^{\prime}$ entry is skipped. This implies

$S_{\bm{\mu}_{\overline{kN}}}^{k}=\bigcup_{a_{k}}S_{\bm{\mu}_{\overline{k^{\prime}N}}}^{k^{\prime}},\
\forall\bm{\mu}_{\overline{kN}}.$ (86)

Now we can establish the following recursive argument. First, setting $k=1$,
and $k^{\prime}=2$ in the above equation we find

$S_{\bm{\mu}_{\overline{1N}}}^{1}=\bigcup_{a_{1}}S_{\bm{\mu}_{\overline{2N}}}^{2}.$
(87)

Next, by setting $k=2$, $k^{\prime}=3$,

$S_{\bm{\mu}_{\overline{2N}}}^{2}=\bigcup_{a_{2}}S_{\bm{\mu}_{\overline{3N}}}^{3},$
(88)

which can be inserted into the previous to find

$S_{\bm{\mu}_{\overline{1N}}}^{1}=\bigcup_{a_{1}}\bigcup_{a_{2}}S_{\bm{\mu}_{\overline{3N}}}^{3}.$
(89)

Iterating this again by writing $S_{\bm{\mu}_{\overline{3N}}}^{3}$ as a union
over $S_{\bm{\mu}_{\overline{4N}}}^{4}$, we find

$S_{\bm{\mu}_{\overline{1N}}}^{1}=\bigcup_{a_{1}}\bigcup_{a_{2}}\bigcup_{a_{3}}S_{\bm{\mu}_{\overline{4N}}}^{4}.$
(90)

Proceeding recursively, we arrive at

$S_{\bm{\mu}_{\overline{1N}}}^{1}=\bigcup_{a_{1}}\cdots\bigcup_{a_{N-2}}S_{\bm{\mu}_{\overline{N-1,N}}}^{N-1}=\bigcup_{\bm{\mu}_{\overline{N-1,N}}}S_{\bm{\mu}_{\overline{N-1,N}}}^{N-1}=S.$
(91)

Since the above equation holds for all $\bm{\mu}_{\overline{1N}}$, we have
shown every set in
$\\{S_{\bm{\mu}_{\overline{1N}}}^{1}\\}_{\bm{\mu}_{\overline{1N}}}$ is the
same. There is nothing unique about choosing $k=1$, allowing us to write

$\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k}=\sum_{a_{k},a_{N},\bm{\mu}_{\overline{kN}}}p(a_{k},a_{N},\bm{\mu}_{\overline{kN}}|\bm{0})\\\
\cdot|a_{k}a_{N}\bm{\mu}_{\overline{kN}}\rangle\\!\langle
a_{k}a_{N}\bm{\mu}_{\overline{kN}}|_{\bm{R}}\\\ \otimes\sum_{\bm{f}\in
S}p_{\bm{f}}|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}},$
(92)

Hence Eve can learn nothing by measuring her register $E^{\prime}$. What
remains is to deal with the vectors
$|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle$; we will show that the
set
$\\{|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\}_{\bm{\mu}_{\overline{kN}}}$
contains one linearly independent vector, hence Eve can learn nothing about
the outcome $\bm{\mu}_{\overline{kN}}$ from measuring her register $E$.

We will use the same approach as before. Eq. 79 now implies, for every
$\bm{f}\in S$,

$\sum_{a_{k}a_{N}\bm{\mu}_{\overline{kN}}}\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{kN}}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle\\\
\cdot|a_{k}a_{N}\bm{\mu}_{\overline{kN}}\rangle\\!\langle
a_{k}a_{N}\bm{\mu}_{\overline{kN}}|\otimes|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|\\\
=\sum_{a_{k^{\prime}}a_{N}\bm{\mu}_{\overline{k^{\prime}N}}}\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{k^{\prime}N}}|\bm{0}}^{\overline{(k^{\prime},N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k^{\prime}}|0}^{(k^{\prime})}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle\\\
\cdot|a_{k^{\prime}}a_{N}\bm{\mu}_{\overline{k^{\prime}N}}\rangle\\!\langle
a_{k^{\prime}}a_{N}\bm{\mu}_{\overline{k^{\prime}N}}|\otimes|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}|.$
(93)

Now equating for a given value of
$\bm{a}=(a_{1},...,a_{k},...,a_{k^{\prime}},...,a_{N})$, we obtain

$\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{kN}}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle\\\
\cdot|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}|\\\
=\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{k^{\prime}N}}|\bm{0}}^{\overline{(k^{\prime},N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k^{\prime}}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle\\\
\cdot|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}\rangle\\!\langle\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}|.$
(94)

We can hence conclude the two vectors are linearly dependent,

$|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\sim|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime}N}},k^{\prime}}\rangle,$
(95)

where $\sim$ denotes equality up to some positive real constant555Note it is
sufficient to just consider the cases for which the probabilities
$\langle\Psi|\tilde{P}_{\bm{\mu}_{\overline{kN}}|\bm{0}}^{\overline{(k,N)}}|\Psi\rangle\langle\Phi|\Big{(}P_{a_{k}|0}^{(k)}\otimes
P_{a_{N}|0}^{(N)}\Big{)}|\Phi\rangle$ are nonzero. If they are zero, then the
vector $|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle$ will not appear
in the summation, and Eve will never observe it.. Notice on the left hand side
of the above equation, one has the freedom to choose any value of
$a_{k^{\prime}}$ without changing the right hand side up to a constant.
Therefore

$|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}}|a_{k^{\prime}}=0,k}\rangle\sim|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}}|a_{k^{\prime}}=1,k}\rangle.$
(96)

There are $2^{N-3}$ such equations written above, corresponding to the
different choices of $\bm{\mu}_{\overline{kN}}$ once $a_{k^{\prime}}$ is
fixed. We have $2^{N-2}$ unknowns that we want to fix, hence this is
sufficient to show linear dependence for the $N=3$ case. If $N>3$, we can
select another party $k^{\prime\prime}$ not equal to $k,k^{\prime},N$ and add
another $2^{N-3}$ equations,

$|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle\sim|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{k^{\prime\prime}N}},k^{\prime\prime}}\rangle,$
(97)

allowing us to write

$\displaystyle|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}}|a_{k^{\prime}}=0,k}\rangle$
$\displaystyle\sim|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}}|a_{k^{\prime}}=1,k}\rangle$
$\displaystyle|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}}|a_{k^{\prime\prime}}=0,k}\rangle$
$\displaystyle\sim|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}}|a_{k^{\prime\prime}}=1,k}\rangle.$
(98)

The combination of the two will solve the $N=4$ case. We can see that for the
first choice of $k^{\prime}$, we get $2^{N-3}$ equations which is half the
unknowns, reducing the number of unknowns to $2^{N-3}$. Each new choice of
$k^{\prime}$, of which there are $N-2$ in total, halves the number of
unknowns, until we are left with one, which shows that every vector can be
written as a linear combination of a fixed vector, i.e.

$|\lambda^{\bm{f}}_{\bm{\mu}_{\overline{kN}},k}\rangle=\beta_{\bm{\mu}_{\overline{kN}}}^{k}|\lambda^{\bm{f}}_{k}\rangle,$
(99)

for some positive real constants $\beta_{\bm{\mu}_{\overline{kN}}}^{k}$, which
due to normalization must be equal to 1. Putting the above into Eq. 93 we also
notice $|\lambda^{\bm{f}}_{k}\rangle=|\lambda^{\bm{f}}_{k^{\prime}}\rangle$,
hence we can drop the $k$ label.

Now we finally conclude

$\rho_{\bm{R}EE^{\prime}|\bm{0}}\equiv\rho_{\bm{R}EE^{\prime}|\bm{0}}^{k}=\Bigg{(}\sum_{a_{k},a_{N},\bm{\mu}_{\overline{kN}}}p(a_{k},a_{N},\bm{\mu}_{\overline{kN}}|\bm{0})\\\
\cdot|a_{k}a_{N}\bm{\mu}_{\overline{kN}}\rangle\\!\langle
a_{k}a_{N}\bm{\mu}_{\overline{kN}}|_{\bm{R}}\Bigg{)}\\\
\otimes\Bigg{(}\sum_{\bm{f}\in
S}p_{\bm{f}}|\lambda^{\bm{f}}\rangle\\!\langle\lambda^{\bm{f}}|_{E}\otimes|\bm{f}\rangle\\!\langle\bm{f}|_{E^{\prime}}\Bigg{)},$
(100)

which is of the desired tensor product form, and completes the proof.

∎

###  A.4 Proof of Lemma 3

Lemma 3. Let $I,\eta_{N}^{\mathrm{Q}}$ be defined as in Eq. 12. Then

$R_{I}(\eta_{N}^{\mathrm{Q}})=H(\\{p(\bm{a}|\bm{0})\\}),$ (101)

where $H(\\{p_{i}\\})$ is the Shannon entropy of a distribution
$\\{p_{i}\\}_{i}$.

###### Proof.

Lemma 3 can be immediately proven using Eq. 12 since the state for which then
entropy is evaluated on is always a tensor product. This implies, for all
compatible post measurement states,
$H(\bm{R}|\bm{X}=\bm{0},E)_{\rho_{\bm{R}E|\bm{0}}}=H(\bm{R}|\bm{X}=\bm{0})_{\rho_{\bm{R}|\bm{0}}}$.
Since $\rho_{\bm{R}|\bm{0}}$, derived explicitly in the proof of Eq. 12, is
the same for all compatible states and measurements, we obtain the claim:

$\inf_{\begin{subarray}{c}|\Psi\rangle_{\tilde{\bm{Q}}E},\big{\\{}\\{\tilde{P}_{a_{k}|x_{k}}^{(k)}\\}_{a_{k}}\big{\\}}_{k}\\\
\mathrm{compatible\ with}\ \langle I\rangle\\\
=\eta^{\mathrm{Q}}_{N}\end{subarray}}H(\bm{R}|\bm{X}=\bm{0},E)_{\rho_{\bm{R}E|\bm{0}}}\\\
=H(\\{p(a_{k},a_{l},\bm{\mu}|\bm{0})\\}).$ (102)

∎

##  Appendix B Proofs and details for DI randomness certification

Recall the bipartite Bell-inequalities $I_{\theta}$ which are defined as

$\langle I_{\theta}^{(k,l)}\rangle=\cos\theta\cos 2\theta\langle
A_{0}^{(k)}A_{0}^{(l)}\rangle-\\\ \cos 2\theta\big{(}\langle
A_{0}^{(k)}A_{1}^{(l)}\rangle+\langle
A_{1}^{(k)}A_{0}^{(l)}\rangle\big{)}+\cos\theta\langle
A_{1}^{(k)}A_{1}^{(l)}\rangle$ (103)

for $\theta\in\mathcal{G}$ where

$\mathcal{G}=(\pi/4,\pi/2)\cup(\pi/2,3\pi/4)\cup(5\pi/4,3\pi/2)\cup(3\pi/2,7\pi/4).$
(104)

We now prove a few results about these Bell-inequalities that were stated in
the main text.

###  B.1 Proof of Lemma 5

Lemma 5. Let $\bm{\mu}$ be a tuple of $N-2$ measurement outcomes for all
parties excluding $k,l$, and $n_{\bm{\mu}}\in\\{0,1\\}$ be the parity of
$\bm{\mu}$. Let $\theta\in\mathcal{G}$ and
$\\{I_{\bm{\mu}}^{(k,l)}\\}_{\bm{\mu}}$ be a set of bipartite Bell expressions
between parties $k,l$, where

$I_{\bm{\mu}}^{(k,l)}=(-1)^{n_{\bm{\mu}}}I_{\theta}^{(k,l)}.$ (105)

Then the expanded Bell expression given by

$I_{\theta}=\sum_{k=1}^{N-1}\Bigg{(}\sum_{\bm{\mu}}\tilde{P}^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}I_{\bm{\mu}}^{(k,N)}\Bigg{)}$
(106)

has quantum bounds $\pm\eta_{N,\theta}^{\mathrm{Q}}$ where
$\eta_{N,\theta}^{\mathrm{Q}}=(N-1)2\sin^{3}\theta$, achieved up to
relabelings by the strategy in Eq. 19, and defines a nontrivial Bell
inequality.

###### Proof.

The above is an example of Footnote 1, where we used the bipartite expression
in Lemma 4 as a seed, and chose $c_{k,l}=1$ if $l=N$ and
$k=\in\\{1,..,N-1\\}$, and 0 otherwise. First we notice that if the bound
$\eta_{N,\theta}^{\mathrm{Q}}$ is achievable, then $I_{\theta}$ must define a
nontrivial Bell inequality. This is because the maximum local value is upper
bounded by $(N-1)\eta_{\theta}^{\mathrm{L}}<\eta_{N,\theta}^{\mathrm{Q}}$,
since $\eta_{\theta}^{\mathrm{L}}<\eta_{\theta}^{\mathrm{Q}}$. A similar
argument holds for the minimum local value.

We now proceed to show $\langle I\rangle=\eta_{N,\theta}^{\mathrm{Q}}$ is
achieved by the strategy in Eq. 19. Notice that, for the ideal operators
$P_{a_{k^{\prime}}|0}^{(k^{\prime})}=|+\rangle\\!\langle+|$
($|-\rangle\\!\langle-|$) if $a_{k^{\prime}}=0$ ($a_{k^{\prime}}=1$),

$P^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}|\psi_{\mathrm{GHZ}}\rangle=\sqrt{\langle\psi_{\mathrm{GHZ}}|P^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}|\psi_{\mathrm{GHZ}}\rangle}|\phi_{\bm{\mu}}\rangle\otimes|\Phi_{\bm{\mu}}\rangle_{Q_{k}Q_{N}},$
(107)

where $|\phi_{\bm{\mu}}\rangle$ spans the support of
$P^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}$, and
$|\Phi_{\bm{\mu}}\rangle=(|00\rangle+i(-1)^{n_{\bm{\mu}}}|11\rangle)/\sqrt{2}$.
We then have

$\displaystyle\sum_{\bm{\mu}}$
$\displaystyle\langle\psi_{\mathrm{GHZ}}|P^{\overline{(k,N)}}_{\bm{\mu}|\bm{0}}\otimes
I_{\bm{\mu}}^{(k,N)}|\psi_{\mathrm{GHZ}}\rangle$
$\displaystyle=\sum_{\bm{\mu}}\langle\psi_{\mathrm{GHZ}}|P_{\bm{\mu}|\bm{0}}^{\overline{(k,N)}}|\psi_{\mathrm{GHZ}}\rangle\langle\Phi_{\bm{\mu}}|I_{\bm{\mu}}^{(k,N)}|\Phi_{\bm{\mu}}\rangle$
$\displaystyle=2\sin^{3}\theta,\ \forall k\in\\{1,...,N-1\\},$ (108)

where the final equality comes from the fact that when $n_{\bm{\mu}}=0$, we
recover the state and measurements in Eq. 18 which yields the maximum quantum
value of $I^{(k,N)}_{\theta}$, and when $n_{\bm{\mu}}=1$, we obtain a strategy
equivalent to Eq. 18 up to a relabeling, which yields the maximum quantum
value of $-I^{(k,N)}_{\theta}$.

Since the maximum quantum bound is achievable, a nontrivial Bell inequality
follows. The minimum quantum value $-\eta_{N,\theta}^{\mathrm{Q}}$ is simply
achieved by relabeling the outcomes.

∎

###  B.2 Proof of Eq. 25

Proposition 3. For $N$ even, let

$\theta^{*}_{N}=\frac{2\pi t_{N}}{N+1},$ (109)

where $t_{N}$ is the $(N/2)^{\mathrm{th}}$ element of the sequence
$1,1,5,7,3,3,11,13,5,5,...$ given by

$t_{N}=\begin{cases}N/4+1/2,\ \mathrm{if}\ N=8n+2,\\\ N/4,\ \mathrm{if}\
N=8n+4,\\\ 3N/4+1/2,\ \mathrm{if}\ N=8n+6,\\\ 3N/4+1,\ \mathrm{if}\ N=8n+8,\
n\in\mathbb{N}_{0}.\end{cases}$ (110)

Then $\theta^{*}_{N}\in\mathcal{G}$.

###### Proof.

The sequence $\theta_{N}^{*}$ splits naturally into four subsequences for
$n\in\mathbb{N}$

$\displaystyle\theta_{8n+2}^{*}$ $\displaystyle=\frac{2\pi(2n+1)}{8n+3}\qquad$
$\displaystyle\theta_{8n+4}^{*}=\frac{2\pi(2n+1)}{8n+5}$ (111)
$\displaystyle\theta_{8n+6}^{*}$ $\displaystyle=\frac{2\pi(6n+5)}{8n+7}\qquad$
$\displaystyle\theta_{8n+8}^{*}=\frac{2\pi(6n+7)}{8n+9}\,.$

First notice that the first terms in each of these subsequences are contained
in one of the subintervals of $\mathcal{G}$

$\displaystyle\theta_{2}^{*}$ $\displaystyle\in(\pi/2,3\pi/4)\qquad$
$\displaystyle\theta_{4}^{*}\in(\pi/4,\pi/2)$ (112)
$\displaystyle\theta_{6}^{*}$ $\displaystyle\in(5\pi/4,3\pi/2)\qquad$
$\displaystyle\theta_{8}^{*}\in(3\pi/2,7\pi/4)\,.$

Looking at the ratio of subsequent terms in each subsequence

$\displaystyle\frac{\theta_{8n+2}^{*}}{\theta_{8n+10}}$
$\displaystyle=\frac{16n^{2}+30n+11}{16n^{2}+30n+9}\quad\frac{\theta_{8n+4}^{*}}{\theta_{8n+12}}=\frac{16n^{2}+34n+13}{16n^{2}+34n+15}$
$\displaystyle\frac{\theta_{8n+6}^{*}}{\theta_{8n+14}}$
$\displaystyle=\frac{48n^{2}+130n+75}{48n^{2}+130n+77}\quad\frac{\theta_{8n+8}^{*}}{\theta_{8n+16}}=\frac{48n^{2}+158n+119}{48n^{2}+158n+117}\,$

we see that the subsequences $\theta_{8n+2}^{*}$ and $\theta_{8n+8}$ are
strictly monotonically decreasing sequences whereas $\theta_{8n+4}^{*}$ and
the subsequences $\theta_{8n+6}$ and $\theta_{8n+8}$ are strictly
monotonically increasing sequences. Furthermore their limits are

$\displaystyle\lim_{n\to\infty}\theta_{8n+2}^{*}$
$\displaystyle=\lim_{n\to\infty}\theta_{8n+4}^{*}=\pi/2$ (113)
$\displaystyle\lim_{n\to\infty}\theta_{8n+6}^{*}$
$\displaystyle=\lim_{n\to\infty}\theta_{8n+8}^{*}=3\pi/2\,.$

Notice the limits correspond to the boundaries of the respective subinterval
of $\mathcal{G}$ that the first terms of the subsequences are contained in. As
they converge strictly monotonically to these limits this implies that every
term in the subsequences in contained within their respective subintervals and
hence $\theta_{N}^{*}\in\mathcal{G}$ for all even $N$. ∎

###  B.3 Evidence for 1

Conjecture 1. Let $\theta_{N}^{*}$ be defined in Eq. 25, and define the
corresponding MABK violation

$m_{N}^{*}=\langle M_{N}(\theta^{*}_{N})\rangle.$ (114)

Then we have the following for $N$ even:

  1. (i)

For every MABK value $s$ in the range $(1,m_{N}^{*}]$, there exists a
$\theta_{s}\in\mathcal{G}$ that satisfies $s=\langle
M_{N}(\theta_{s})\rangle$.

  2. (ii)

$m_{N}^{*}$ is the maximum MABK value achievable by quantum strategies which
generate maximum randomness, i.e. strategies with $p(\bm{a}|\bm{0})=1/2^{N},\
\forall\bm{a}$.

For $N$ odd we have:

  1. (iii)

For every MABK value $s$ in the range $(1,2^{(N-1)/2})$, there exists a
$\theta_{s}\in\mathcal{G}$ that satisfies $s=\langle
M_{N}(\theta_{s})\rangle$.

####  B.3.1 Part $(i)$

The goal of part $(i)$ is to establish the range of MABK values which are
accessible by the family of strategies in Eq. 19, for $\theta\in\mathcal{G}$.
We know that the MABK value $m_{N}^{*}$ is always accessible due to Eq. 25, so
what remains to be shown is that one can cover the full range of Mermin values
by varying $\theta\in\mathcal{G}$.

To begin with, as a consequence of Eq. 25, we can argue that the conjecture is
true for range of values $(1/\sqrt{2},m_{N}^{*}]$. This can be obtained by
calculating, for example when $N=8n+2$, $\langle
M_{N}(\pi/2)\rangle=1/\sqrt{2}$. Now from the proof of Eq. 25, we know
$\pi/2<\theta_{N}^{*}<3\pi/4$. Since $\langle M_{N}(\theta)\rangle$ is smooth
across the domain $(\pi/2,\theta_{N}^{*}]\subset\mathcal{G}$, we can hence
conclude that for every $s\in(1/\sqrt{2},m_{N}^{*}]$ there exists a
$\theta_{s}\in(\pi/2,\theta_{N}^{*}]$ which gives rise to that value. A
similar argument holds for other values of $N$.

For the full range of MABK values, The easiest way to see that part $(i)$ of
the conjecture holds for a given $N$ is to plot $\langle M_{N}(\theta)\rangle$
and visually check. Fig. 1 displays this for $N=2,4,...,16$, showing the
conjecture holds for these values.

####  B.3.2 Part (ii)

The goal of part $(ii)$ is to claim the analytical lower bound, $m_{N}^{*}$,
on the maximum MABK value achievable whilst generating maximum randomness, is
optimal, in the sense there exists no other set of quantum correlations with a
higher MABK value achieving maximum randomness. To justify this claim, we
developed a numerical technique to upper bound the maximum MABK value of
quantum correlations achieving maximum randomness, and checked this against
the achievable lower bounds $m_{N}^{*}$. We found close agreement between our
numerical calculations and the analytic lower bounds, modulo a small
discrepancy which pushed the numerical values slightly below the analytical
ones. Since the SDP being solved is a minimization, we judge this to be caused
by numerical precision, and the accumulations of errors pushing the global
optimum below its true value. A comparison between our analytical lower bound
and the numerics can be found in Table 1, and details of the numerical method
can be found in Section B.9.1. We also remark that this conjecture was proven
analytically for the $N=2$ case in Wooltorton  _et al._ (2022).

$N$ | Analytical lower bound | Numerical upper bound
---|---|---
2 | $3\sqrt{3}/4\approx 1.29903811$ | 1.29903810
4 | $(5/8)\sqrt{(5/2)(5+\sqrt{5})}\approx 2.65828378$ | 2.65828370
6 |  | $(7/8)\big{(}\cos(\pi/14)+3\sqrt{2}\cos(3\pi/28)-3\cos(\pi/7)$
---
$+5\cos(3\pi/14)\big{)}\approx 5.41251947$
5.41251940
8 |  | $45/16+33\sqrt{3}/4+(45\sqrt{2}/16)(3+\sqrt{3})\cos(\pi/36)$
---
$-(1/16)(180\sqrt{3}+90)\cos^{2}(\pi/36)\approx 10.93208548$
10.93208548
10 |  | $(11/32)\big{(}\cos(\pi/22)+30\sqrt{2}\cos(3\pi/44)-5\cos(\pi/11)+15\cos(3\pi/22)$
---
$+5\sqrt{2}\cos(7\pi/44)-30\cos(2\pi/11)+42\cos(5\pi/22)\approx 22.00126184$
22.00125885
12 |  | $(429\sqrt{2}/16)\cos(\pi/52)+(39\sqrt{2}/32)\cos(9\pi/52)+(715\sqrt{2}/64)\cos(5\pi/52)$
---
$+(13/64)\cos(\pi/26)+(1287/64)\cos(5\pi/26)-(715/64)\cos(2\pi/13)+(143/32)\cos(3\pi/26)$
$-(39/32)\cos(\pi/13)-(429/16)\cos(3\pi/13)\approx 44.19316043$
44.19316040
Table 1: Comparison between upper and lower bounds on the maximum MABK value
which can be achieved by quantum correlations certifying maximum randomness,
for different numbers of parties $N$, rounded to 8 d.p. The analytical lower
bound is provided by the family of strategies Eq. 19 in the main text, and the
numerical upper bound is calculated with an SOS approach, which amounts to
solving an SDP. We observe instances where the numerical upper bound is
seemingly below the analytical value. Since the SDP being solved is a