# Improved device-independent randomness expansion rates from tight bounds on
the two sided randomness using CHSH tests

Rutvij Bhavsar<EMAIL_ADDRESS>Department of Mathematics,
University of York, Heslington, York, YO10 5DD, United Kingdom  Sammy Ragy
<EMAIL_ADDRESS>Department of Mathematics, University of York, Heslington,
York, YO10 5DD, United Kingdom  Roger Colbeck<EMAIL_ADDRESS>Department of Mathematics, University of York, Heslington, York, YO10 5DD,
United Kingdom

($23^{\text{rd}}$ May 2021)

###### Abstract

A device-independent randomness expansion protocol aims to take an initial
random string and generate a longer one, where the security of the protocol
does not rely on knowing the inner workings of the devices used to run it. In
order to do so, the protocol tests that the devices violate a Bell inequality
and one then needs to bound the amount of extractable randomness in terms of
the observed violation. The entropy accumulation theorem gives a bound in
terms of the single-round von Neumann entropy of any strategy achieving the
observed score. Tight bounds on this are known for the one-sided randomness
when using the Clauser-Horne-Shimony-Holt (CHSH) game. Here we find the
minimum von Neumann entropies for a given CHSH score relevant for one and two
sided randomness that can be applied to various protocols. In particular, we
show the gain that can be made by using the two-sided randomness and by using
a protocol without spot-checking where the input randomness is recycled. We
also discuss protocols that fully close the locality loophole while expanding
randomness. Although our bounds are mostly numerical, we conjecture analytic
formulae for the curves in two cases.

##  I Introduction

Random numbers have a wide variety of uses. In some applications, only the
distribution of the random numbers matters, while in others it is important
that the generated numbers are also private, for instance when used for
cryptography. According to our current understanding of physics, generating
fundamentally random numbers requires quantum processes. While it is easy to
come up with a quantum process that can in theory generate random numbers,
given a candidate quantum random number generator, verifying that it is indeed
generating random numbers and at what rate is a difficult task that requires
detailed understanding of the physical device. Any mismatch between the model
of the device used in the security proof and the real device could in
principle be exploited by an adversary.

Device-independent protocols aim to circumvent the mismatch problem by
designing the protocol to abort unless the devices used are performing
sufficiently well, without needing to know the internal mechanism by which
they operate. In the context of device-independent randomness expansion (DIRE)
the main idea is that the ability to violate a Bell inequality implies that
the devices doing so must be generating randomness Colbeck (2007); Colbeck and
Kent (2011). Thus, in a sense, the protocol self-tests Mayers and Yao (1998)
the devices during its operation, leading to enhanced security. Although
challenging to accomplish, recently the first experimental demonstrations of
DIRE were performed Li  _et al._ (2021); Shalm  _et al._ (2021); Liu  _et al._
(2021), following earlier experiments considering randomness generation
Pironio  _et al._ (2010); Bierhorst  _et al._ (2018); Liu  _et al._ (2018). On
the theoretical side, an increasingly sophisticated series of proofs Vazirani
and Vidick (2012); Miller and Shi (2014, 2017) led to the current state of the
art Zhang  _et al._ (2020); Arnon-Friedman  _et al._ (2019). In this work we
consider the proofs based on the entropy accumulation theorem Dupuis  _et al._
(2020); Dupuis and Fawzi (2019), which establishes a lower bound on the amount
of randomness after many Bell tests in terms of the von Neumann entropy of a
single round achieving the observed score (see Appendix E for a precise
statement). In this work we focus on generating bounds on the von Neumann
entropy, before combining these bounds with the entropy accumulation theorem
to illustrate the improvement.

In a DIRE protocol, randomly chosen inputs are made to two separated devices
in such a way that each device cannot learn the input chosen by the other. We
use $X$ and $Y$ to label the inputs and $A$ and $B$ to label the outputs, and
consider an adversary with side information $E$. This side information could
be quantum, i.e., the general strategy has an adversary hold the $E$ part of a
state $\rho_{A^{\prime}B^{\prime}E}$ where the $A^{\prime}$ and $B^{\prime}$
systems are held by the devices. Each input $X$ to the first device
corresponds to a measurement on $A^{\prime}$ giving outcome $A$ and,
analogously, for each input $Y$ to the other device there is a corresponding
measurement on $B^{\prime}$ with outcome $B$. There are two quantities of
interest, both of which depend on the post-measurement state: the first is the
score in some non-local game, which is a function of the conditional
distribution $p_{AB|XY}$; the second is the von Neumann entropy of either one
or both of the outputs. More precisely, we want to express the minimum von
Neumann entropy as a function of the score. In this work we study six such von
Neumann entropies: $H(AB|X=0,Y=0,E)$, $H(AB|XYE)$, $H(AB|E)$,
$H(A|X=0,Y=0,E)$, $H(A|XYE)$ and $H(A|E)$111In the one sided cases,
conditioning on $Y$ is irrelevant, but we keep this for notational symmetry..

The difficulty in bounding these stems from the fact that a priori there is no
upper bound on the dimension of the systems $A^{\prime}$, $B^{\prime}$ and $E$
that need to be considered. For instance, for some Bell inequalities it is
known that the maximum quantum violation cannot be achieved if $A^{\prime}$
and $B^{\prime}$ are finite dimensional Slofstra (2019), and there is evidence
that this is true even in the case where $X$ and $Y$ are binary and where $A$
and $B$ have three possible values Pál and Vértesi (2010). However, in the
case where $A$, $B$, $X$ and $Y$ are all binary, Jordan’s lemma Jordan (1875)
implies that there is no loss in generality in considering a convex
combination of strategies in which $A^{\prime}$ and $B^{\prime}$ are two-
dimensional. This observation was used to give a tight analytic lower bound on
$H(A|X=0,Y=0,E)$ in terms of the CHSH score Pironio  _et al._ (2009) and is
also crucial for the present work. This analytic bound was also extended to a
family of CHSH-like inequalities in Woodhead  _et al._ (2021). In cases where
such simplifications do not hold, we are limited to lower bounding the single-
round von Neumann entropy instead. For instance, it can be bounded using the
single-round min entropy, which can be optimized at a particular level of the
semi-definite hierarchy Navascués  _et al._ (2008). Although this method can
generate numerically certified lower bounds for arbitrary protocols Brown  _et
al._ (2020), there is a significant loss in tightness when moving to the
single-round min entropy. More recent methods give tighter computational
bounds on the von Neumann entropy Sekatski  _et al._ (2020); Brown  _et al._
(2021). Forming more direct and tighter bounds is a key open problem in the
field of device-independence and would go along way towards making device
independent quantum key distribution (DIQKD) experimentally implementable.

Which of the six entropic quantities is of most interest depends on the
situation. The one-sided entropies are most-relevant in the context of DIQKD,
for instance, while using both outputs is useful for DIRE. The quantities that
are conditioned on $X=0$ and $Y=0$ are useful for spot-checking protocols in
which particular fixed measurements (taken here to be the $X=0$ and $Y=0$
measurements) are used to generate randomness/key, and where the other
measurements are used only rarely to check that the devices are behaving
honestly. The quantities conditioned on $X$ and $Y$ are useful for analysing
protocols in which the generation rounds involve multiple settings, where the
input randomness is recycled, and can also be used to close the locality
loophole in randomness generation. The remaining quantities, $H(AB|E)$ and
$H(A|E)$, tell us something about the fundamental randomness based on the Bell
violation, and the second of these can be useful for DIQKD protocols in which
the measurement settings in the generation rounds are chosen randomly and to
which an adversary, Eve, does not have access.

In this paper we give numerically generated curves for each of these six
quantities when using the CHSH game as the Bell test. For $H(A|XYE)$ and
$H(AB|XYE)$ we additionally give conjectured analytic forms for the curves. We
then use these together with the EAT to show the improvement based on finite
statistics.

##  II The significance of various entropic quantities

In this section we discuss the significance of the six entropic quantities
given above in the context of DIRE, noting that the one-sided quantities are
also useful for DIQKD. To do so we first describe the general structure of the
raw randomness generation part of a spot-checking and non-spot-checking DIRE
protocol. A more complete description of the protocols is in Section V.

In a protocol without spot-checking, there are two untrusted devices, and in
every round their inputs $X_{i}$ and $Y_{i}$ are generated according to some
distribution $p_{XY}$. Often two independent random number generators are used
for this, so that $p_{XY}=p_{X}p_{Y}$. The generated numbers are used as
inputs to the devices, which return two outputs $A_{i}$ and $B_{i}$
respectively. This is repeated for $n$ rounds generating the raw randomness
${\bf A}$, ${\bf B}$, where the bold font denotes the concatenation of all the
outputs.

In a spot-checking protocol there is an additional step in which each round is
declared to be either a test round ($T_{i}=1$) or a generation round
($T_{i}=0$), where test rounds occur with probability $\gamma$, which is
typically small. On test rounds $X_{i}$ and $Y_{i}$ are generated according to
some distributions $p_{XY}$. On generation rounds, $X_{i}$ and $Y_{i}$ are set
according to some other distribution – in this work we use the deterministic
distribution $X_{i}=Y_{i}=0$. These are used as inputs to the devices, which
return two outputs $A_{i}$ and $B_{i}$ respectively. The rationale behind
using a spot-checking protocol is that randomness is required to perform a
Bell test and it is desirable to be able to run the protocol with a smaller
requirement on the amount of input randomness required. Choosing whether to
test or not requires roughly $H_{\mathrm{bin}}(\gamma)$ bits of randomness per
round222Here $H_{\mathrm{bin}}$ denotes the binary entropy., so choosing
$\gamma$ small enough leads to an overall saving. Furthermore, protocols often
discard the input randomness, in which case for many Bell tests spot-checking
is necessary in order to achieve expansion. In the CHSH game, for instance, if
$p_{XY}$ is chosen uniformly, each test round requires $2$ bits of randomness,
but the amount of two-sided randomness output by the quantum strategy with the
highest possible winning probability is only
$1+H_{\mathrm{bin}}(\frac{1}{2}(1+\frac{1}{\sqrt{2}}))\approx 1.60$ bits.
However, as we discuss later, the input randomness need not be discarded.

In the case of small $\gamma$, almost every round is a generation round and
hence an eavesdropper wishes to guess the outputs for the inputs $X=0$ and
$Y=0$. The entropy $H(AB|X=0,Y=0,E)$ is thus the relevant quantity for spot-
checking DIRE protocols. The one-sided quantity $H(A|X=0,Y=0,E)$ has often
been used instead because of the existing analytic bound for this Pironio  _et
al._ (2009); Woodhead  _et al._ (2021), but, because this ignores one of the
outputs, it is wasteful as an estimate of the generated randomness. For DIQKD
protocols, on the other hand, the one-sided entropy is the relevant quantity,
since to make key Alice’s and Bob’s strings should match. We also remark that
these quantities can be useful bounds for protocols without spot-checking if
the distribution $p_{XY}$ is heavily biased towards $X=Y=0$.

The quantities $H(AB|XYE)$ and $H(A|XYE)$ are useful for protocols without
spot checking. One might imagine, for example, using a source of public
randomness, such as a randomness beacon to choose the inputs to the protocol,
in which case $X$ and $Y$ become known to the adversary (but are not known
before the devices are prepared). In this case, rather than being interested
in randomness expansion, the task is to turn public randomness into private
randomness in a device-independent way. One can also use $H(AB|XYE)$ and
$H(A|XYE)$ in protocols when the input randomness is recycled. In this case we
are really interested in $H(ABXY|E)$, but, because $X$ and $Y$ are chosen
independently of $E$, this can be expanded as $H(XY)+H(AB|XYE)$. Hence
$H(AB|XYE)$ is the relevant quantity in this case as well. The one-sided
quantity $H(A|XYE)$ could also be used for DIQKD without spot-checking.

In addition we consider the quantities $H(AB|E)$ and $H(A|E)$. The second of
these could be useful for QKD protocols in which the key generation rounds do
not have a fixed input and where Alice and Bob do not publicly reveal their
measurement choices during the protocol. For instance, the sharing of these
choices could be encrypted using an initial key, analogously to a suggested
defence against memory attacks Barrett  _et al._ (2013)333Note that such
protocols would only be useful if more key is generated than is required, so
the protocol we are thinking of here is really quantum key expansion.
Furthermore, the results presented in Figure 1 show that the use of $H(A|E)$
only gives a minor advantage over $H(A|XYE)$.. $H(AB|E)$ would be a useful
quantity for randomness generation in a protocol without spot-checking and in
which $X$ and $Y$ are kept private after running the protocol and not used in
the overall output. When such protocols are based on the CHSH inequality, they
cannot allow expansion. These quantities can also be thought of as quantifying
the fundamental amount of randomness obtainable from a given Bell violation.
Although we have computed the graphs for $H(AB|E)$ and $H(A|E)$, existing
versions of the EAT cannot be directly applied to them — see Appendix E.

##  III Rates for CHSH-based protocols

We calculate various one sided and two sided rates for protocols based on the
CHSH game, which involves trying to violate the CHSH Bell inequality Clauser
_et al._ (1969). In this game, each party makes a binary input and receives a
binary output and the game is won if $A\oplus B=XY$. We define the CHSH score
by

$\frac{1}{4}\left(\sum_{a}p_{AB|00}(a,a)+\sum_{a}p_{AB|01}(a,a)+\sum_{a}p_{AB|10}(a,a)+\sum_{a}p_{AB|11}(a,a\oplus
1)\right)\,,$

which is the probability of winning the CHSH game when the inputs are chosen
at random444Note that even if nonuniform distributions of inputs are used when
running protocols, in this work the CHSH score is always defined as here..
Classical strategies can win this game with probability at most $3/4$, while
quantum strategies can get as high as
$\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)\approx 0.85$. For a fixed CHSH
game score, $\omega$, we wish to compute the minimum von Neumann entropy over
all strategies achieving that score. In this context a strategy comprises
three Hilbert spaces $\mathcal{H}_{A^{\prime}}$, $\mathcal{H}_{B^{\prime}}$
and $\mathcal{H}_{E}$, POVMs $\\{M_{a|x}\\}_{a}$ on $\mathcal{H}_{A^{\prime}}$
for both $x=0$ and $x=1$, POVMs $\\{N_{b|y}\\}_{b}$ on
$\mathcal{H}_{B^{\prime}}$ for both $y=0$ and $y=1$, and a state
$\rho_{A^{\prime}B^{\prime}E}$ on
$\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}$.
Given a strategy, and a distribution $p_{XY}$ there is an associated channel
$\mathcal{N}$ that acts on $A^{\prime}B^{\prime}$ and takes the state to the
post-measurement state, i.e.,

$\tau_{ABXYE}=(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})=\sum_{abxy}p_{XY}(x,y)|a\rangle\\!\langle
a|_{A}\otimes|b\rangle\\!\langle b|_{B}\otimes|x\rangle\\!\langle
x|_{X}\otimes|y\rangle\\!\langle
y|_{Y}\otimes\mathrm{tr}_{A^{\prime}B^{\prime}}\left((M_{a|x}\otimes
N_{b|y}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}\right)\,,$

where $\mathcal{I}_{E}$ is the identity channel on $E$. The entropic
quantities we consider all pertain to this state555In the cases where we
condition on $X=0$ and $Y=0$, we can project this state onto
$|0\rangle\\!\langle 0|_{X}\otimes|0\rangle\\!\langle 0|_{Y}$ and renormalize
– see Appendix C for more detail.. Note also that the score is a function of
$\tau$, which we denote $S(\tau)$ – in particular,
$p_{AB|xy}(a,b)=\mathrm{tr}\left((M_{a|x}\otimes
N_{b|y}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}\right)$.

For each of the six entropic quantities previously discussed we consider the
infimum over all strategies that achieve a given score. We use this to define
a set of curves. We write $F_{AB|XYE}(\omega,p_{XY})=\inf H(AB|XYE)_{\tau}$,
where the infimum is over all strategies for which $S(\tau)=\omega$. In the
same way we define $F_{AB|E}(\omega,p_{XY})$, $F_{A|XYE}(\omega,p_{XY})$ and
$F_{A|E}(\omega,p_{XY})$, replacing the objective function by the
corresponding entropy. We also define $F_{AB|00E}(\omega)$ and
$F_{A|00E}(\omega)$ analogously, noting that these are independent of
$p_{XY}$. Furthermore, if we write $F_{AB|XYE}(\omega)$ etc. (i.e., leaving
out the $p_{XY}$), we refer to the case where $p_{XY}$ is uniform over $X$ and
$Y$. For a more precise writing of these optimizations, see (11).

We also consider a related set of functions $G_{AB|XYE}(\omega,p_{XY})$,
$G_{AB|E}(\omega,p_{XY})$ etc. that are defined analogously, but while
optimizing over a smaller set of allowed strategies. More precisely, the $G$
functions are defined by restricting $\mathcal{H}_{A^{\prime}}$ and
$\mathcal{H}_{B^{\prime}}$ to be two dimensional and $\mathcal{H}_{E}$ to have
dimension 4, taking $\rho_{A^{\prime}B^{\prime}E}$ to be pure with
$\rho_{A^{\prime}B^{\prime}}$ diagonal in the Bell basis, and taking the POVMs
to be projective measurements onto states of the form
$\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle$ (see (16)).

It turns out that $F_{AB|00E}(\omega)=G_{AB|00E}(\omega)$,
$F_{A|00E}(\omega)=G_{A|00E}(\omega)$, and that in each of the other four
cases $F$ is formed from $G$ by taking the convex lower bound. The underlying
reason for this is that Jordan’s lemma Jordan (1875) implies that in the case
of Bell inequalities with two inputs and two outputs, any strategy is
equivalent to a convex combination of strategies in which $A^{\prime}$ and
$B^{\prime}$ are qubit systems. This means that if we solve the qubit case,
the general case follows by taking the convex lower bound666The convex lower
bound is not needed in the cases where we condition on $X=0$ and $Y=0$ because
$G$ is already convex in these cases.. Such an argument was made in Pironio
_et al._ (2009) and we give the details in Appendix B.

##  IV Numerical analysis for rates

The optimizations that generate the $G$ functions can be expressed in terms of
$7$ real parameters ($3$ to specify the state and $4$ to choose the
measurements). They are hence amenable to numerical optimizations. We note
also that except in the cases $G_{AB|E}(\omega,p_{XY})$ and
$G_{A|E}(\omega,p_{XY})$ we can remove an additional parameter. We discuss
simple ways to write the entropic expressions in Appendix C.

Our program for computing $G$ runs in $N$ iterations. In each iteration the
program starts by making a random guess for the parameters from within the
valid range. It then uses sequential quadratic programming to minimize
$\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$
subject to the CHSH score being fixed. On each iteration, the program arrives
at a candidate for the minimum value, and we run $N\approx 10^{4}$ iterations
to arrive at the conjectured minimum value for
$\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$.
The numerical optimization is performed in Python using the SLSQP solver in
SciPy. Since these optimizations are not guaranteed to converge, strictly
speaking the generated curves are upper bounds on the infima. For the purposes
of applying the EAT, we assume they are tight.

$G_{AB|00E}$ and $G_{A|00E}$ are convex functions, and hence $F=G$ for these.
For the other cases we generate the graphs in the case where $p_{XY}$ is
uniform, observing that each of the $G$ curves starts with a concave part and
switches to convex for larger CHSH scores. Since the minimum entropy is always
zero for classical scores, each of the $G$ curves approach $0$ as $\omega$
approaches $3/4$. Each of the $F$ curves can be found from $G$ by finding the
tangent to $G$ that passes through $(3/4,0)$. We call the score at which this
tangent is taken $\omega^{*}$, defined by
$(\omega^{*}-3/4)G^{\prime}(\omega^{*})=G(\omega^{*})$. We then have

$F(\omega)=\begin{cases}G^{\prime}(\omega^{*})(\omega-\frac{3}{4})&\text{if}\
\omega\leq\omega^{*}\\\ G(\omega)&\text{otherwise}\\\ \end{cases}\,.$ (1)

We give estimates for $\omega^{*}$ for each of the cases below. In essence,
what this means is that for $\omega<\omega^{*}$ the optimal strategy for Eve
is to either use a deterministic classical strategy with score $3/4$ or a
strategy that achieves score $\omega^{*}$, mixing these such that the average
score is $\omega$. Eve can remember which strategy she used, and hence the
entropy from her perspective is also the convex mixture of the entropies of
the endpoints.

Figure 1 shows the curves we obtained for the functions $F$ in each of the six
cases. Note that, except in the cases where we condition on $X=0$ and $Y=0$,
the graphs all have linear sections as a result of taking the convex lower
bound. In Appendix A we show the graphs for $G$ together with those for $F$.
The approximate coordinate of the top of the linear segment for $F_{AB|E}$ is
$(0.8523,1.8735)$ and for $F_{A|E}$ it is $(0.8505,0.967)$. Note also that
$1+H_{\mathrm{bin}}\left(\frac{1}{2}+\frac{1}{\sqrt{32}}\right)\approx 1.908$
is the maximum value on the graph $F_{AB|E}(\omega)$.

m(a) (b)

Figure 1: Graphs of the rates for (a) the one-sided and (b) the two-sided
randomness with uniformly chosen inputs. Each of these curves has a non-linear
part and the blue curves do not have a linear part.

By examining the parameters that come out of the numerical optimizations we
have the following.

######  Lemma 1.

Consider the curve
$g_{1}(\omega)=1+H_{\mathrm{bin}}(\omega)-2H_{\mathrm{bin}}(\frac{1}{2}+\frac{2\omega-1}{\sqrt{2}})$.
$F_{AB|XYE}(\omega)$ is upper bounded by

$F_{AB|XYE}(\omega)\leq\begin{cases}g_{1}(\omega)&\omega_{AB|XYE}^{*}\leq\omega\leq\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)\\\
g_{1}^{\prime}(\omega_{AB|XYE}^{*})(\omega-3/4)&3/4\leq\omega\leq\omega_{AB|XYE}^{*}\end{cases}\,.$
(2)

where $\omega_{AB|XYE}^{*}\approx 0.84403$ is the solution to
$g^{\prime}_{1}(\omega)(\omega-3/4)=g_{1}(\omega)$. Note that
$g_{1}(\omega^{*})\approx 1.4186$ and the maximum value reached is
$1+H_{\mathrm{bin}}(1/2+1/(2\sqrt{2}))\approx 1.601$.

###### Proof.

In Appendix C we give a parameterization of a two-qubit state (with parameters
$R$, $\theta$ and $\delta$) and measurements (with parameters $\alpha_{0}$,
$\alpha_{1}$, $\beta_{0}$ and $\beta_{1}$) before computing an expression for
$H(AB|XYE)$ in terms of these (cf. (31)). We also obtained an expression for
the CHSH score (cf. (30)). Choosing $R=\sqrt{2}(2\omega-1)$, $\theta=0$,
$\delta=0$, $\alpha_{0}=0$, $\alpha_{1}=\pi/2$, $\beta_{0}=\pi/8$,
$\beta_{1}=-\pi/8$ we find a score $\omega$, and calculating $H(AB|XYE)$ we
obtain $H(AB|XYE)=g_{1}(\omega)$ and hence $G_{AB|XYE}(\omega)\leq
g_{1}(\omega)$. Since, $G_{AB|XYE}(3/4)=0$, and $F_{AB|XYE}$ is formed from
$G_{AB|XYE}$ by taking the convex lower bound, we establish the claim. ∎

######  Lemma 2.

Consider the curve
$g_{2}(\omega)=1-H_{\mathrm{bin}}\left(\frac{1}{2}+\frac{2\omega-1}{\sqrt{2}}\right)$.
$F_{A|XYE}(\omega)$ is upper bounded by the convex lower bound of
$g_{2}(\omega)$. In other words,

$F_{A|XYE}(\omega)\leq\begin{cases}g_{2}(\omega)&\omega_{A|XYE}^{*}\leq\omega\leq\frac{1}{2}\left(1+\frac{1}{\sqrt{2}}\right)\\\
g_{2}^{\prime}(\omega_{A|XYE}^{*})(\omega-3/4)&3/4\leq\omega\leq\omega_{A|XYE}^{*}\end{cases}\,.$
(3)

where $\omega_{A|XYE}^{*}\approx 0.84698$ is the solution to
$g^{\prime}_{2}(\omega)(\omega-3/4)=g_{2}(\omega)$. Note that
$g_{2}(\omega^{*})\approx 0.92394$.

###### Proof.

The proof is the same as for Lemma 1, except that $g_{1}$ is replaced by
$g_{2}$ — the choice of state and measurements remains the same. ∎

######  Conjecture 1.

The upper bounds in Lemmas 1 and 2 are tight.

##  V Protocols for randomness expansion

In this section we discuss CHSH-based protocols for DIRE of both the spot-
checking and non spot-checking types. We pick specific protocols for
concreteness, but there are many possible variations. For instance, the
protocols we discuss condense the observed statistics to a single score, but
this is not necessary, and in some cases and for some sets of experimental
conditions it can be advantageous to use multiple scores Brown  _et al._
(2020); Tan  _et al._ (2019).

Before getting to the protocols, we first describe the setup, assumptions and
security definition. Although DIRE requires no assumptions on how the devices
used operate, the setup for DIRE involves a user who performs the protocol
within a secure laboratory, from which information cannot leak. Individual
devices can also be isolated within their own sub-laboratory and the user can
ensure that these devices only learn the information necessary for the
protocol (in particular, they cannot learn any inputs given to other devices).
The user has access to a trusted classical computer and an initial source (or
sources) of trusted randomness.

The quantum devices used for the protocol are only limited by the laws of
quantum theory and may share arbitrary entanglement with each other and with
an adversary. However, they cannot communicate with each other, or to the
adversary after the protocol starts. Furthermore, we assume they are kept
isolated after the protocol (cf. the discussion in Appendix F).

For security of the protocols, we use a composable security definition.
Consider a protocol with output $Z$ and use $\Omega$ to denote the event that
it does not abort. The protocol is $(\epsilon_{S},\epsilon_{C})$-secure if

  1. 1.

$\frac{1}{2}p_{\Omega}||\rho_{ZE|\Omega}-\frac{1}{d_{Z}}\openone_{Z}\otimes\rho_{E|\Omega}||_{1}\leq\epsilon_{S}$,
where $E$ represents all the systems held by an adversary and $d_{Z}$ is the
dimension of system $Z$; and

  2. 2.

There exists a quantum strategy such that $p_{\Omega}\geq 1-\epsilon_{C}$.

Here $\epsilon_{S}$ is called the soundness error, and $\epsilon_{C}$ is the
completeness error.

###  V.1 CHSH-based spot-checking protocol for randomness expansion

We now describe a spot-checking protocol for randomness expansion. It uses a
central biased random number generator $R_{T}$ and two other random number
generators, $R_{A}$ and $R_{B}$ that are near each of the devices used to run
the protocol.

######  Protocol 1.

(Spot-checking protocol) a

Parameters:
$n$ – number of rounds
$\gamma$ – test probability
$\omega_{\exp}$ – expected CHSH score
$\delta$ – confidence width for the score

  1. 1.

Set $i=1$ for the first round, or increase $i$ by 1.

  2. 2.

Use $R_{T}$ to choose $T_{i}\in\\{0,1\\}$ where $T_{i}=1$ occurs with
probability $\gamma$.

  3. 3.

If $T_{i}=1$ (test round), $R_{A}$ is used to choose $X_{i}$ uniformly, which
is input to one device giving output $A_{i}$. Likewise $R_{B}$ is used to
choose $Y_{i}$ uniformly, which is input to the other device giving output
$B_{i}$. Set $U_{i}=1$ if $A_{i}\oplus B_{i}=X_{i}Y_{i}$ and $U_{i}=0$
otherwise.

  4. 4.

If $T_{i}=0$ (generation round), the devices are given inputs $X_{i}=Y_{i}=0$,
and return the outputs $A_{i}$ and $B_{i}$. Set $U_{i}=\bot$.

  5. 5.

Return to Step 1 unless $i=n$.

  6. 6.

Calculate the number of rounds in which $U_{i}=0$ occurred, and abort the
protocol if this is larger than $n\gamma(1-\omega_{\exp}+\delta)$.

  7. 7.

Process the concatenation of all the outputs with a quantum-proof strong
extractor $\mathrm{Ext}$ to yield $\mathrm{Ext}({\bf AB},{\bf R})$, where
${\bf R}$ is a random seed for the extractor. Since a strong extractor is
used, the final outcome can be taken to be the concatenation of ${\bf R}$ and
$\mathrm{Ext}({\bf AB},{\bf R})$.

There are a few important points to take into account when running the
protocol. Firstly, it is crucial that each device only learns its own input
and not the value of the other input, or of $T_{i}$. If this is not satisfied
it is easy for devices to pass the protocol without generating randomness.
Secondly, for implementations in which devices can fail to record outcomes
when they should, it is important to close the detection loophole, which can
be done by assigning an outcome, say $0$, when a device fails to make a
detection.

In order to run the protocol, some initial randomness is needed to choose
which rounds are test rounds, to choose the inputs in the test rounds and to
seed the extractor. Since the extractor randomness forms part of the final
output, it is not consumed in the protocol, so for considering the rate at
which the protocol consumes randomness we can work out the amount of uniform
randomness needed to supply the inputs. Using the rounded interval algorithm
Hao and Hoshi (1997) to make the biased random number generator,
$n(H_{\mathrm{bin}}(\gamma)+2\gamma)+3$ is the expected amount of input
randomness required. To achieve expansion the number of output bits must be
greater than this. We use the entropy accumulation theorem (EAT) to lower
bound the amount of output randomness. Asymptotically the relevant quantity is
$H(AB|X=0,Y=0,E)$. The quantity $H(A|X=0,Y=0,E)$ acts as a lower bound for
this, and can be used in its place if convenient, for instance in analyses
that are more straightforward with an analytic curve.

###  V.2 CHSH-based protocols without spot-checking

In this section we discuss two such protocols. Protocol 2 uses two biased
local random number generators to choose the inputs on each round. Protocol 3
eliminates the bias, but also recycles the input randomness. Recycling the
input randomness is necessary when unbiased random number generators are used,
since otherwise more randomness is required to run the protocol than is
generated. Protocol 3 gives the highest randomness generation rate of all the
protocols we discuss.

######  Protocol 2.

(Protocol with biased local random number generators)

a

Parameters:
$n$ – number of rounds
$\zeta^{A}$ – probability of 1 for random number generator $R_{A}$ (taken to
be below $1/2$)
$\zeta^{B}$ – probability of 1 for random number generator $R_{B}$ (taken to
be below $1/2$)
$\omega_{\text{exp}}$ – expected CHSH score.
$\delta$ – confidence widths for each score.

  1. 1.

Set $i=1$ for the first round, or increase $i$ by 1.

  2. 2.

Use $R_{A}$ to choose $X_{i}\in\\{0,1\\}$, which is input to one of the
devices giving output $A_{i}\in\\{0,1\\}$. Likewise use $R_{B}$ to generate
$Y_{i}\in\\{0,1\\}$, which is input to the other device giving output
$B_{i}\in\\{0,1\\}$. Here $X_{i}=1$ occurs with probability $\zeta^{A}$ and
$Y_{i}=1$ occurs with probability $\zeta^{B}$. Set $U_{i}=(X_{i},Y_{i},1)$ if
$A_{i}\oplus B_{i}=X_{i}Y_{i}$ and $U_{i}=(X_{i},Y_{i},0)$ otherwise.

  3. 3.

Return to Step 1 unless $i=n$.

  4. 4.

Compute the value

$\displaystyle\omega=\frac{1}{4}\sum_{x,y}\frac{|\\{i:U_{i}=(x,y,1)\\}|}{np_{X}(x)p_{Y}(y)}$
(4)

and abort the protocol if $\omega<\omega_{\exp}-\delta$. Here
$p_{X}(1)=\zeta^{A}$, $p_{X}(0)=1-\zeta^{A}$, $p_{Y}(1)=\zeta^{B}$ and
$p_{Y}(0)=1-\zeta^{B}$.

  5. 5.

Process the concatenation of all the outputs with a quantum-proof strong
extractor $\mathrm{Ext}$ to yield $\mathrm{Ext}({\bf AB},{\bf R})$, where
${\bf R}$ is a random seed for the extractor. Since a strong extractor is
used, the final outcome can be taken to be the concatenation of ${\bf R}$ and
$\mathrm{Ext}({\bf AB},{\bf R})$.

Note that the quantity $|\\{i:U_{i}=(x,y,1)\\}|/(np_{X}(x)p_{Y}(y))$ in (4) is
an estimate of the probability of winning the CHSH game for inputs $X=x$ and
$Y=y$, and hence the $\omega$ computed in Step 4 is an estimate of the CHSH
value that would be observed if the same setup was used but with $X$ and $Y$
chosen uniformly.

The input randomness required per round in this protocol is roughly
$H_{\mathrm{bin}}(\zeta^{A})+H_{\mathrm{bin}}(\zeta^{B})$. To quantify the
amount of output randomness (before randomness extraction is performed), in
the asymptotic limit similar to the spot checking protocol, the relevant
operational quantity is the von Neumann entropy $H(AB|XYE)$. Expansion hence
cannot be achieved if
$H(AB|XYE)-H_{\mathrm{bin}}(\zeta^{A})-H_{\mathrm{bin}}(\zeta^{B})<0$, which
places constraints on the pairs of possible $(\zeta^{A},\zeta^{B})$. For
$\zeta^{A}$ and $\zeta^{B}$ smaller than $1/2$, the quantity
$H(AB|XYE)-H_{\mathrm{bin}}(\zeta^{A})-H_{\mathrm{bin}}(\zeta^{B})$ increases
as $\zeta^{A}$ and $\zeta^{B}$ decrease, and hence we want to take these to be
small. They only need to be large enough to ensure that $X=1,Y=1$ occurs often
enough to give a good estimate of the empirical score.

Since

$\displaystyle H(AB|XYE)$ $\displaystyle=$
$\displaystyle\sum_{xy}p_{XY}(x,y)H(AB|XYE)$ (5) $\displaystyle\geq$
$\displaystyle\min_{x,y}H(AB|X=x,Y=y,E)$

we can use the bounds formed for $H(AB|X=0,Y=0,E)$ instead777There is nothing
special about the choice $X=0$ and $Y=0$ when computing the bounds for
$H(AB|X=0,Y=0,E)$., albeit with a loss of entropy (this loss of entropy is
small if $\zeta_{A}$ and $\zeta_{B}$ are small).

One reason for using Protocol 2 rather than Protocol 1 is that the former
enables the locality loophole to be closed while expanding randomness. In
order to perform the Bell tests as part of a device-independent protocol we
need to make inputs to two devices in such a way that neither device knows the
input of the other. One way to ensure this is by using independent random
number generators on each side of the experiment, and ensuring the the outcome
of each device is given at space-like separation from the production of the
random input to the other. Although space-like separation can provide a
guarantee (within the laws of physics) that each device does not know the
input of the other888Provided we have a reasonable way to give a time before
which the output of $R_{A}$ and $R_{B}$ did not exist., in a cryptographic
setting it is necessary to assume a secure laboratory to prevents any unwanted
information leaking from inside the lab to an eavesdropper. The same mechanism
by which the lab is shielded from the outside world can be used to shield
devices in the lab from one another and hence can prevent communication
between the two devices during the protocol. However, although unnecessary for
cryptographic purposes, it is interesting to consider closing the locality
loophole while expanding randomness.

This is not possible in a typical spot-checking protocol, where a central
random number generator is used to decide whether a round is a test round or
not. Considering Protocol 1, the locality loophole can be readily closed
during the test rounds, but the use of the central random number generator
means that, if one is worried that hidden communication channels are being
exploited, there is a loophole that the devices could behave differently on
test rounds and generation rounds. For instance, measurement devices that know
whether a round is a test or generation round could supply pre-programmed
outputs in generation rounds, while behaving honestly in test rounds. Thus,
spot-checking protocols do not enable fully closing the locality loophole
while expanding randomness.

When using Protocol 2 with $\zeta^{A}=\zeta^{B}-\zeta$, the main difference to
Protocol 1 is that the distribution of $X$ and $Y$ is
$((1-\zeta)^{2},\zeta(1-\zeta),\zeta(1-\zeta),\zeta^{2})$ rather than
$(1-3\gamma/4,\gamma/4,\gamma/4,\gamma/4)$. In the analysis this manifests
itself in the statistics, and the much lower probability of $X=1,Y=1$ requires
an adjustment of $\delta$ to achieve the same error parameters for the
protocol. A comparison between the output rates for Protocols 1 and 2 is shown
in Figures 2 and 3.

######  Protocol 3.

(Protocol with recycled input randomness) a

Parameters:
$n$ – number of rounds
$\omega_{\exp}$ – expected CHSH score.
$\delta$ – confidence width.

  1. 1.

Set $i=1$ for the first round, or increase $i$ by 1.

  2. 2.

Use $R_{A}$ to choose $X_{i}\in\\{0,1\\}$ uniformly, serving as the input to
one of the devices giving output $A_{i}\in\\{0,1\\}$. Likewise use $R_{B}$ to
generate $Y_{i}\in\\{0,1\\}$ uniformly, which is input to the other device
giving output $B_{i}\in\\{0,1\\}$. Set $U_{i}=1$ if $A_{i}\oplus
B_{i}=X_{i}Y_{i}$ and $U_{i}=0$ otherwise.

  3. 3.

Return to Step 1 unless $i=n$.

  4. 4.

Count the number of rounds for which $U_{i}=0$ occurred and abort the protocol
if this is above $n(1-\omega_{\exp}+\delta)$.

  5. 5.

Process the concatenation of all the inputs and outputs with a quantum-proof
strong extractor $\mathrm{Ext}$ to yield $\mathrm{Ext}({\bf ABXY},{\bf R})$,
where ${\bf R}$ is a random seed for the extractor. Since a strong extractor
is used, the final outcome can be taken to be the concatenation of ${\bf R}$
and $\mathrm{Ext}({\bf ABXY},{\bf R})$.

An important difference in this protocol compared to Protocols 1 and 2 and is
in the extraction step, which now extracts randomness from the input strings
${\bf X}$ and ${\bf Y}$ as well as the outputs. Without recycling the inputs
expansion would not be possible in Protocol 3. With the modification the
relevant quantity to decide the length of the output is $H(ABXY|E)$, and so
$H(AB|XYE)=H(ABXY|E)-H(XY)=H(ABXY|E)-2$ is the relevant quantity for
calculating the rate of expansion. Note that in order to reuse the input in a
composable way, it also needs to be run through an extractor Colbeck and Kent
(2011) (for a discussion of why it is important to do so and a few more
composability-related issues, see Appendix F).

We could also consider an adaptation of Protocol 1 in which the input
randomness is recycled, forming Protocol 1′ from Protocol 1 by replacing Step
7 by

  1. 7′.

Process the concatenation of all the inputs and outputs with a quantum-proof
strong extractor $\mathrm{Ext}$ to yield $\mathrm{Ext}({\bf ABXY},{\bf R})$,
where ${\bf R}$ is a random seed for the extractor. Since a strong extractor
is used, the final outcome can be taken to be the concatenation of ${\bf R}$
and $\mathrm{Ext}({\bf ABXY},{\bf R})$.

In this case, as the number of rounds, $n$, increases the advantage gained by
this modification decreases, becoming negligible asymptotically. This is
because as $n$ increases, the value of $\gamma$ required to give the same
overall security tends to zero, and hence the amount of input randomness
required becomes negligible. Note that recycling the input randomness in
Protocol 2 in the case where $\zeta^{A}=\zeta^{B}=1/2$ is equivalent to
Protocol 3.

Like Protocol 2, Protocol 3 also allows the locality loophole to be closed if
on each round $i$, the random choice $X_{i}$ is space-like separated from the
output $B_{i}$ and the random choice $Y_{i}$ is space-like separated from the
output $A_{i}$.

m(a) (b) (c)

Figure 2: Graphs of the net amount of certifiable randomness according to the
EAT for (a) the spot checking protocol (Protocol 1), (b) Protocol 2, and (c)
the protocol with recycled input randomness (Protocol 3), showing the
variation with the number of rounds for three different scores, $\omega$. The
error parameters used were $\epsilon_{S}=3.09\times 10^{-12}$ and
$\epsilon_{C}=10^{-6}$. For each point on the curve (a) an optimization over
$\gamma$ was performed to maximize the randomness; similarly, the values of
$\zeta^{A}=\zeta^{B}$ were optimized over to generate the curves in (b).

m(a) (b) (c)

Figure 3: Graphs of the net amount of certifiable randomness according to the
EAT for (a) the spot checking protocol (Protocol 1), (b) Protocol 2, and (c)
the protocol with recycled input randomness (Protocol 3), showing the
variation with the CHSH score $\omega$. The round numbers, $n$, are indicated
in the legend. The error parameters used were $\epsilon_{S}=3.09\times
10^{-12}$ and $\epsilon_{C}=10^{-6}$. As in Figure 2, the values of $\gamma$
and $\zeta^{A}=\zeta^{B}$ were optimized over for each point.

In each of the protocols, the parameter $\delta$ should be chosen depending on
the desired completeness error. For the spot-checking protocol, the relation
between the two is discussed in (Liu  _et al._ , 2021, Supplementary
Information I D). The analysis there can be applied to the protocol with
recycled input randomness by setting $\gamma=1$ and the protocol with biased
local random number generators is discussed in Appendix E.3.2. The chosen
soundness error affects the length of the extractor output, and, if chosen too
small the output length becomes zero (see Appendix E for further discussion).

Figures 2 and 3 show how the amount of certifiable randomness varies with the
score, $\omega$, and round number, $n$. Note that in the cases where the rate
curves are linear, they are linear for most of their ranges. Extending the
linear part to the full range of quantum scores makes it easier to use the EAT
while only resulting in a small drop in rate for scores close to the maximum
quantum value. Note that, as mentioned above, strictly the numerical curves we
gave for the von Neumann entropy are upper bounds; the curves in Figures 2 and
3 are generated under the assumption that these upper bounds are tight.

To demonstrate the increased practicality of the two-sided curves, we use the
parameters from a recent experiment Liu  _et al._ (2021) with Protocol 1.
There a score of just over $0.752$ was obtained, for which it would require
about $9\times 10^{10}$ rounds to achieve expansion using Protocol 1 with
$\gamma=3.383\times 10^{-4}$, $\epsilon_{S}=3.09\times 10^{-12}$,
$\epsilon_{C}=10^{-6}$ and taking the one-sided randomness Liu  _et al._
(2021). Using Protocol 3 instead, and taking the two-sided randomness for the
same score and error parameters allows expansion for $n\gtrsim 8\times
10^{7}$, significantly increasing the practicality. For instance, the main
experiment of Liu  _et al._ (2021) was based on a spot-checking protocol and
took $19.2$ hours; the use of Protocol 3 instead would allow the same amount
of expansion in about $60$ seconds (this time holds under the assumption that
the same repetition rate of the experiment can be met in the non-spot checking
protocol999In some experiments, the rate at which we can switch between the
two measurements is relatively slow, and hence when using Protocol 3, where
switching is required on most rounds, the switching rate dominates, slightly
increasing the time.). Protocol 2, however, produces lower randomness rates
compared to the spot-checking protocol. This is partly because more input
randomness is required ($2H_{\text{bin}}(\sqrt{\gamma})\gg
H_{\text{bin}}(\gamma)+2\gamma$ for small $\gamma$), and also because the
completeness error has a worse behaviour. Protocol 2 is hence useful when
inputs are not recycled and when closing the locality loophole is desirable.

When discussing randomness expansion we have considered the figure of merit to
be the amount of expansion per entangled pair shared. An alternative figure of
merit is the ratio of the final randomness to the initial randomness, i.e.,
here we are considering how much randomness we can get from a given amount of
initial randomness. For the latter figure of merit, Protocol 3 is no longer
optimal, since the amount of expansion cannot exceed the amount of input
randomness. For the other two protocols the ratio of output randomness to
input randomness can be made much higher by taking either $\gamma$ or
$\zeta^{A}\zeta^{B}$ to be small.

##  VI Discussion

In this paper, we have given numerical and analytic bounds on various
conditional von Neumann entropies that are relevant for CHSH-based device-
independent protocols and discussed when each can be applied. We have applied
these results to explicit protocols, comparing the finite statics rates using
the EAT. We discussed variations of the usual spot-checking protocol, the
first removes the spot checking to allow expansion while closing the locality
loophole, and the second recycles the input randomness, so allowing expansion
when performing a CHSH test on every round.

It remains an open question to find an analytic form for $F_{AB|X=0,Y=0,E}$,
$F_{A|E}$ and $F_{AB|E}$. Since the curves $F_{A|E}$ and $F_{AB|E}$ are linear
for all but the very highest (experimentally least achievable) scores, in
these cases not much is lost by extending the line to all scores forming a
lower bound that tightly covers all of the experimentally relevant cases. On
the other hand $F_{AB|X=0,Y=0,E}$ is a convex curve throughout and hence a
tight analytic form would be particularly useful in this case. Our initial
analysis suggests that form of the parameters achieving the optima for these
is sufficiently complicated that any analytic expression would not be compact.
A reasonably tight analytic lower bound for $F_{AB|X=0,Y=0,E}$ could also be
useful for theoretical analysis. Note also that the bound $F_{A|E}\geq
F_{A|XYE}$ is fairly tight (see Figure 1(a)) so the analytic form for
$F_{A|XYE}$ can be used to bound $F_{A|E}$ with little loss. Another open
problem is to find a concrete scenario in which $F_{AB|E}$ is directly useful.

The use of Jordan’s lemma in this work prevents the techniques used being
extended to general protocols, and finding improved ways to bound the
conditional von Neumann entropy numerically in general cases remains of
interest, in particular to ease the experimental burden required to
demonstrate DIQKD in the lab.

Additional note: While completing this work a new paper appeared Tan  _et al._
(2020), which also found numerical curves for $H(A|XYE)$ and used them with
some new protocols to generate improved rates for DIQKD.

###### Acknowledgements.

We thank Erik Woodhead for useful comments. This work was supported by the
Quantum Communications Hub of the UK Engineering and Physical Sciences
Research Council (EPSRC) (grant nos. EP/M013472/1 and EP/T001011/1).

##  Appendix A Additional graphs

Figure 4(a) gives the graphs of $F_{AB|XYE}(\omega)$ and $G_{AB|XYE}(\omega)$,
while Figure 4(b) shows those for $F_{A|XYE}(\omega)$ and $G_{A|XYE}(\omega)$.
In each case the $G$ graphs have a concave and convex part and the $F$ graphs
are formed by taking the convex lower bound. For these cases the points at
which the tangents are taken are $\omega^{*}_{AB|XYE}\approx 0.8440$ and
$\omega^{*}_{A|XYE}\approx 0.8470$.

Figure 5(a) gives the graphs of $F_{AB|E}(\omega)$ and $G_{AB|E}(\omega)$,
while Figure 5(b) shows those for $F_{A|XYE}(\omega)$ and $G_{A|XYE}(\omega)$.
Again, in each case the $G$ graphs have a concave and convex part and the $F$
graphs are formed by taking the convex lower bound. For these cases the points
at which the tangents are taken are $\omega^{*}_{A|E}\approx 0.8505$ and
$\omega^{*}_{AB|E}\approx 0.8523$.

(a) (b)

Figure 4: (a) Two-sided and (b) one-sided entropy curves conditioned on $X$,
$Y$ and $E$ with uniform input distribution.

(a) (b)

Figure 5: (a) Two-sided and (b) one-sided entropy curves conditioned on $E$
with uniform input distribution.

##  Appendix B Simplifying the strategy

Given a Hilbert space $\mathcal{H}$, we use $\mathcal{P}(\mathcal{H})$ to be
the set of positive semi-definite operators on $\mathcal{H}$, and
$\mathcal{S}(\mathcal{H})$ to be the set of density operators, i.e., elements
of $\mathcal{P}$ with trace 1. The pure states on $\mathcal{H}$ (elements of
$\mathcal{S}(\mathcal{H})$ with rank 1) will be denoted
$\mathcal{S}_{P}(\mathcal{H})$. A POVM on $\mathcal{H}$ is a set of positive
operators $\\{E_{i}\\}_{i}$ with $E_{i}\in\mathcal{P}(\mathcal{H})$ for all
$i$ and $\sum_{i}E_{i}=\openone_{\mathcal{H}}$, where $\openone_{\mathcal{H}}$
is the identity operator on $\mathcal{H}$. A projective measurement on
$\mathcal{H}$ is a POVM on $\mathcal{H}$ where $E_{i}^{2}=E_{i}$ for all $i$.
We define the Bell states

$\displaystyle|\Phi_{0}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(|00\rangle+|11\rangle\right)$ (6)
$\displaystyle|\Phi_{1}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(|00\rangle-|11\rangle\right)$ (7)
$\displaystyle|\Phi_{2}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(|01\rangle+|10\rangle\right)$ (8)
$\displaystyle|\Phi_{3}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(|01\rangle-|10\rangle\right)\,,$ (9)

and use $\sigma_{1}=|1\rangle\\!\langle 0|+|0\rangle\\!\langle 1|$,
$\sigma_{2}=\mathrm{i}|1\rangle\\!\langle 0|-\mathrm{i}|0\rangle\\!\langle 1|$
and $\sigma_{3}=|0\rangle\\!\langle 0|-|1\rangle\\!\langle 1|$ as the three
Pauli operators.

In this section we make a series of simplifications of the form of the
optimization. The argument given broadly follows the logic of Pironio  _et
al._ (2009) (see also Woodhead  _et al._ (2021) for an alternative).

######  Definition 1.

A _single-round CHSH measurement strategy_ is a tuple
$(\mathcal{H}_{A^{\prime}},\mathcal{H}_{B^{\prime}},\\{M_{a|x}\\}_{x,a},\\{N_{b|y}\\}_{y,b})$,
where $\mathcal{H}_{A^{\prime}}$ and $\mathcal{H}_{B^{\prime}}$ are Hilbert
spaces, and $\\{M_{a|x}\\}_{a}$ is a POVM on $\mathcal{H}_{A^{\prime}}$ for
each $x\in\\{0,1\\}$ and likewise $\\{N_{b|y}\\}_{b}$ is a POVM on
$\mathcal{H}_{B^{\prime}}$ for each $y\in\\{0,1\\}$. In the case that all the
POVMs are projective we will call this a _single-round CHSH projective
measurement strategy_.

######  Definition 2.

A _single-round CHSH strategy_ is a single-round CHSH measurement strategy
together with a state
$\rho_{A^{\prime}B^{\prime}E}\in\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}$,
where $\mathcal{H}_{E}$ is an arbitrary Hilbert space.

Note that in a device-independent scenario, such a strategy can be chosen by
the adversary.

######  Definition 3.

Given a single-round CHSH measurement strategy and a distribution $p_{XY}$
over the settings $X$ and $Y$, the _associated CHSH channel_ is defined by

$\mathcal{N}:\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}})\to\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{X}\otimes\mathcal{H}_{Y}):\sigma\mapsto\sum_{abxy}p_{XY}(x,y)|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes|x\rangle\\!\langle
x|\otimes|y\rangle\\!\langle y|\mathrm{tr}\left((M_{a|x}\otimes
N_{b|y})\sigma\right)\,,$

where $\mathcal{H}_{A}$, $\mathcal{H}_{B}$, $\mathcal{H}_{X}$ and
$\mathcal{H}_{Y}$ are two dimensional Hilbert spaces. The union of the sets of
associated CHSH channels for all single-round CHSH measurement strategies for
some fixed input distribution $p_{XY}$ is denoted $\mathcal{C}(p_{XY})$. The
union of the sets of associated CHSH channels for all single-round CHSH
projective measurement strategies is denoted $\mathcal{C}_{\Pi}(p_{XY})$.

The output of the associated CHSH channel is classical, and
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{X}\otimes\mathcal{H}_{Y}$
stores the outcomes and the chosen measurements. We will usually apply this
channel to the $AB$ part of a tripartite system, giving

$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})=\sum_{abxy}p_{XY}(x,y)p_{AB|xy}(a,b)|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes|x\rangle\\!\langle
x|\otimes|y\rangle\\!\langle y|\otimes\tau^{a,b,x,y}_{E}\,,$ (10)

where $\tau^{a,b,x,y}_{E}\in\mathcal{S}(\mathcal{H}_{E})$ for each $a,b,x,y$
(it is the normalization of
$\mathrm{tr}_{A^{\prime}B^{\prime}}\left((M_{a|x}\otimes
N_{b|y}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}\right)$).

Note that the CHSH score, which we denote
$S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$ does
not depend on the distribution $p_{XY}$ of input settings.

We will be interested in optimization problems of the form

$\displaystyle F(\omega,p_{XY})=$
$\displaystyle\inf_{\mathcal{R}}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))\text{
where }$ (11)
$\displaystyle\mathcal{R}=\\{(\mathcal{N},\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}(p_{XY}),\,S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega\\}$

where $\mathcal{H}_{E}$ is an arbitrary Hilbert space and the spaces
$\mathcal{H}_{A^{\prime}}$ and $\mathcal{H}_{B^{\prime}}$ are those from the
chosen element of $\mathcal{C}(p_{XY})$, i.e., the set $\mathcal{R}(\omega)$
runs over all possible dimensions of these spaces, and $\omega$ is some fixed
real number. Here $\bar{H}$ can be any one of the following entropic
quantities defined on the state
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$:
$H(AB|X=0,Y=0,E)$, $H(AB|XYE)$, $H(AB|E)$, $H(A|X=0,Y=0,E)$, $H(A|XYE)$ or
$H(A|E)$. We consider the family of optimizations in this work and many of the
arguments that follow are independent of this choice.

###  B.1 Reduction to projective measurements

In this section, we conclude that there is no loss in generality in assuming
that the devices perform projective measurements. More precisely, we prove the
following lemma.

######  Lemma 3.

The sets

$\displaystyle\mathcal{T}_{1}$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}(p_{XY}),\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})\\}\text{
and}$ $\displaystyle\mathcal{T}_{2}$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{\Pi}(p_{XY}),\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})\\}$

are identical.

This is a corollary of Naimark’s theorem, which we state in the following way.

######  Theorem 1 (Naimark’s theorem).

Let $\\{E_{i}\\}_{i}$ be a POVM on $\mathcal{H}$. There exists a Hilbert space
$\mathcal{H}^{\prime}$ and a projective measurement $\\{\Pi_{i}\\}_{i}$ on
$\mathcal{H}\otimes\mathcal{H}^{\prime}$ such that for any
$\rho\in\mathcal{S}(\mathcal{H})$

$\sum_{i}|i\rangle\\!\langle i|\mathrm{tr}(\rho
E_{i})=\sum_{i}|i\rangle\\!\langle
i|\mathrm{tr}(\Pi_{i}(\rho\otimes|0\rangle\\!\langle 0|))\,.$

###### Proof.

We can directly construct this measurement as follows. Consider the isometry
$V:\mathcal{H}\to\mathcal{H}\otimes\mathcal{H}^{\prime}$ given by
$V=\sum_{i}\sqrt{E_{i}}\otimes|i\rangle$, and let $U$ be the extension of $V$
to a unitary with the property that
$U(|\psi\rangle\otimes|0\rangle)=\sum_{i}\sqrt{E_{i}}|\psi\rangle\otimes|i\rangle$
for any $|\psi\rangle\in\mathcal{H}$. This construction ensures that the
channels

$\displaystyle\mathcal{E}:\rho$ $\displaystyle\mapsto$
$\displaystyle\sum_{i}|i\rangle\\!\langle i|\mathrm{tr}(E_{i}\rho)\text{ and}$
$\displaystyle\mathcal{E}^{\prime}:\rho$ $\displaystyle\mapsto$
$\displaystyle\sum_{i}|i\rangle\\!\langle
i|\mathrm{tr}\left((\openone\otimes|i\rangle\\!\langle
i|)U(\rho\otimes|0\rangle\\!\langle 0|)U^{\dagger}\right)$

are identical. The second of these can be rewritten

$\rho\mapsto\sum_{i}|i\rangle\\!\langle
i|\mathrm{tr}\left(\Pi_{i}(\rho\otimes|0\rangle\\!\langle 0|)\right)\,,$

where we take $\Pi_{i}=U^{\dagger}(\openone\otimes|i\rangle\\!\langle i|)U$,
as required. ∎

###### Proof of Lemma 3.

By definition $\mathcal{T}_{2}\subseteq\mathcal{T}_{1}$. For the other
direction, consider a state $\rho_{A^{\prime}B^{\prime}E}$ and POVMs
$\\{M_{a|x}\\}_{a,x}$ and $\\{N_{b|y}\\}_{b,y}$ forming a single-round CHSH
strategy in $\mathcal{T}_{1}$. We use the construction in the proof of Theorem
1 to generate the projectors $\Pi^{A}_{a|x}$ and $\Pi^{B}_{b|y}$ as Naimark
extensions of the POVMs. Instead of creating the state
$\rho_{A^{\prime}B^{\prime}E}$, the state
$\rho_{A^{\prime}B^{\prime}E}\otimes|0\rangle\\!\langle
0|_{A^{\prime\prime}}\otimes|0\rangle\\!\langle 0|_{B^{\prime\prime}}$ is
created instead, where the projectors $\Pi^{A}_{a|x}$ act on
$A^{\prime}A^{\prime\prime}$ and $\Pi^{B}_{b|y}$ act on
$B^{\prime}B^{\prime\prime}$. Since the latter is a strategy in
$\mathcal{T}_{2}$ leading to the same post-measurement state (10), we have
$\mathcal{T}_{1}\subseteq\mathcal{T}_{2}$, which completes the proof. ∎

###  B.2 Reduction to convex combinations of qubit strategies

This is a consequence of Jordan’s lemma Jordan (1875) and is a special feature
that applies only because the Bell inequality has two inputs and two outputs
for each party.

######  Lemma 4 (Jordan’s lemma).

Let $A_{1}$ and $A_{2}$ be two Hermitian operators on $\mathcal{H}$ with
eigenvalues $\pm 1$, then we can decompose
$\mathcal{H}=\bigoplus_{\alpha}\mathcal{H}_{\alpha}$ such that $A_{1}$ and
$A_{2}$ preserve the subspaces $\mathcal{H}_{\alpha}$, and where each
$\mathcal{H}_{\alpha}$ has dimension at most 2.

######  Corollary 1.

Let $\Pi_{1}$ and $\Pi_{2}$ be two projections on $\mathcal{H}$. We can
decompose $\mathcal{H}=\bigoplus_{\alpha}\mathcal{H}_{\alpha}$ such that
$\Pi_{1}$, $\openone-\Pi_{1}$, $\Pi_{2}$ and $\openone-\Pi_{2}$ preserve the
subspaces $\mathcal{H}_{\alpha}$, and where each $\mathcal{H}_{\alpha}$ has
dimension at most 2.

###### Proof.

Apply Jordan’s lemma to the Hermitian operators $A_{1}=2\Pi_{1}-\openone$ and
$A_{2}=2\Pi_{2}-\openone$ with eigenvalues $\pm 1$, and consider
$|\psi\rangle\in\mathcal{H}_{\alpha}$ for some $\alpha$. By construction
$A_{1}|\psi\rangle\in\mathcal{H}_{\alpha}$ from which it follows that
$\Pi_{1}|\psi\rangle\in\mathcal{H}_{\alpha}$, and hence also
$(\openone-\Pi_{1})|\psi\rangle\in\mathcal{H}_{\alpha}$. Thus, $\Pi_{1}$ and
$\openone-\Pi_{1}$ preserve the subspace; likewise $\Pi_{2}$ and
$\openone-\Pi_{2}$. ∎

This implies the following

######  Lemma 5.

Let $\mathcal{C}_{2\times 2}(p_{XY})$ be the set of CHSH channels associated
with the single-round CHSH projective measurement strategies where each of the
four projectors $M_{a|x}$ is block diagonal with $2\times 2$ blocks, and each
of the four projectors $N_{b|y}$ is block diagonal with $2\times 2$ blocks.
The sets

$\displaystyle\mathcal{T}_{2}$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{\Pi}(p_{XY}),\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})\\}\text{
and}$ $\displaystyle\mathcal{T}_{3}$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{2\times
2}(p_{XY}),\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})\\}$

are identical.

###### Proof.

This follows by applying Corollary 1 to the projectors $M_{0|0}$ and $M_{0|1}$
to get the blocks on $\mathcal{H}_{A^{\prime}}$ and to the projectors
$N_{0|0}$ and $N_{0|1}$ to get the blocks on $\mathcal{H}_{B^{\prime}}$.
Although some of the blocks may be $1\times 1$, we can collect these together
and treat them as a $2\times 2$ block, or add an extra dimension to the space
(on which the state has no support) to achieve all $2\times 2$ blocks. ∎

We can also make the state only have support on the $2\times 2$ blocks.

######  Lemma 6.

The sets

$\displaystyle\mathcal{T}_{3}$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{2\times
2}(p_{XY}),\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})\\}\text{
and}$ $\displaystyle\mathcal{T}_{4}$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{2\times
2}(p_{XY}),\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}_{2\times
2}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})\\}$

are identical. Here $\mathcal{S}_{2\times
2}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$
is the subset of
$\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$
such that $\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}_{2\times
2}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$
implies

$\rho_{A^{\prime}B^{\prime}E}=\sum_{\alpha,\beta}(\Pi^{\alpha}_{A^{\prime}}\otimes\Pi^{\beta}_{B^{\prime}}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(\Pi^{\alpha}_{A^{\prime}}\otimes\Pi^{\beta}_{B^{\prime}}\otimes\openone_{E})\,,$

where $\\{\Pi^{\alpha}\\}_{\alpha}$ are projectors onto the $2\times 2$
diagonal blocks.

###### Proof.

Consider a state $\rho_{A^{\prime}B^{\prime}E}$ and sets of projectors
$\\{M_{a|x}\\}_{a,x}$ and $\\{N_{b|y}\\}_{b,y}$ from the set
$\mathcal{T}_{3}$. For brevity, write
$\Pi^{\alpha,\beta}=\Pi^{\alpha}_{A^{\prime}}\otimes\Pi^{\beta}_{B^{\prime}}$.
Then, since

$M_{a|x}\otimes
N_{b|y}=\sum_{\alpha,\beta}(\Pi^{\alpha}_{A^{\prime}}\otimes\Pi^{\beta}_{B^{\prime}})(M_{a|x}\otimes
N_{b|y})(\Pi^{\alpha}_{A^{\prime}}\otimes\Pi^{\beta}_{B^{\prime}})\,,$

we have

$\displaystyle\mathrm{tr}_{A^{\prime}B^{\prime}}((M_{a|x}\otimes
N_{b|y}\otimes\openone)\rho_{A^{\prime}B^{\prime}E})$ $\displaystyle=$
$\displaystyle\mathrm{tr}_{A^{\prime}B^{\prime}}\left(\sum_{\alpha,\beta}(\Pi^{\alpha,\beta}\otimes\openone_{E})(M_{a|x}\otimes
N_{b|y}\otimes\openone)(\Pi^{\alpha,\beta}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}\right)$
$\displaystyle=$
$\displaystyle\mathrm{tr}_{A^{\prime}B^{\prime}}\left(\sum_{\alpha,\beta}(M_{a|x}\otimes
N_{b|y}\otimes\openone)(\Pi^{\alpha,\beta}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(\Pi^{\alpha,\beta}\otimes\openone_{E})\right)$
$\displaystyle=$
$\displaystyle\mathrm{tr}_{A^{\prime}B^{\prime}}((M_{a|x}\otimes
N_{b|y}\otimes\openone)\rho^{\prime}_{A^{\prime}B^{\prime}E})\,,$

where
$\rho^{\prime}_{A^{\prime}B^{\prime}E}=\sum_{\alpha,\beta}(\Pi^{\alpha,\beta}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(\Pi^{\alpha,\beta}\otimes\openone_{E})$.
Thus, if we replace $\rho_{A^{\prime}B^{\prime}E}$ by
$\rho^{\prime}_{A^{\prime}B^{\prime}E}$ we obtain the same post-measurement
state (10). Hence $\mathcal{T}_{3}\subseteq\mathcal{T}_{4}$, and, since the
other inclusion is trivial, $\mathcal{T}_{3}=\mathcal{T}_{4}$. ∎

######  Lemma 7.

Let $\mathcal{N}\in\mathcal{C}_{2\times 2}(p_{XY})$ and
$\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}_{2\times
2}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$.
The state $(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$
can be formed as a convex combination of states
$(\mathcal{N}_{\lambda}\otimes\mathcal{I}_{E})(\rho^{\lambda}_{A^{\prime\prime}B^{\prime\prime}E})$,
where for each $\lambda$, the channel $\mathcal{N}_{\lambda}$ is that
associated with a single-round measurement strategy with two 2-dimensional
Hilbert spaces and distribution $p_{XY}$.

###### Proof.

Since $\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}_{2\times
2}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$
the $2\times 2$ block structure means we can write
$\rho_{A^{\prime}B^{\prime}E}=\sum_{\alpha,\beta}p_{\alpha,\beta}\rho^{\alpha,\beta}_{A^{\prime}B^{\prime}E}$,
where
$p_{\alpha,\beta}\rho^{\alpha,\beta}_{A^{\prime}B^{\prime}E}=(\Pi^{\alpha,\beta}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(\Pi^{\alpha,\beta}\otimes\openone_{E})$
and $\mathrm{tr}(\rho^{\alpha,\beta}_{A^{\prime}B^{\prime}E})=1$ for all
$\alpha$ and $\beta$. Likewise, taking
$M^{\alpha}_{a|x}=\Pi_{A^{\prime}}^{\alpha}M_{a|x}\Pi_{A^{\prime}}^{\alpha}$
and $N^{\beta}_{b|y}=\Pi^{\beta}_{B^{\prime}}N_{b|y}\Pi^{\beta}_{B^{\prime}}$
we can write $M_{a|x}=\sum_{\alpha}M^{\alpha}_{a|x}$ and
$N_{b|y}=\sum_{\beta}N^{\beta}_{b|y}$. In terms of these we have

$\displaystyle\mathrm{tr}_{A^{\prime}B^{\prime}}((M_{a|x}\otimes
N_{b|y}\otimes\openone)\rho_{A^{\prime}B^{\prime}E})$ $\displaystyle=$
$\displaystyle\sum_{\alpha,\beta}p_{\alpha,\beta}\mathrm{tr}_{A^{\prime}B^{\prime}}((M^{\alpha}_{a|x}\otimes
N^{\beta}_{b|y}\otimes\openone)\rho^{\alpha,\beta}_{A^{\prime}B^{\prime}E})$

We can then associate a value of $\lambda$ with each pair $(\alpha,\beta)$,
replace each $\rho^{\alpha,\beta}_{A^{\prime}B^{\prime}E}$ by a state on
$A^{\prime\prime}B^{\prime\prime}E$ in which $A^{\prime\prime}$ and
$B^{\prime\prime}$ are two-dimensional (the support of
$\rho^{\alpha,\beta}_{A^{\prime}B^{\prime}}$ has dimension at most 4), and
likewise replace the projectors by qubit projectors. In terms of these we have

$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})=\sum_{\lambda}p_{\lambda}(\mathcal{N}_{\lambda}\otimes\mathcal{I}_{E})(\rho^{\lambda}_{A^{\prime\prime}B^{\prime\prime}E})\,.\qed$

In other words, any post-measurement state (10) that can be generated in the
general case, can also be generated if Eve sends a convex combination of two
qubit states, and where the measurements used by the separated devices depend
on the state sent. Eve could realise such a strategy in practice by using pre-
shared randomness. We can proceed to consider strategies in which qubits are
shared between the two devices, and then consider the mixture of such
strategies after doing so.

###  B.3 Qubit strategies

In this section we consider the single-round CHSH measurement strategies in
which $\mathcal{H}_{A^{\prime}}$ and $\mathcal{H}_{B^{\prime}}$ are two-
dimensional and the measurements are rank-1 projectors. Given a distribution
$p_{XY}$ we use $\mathcal{C}_{\Pi_{1},2}(p_{XY})$ to denote the set of
associated CHSH channels. We restrict to rank-1 projectors because if one of
the projectors is identity it is not possible to achieve a non-classical CHSH
score, and the non-classical scores are the ones of interest.

######  Lemma 8.

Consider a single-round CHSH measurement strategy for which one of the POVM
elements is identity and let $\mathcal{N}$ be the associated CHSH channel. For
any state $\rho_{A^{\prime}B^{\prime}}$ on which $\mathcal{N}$ can act we have
$S(\mathcal{N}(\rho_{A^{\prime}B^{\prime}}))\leq 3/4$.

###### Proof.

Suppose the identity element corresponds to $M_{0|0}$ (the other cases follow
symmetrically). The conditional distribution $p_{AB|XY}$ then takes the form
$X=0$ $X=1$ $A=0$ $A=1$ $A=0$ $A=1$ $Y=0$ $B=0$ $\mu$ $0$ $\nu$ $\mu-\nu$
$B=1$ $1-\mu$ $0$ $\zeta$ $1-\mu-\zeta$ $Y=1$ $B=0$ $\gamma$ $0$ $\xi$
$\gamma-\xi$ $B=1$ $1-\gamma$ $0$ $\nu+\zeta-\xi$ $1+\xi-\gamma-\nu-\zeta$
where we have used the no-signalling conditions. The associated score is

$\displaystyle\frac{1}{4}\left(\mu+\nu+(1-\mu-\zeta)+\gamma+(\gamma-\xi)+(\nu+\zeta-\xi)\right)$
$\displaystyle=$ $\displaystyle\frac{1}{4}\left(1+2\nu+2\gamma-2\xi\right)$

Since every element of the distribution must be between $0$ and $1$ we have
$1+\xi-\gamma-\nu-\zeta\geq 0$, and hence $1+2\nu+2\gamma-2\xi\leq
3-2\zeta\leq 3$, from which the claim follows. ∎

We will then consider an optimization of the form (11), but restricting to
$\mathcal{C}_{\Pi_{1},2}$, i.e.

$\displaystyle h(\omega)$
$\displaystyle=\inf_{\mathcal{R}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))\text{
where }$ (12) $\displaystyle\mathcal{R}(\omega)$
$\displaystyle=\\{(\mathcal{N},\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{\Pi_{1},2}(p_{XY}),\,S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega\\}$

The next step is to show that without loss of generality we can reduce to
states that are invariant under application of $\sigma_{2}\otimes\sigma_{2}$
on $A^{\prime}B^{\prime}$.

######  Lemma 9.

Let $p_{XY}$ be a distribution,
$\mathcal{N}\in\mathcal{C}_{\Pi_{1},2}(p_{XY})$ and
$\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$
be such that
$S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega$.
There exists a state
$\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}\otimes\mathcal{H}_{E^{\prime}})$
such that
$S((\mathcal{N}\otimes\mathcal{I}_{EE^{\prime}})(\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}))=\omega$,
$\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}=(\sigma_{2}\otimes\sigma_{2}\otimes\openone_{EE^{\prime}})\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}(\sigma_{2}\otimes\sigma_{2}\otimes\openone_{EE^{\prime}})$
and
$\bar{H}((\mathcal{N}\otimes\mathcal{I}_{EE^{\prime}})(\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}))=\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$
for all six of the entropic functions given earlier.

Note that this implies that $p_{A|X}$ and $p_{B|Y}$ can be taken to be
uniform.

This is a consequence of the following lemmas.

######  Lemma 10.

Let $\\{\Pi_{0|0},\Pi_{1|0}\\}$ and $\\{\Pi_{0|1},\Pi_{1|1}\\}$ be two rank-
one projective measurements on a two dimensional Hilbert space $\mathcal{H}$.
There exists a basis $\\{|e_{i}\rangle\\}_{i=1}^{2}$ such that $\langle
e_{l}|\Pi_{i|j}|e_{k}\rangle\in\mathbb{R}$ for all $i,j,k,l$.

###### Proof.

Without loss of generality, we can take $\Pi_{0|0}=|0\rangle\\!\langle 0|$ and
$\Pi_{1|0}=|1\rangle\\!\langle 1|$, and then write
$\Pi_{0|1}=|\alpha_{0|1}\rangle\\!\langle\alpha_{0|1}|$ and
$\Pi_{1|1}=|\alpha_{1|1}\rangle\\!\langle\alpha_{1|1}|$, where
$|\alpha_{0|1}\rangle=\cos(\lambda)|0\rangle+\operatorname{e}^{\mathrm{i}\chi}\sin(\lambda)|1\rangle$
and
$|\alpha_{1|1}\rangle=\sin(\lambda)|0\rangle-\operatorname{e}^{\mathrm{i}\chi}\cos(\lambda)|1\rangle$.
Then, we can re-define
$|1\rangle\rightarrow\operatorname{e}^{\mathrm{i}\chi}|1\rangle$ so that
$|\alpha_{0|1}\rangle=\cos(\lambda)|0\rangle+\sin(\lambda)|1\rangle$ and
$|\alpha_{1|1}\rangle=\sin(\lambda)|0\rangle-\cos(\lambda)|1\rangle$, with
$\lambda\in\mathbb{R}$. ∎

######  Lemma 11.

Let $\\{\Pi_{0|0},\Pi_{1|0}\\}$ and $\\{\Pi_{0|1},\Pi_{1|1}\\}$ be two rank-
one projective measurements on a two dimensional Hilbert space $\mathcal{H}$,
then, there exists a unitary transformation $U$ such that
$U\Pi_{j|i}U^{\dagger}=\Pi_{j\oplus 1|i}$ for all $i,j$.

###### Proof.

Let $\Pi_{j|i}=|\alpha_{0|1}\rangle\\!\langle\alpha_{0|1}|$ for all $i,j$.
From Lemma 10, we can change basis such that $|\alpha_{0|0}\rangle=|0\rangle$,
$|\alpha_{1|0}\rangle=|1\rangle$,
$|\alpha_{0|1}\rangle=\cos(\lambda)|0\rangle+\sin(\lambda)|1\rangle$ and
$|\alpha_{1|1}\rangle=\sin(\lambda)|0\rangle-\cos(\lambda)|1\rangle$ for some
$\lambda\in\mathbb{R}$. Any unitary of the form
$U=\operatorname{e}^{\mathrm{i}\phi}(|0\rangle\\!\langle
1|-|1\rangle\\!\langle 0|)$, with $\phi\in\mathbb{R}$ then satisfies the
desired relations. ∎

The following lemma is well-known (it follows straightforwardly from e.g.,
(Nielsen and Chuang, 2000, Section 11.3.5))

######  Lemma 12.

For
$\rho_{CZEE^{\prime}}=\sum_{i}p_{i}\rho^{i}_{CZE}\otimes|i\rangle\\!\langle
i|_{E^{\prime}}$ we have
$H(C|ZEE^{\prime})_{\rho}=\sum_{i}p_{i}H(C|ZE)_{\rho^{i}}$.

We now prove Lemma 9.

###### Proof of Lemma 9.

Let $U_{A}$ and $U_{B}$ be the unitaries formed by applying Lemma 11 to
respective measurements of each device and using the choice of basis specified
in the proof of Lemma 11 we can take $U_{A}=\sigma_{2}$ and
$U_{B}=\sigma_{2}$. Then define
$\rho^{\prime}_{A^{\prime}B^{\prime}E}=(\sigma_{2}\otimes\sigma_{2}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(\sigma_{2}\otimes\sigma_{2}\otimes\openone_{E})$.
The states
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{\prime}_{A^{\prime}B^{\prime}E})$
and $(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$ are
related by

$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{\prime}_{A^{\prime}B^{\prime}E})=(\openone_{XYE}\otimes\sigma_{1}\otimes\sigma_{1})(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})(\openone_{XYE}\otimes\sigma_{1}\otimes\sigma_{1})\,.$

In other words
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{\prime}_{A^{\prime}B^{\prime}E})$
is identical to
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$, except
that the outcomes of each device have been relabelled. It follows that
$S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{\prime}_{A^{\prime}B^{\prime}E}))=\omega$
and
$\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{\prime}_{A^{\prime}B^{\prime}E}))=\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$.

Now consider the state
$\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}=(\rho_{A^{\prime}B^{\prime}E}\otimes|0\rangle\\!\langle
0|_{E^{\prime}}+\rho^{\prime}_{A^{\prime}B^{\prime}E^{\prime}}\otimes|1\rangle\\!\langle
1|_{E^{\prime}})/2$. We have
$(\mathcal{N}\otimes\mathcal{I}_{EE^{\prime}})(\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}})=((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})\otimes|0\rangle\\!\langle
0|_{E^{\prime}}+(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{\prime}_{A^{\prime}B^{\prime}E^{\prime}})\otimes|1\rangle\\!\langle
1|_{E^{\prime}})/2$. Since the CHSH score is linear, we have
$S((\mathcal{N}\otimes\mathcal{I}_{EE^{\prime}})(\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}}))=\omega$.
By construction,
$\tilde{\rho}_{A^{\prime}B^{\prime}E}=(\sigma_{2}\otimes\sigma_{2}\otimes\openone_{E})\tilde{\rho}_{A^{\prime}B^{\prime}E}(\sigma_{2}\otimes\sigma_{2}\otimes\openone_{E})$.
Finally, as a consequence of Lemma 12, for any of the entropy functions $H$ we
have
$\bar{H}(\tilde{\rho}_{A^{\prime}B^{\prime}EE^{\prime}})=\bar{H}(\rho_{A^{\prime}B^{\prime}E})$.
∎

######  Corollary 2.

Any optimization of the form (12) is equivalent to an optimization of the same
form but where each of the projectors are onto states of the form
$\alpha|0\rangle+\beta|1\rangle$ with $\alpha,\beta\in\mathbb{R}$ and
$\rho_{A^{\prime}B^{\prime}E}=(\sigma_{2}\otimes\sigma_{2}\otimes\openone)\rho_{A^{\prime}B^{\prime}E}(\sigma_{2}\otimes\sigma_{2}\otimes\openone)$.

Next we consider the form of the reduced state $\rho_{A^{\prime}B^{\prime}}$
in the Bell basis.

######  Lemma 13.

Let $\mathcal{N}$ be the channel associated with a single-round CHSH strategy
in which each POVM element is a projector of the form
$\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle$ with $\alpha\in\mathbb{R}$. The
state $\rho^{P}_{A^{\prime}B^{\prime}E}$ satisfies
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{P}_{A^{\prime}B^{\prime}E})=(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$,
where $\rho^{P}_{A^{\prime}B^{\prime}E}$ is formed from
$\rho_{A^{\prime}B^{\prime}E}$ by taking the partial transpose on
$A^{\prime}B^{\prime}$ in the Bell basis.

###### Proof.

By definition, the partial transpose generates the state

$\rho^{P}_{A^{\prime}B^{\prime}E}=\sum_{ij}(|\Psi_{i}\rangle\\!\langle\Psi_{j}|\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(|\Psi_{i}\rangle\\!\langle\Psi_{j}|\otimes\openone_{E})\,.$

Writing the partial trace out in the Bell basis, for any two projectors
$\Pi_{1}$ and $\Pi_{2}$ on $\mathcal{H}_{A^{\prime}}$ and
$\mathcal{H}_{B^{\prime}}$ we have

$\displaystyle\mathrm{tr}_{A^{\prime}B^{\prime}}((\Pi_{1}\otimes\Pi_{2}\otimes\openone_{E})\rho^{P}_{A^{\prime}B^{\prime}E})$
$\displaystyle=$
$\displaystyle\sum_{i}(\langle\Psi_{i}|(\Pi_{1}\otimes\Pi_{2})\otimes\openone_{E})\rho^{P}_{A^{\prime}B^{\prime}E}(|\Psi_{i}\rangle\otimes\openone_{E})$
(13) $\displaystyle=$
$\displaystyle\sum_{ijk}((\langle\Psi_{i}|(\Pi_{1}\otimes\Pi_{2})|\Psi_{j}\rangle\\!\langle\Psi_{k}|)\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(|\Psi_{j}\rangle\\!\langle\Psi_{k}||\Psi_{i}\rangle\otimes\openone_{E})$
$\displaystyle=$
$\displaystyle\sum_{ij}\langle\Psi_{i}|(\Pi_{1}\otimes\Pi_{2})|\Psi_{j}\rangle(\langle\Psi_{i}|\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E}(|\Psi_{j}\rangle\otimes\openone_{E})\,.$

When $\Pi_{1}$ and $\Pi_{2}$ are each projectors onto states of the form
$\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle$ a short calculation reveals
$\langle\Psi_{i}|(\Pi_{1}\otimes\Pi_{2})|\Psi_{j}\rangle=\langle\Psi_{j}|(\Pi_{1}\otimes\Pi_{2})|\Psi_{i}\rangle$.
Using this in (13) we can conclude that

$\mathrm{tr}_{A^{\prime}B^{\prime}}((\Pi_{1}\otimes\Pi_{2}\otimes\openone_{E})\rho^{P}_{A^{\prime}B^{\prime}E})=\mathrm{tr}_{A^{\prime}B^{\prime}}((\Pi_{1}\otimes\Pi_{2}\otimes\openone_{E})\rho_{A^{\prime}B^{\prime}E})\,,$

from which it follows that
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{P}_{A^{\prime}B^{\prime}E})=(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$.
∎

######  Corollary 3.

Any optimization of the form (12) is equivalent to an optimization of the same
form but where each of the projectors are onto states of the form
$\alpha|0\rangle+\beta|1\rangle$ with $\alpha,\beta\in\mathbb{R}$,
$\rho_{A^{\prime}B^{\prime}E}=(\sigma_{2}\otimes\sigma_{2}\otimes\openone)\rho_{A^{\prime}B^{\prime}E}(\sigma_{2}\otimes\sigma_{2}\otimes\openone)$
and $\rho_{A^{\prime}B^{\prime}E}=\rho^{P}_{A^{\prime}B^{\prime}E}$.

###### Proof.

We established the invariance under
$(\sigma_{2}\otimes\sigma_{2}\otimes\openone)$ in Corollary 2. Since
$(\mathcal{N}\otimes\mathcal{I}_{E})(\rho^{P}_{A^{\prime}B^{\prime}E})=(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$,
if Eve uses the state $(\rho_{A^{\prime}B^{\prime}E}\otimes|0\rangle\\!\langle
0|_{E^{\prime}}+\rho^{P}_{A^{\prime}B^{\prime}E}\otimes|1\rangle\\!\langle
1|_{E^{\prime}})/2$, then, by the same argument used at the end of the proof
of Lemma 9, the entropy and scores are unchanged while the state satisfies the
required conditions. ∎

The next step is to show that the state on $A^{\prime}B^{\prime}$ can be taken
to come from the set of density operators that are diagonal in the Bell basis.
We define

$\displaystyle\mathcal{S}_{B}:=$
$\displaystyle\left\\{\lambda_{0}|\Phi_{0}\rangle\\!\langle\Phi_{0}|+\lambda_{1}|\Phi_{1}\rangle\\!\langle\Phi_{1}|+\lambda_{2}|\Phi_{2}\rangle\\!\langle\Phi_{2}|+\lambda_{3}|\Phi_{3}\rangle\\!\langle\Phi_{3}|:1\geq\lambda_{0}\geq\lambda_{3}\geq
0,\,1\geq\lambda_{1}\geq\lambda_{2}\geq 0,\vphantom{\sum_{i}}\right.$
$\displaystyle\left.\lambda_{0}-\lambda_{3}\geq\lambda_{1}-\lambda_{2},\sum_{i}\lambda_{i}=1\right\\}\,,$
(14)

where the states $\\{|\phi_{i}\rangle\\}_{i}$ are defined by (6)–(9).

######  Lemma 14.

Any optimization of the form (12) is equivalent to an optimization of the same
form but where each of the projectors are onto states of the form
$\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle$ with $\alpha\in\mathbb{R}$ and
$\rho_{A^{\prime}B^{\prime}}\in\mathcal{S}_{B}$.

###### Proof.

From Corollary 3, we have that $\rho_{A^{\prime}B^{\prime}}$ can be taken to
be invariant under $\sigma_{2}\otimes\sigma_{2}$. Hence we can write

$\rho_{A^{\prime}B^{\prime}}=\left(\begin{array}[]{cccc}\lambda^{\prime}_{0}&0&0&r_{1}\\\
0&\lambda^{\prime}_{1}&r_{2}&0\\\ 0&r_{2}^{*}&\lambda^{\prime}_{2}&0\\\
r_{1}^{*}&0&0&\lambda^{\prime}_{3}\end{array}\right)\,$ (15)

where the matrix is expressing the coefficients in the Bell basis. That
$\rho_{A^{\prime}B^{\prime}}=\rho_{A^{\prime}B^{\prime}}^{T}$ then implies
that $r_{1}$ and $r_{2}$ are real. Note that in order that
$\rho_{A^{\prime}B^{\prime}}$ is a positive operator we require
$r_{1}^{2}\leq\lambda^{\prime}_{0}\lambda^{\prime}_{3}$ and
$r_{2}^{2}\leq\lambda^{\prime}_{1}\lambda^{\prime}_{2}$.

Let $U_{\theta}=\cos(\theta/2)|0\rangle\\!\langle
0|+\sin(\theta/2)|0\rangle\\!\langle 1|-\sin(\theta/2)|1\rangle\\!\langle
0|+\cos(\theta/2)|1\rangle\\!\langle 1|$, so that $U_{\theta}$ preserves the
set $\\{\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle:\alpha\in\mathbb{R}\\}$.
We proceed to show that for any state of the form (15) with $r_{1}$ and
$r_{2}$ real, there exist values of $\theta_{A}$ and $\theta_{B}$ such that

$\rho^{\prime}_{A^{\prime}B^{\prime}}=(U_{\theta_{A}}\otimes
U_{\theta_{B}})\rho_{A^{\prime}B^{\prime}}(U^{\dagger}_{\theta_{A}}\otimes
U^{\dagger}_{\theta_{B}})$

is diagonal in the Bell basis. We can compute the form of
$\rho^{\prime}_{A^{\prime}B^{\prime}}$ in the Bell basis. This has the same
form as (15), but with $r_{1}$ replaced by
$r_{1}\cos(\theta_{A}-\theta_{B})+\frac{\lambda^{\prime}_{0}-\lambda^{\prime}_{3}}{2}\sin(\theta_{A}-\theta_{B})$
and $r_{2}$ replaced by
$r_{2}\cos(\theta_{A}+\theta_{B})+\frac{\lambda^{\prime}_{2}-\lambda^{\prime}_{1}}{2}\sin(\theta_{A}+\theta_{B})$.
To make these zero we need to choose $\theta_{A}$ and $\theta_{B}$ such that
$\cos^{2}(\theta_{A}-\theta_{B})=\frac{(\lambda^{\prime}_{0}-\lambda^{\prime}_{3})^{2}}{(\lambda^{\prime}_{0}-\lambda^{\prime}_{3})^{2}+4r_{1}^{2}}$
and
$\cos^{2}(\theta_{A}+\theta_{B})=\frac{(\lambda^{\prime}_{1}-\lambda^{\prime}_{2})^{2}}{(\lambda^{\prime}_{1}-\lambda^{\prime}_{2})^{2}+4r_{2}^{2}}$.
If we write

$\displaystyle\phi_{1}=\cos^{-1}\left(\frac{\lambda^{\prime}_{0}-\lambda^{\prime}_{3}}{\sqrt{(\lambda^{\prime}_{0}-\lambda^{\prime}_{3})^{2}+4r_{1}^{2}}}\right),\quad$
$\displaystyle\phi_{2}=\cos^{-1}\left(\frac{\lambda^{\prime}_{1}-\lambda^{\prime}_{2}}{\sqrt{(\lambda^{\prime}_{1}-\lambda^{\prime}_{2})^{2}+4r_{2}^{2}}}\right),$
$\displaystyle\zeta_{A}=\frac{\phi_{1}+\phi_{2}}{2}\quad\text{and}\quad$
$\displaystyle\zeta_{B}=\frac{\phi_{1}-\phi_{2}}{2}$

then we can express the four solutions

$(\theta_{A},\theta_{B})=(\zeta_{A},\zeta_{B}),\,(\zeta_{A}+\pi/2,\zeta_{B}-\pi/2),\,(\zeta_{A}+\pi/2,\zeta_{B}+\pi/2),\,(\zeta_{A}+\pi,\zeta_{B})\,.$

Each of these brings the state into the form
$\rho_{A^{\prime}B^{\prime}}=\lambda_{0}|\Phi_{0}\rangle\\!\langle\Phi_{0}|+\lambda_{1}|\Phi_{1}\rangle\\!\langle\Phi_{1}|+\lambda_{2}|\Phi_{2}\rangle\\!\langle\Phi_{2}|+\lambda_{3}|\Phi_{3}\rangle\\!\langle\Phi_{3}|$.
The difference between the first two of these is an exchange of $\lambda_{0}$
with $\lambda_{3}$, the difference between the first and the third is an
exchange of $\lambda_{1}$ with $\lambda_{2}$ and the difference between the
first and the fourth is an exchange of $\lambda_{0}$ with $\lambda_{3}$ and of
$\lambda_{1}$ with $\lambda_{2}$. It follows that we can ensure
$\lambda_{0}\geq\lambda_{3}$ and $\lambda_{1}\geq\lambda_{2}$. Finally, if
$\lambda_{0}-\lambda_{3}<\lambda_{1}-\lambda_{2}$ we can apply
$\sigma_{3}\otimes\openone$ to the resulting state, which simultaneously
switches $\lambda_{0}$ with $\lambda_{1}$ and $\lambda_{2}$ with
$\lambda_{3}$, while again preserving the set
$\\{\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle:\alpha\in\mathbb{R}\\}$. ∎

The culmination of this section is the following.

######  Lemma 15.

For given $p_{XY}$, let

$\displaystyle\mathcal{R}_{1}(\omega)$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N},\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{\Pi_{1},2}(p_{XY}),\,\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}),\,S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega\\}\quad\text{and}$
$\displaystyle\mathcal{R}_{2}(\omega)$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N},\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{\Pi_{1},2}(p_{XY}),\,\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}),\,\rho_{A^{\prime}B^{\prime}}\in\mathcal{S}_{B},\,S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega\\}\,.$

We have
$\inf_{\mathcal{R}_{2}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\inf_{\mathcal{R}_{1}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$
for any of the six entropy functions $\bar{H}$.

###  B.4 Reduction to pure states

Here we show that it is sufficient to restrict any of the optimizations we are
interested in to pure states.

######  Lemma 16.

For given $p_{XY}$ let $\mathcal{R}_{2}(\omega)$ be as in Lemma 15 and
consider

$\displaystyle\mathcal{R}_{3}(\omega)$ $\displaystyle:=$
$\displaystyle\\{(\mathcal{N},\rho_{A^{\prime}B^{\prime}E}):\mathcal{N}\in\mathcal{C}_{\Pi_{1},2}(p_{XY}),\,\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}_{P}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}),\,\rho_{A^{\prime}B^{\prime}}\in\mathcal{S}_{B},\,S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega\\}\,.$

We have
$\inf_{\mathcal{R}_{3}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\inf_{\mathcal{R}_{2}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$
for any of the six entropy functions $\bar{H}$.

###### Proof.

Since $\mathcal{R}_{3}\subset\mathcal{R}_{2}$, we have
$\inf_{\mathcal{R}_{3}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))\geq\inf_{\mathcal{R}_{2}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$.
For the other direction, consider a state $\rho_{A^{\prime}B^{\prime}E}$ from
the set $\mathcal{R}_{2}$, and let $\rho_{A^{\prime}B^{\prime}EE^{\prime}}$ be
its purification. Using the strong subadditivity of the von-Neumann entropy,
$H(C|ZEE^{\prime})\leq H(C|ZE)$, a new strategy in which the only change is
that Eve holds a purification of $\rho_{A^{\prime}B^{\prime}E}$ cannot
increase any of the entropic quantities of interest and makes no change to the
score. Thus,
$\inf_{\mathcal{R}_{3}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))\leq\inf_{\mathcal{R}_{2}(\omega)}\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$.
∎

Note that this also means that we can restrict $\mathcal{H}_{E}$ to be 4
dimensional.

##  Appendix C Simplifications of qubit strategies for specific entropic
quantities

In this section, we compute expressions for each of the entropies of interest,
based on the simplifications from the previous section. In other words, we are
considering the optimizations

$\displaystyle G(\omega,p_{XY}):=\min\ $
$\displaystyle\bar{H}((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))$
(16)
$\displaystyle\mathcal{H}_{A^{\prime}}=\mathcal{H}_{B^{\prime}}=\mathbb{C}^{2},\
\mathcal{H}_{E}=\mathbb{C}^{4},\
\rho_{A^{\prime}B^{\prime}E}\in\mathcal{S}_{P}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E}),\
\rho_{A^{\prime}B^{\prime}}\in\mathcal{S}_{B}$
$\displaystyle\mathcal{N}:\sigma_{A^{\prime}B^{\prime}}\mapsto\sum_{abxy}p_{XY}(x,y)|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes|x\rangle\\!\langle
x|\otimes|y\rangle\\!\langle
y|\mathrm{tr}\left(\left(|\phi^{A}_{a|x}\rangle\\!\langle\phi^{A}_{a|x}|\otimes|\phi^{B}_{b|y}\rangle\\!\langle\phi^{B}_{b|y}|\right)\sigma_{A^{\prime}B^{\prime}}\right)$
$\displaystyle|\phi^{A}_{a|x}\rangle=\cos(\alpha_{a|x})|0\rangle+\sin(\alpha_{a|x})|1\rangle\quad\text{and}\quad|\phi^{B}_{b|y}\rangle=\cos(\beta_{b|y})|0\rangle+\sin(\beta_{b|y})|1\rangle$
(17)
$\displaystyle\alpha_{1|x}=\pi/2+\alpha_{0|x}\quad\text{and}\quad\beta_{1|x}=\pi/2+\beta_{0|x}$
(18) $\displaystyle
S((\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}))=\omega.$
(19)

For convenience we sometimes use $\alpha_{x}=\alpha_{0|x}$ and
$\beta_{x}=\beta_{0|x}$.

Let

$\displaystyle\tau_{ABXYE}$ $\displaystyle=$
$\displaystyle(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$
(20) $\displaystyle=$ $\displaystyle\sum_{abxy}p_{XY}(x,y)|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes|x\rangle\\!\langle
x|\otimes|y\rangle\\!\langle
y|\otimes\mathrm{tr}_{A^{\prime}B^{\prime}}\left(\left(|\phi^{A}_{a|x}\rangle\\!\langle\phi^{A}_{a|x}|\otimes|\phi^{B}_{b|y}\rangle\\!\langle\phi^{B}_{b|y}|\otimes\openone_{E}\right)\rho_{A^{\prime}B^{\prime}E}\right)$
$\displaystyle=$
$\displaystyle\sum_{abxy}p_{XY}(x,y)p_{AB|xy}(a,b)|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes|x\rangle\\!\langle
x|\otimes|y\rangle\\!\langle y|\otimes\tau_{E}^{abxy}\,,$

where $\\{\tau_{E}^{abxy}\\}$ are normalized.

We make a few initial observations.

Consider
$p_{AB|xy}(a,b)\tau_{E}^{abxy}=\mathrm{tr}_{A^{\prime}B^{\prime}}\left(\left(|\phi^{A}_{a|x}\rangle\\!\langle\phi^{A}_{a|x}|\otimes|\phi^{B}_{b|y}\rangle\\!\langle\phi^{B}_{b|y}|\otimes\openone_{E}\right)\rho_{A^{\prime}B^{\prime}E}\right)$.
Since $\rho_{A^{\prime}B^{\prime}E}$ is pure, we can use the Schmidt
decomposition to write
$\rho_{A^{\prime}B^{\prime}E}=|\Phi\rangle\\!\langle\Phi|_{A^{\prime}B^{\prime}E}$,
where

$|\Phi\rangle_{A^{\prime}B^{\prime}E}=\sum_{i}\sqrt{\lambda_{i}}|\Psi_{i}\rangle\otimes|i\rangle\,$

where $\\{|i\rangle\\}$ is an orthonormal basis for $\mathcal{H}_{E}$. We have

$\displaystyle
p_{AB|xy}(a,b)\tau_{E}^{abxy}=\sum_{ij}\sqrt{\lambda_{i}\lambda_{j}}\left(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|\right)|\Psi_{i}\rangle\langle\Psi_{j}|\left(|\phi^{A}_{a|x}\rangle\otimes|\phi^{B}_{b|y}\rangle\right)|i\rangle\\!\langle
j|=|\zeta^{abxy}\rangle\\!\langle\zeta^{abxy}|\,,$

where

$\displaystyle|\zeta^{abxy}\rangle=\\!\sum_{i}\sqrt{\lambda_{i}}(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|)|\Psi_{i}\rangle|i\rangle\\!\quad\\!\text{and}\\!\quad\\!p_{AB|xy}(a,b)=\\!\sum_{i}\lambda_{i}\left|(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|)|\Psi_{i}\rangle\right|^{2}\,.$
(21)

Hence $\tau_{E}^{abxy}$ is pure for each $a,b,x,y$. Note also that

$\displaystyle\left(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|\right)|\Psi_{0}\rangle$
$\displaystyle=$
$\displaystyle\frac{\cos(\beta_{b|y}-\alpha_{a|x})}{\sqrt{2}}$ (22)
$\displaystyle\left(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|\right)|\Psi_{1}\rangle$
$\displaystyle=$
$\displaystyle\frac{\cos(\beta_{b|y}+\alpha_{a|x})}{\sqrt{2}}$ (23)
$\displaystyle\left(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|\right)|\Psi_{2}\rangle$
$\displaystyle=$
$\displaystyle\frac{\sin(\beta_{b|y}+\alpha_{a|x})}{\sqrt{2}}$ (24)
$\displaystyle\left(\langle\phi^{A}_{a|x}|\otimes\langle\phi^{B}_{b|y}|\right)|\Psi_{3}\rangle$
$\displaystyle=$
$\displaystyle\frac{\sin(\beta_{b|y}-\alpha_{a|x})}{\sqrt{2}}$ (25)

Because $\tau_{ABXYE}$ is formed from $\rho_{A^{\prime}B^{\prime}E}$ without
acting on $E$, we have $H(E)_{\tau}=H(E)_{\rho}$, and because
$\rho_{A^{\prime}B^{\prime}E}$ is pure,
$H(E)_{\rho}=H(A^{\prime}B^{\prime})_{\rho}=H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$.101010We
use $H$ for both the von Neumann and Shannon entropies; if a list of
probabilities is given as the argument to $H$ it signifies the Shannon
entropy. For the same reason, $\sum_{ab}p_{AB}(a,b)\tau_{E}^{abxy}=\tau_{E}$
for all $x,y$.

######  Lemma 17.

For $\sigma_{AXE}=\sum_{ax}p_{AX}(a,x)|a\rangle\\!\langle
a|\otimes|x\rangle\\!\langle x|\otimes\sigma^{a,x}_{E}$, we have

$H(A|XE)=H(A|X)+\sum_{ax}p_{AX}(a,x)H(\sigma^{a,x}_{E})-\sum_{x}p_{X}(x)H\left(\sum_{a}p_{A|x}(a)\sigma^{a,x}_{E}\right)\,.$

###### Proof.

We have

$\displaystyle H(A|XE)$
$\displaystyle=H(AXE)-H(XE)=H(AX)+\sum_{ax}p_{AX}(a,x)H(E|A=a,X=x)-H(X)-\sum_{x}p_{X}(x)H(E|X=x)$
$\displaystyle=H(A|X)+\sum_{ax}p_{AX}(a,x)\left(H(\sigma^{a,x}_{E})-H\left(\sum_{a^{\prime}}p_{A|x}(a^{\prime})\sigma^{a^{\prime},x}_{E}\right)\right)\,.\qed$

We can parameterize the Bell diagonal state in the following way:

$\displaystyle\lambda_{0}$ $\displaystyle=$
$\displaystyle\frac{1}{4}+\frac{R\cos(\theta)}{2}+\delta$ (26)
$\displaystyle\lambda_{1}$ $\displaystyle=$
$\displaystyle\frac{1}{4}+\frac{R\sin(\theta)}{2}-\delta$ (27)
$\displaystyle\lambda_{2}$ $\displaystyle=$
$\displaystyle\frac{1}{4}-\frac{R\sin(\theta)}{2}-\delta$ (28)
$\displaystyle\lambda_{3}$ $\displaystyle=$
$\displaystyle\frac{1}{4}-\frac{R\cos(\theta)}{2}+\delta$ (29)

where $0\leq R\leq 1$, $0\leq\theta\leq\pi/4$ if $R\leq 1/\sqrt{2}$, or
$0\leq\theta\leq\pi/4-\cos^{-1}(1/(R\sqrt{2}))$ if $R>1/\sqrt{2}$ and
$-1/4+R\cos(\theta)/2\leq\delta\leq 1/4-R\sin(\theta)/2$.

######  Lemma 18.

For $R>1/\sqrt{2}$,
$\max_{\delta}H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$ is
achieved when $\delta=\delta^{*}=\frac{R^{2}\cos(2\theta)}{4}$.

###### Proof.

One can compute the derivative of
$H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$ with respect to
$\delta$ to see that it is $0$ only for
$\delta=\delta^{*}:=\frac{R^{2}\cos(2\theta)}{4}$.

We next check that $\delta^{*}$ is in the valid range of $\delta$. The
condition $\delta^{*}\leq 1/4-R\sin(\theta)/2$ rearranges to
$2R^{2}\sin^{2}(\theta)-2R\sin(\theta)+1-R^{2}\geq 0$. The roots of the
quadratic equation $2R^{2}x^{2}-2Rx+1-R^{2}$ are at
$x=\frac{1}{2R}(1\pm\sqrt{2R^{2}-1})$. For $R\geq\frac{1}{\sqrt{2}}$ the roots
are real111111If $R<\frac{1}{\sqrt{2}}$ there are no real roots and the
condition always holds.. Our condition on $\theta$ implies that
$0\leq\sin(\theta)\leq\frac{1}{2R}(1-\sqrt{2R^{2}-1})$, hence taking
$x=\sin(\theta)$ we are always to the left of the first root and so
$\delta^{*}\leq 1/4-R\sin(\theta)/2$. A similar argument shows
$\delta^{*}\geq-1/4+R\cos(\theta)/2$.

We can then compute the double derivative of
$H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$ with respect to
$\delta$ and evaluate it at $\delta^{*}$. This gives
$-\frac{32}{\ln(2)(2-4R^{2}+R^{4}+R^{4}\cos(4\theta))}$, which can be shown to
be negative for $R>1/\sqrt{2}$ and any valid $\theta$ using a similar argument
to that above. ∎

Using this state and the specified measurements, the probability table for the
observed distribution has the form given in the table below (whose entries
correspond to $p_{AB|XY}$):

|  | $Y=0$ |  | $Y=1$ |
---|---|---|---|---|---
|  | $B=0$ |  $B$ = 1 | $B=0$ | $A=1$
$X=0$ | $A=0$ | $\epsilon_{00}$ |  $\frac{\sum^{a}}{f}$ $\frac{1}{2}-\epsilon_{00}$ | $\epsilon_{01}$ | $\frac{1}{2}-\epsilon_{01}$
| $A=1$ |  $\frac{\sum^{a}}{f}$ $\frac{1}{2}-\epsilon_{00}$ | $\epsilon_{00}$ | $\frac{1}{2}-\epsilon_{01}$ | $\epsilon_{01}$
$X=1$ | $A=0$ | $\epsilon_{10}$ |  $\frac{\sum^{a}}{f}$ $\frac{1}{2}-\epsilon_{10}$ | $\frac{1}{2}-\epsilon_{11}$ | $\epsilon_{11}$
| $A=1$ |  $\frac{\sum^{a}}{f}$$\frac{1}{2}-\epsilon_{10}$ | $\epsilon_{10}$ | $\epsilon_{11}$ | $\frac{1}{2}-\epsilon_{11}$

where

$\displaystyle\epsilon_{00}$
$\displaystyle=\frac{1}{4}\left(1+R\cos(\theta)\cos(2(\alpha_{0}-\beta_{0}))+R\sin(\theta)\cos(2(\alpha_{0}+\beta_{0}))\right)$
$\displaystyle\epsilon_{01}$
$\displaystyle=\frac{1}{4}\left(1+R\cos(\theta)\cos(2(\alpha_{0}-\beta_{1}))+R\sin(\theta)\cos(2(\alpha_{0}+\beta_{1}))\right)$
$\displaystyle\epsilon_{10}$
$\displaystyle=\frac{1}{4}\left(1+R\cos(\theta)\cos(2(\alpha_{1}-\beta_{0}))+R\sin(\theta)\cos(2(\alpha_{1}+\beta_{0}))\right)$
$\displaystyle\epsilon_{11}$
$\displaystyle=\frac{1}{4}\left(1-R\cos(\theta)\cos(2(\alpha_{1}-\beta_{1}))-R\sin(\theta)\cos(2(\alpha_{1}+\beta_{1}))\right)\,.$

Note that

$\displaystyle S(\tau_{ABXY})=$
$\displaystyle(\epsilon_{00}+\epsilon_{01}+\epsilon_{10}+\epsilon_{11})/2$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{R\cos(\theta)}{8}\bigl{(}\cos(2(\alpha_{0}-\beta_{0}))+\cos(2(\alpha_{0}-\beta_{1}))+\cos(2(\alpha_{1}-\beta_{0}))-\cos(2(\alpha_{1}-\beta_{1}))\bigr{)}$
$\displaystyle+\frac{R\sin(\theta)}{8}\bigl{(}\cos(2(\alpha_{0}+\beta_{0}))+\cos(2(\alpha_{0}+\beta_{1}))+\cos(2(\alpha_{1}+\beta_{0}))-\cos(2(\alpha_{1}+\beta_{1}))\bigr{)}\,,$
(30)

which is independent of $\delta$.

###  C.1 H(AB|X=0,Y=0,E)

For $H(AB|X=0,Y=0,E)$ we are interested in the state

$\tau^{\prime}_{ABE}=\sum_{ab}p_{AB|00}(a,b)|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes\tau_{E}^{ab00}$

since $H(AB|X=0,Y=0,E)_{\tau}=H(AB|E)_{\tau^{\prime}}$. Note that, as above,
$H(E)_{\tau^{\prime}}=H(E)_{\rho}$. Using Lemma 17 we have

$\displaystyle H(AB|E)_{\tau^{\prime}}$
$\displaystyle=H(AB)_{\tau^{\prime}}+\sum_{ab}p_{AB}(a,b)H(\tau_{E}^{ab00})-H\left(\sum_{ab}p_{AB}(a,b)\tau_{E}^{ab00}\right)$
$\displaystyle=H(AB)_{\tau^{\prime}}+\sum_{ab}p_{AB}(a,b)H(\tau_{E}^{ab00})-H(E)_{\tau^{\prime}}\,.$

However, since $\tau_{E}^{ab00}$ is pure for each $a,b$,
$H(\tau_{E}^{ab00})=0$ and we find

$\displaystyle H(AB|E)_{\tau^{\prime}}$
$\displaystyle=H(AB)_{\tau^{\prime}}-H(E)_{\rho}$
$\displaystyle=H(\\{\epsilon_{00},\epsilon_{00},1/2-\epsilon_{00},1/2-\epsilon_{00}\\})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$
$\displaystyle=1+H_{\mathrm{bin}}(2\epsilon_{00})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\,.$

Lemma 18 shows that
$\max_{\delta}H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$ is
achieved for $\delta=\delta^{*}=\frac{R^{2}\cos(2\theta)}{4}$. Since the score
is independent of $\delta$ we can take the state to satisfy
$\delta=\delta^{*}$ and remove $\delta$ from the optimization.

###  C.2 H(AB|XYE)

In this case we again use Lemma 17 to obtain

$\displaystyle H(AB|XYE)$
$\displaystyle=H(AB|XY)+\sum_{abxy}p_{ABXY}(a,b,x,y)H(\tau_{E}^{abxy})-\sum_{xy}p_{XY}(x,y)H\left(\sum_{ab}p_{AB|xy}(a,b)\tau_{E}^{abxy}\right)$
$\displaystyle=H(AB|XY)-H(E)\,,$

where we again use that $H(\tau_{E}^{abxy})=0$, and note that
$\sum_{ab}p_{AB|xy}(a,b)\tau_{E}^{abxy}=\rho_{E}$ for all $x,y$. Note that

$\displaystyle H(AB|XY)$ $\displaystyle=\sum_{xy}p_{XY}(x,y)H(AB|X=x,Y=y)$
$\displaystyle=1+\sum_{xy}p_{XY}(x,y)H_{\mathrm{bin}}(2\epsilon_{xy})\,,$

and so we have

$H(AB|XYE)=1+\sum_{xy}p_{XY}(x,y)H_{\mathrm{bin}}(2\epsilon_{xy})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\,.$
(31)

This is again independent of $\delta$, so, like in the case of
$H(AB|X=0,Y=0,E)$ we can take $\delta=\delta^{*}$ and remove $\delta$ from the
optimization.

###  C.3 H(AB|E)

We first trace out $XY$ to give $\tau_{ABE}=\sum_{ab}p_{AB}|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes\sum_{xy}p_{XY|ab}(x,y)\tau_{E}^{abxy}$.
For this state, Lemma 17 gives

$\displaystyle H(AB|E)$
$\displaystyle=H(AB)+\sum_{ab}p_{AB}(a,b)H\left(\sum_{xy}p_{XY|ab}(x,y)\tau_{E}^{abxy}\right)-H\left(\sum_{abxy}p_{AB}(a,b)p_{XY|ab}(x,y)\tau_{E}^{abxy}\right)$
$\displaystyle=H(AB)+\sum_{ab}p_{AB}(a,b)H\left(\sum_{xy}p_{XY|ab}(x,y)\tau_{E}^{abxy}\right)-H(E)$
$\displaystyle=H(AB)+\sum_{ab}p_{AB}(a,b)H\left(\sum_{xy}\frac{1}{p_{AB}(a,b)}p_{XY}(x,y)p_{AB|xy}(a,b)\tau_{E}^{abxy}\right)-H(E)\,.$

In this case we cannot remove the middle term, and the middle term is not
independent of $\delta$. The optimization in this case is hence significantly
more complicated. Note that

$\displaystyle
H(AB)=1+H_{\mathrm{bin}}\left(2\left(p_{XY}(0,0)\epsilon_{00}+p_{XY}(0,1)\epsilon_{01}+p_{XY}(1,0)\epsilon_{10}+p_{XY}(1,1)\left(\frac{1}{2}-\epsilon_{11}\right)\right)\right)\,.$

###  C.4 H(A|X=0,Y=0,E)

This case was already covered in Pironio  _et al._ (2009) where it was solved
analytically (see also Woodhead  _et al._ (2021) for a slight generalization).

######  Lemma 19.

For $3/4\leq\omega\leq\frac{1}{2}(1+\frac{1}{\sqrt{2}})$ the solution to the
optimization problem (16) when $\bar{H}=H(A|X=0,Y=0,E)$ is
$1-H_{\mathrm{bin}}\left(\frac{1}{2}(1+\sqrt{16\omega(\omega-1)+3})\right)$.

For completeness we give a proof here as well. We first show that the maximum
CHSH score for a Bell diagonal state depends only on $R$.

######  Lemma 20.

Given a state $\rho_{A^{\prime}B^{\prime}E}$ with
$\rho_{A^{\prime}B^{\prime}}$ parameterized as in (26)–(29), if $\mathcal{N}$
satisfies the requirements of the optimization problem (16), then
$\tau_{ABXYE}=(\mathcal{N}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E})$
satisfies $S(\tau_{ABXYE})\leq\frac{1}{2}+\frac{R}{2\sqrt{2}}$, and there
exists a channel $\mathcal{N}$ achieving equality.

###### Proof.

Consider the score function (30). Collecting all the terms involving
$\alpha_{0}$ and $\alpha_{1}$ and some manipulation gives

$\displaystyle S(\tau_{ABXYE})=$
$\displaystyle\frac{1}{2}+\frac{R}{2\sqrt{2}}\cos(\beta_{0}-\beta_{1})\left[\sin(2\alpha_{0})\sin(\beta_{0}+\beta_{1})\cos(\frac{\pi}{4}+\theta)+\cos(2\alpha_{0})\cos(\beta_{0}+\beta_{1})\sin(\frac{\pi}{4}+\theta)\right]$
$\displaystyle+\frac{R}{2\sqrt{2}}\sin(\beta_{0}-\beta_{1})\left[\sin(2\alpha_{1})\cos(\beta_{0}+\beta_{1})\cos(\frac{\pi}{4}+\theta)-\cos(2\alpha_{1})\sin(\beta_{0}+\beta_{1})\sin(\frac{\pi}{4}+\theta)\right],$

where we have used $\cos(\theta)+\sin(\theta)=\sqrt{2}\sin(\pi/4+\theta)$ and
$\cos(\theta)-\sin(\theta)=\sqrt{2}\cos(\pi/4+\theta)$. For brevity we write
$\bar{\theta}=\frac{\pi}{4}+\theta$. We then use that for
$r,t,\phi\in\mathbb{R}$ we have
$r\cos(\phi)+t\sin(\phi)\leq\sqrt{r^{2}+t^{2}}$ with equality if
$r\cos(\phi)+t\sin(\phi)\geq 0$ and $r\sin(\phi)=t\cos(\phi)$. This allows us
to form the bound

$\displaystyle S(\tau_{ABXYE})\leq$
$\displaystyle\frac{1}{2}+\frac{R}{2\sqrt{2}}\left(|\cos(\beta_{0}-\beta_{1})|\sqrt{\sin^{2}(\beta_{0}+\beta_{1})\cos^{2}(\bar{\theta})+\cos^{2}(\beta_{0}+\beta_{1})\sin^{2}(\bar{\theta})}\right.$
$\displaystyle\left.+|\sin(\beta_{0}-\beta_{1})|\sqrt{\cos^{2}(\beta_{0}+\beta_{1})\cos^{2}(\bar{\theta})+\sin^{2}(\beta_{0}+\beta_{1})\sin^{2}(\bar{\theta})}\right)$
$\displaystyle\phantom{S}\leq$
$\displaystyle\frac{1}{2}+\frac{R}{2\sqrt{2}}\,.$

Choosing $\alpha_{0}=0$, $\alpha_{1}=\pi/4$,
$\beta_{0}=\frac{\pi}{8}-\frac{\theta}{2}$,
$\beta_{1}=-\frac{\pi}{8}+\frac{\theta}{2}$ achieves equality (for instance).
∎

It follows that $\omega>3/4$ is only possible if $R>1/\sqrt{2}$.

We now turn to the entropy. In this case we trace out $B$ from the state
$\tau^{\prime}$ in Section C.1 to give
$\tau^{\prime}_{AE}=\sum_{a}p_{A|00}(a)|a\rangle\\!\langle
a|\otimes\sum_{b}p_{B|a00}(b)\tau_{E}^{ab00}$, so that
$H(A|X=0,Y=0,E)_{\tau}=H(A|E)_{\tau^{\prime}}$. Using Lemma 17 we have

$\displaystyle H(A|E)_{\tau^{\prime}}$
$\displaystyle=H(A)_{\tau^{\prime}}+\sum_{a}p_{A|00}(a)H\left(\sum_{b}p_{B|a00}(b)\tau_{E}^{ab00}\right)-H\left(\sum_{ab}p_{AB|00}(a,b)\tau_{E}^{ab00}\right)$
$\displaystyle=1+\sum_{a}\frac{1}{2}H\left(\sum_{b}p_{B|a00}(b)\tau_{E}^{ab00}\right)-H(E)_{\rho}$
$\displaystyle=1+\sum_{a}\frac{1}{2}H\left(\sum_{b}2p_{AB|00}(a,b)\tau_{E}^{ab00}\right)-H(E)_{\rho}\,,$

where we have used the fact that $p_{A|00}(a)=1/2$ for $a=0,1$. The
eigenvalues of $\sum_{b}2p_{AB|00}(a,b)\tau_{E}^{ab00}$ turn out to be

$\frac{1}{2}\left(1\pm\sqrt{2(\lambda_{0}-\lambda_{3})(\lambda_{1}-\lambda_{2})\cos(4\alpha_{0})+(\lambda_{0}-\lambda_{3})^{2}+(\lambda_{1}-\lambda_{2})^{2}}\right)\,,$

independently of $a$. Hence, we can write $H(A|E)_{\tau^{\prime}}$ in terms of
the Bell diagonal state using

$\displaystyle\sum_{a}\frac{1}{2}H\left(\sum_{b}2p_{AB|00}(a,b)\tau_{E}^{ab00}\right)$
$\displaystyle=H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{2(\lambda_{0}-\lambda_{3})(\lambda_{1}-\lambda_{2})\cos(4\alpha_{0})+(\lambda_{0}-\lambda_{3})^{2}+(\lambda_{1}-\lambda_{2})^{2}}\right)\right)$
$\displaystyle H(E)_{\rho}$
$\displaystyle=H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$

Having established this, we show the following.

######  Lemma 21.

Let $\rho_{A^{\prime}B^{\prime}E}$ be pure with
$\mathcal{H}_{A^{\prime}}=\mathcal{H}_{B^{\prime}}=\mathbb{C}^{2}$, and let
$\rho_{A^{\prime}B^{\prime}}$ be a Bell diagonal state parameterized by
(26)–(29) with $R>1/\sqrt{2}$. Let $\tau$ be the state defined by (20)
$H(A|X=0,Y=0,E)_{\tau}\geq
1+H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{2R^{2}-1}\right)\right)$
where equality is achievable for $\alpha_{0}=0$.

###### Proof.

We note that

$\displaystyle\sum_{a}\frac{1}{2}H\left(\sum_{b}2p_{AB|00}(a,b)\tau_{E}^{ab00}\right)$
$\displaystyle\geq
H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{2(\lambda_{0}-\lambda_{3})(\lambda_{1}-\lambda_{2})+(\lambda_{0}-\lambda_{3})^{2}+(\lambda_{1}-\lambda_{2})^{2}}\right)\right)$
$\displaystyle=H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})\,,$

with equality for $\alpha_{0}=0$. Hence

$H(A|E)_{\tau^{\prime}}\geq
1+H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\,.$
(32)

Using the parameterization of (26)–(29) we have
$\lambda_{0}+\lambda_{1}=1/2(1+R(\cos(\theta)+\sin(\theta)))$. Thus, the
minimum of $H(A|E)_{\tau^{\prime}}$ over $\delta$ is achieved for
$\delta=\delta^{*}$ (as in the case $H(AB|X=0,Y=0,E)$). Taking
$\delta=\delta^{*}$ and differentiating the resulting expression with respect
to $\theta$ yields

$\frac{R}{2}(\cos(\theta)+\sin(\theta))\log\left(\frac{1-R\cos(\theta)+R\sin(\theta)}{1+R\cos(\theta)-R\sin(\theta)}\right)\,.$

Since $\cos(\theta)+\sin(\theta)=\sqrt{2}\sin(\pi/4+\theta)$, the leading
factor is always positive over our range of $\theta$. The logarithm term is
always negative, except for $\theta=\pi/4$ where it reaches zero. Thus, the
minimum over $\theta$ is always obtained at the largest possible $\theta$,
i.e., $\theta=\pi/4-\cos^{-1}\left(1/(R\sqrt{2})\right)$.

With this substitution the right hand side of (32) reduces to

$1+H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{2R^{2}-1}\right)\right)\,,$

establishing the claim. ∎

Lemma 19 is then a corollary of Lemmas 20 and 21.

###### Proof of Lemma 19.

From Lemma 21 we have

$H(A|X=0,Y=0,E)_{\tau}\geq
1+H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{2R^{2}-1}\right)\right)\,.$

However, Lemma 20 then implies

$\displaystyle H(A|X=0,Y=0,E)_{\tau}$ $\displaystyle\geq$ $\displaystyle
1+H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{4(2\omega-1)^{2}-1}\right)\right)$
$\displaystyle=$ $\displaystyle
1+H_{\mathrm{bin}}\left(\frac{1}{2}\left(1+\sqrt{16\omega(\omega-1)+3)}\right)\right)\,,$

where we use the fact that $H_{\mathrm{bin}}(p)$ is decreasing and concave for
$p\geq 1/2$. Equality is achievable by taking $\alpha_{0}=0$,
$\alpha_{1}=\pi/4$, $\beta_{0}=\frac{\pi}{8}-\frac{\theta}{2}$,
$\beta_{1}=-\frac{\pi}{8}+\frac{\theta}{2}$. ∎

We use this case to gain confidence in our numerics, since we can make a
direct comparison to the analytic curve.

###  C.5 H(A|XYE)

In this case Lemma 17 gives

$\displaystyle H(A|XYE)$ $\displaystyle=$ $\displaystyle
H(A|XY)+\sum_{axy}p_{AXY}(a,x,y)H\left(\sum_{b}p_{B|axy}(b)\tau_{E}^{abxy}\right)$
$\displaystyle-\sum_{xy}p_{XY}(x,y)H\left(\sum_{ab}p_{AB|xy}(a,b)\tau_{E}^{abxy}\right)$
$\displaystyle=$ $\displaystyle
1+\sum_{axy}p_{XY}(x,y)p_{A|xy}(a)H\left(\sum_{b}2p_{AB|xy}(a,b)\tau_{E}^{abxy}\right)-H(E)\,.$

The eigenvalues of $\sum_{b}2p_{AB|xy}(a,b)\tau_{E}^{abxy}$ can be computed to
be

$\frac{1}{2}\left(1\pm\sqrt{2(\lambda_{0}-\lambda_{3})(\lambda_{1}-\lambda_{2})\cos(4\alpha_{x})+(\lambda_{0}-\lambda_{3})^{2}+(\lambda_{1}-\lambda_{2})^{2}}\right)\,,$

independently of $a,y$. If we define

$g(\alpha):=\frac{1}{2}\left(1+\sqrt{2(\lambda_{0}-\lambda_{3})(\lambda_{1}-\lambda_{2})\cos(4\alpha)+(\lambda_{0}-\lambda_{3})^{2}+(\lambda_{1}-\lambda_{2})^{2}}\right)$

then

$\displaystyle H(A|XYE)$
$\displaystyle=1+\sum_{x}p_{X}(x)H_{\mathrm{bin}}(g(\alpha_{x}))-H(E)\,.$

Note that using the parameterization (26)–(29) we have

$g(\alpha)=\frac{1}{2}\left(1+R\sqrt{1+\sin(2\theta)\cos(4\alpha)}\right)\,.$

Since this is independent of $\delta$, we can again use $\delta=\delta^{*}$ to
remove one parameter when minimizing $H(A|XYE)$.

###  C.6 H(A|E)

In this case Lemma 17 gives

$\displaystyle H(A|E)$
$\displaystyle=H(A)+\sum_{a}p_{A}(a)H\left(\sum_{bxy}p_{BXY|a}(b,x,y)\tau_{E}^{abxy}\right)-H\left(\sum_{abxy}p_{AB}(a,b)p_{XY|ab}(x,y)\tau_{E}^{abxy}\right)$
$\displaystyle=1+\frac{1}{2}\sum_{a}H\left(\sum_{bxy}2p_{ABXY}(a,b,x,y)\tau_{E}^{abxy}\right)-H(E)$
$\displaystyle=1+\frac{1}{2}\sum_{a}H\left(\sum_{bxy}2p_{XY}(x,y)P_{AB|xy}(a,b)\tau_{E}^{abxy}\right)-H(E)$
$\displaystyle=1+\frac{1}{2}\sum_{a}H\left(\sum_{x}2p_{X}(x)\mathrm{tr}_{A^{\prime}}\left(\left(|\phi^{A}_{a|x}\rangle\\!\langle\phi^{A}_{a|x}|\otimes\openone_{E}\right)\rho_{A^{\prime}E}\right)\right)-H(E)\,.$

Like in the case $H(AB|E)$ the middle term cannot be removed and this term is
not independent of $\delta$.

##  Appendix D Monotonicity

In this section we prove the monotonicity of the functions
$G_{A|XYE}(\omega)$, $G_{AB|00E}(\omega)$ and $G_{AB|XYE}(\omega)$. There is a
common part to the proofs, which we first establish.

######  Lemma 22.

Let $\lambda_{0}(R,\theta),\lambda_{1}(R,\theta),\lambda_{2}(R,\theta)$ and
$\lambda_{3}(R,\theta)$ be the eigenvalues of a Bell-diagonal states
$\rho_{A^{\prime}B^{\prime}}$ as in (26)–(29) in the case where
$\delta=\frac{R^{2}}{4}\cos(2\theta)$. Then

$\displaystyle\frac{\partial}{\partial
R}\left(H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\right)>0.$
(33)

###### Proof.

$\displaystyle\frac{\partial}{\partial
R}\Big{(}H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})\Big{)}$ $\displaystyle=$
$\displaystyle-\log(\lambda_{0}+\lambda_{1})\frac{\partial}{\partial
R}(\lambda_{0}+\lambda_{1})-\log(\lambda_{2}+\lambda_{3})\frac{\partial}{\partial
R}(\lambda_{2}+\lambda_{3})$ (34)

The equality above follows from the fact that
$1-\lambda_{1}-\lambda_{0}=\lambda_{2}+\lambda_{3}$ and thus
$H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})=-(\lambda_{0}+\lambda_{1})\log(\lambda_{1}+\lambda_{0})-(\lambda_{2}+\lambda_{3})\log(\lambda_{2}+\lambda_{3})$.
We also have that

$\displaystyle\frac{\partial}{\partial
R}H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})=-\sum_{i}\log{\lambda_{i}}\frac{\partial\lambda_{i}}{\partial
R}.$ (35)

Adding the derivatives, we have

$\displaystyle\frac{\partial}{\partial
R}\Big{(}H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\Big{)}$
$\displaystyle=$
$\displaystyle\log\left(\frac{\lambda_{0}}{\lambda_{0}+\lambda_{1}}\right)\frac{\partial\lambda_{0}}{\partial
R}+\log\left(\frac{\lambda_{1}}{\lambda_{0}+\lambda_{1}}\right)\frac{\partial\lambda_{1}}{\partial
R}$ (36)
$\displaystyle+\log\left(\frac{\lambda_{2}}{\lambda_{3}+\lambda_{2}}\right)\frac{\partial\lambda_{2}}{\partial
R}+\log\left(\frac{\lambda_{3}}{\lambda_{2}+\lambda_{3}}\right)\frac{\partial\lambda_{3}}{\partial
R}$ $\displaystyle=$
$\displaystyle\log_{2}\Big{(}\frac{\lambda_{0}}{\lambda_{0}+\lambda_{1}}\Big{)}\frac{\partial}{\partial
R}(\lambda_{0}+\lambda_{2})+\log_{2}\Big{(}\frac{\lambda_{1}}{\lambda_{0}+\lambda_{1}}\Big{)}\frac{\partial}{\partial
R}(\lambda_{1}+\lambda_{3})$ $\displaystyle=$
$\displaystyle\log\left(\frac{\lambda_{0}}{\lambda_{1}}\right)\frac{\partial}{\partial
R}(\lambda_{0}+\lambda_{2})=\log\left(\frac{\lambda_{0}}{\lambda_{1}}\right)\frac{\cos(\theta)-\sin(\theta)}{2}$
$\displaystyle\geq$ $\displaystyle 0.$

Where the second equality follows from the fact that for Bell-diagonal states
parameterized by $\delta=\frac{R^{2}}{4}\cos(2\theta)$, the eigenvalues obey

$\displaystyle\frac{\lambda_{0}}{\lambda_{0}+\lambda_{1}}=\frac{\lambda_{2}}{\lambda_{2}+\lambda_{3}}\quad\text{and}\quad\frac{\lambda_{1}}{\lambda_{0}+\lambda_{1}}=\frac{\lambda_{3}}{\lambda_{2}+\lambda_{3}}$

and the inequality comes from the parameterization. ∎

######  Lemma 23.

For $\omega\in(\frac{3}{4},\frac{1}{2}(1+\frac{1}{\sqrt{2}}))$ and any
distribution $p_{XY}$, the function $G_{A|XYE}(\omega,p_{XY})$ is increasing
in $\omega$.

###### Proof.

Let us fix the score $\omega$. From the analysis in Appendix C.5 we know that
the optimum value of $\delta$ is $\frac{R^{2}}{4}\cos(2\theta)$. Throughout
this proof we take $\delta=\frac{R^{2}}{4}\cos(2\theta)$ and consider
$\rho_{A^{\prime}B^{\prime}}$ to depend on two parameters $R$ and $\theta$.
Let $(\mathcal{N}^{*},\rho^{*}\equiv\rho(R^{*},\theta^{*}))$ be the channel
and state that that solves the optimization problem for
$G_{A|XYE}(\omega,p_{XY})$, i.e., such that
$G_{A|XYE}(\omega,p_{XY})=H(A|XYE)_{(\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}(R^{*},\theta^{*}))}$.
It suffices to show that there exists a curve
$\sigma:[-1,0]\mapsto\mathcal{S}(\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{B^{\prime}}\otimes\mathcal{H}_{E})$,
such that

  1. 1.

$\sigma(0)=\rho^{*}$

  2. 2.

$g(t):=H(A|XYE)_{(\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t))}$ is
differentiable for all $t\in[-1,0]$.

  3. 3.

$\left.\frac{\mathrm{d}g(t)}{\mathrm{d}t}\right|_{t=0}>0$

  4. 4.

$\forall
t:\frac{\mathrm{d}}{\mathrm{d}t}S\left((\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t))\right)>0$.

Then, if 1–4 hold, using the fact that $g(t)$ is continuous and has a positive
derivative at $t=0$, there exists $t_{0}<0$ such that for $t\in(t_{0},0)$,
$g(t)<g(0)$. Since the
$S\left((\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t))\right)$ is
continuous function, we must have that for any $t\in(t_{0},0)$

$\displaystyle
H(A|XYE)_{(\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}^{*})}$
$\displaystyle>$ $\displaystyle
H(A|XYE)_{(\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t))}$ (37)
$\displaystyle\geq$ $\displaystyle
G_{A|XYE}\left(S((\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t)),p_{XY}\right).$
(38)

Since $S((\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t))<\omega$ this
establishes the claim.

It remains to show that there exists a function $\sigma(t)$ such that 1–4
hold. Recall from Appendix C.5 that we can write

$\displaystyle
H(A|XYE)=1+p_{X}(0)H_{\mathrm{bin}}(g(\theta,\alpha_{0}))+p_{X}(1)H_{\mathrm{bin}}(g(\theta,\alpha_{1}))-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})$
(39)

where
$g(\theta,\alpha):=\frac{1}{2}\left(1+R\sqrt{1+\sin(2\theta)\cos(4\alpha)}\right)$.
We then set

$\displaystyle\sigma(t)=\rho(R^{*}+\kappa t,\theta^{*})$ (40)

for some positive number $\kappa$ such that $R^{*}-\kappa>3/4$. Thus,
$\sigma(0)=\rho^{*}$ and differentiability of $g(t)$ can be shown using the
form (39). We compute the $t$ derivative:

$\displaystyle\left.\frac{\mathrm{d}g(t)}{\mathrm{d}t}\right|_{t=0}=\left.\kappa\frac{\partial}{\partial
R}\Big{(}H(A|XYE)_{(\mathcal{N^{*}}\otimes\mathcal{I}_{E})(\rho_{A^{\prime}B^{\prime}E}(R,\theta))}\Big{)}\right|_{R=R^{*},\theta=\theta^{*}}$
(41)

Note that

$\displaystyle\frac{\partial}{\partial R}H_{\mathrm{bin}}(g(\theta,\alpha))$
$\displaystyle=$ $\displaystyle
H_{\mathrm{bin}}^{\prime}(g(\theta,\alpha))\frac{\sqrt{1+\sin(2\theta)\cos(4\alpha)}}{2}$
$\displaystyle\geq$ $\displaystyle
H_{\mathrm{bin}}^{\prime}\Big{(}\frac{1}{2}+\frac{R}{2}(\cos(\theta)+\sin(\theta))\Big{)}\frac{\cos(\theta)+\sin(\theta)}{2}$
$\displaystyle=$ $\displaystyle
H_{\mathrm{bin}}^{\prime}(\lambda_{0}+\lambda_{1})\frac{\partial}{\partial
R}(\lambda_{0}+\lambda_{1})$ $\displaystyle=$
$\displaystyle\frac{\partial}{\partial
R}H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})\,,$

where we have used that $H^{\prime}_{\mathrm{bin}}(p)$ is decreasing in $p$
for $p>1/2$, so we take $\alpha=0$ to obtain a bound. It follows that

$\displaystyle\left.\frac{\mathrm{d}g(t)}{\mathrm{d}t}\right|_{t=0}=\kappa\frac{\partial}{\partial
R}\Big{(}H_{\mathrm{bin}}(\lambda_{0}+\lambda_{1})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\Big{)}>0\,,$

where the inequality is Lemma 22.

Finally, the function

$S((\mathcal{N}^{*}\otimes\mathcal{I}_{E})(\sigma(t))=\frac{1}{2}\sum_{i,j}\epsilon_{ij}$

increases linearly with $t$ (the score is linear in $R$). ∎

######  Lemma 24.

For $\omega\in(\frac{3}{4},\frac{1}{2}(1+\frac{1}{\sqrt{2}}))$, the function
$G_{AB|X=0,Y=0,E}(\omega)$ is increasing in $\omega$.

###### Proof.

The proof follows the same lines as the previous lemma but with the entropy
changed. From Appendix C.1 we have

$H(AB|X=0,Y=0,E)=1+H_{\mathrm{bin}}(2\epsilon_{00})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\}).$

We have

$\displaystyle\frac{\partial}{\partial R}H_{\mathrm{bin}}(2\epsilon_{00})$
$\displaystyle=$ $\displaystyle
H^{\prime}_{\mathrm{bin}}(2\epsilon_{00})\frac{\cos(\theta)\cos(2(\alpha_{0}-\beta_{0}))+\sin(\theta)\cos(2(\alpha_{0}+\beta_{0}))}{2}$
(42) $\displaystyle\geq$ $\displaystyle
H^{\prime}_{\mathrm{bin}}\left(\frac{1}{2}+\frac{R}{2}(\cos(\theta)+\sin(\theta))\right)\frac{\cos(\theta)+\sin(\theta)}{2}$

and the remainder of the argument matches the previous proof. ∎

######  Lemma 25.

For $\omega\in(\frac{3}{4},\frac{1}{2}(1+\frac{1}{\sqrt{2}}))$ and any
distribution $p_{XY}$, the function $G_{AB|XYE}(\omega,p_{XY})$ is increasing
in $\omega$.

###### Proof.

The proof for this again follows those above, except in this case (see
Appendix C.2)

$\displaystyle H(AB|XYE)$ $\displaystyle=$ $\displaystyle
1+\sum_{xy}p_{XY}(x,y)H_{\mathrm{bin}}(2\epsilon_{xy})-H(\\{\lambda_{0},\lambda_{1},\lambda_{2},\lambda_{3}\\})\,.$
(43)

The bound that holds for $\epsilon_{00}$ in (42) holds for all
$\epsilon_{xy}$, and hence the rest of the argument goes through as before. ∎

##  Appendix E Entropy Accumulation Theorem

In this section we state the Entropy Accumulation Theorem (EAT). The theorem
is phrased in terms of a set of channels $\\{\mathcal{M}_{i}\\}_{i}$ called
EAT channels, where
$\mathcal{M}_{i}:\mathcal{S}(R_{i-1})\to\mathcal{S}(C_{i}D_{i}U_{i}R_{i})$.

######  Definition 4 (EAT Channels).

Let $\\{R_{i}\\}_{i=0}^{n}$ be arbitrary quantum systems and
$\\{C_{i}\\}_{i=1}^{n}$, $\\{D_{i}\\}_{i=1}^{n}$, and $\\{U_{i}\\}_{i=1}^{n}$
be finite dimensional classical systems. Suppose that $U_{i}$ is a
deterministic function of $C_{i}$, $D_{i}$ and that
$\\{\mathcal{M}_{i}\\}_{i=1}^{n}$,
$\mathcal{M}_{i}:\mathcal{S}(R_{i-1})\to\mathcal{S}(C_{i}D_{i}U_{i}R_{i})$ are
a set of quantum channels. These channels form a set of EAT channels if for
all $\rho_{R_{0}E}\in\mathcal{S}(R_{0}E)$ the state $\rho_{{\bf
CDU}R_{n}E}=(\mathcal{M}_{n}\circ\ldots\mathcal{M}_{1})(\rho_{R_{0}E})$ after
applying the channels satisfies $I(C_{1}^{i-1}:D_{i}|D_{1}^{i-1}E)=0$, where
$I$ is the mutual information, and $C_{1}^{i-1}$ is shorthand for
$C_{1}C_{2}\ldots C_{i-1}$.

In the context of DI algorithms, the quantum register $R_{0}$ can be taken to
represent the initial state of the devices, which may be entangled with the
register $E$. This state updates to $R_{1},R_{2},\ldots$ as the protocol
proceeds. At step $i$ the devices (together with the random number generators
$\mathcal{R}_{A}$ and $\mathcal{R}_{B}$) perform a map $\mathcal{M}_{i}$ to
give the output classical random variables and the random choices generated by
the random number generators. The mutual information condition encodes the
property that the random number generators are independent of $E$ and the
previously generated data. The register $U_{i}$ records the score in the Bell
game for that round. Along with the classical inputs, the channel
$\mathcal{M}_{i}$ also outputs the updated state of the devices represented by
the register $R_{i}$ which may be stored by the device and acted on by the
next channel121212In practice, the devices may be sent new states in each
round, but there is no loss in generality in assuming that the devices pre-
share all the entangled quantum resources they need for the protocol.. Each
EAT channel, therefore, for the DI protocols is a set of maps of the form

$\displaystyle\mathcal{M}_{i}(\rho)=\sum_{c,d}|c\rangle\\!\langle
c|\otimes|d\rangle\\!\langle d|\otimes|u(c,d)\rangle\\!\langle
u(c,d)|\otimes\mathcal{M}_{i}^{c,d}(\rho)\,,$ (44)

where $u(c,d)$ records the score in the Bell game, and each
$\mathcal{M}_{i}^{c,d}$ is a subnormalized quantum channel from
$\mathcal{S}(R_{i-1})$ to $\mathcal{S}(R_{i})$. The joint distribution of the
classical variables $C_{i}$ and $D_{i}$ is

$p_{C_{i}D_{i}}(c,d):=\mathrm{tr}(\mathcal{M}_{i}^{c,d}(\rho))\,.$ (45)

######  Definition 5 (Frequency distribution function).

Let ${\bf U}=U_{1}U_{2}\ldots U_{n}$ be a string of variables. The associated
frequency distribution is

$\mathrm{Freq}_{{\bf
U}}(u):=\frac{|\\{i\in\\{1,\ldots,n\\}:U_{i}=u\\}|}{n}\,.$ (46)

######  Definition 6.

Given a set of channels $\mathfrak{G}$ whose outputs have a register $U$, the
set of achievable score distributions is

$\mathcal{Q}_{\mathfrak{G}}:=\\{p_{U}:\mathcal{M}(\rho)_{U}=\sum_{u}p_{U}(u)|u\rangle\\!\langle
u|\text{ for some }\mathcal{M}\in\mathfrak{G}\\}.$ (47)

We also use

$\mathcal{Q}_{\mathfrak{G}}^{\gamma}:=\\{p_{U}:p_{U}(\bot)=(1-\gamma)\text{
and }p_{U}(u)=\gamma\tilde{p}_{U}(u)\text{ with
}\tilde{p}_{U}\in\mathcal{Q}_{\mathfrak{G}}\\}.$ (48)

######  Definition 7 (Rate function).

Let $\mathfrak{G}$ be a set of EAT channels. A _rate function_
$\mathrm{rate}:\mathcal{Q}_{\mathfrak{G}}\to\mathbb{R}$ is any function that
satisfies

$\displaystyle\mathrm{rate}(q)\leq\inf_{(\mathcal{M},\rho_{RE})\in\Gamma_{\mathfrak{G}}(q)}H(C|DE)_{(\mathcal{M}\otimes\mathcal{I}_{E})(\rho_{RE})}\,,$
(49)

where

$\Gamma_{\mathfrak{G}}(q):=\\{(\mathcal{M},\rho_{RE}):(\mathcal{M}\otimes\mathcal{I}_{E})(\rho_{RE})_{U}=\sum_{u}q(u)|u\rangle\\!\langle
u|\text{ for some }\mathcal{M}\in\mathfrak{G}\\}$ (50)

is the set of states and channels that can achieve distribution $q$.

######  Definition 8 (Min-tradeoff function).

A function $f:\mathcal{Q}_{\mathfrak{G}}\to\mathbb{R}$ is a _min-tradeoff
function_ if $f$ is an affine rate function. Since min-tradeoff functions are
affine, we can naturally extend their domain to all probability distributions
on $U$, denoted $\mathcal{P}$.

The entropy accumulation theorem then can be stated as follows (this is
Theorem 2 of Liu  _et al._ (2021), which is a generalization of the results of
Dupuis and Fawzi (2019)).

######  Theorem 2.

Let $f$ be a min-tradeoff function for a set of EAT channels
$\mathfrak{G}=\\{\mathcal{M}_{i}\\}_{i}$ and $\rho_{{\bf CDU}E}$ be the output
after applying these channels to initial state $\rho_{RE}$. In addition let
$\epsilon_{h}\in(0,1)$, $\alpha\in(1,2)$ and $r\in\mathbb{R}$ and $\Omega$ be
an event on ${\bf U}$ that implies $f(\mathrm{Freq}_{\bf U})\geq r$. We have

$\displaystyle H_{\min}^{\epsilon_{h}}({\bf C}|{\bf D}E)_{\rho_{{\bf
CD}E|\Omega}}>$ $\displaystyle
nr-\frac{\alpha}{\alpha-1}\log\left(\frac{1}{p_{\Omega}(1-\sqrt{1-\epsilon_{h}^{2}})}\right)+$
$\displaystyle
n\inf_{p\in\mathcal{Q}_{\mathfrak{G}}}\left(\Delta(f,p)-(\alpha-1)V(f,p)-(\alpha-1)^{2}K_{\alpha}(f)\right)\,,$
(51)

where $\Delta(f,p)=\mathrm{rate}(p)-f(p)$, and

$\displaystyle V(f,p)$ $\displaystyle=\frac{\ln
2}{2}\left(\log(1+2d_{C}^{2})+\sqrt{2+\mathrm{Var}_{p}(f)}\right)^{2}$
$\displaystyle K_{\alpha}(f)$ $\displaystyle=\frac{1}{6(2-\alpha)^{3}\ln
2}2^{(\alpha-1)(\log(d_{C})+\mathrm{Max}(f)-\mathrm{Min}_{\mathcal{Q}_{\mathfrak{G}}}(f))}\ln^{3}\left(2^{\log(d_{C})+\mathrm{Max}(f)-\mathrm{Min}_{\mathcal{Q}_{\mathfrak{G}}}(f)}+\operatorname{e}^{2}\right)\,,$

and we have also used

$\displaystyle\mathrm{Max}(f)$ $\displaystyle=\max_{p\in\mathcal{P}}f(p)$
$\displaystyle\mathrm{Min}_{\mathcal{Q}_{\mathfrak{G}}}(f)$
$\displaystyle=\inf_{p\in\mathcal{Q}_{\mathfrak{G}}}f(p)$
$\displaystyle\mathrm{Var}_{p}(f)$
$\displaystyle=\sum_{u}p(u)\left(f(\delta_{u})-\mathbb{E}(f(\delta_{u}))\right)^{2}\,,$

and $\delta_{u}$ is the deterministic distribution with outcome $u$.

To use this theorem we have to assign the variables $C_{i}$ and $D_{i}$ to the
parameters in the protocol.

###  E.1 Protocol with recycled input randomness (Protocol 3)

For this protocol we want to extract randomness from the inputs and outputs.
We hence set $C_{i}=A_{i}B_{i}X_{i}Y_{i}$ and take $D_{i}$ to be trivial. When
running a protocol, we do not generally know the set of EAT channels being
used (these are set by the adversary), but instead only know that they have
the no-signalling form, i.e., we have

$\mathcal{M}(\rho_{A^{\prime}B^{\prime}})=\sum_{abxy}|a\rangle\\!\langle
a|\otimes|b\rangle\\!\langle b|\otimes|x\rangle\\!\langle
x|\otimes|y\rangle\\!\langle y|\otimes|u(a,b,x,y)\rangle\\!\langle
u(a,b,x,y)|\otimes\mathcal{M}^{abxy}(\rho_{A^{\prime}B^{\prime}})\,,$

where
$\mathcal{M}^{abxy}(\rho_{A^{\prime}B^{\prime}})=p_{XY}(x,y)(\mathcal{E}^{x,a}\otimes\mathcal{F}^{y,b})(\rho_{A^{\prime}B^{\prime}})$
and $\\{\mathcal{E}^{x,a}\\}_{a}$ and $\\{\mathcal{F}^{y,b}\\}_{b}$ are
instruments on $A^{\prime}$ and $B^{\prime}$ respectively (cf. (44)).
Henceforth, the set $\mathfrak{G}$ will refer to all channels of this type.

In the CHSH protocol without spot-checking the rate function should be a lower
bound on $H(ABXY|E)=2+H(AB|XYE)$ and we can form our rate function via
$\mathrm{rate}(\\{1-s,s\\})=2+F_{AB|XYE}(s)$ or
$\mathrm{rate}(\\{1-s,s\\})=2+F_{A|XYE}(s)$, the former being preferred as it
is larger. A min-tradeoff function can then be obtained by taking the tangent
at some point. Since $F_{AB|XYE}(s)$ is linear for $3/4\leq
s\leq\omega_{AB|XYE}^{*}\approx 0.847$, for experimentally relevant scores we
can form the min-tradeoff function using the extension of this line to the
domain $[0,1]$, i.e., we can take
$f(\\{1-s,s\\})=2+G^{\prime}_{AB|XYE}(\omega^{*})(s-3/4)$ in Theorem 2 when
applying to Protocol 3, and in this case $d_{C}=d_{A}d_{B}d_{X}d_{Y}=16$ and
we get a bound on $H_{\min}^{\epsilon_{h}}({\bf ABXY}|E)$. The theorem holds
for all $\alpha\in(1,2)$ and we can optimize over $\alpha$ to increase the
bound.

###  E.2 Spot-checking CHSH protocol (Protocol 1)

To use the EAT in the spot-checking CHSH protocol (Protocol 1) we set
$C_{i}=A_{i}B_{i}$ and $D_{i}=X_{i}Y_{i}$ in Theorem 2. The channels again
have the no-signalling form mentioned above, and we can use either
$F_{AB|00E}$ or $F_{A|00E}$ as the basis of our rate function. Since the two-
sided version is larger, it is better to work with $F_{AB|00E}(s)$, and the
related min-tradeoff function based on taking its tangent at some point.
Modification is required to account for the spot-checking structure. If we let
$g_{t}(\\{1-s,s\\})$ be the tangent of $F_{AB|00E}(s)$ taken at $t$ then we
can form the spot-checking min-tradeoff functions

$\displaystyle
f_{t}(\delta_{u})=\begin{cases}\frac{1}{\gamma}g_{t}(\delta_{u})+(1-\frac{1}{\gamma})g_{t}(\delta_{1})&u\in\\{0,1\\}\\\
g_{t}(\delta_{1})&u=\bot\end{cases}\,.$

where $t$ can be chosen (see e.g. (Dupuis and Fawzi, 2019, Section 5) for the
argument behind this). Using this construction the following theorem can be
derived (this is an adaptation of Theorem 3 in Liu  _et al._ (2021)).

######  Theorem 3 (Entropy Accumulation Theorem for spot-checking CHSH
protocol).

Let $\rho_{{\bf ABXYU}E}$ be a CQ state obtained using the spot-checking CHSH
protocol (Protocol 1). Let $\Omega$ be the event
$\left|\\{i:U_{i}=0\\}\right|\leq n\gamma(1-\omega_{\exp}+\delta)$ with
$p_{\Omega}$ being the probability of this event in $\rho_{{\bf ABXYU}E}$, and
let $\rho_{{\bf ABXYU}E|\Omega}$ be the state conditioned on $\Omega$. Let
$\epsilon_{h}\in(0,1)$ and $\alpha\in(1,2)$. Then for any $r$ such that
$f_{t}(\mathrm{Freq}_{\bf U})\geq r$ for all events in $\Omega$ we have

$\displaystyle H^{\epsilon_{h}}_{\min}({\bf AB}|{\bf XY}E)_{\rho_{{\bf
ABXY}E|\Omega}}>$ $\displaystyle
nr-\frac{\alpha}{\alpha-1}\log\left(\frac{1}{p_{\Omega}(1-\sqrt{1-\epsilon_{h}^{2}})}\right)$
(53)
$\displaystyle+n\inf_{p\in\mathcal{Q}^{\gamma}_{\mathfrak{G}}}(\Delta(f_{t},p)-(\alpha-1)V(f_{t},p)-(\alpha-1)^{2}K_{\alpha}(f_{t}))\,,$

where

$\displaystyle\Delta(f_{t},p)$ $\displaystyle:=$ $\displaystyle
F_{AB|XYE}(p(1)/\gamma)-f_{t}(p)$ (54) $\displaystyle V(f_{t},p)$
$\displaystyle=$ $\displaystyle\frac{\ln
2}{2}\left(\log(33)+\sqrt{\mathrm{Var}_{p}(f_{t})+2}\right)^{2}$ (55)
$\displaystyle K_{\alpha}(f_{t})$ $\displaystyle=$
$\displaystyle\frac{1}{6\log(2-\alpha)^{3}\ln
2}2^{(\alpha-1)(2+\mathrm{Max}(f_{t})-\mathrm{Min}_{\mathcal{Q}^{\gamma}_{\mathfrak{G}}}(f_{t}))}\ln^{3}(2^{2+\mathrm{Max}(f_{t})-\mathrm{Min}_{\mathcal{Q}^{\gamma}_{\mathfrak{G}}}(f_{t})}+\operatorname{e}^{2}).$

To use this theorem we can take
$r=(F_{AB|00E}(t)+(\omega_{\exp}-\delta-t)F^{\prime}_{AB|00E}(t))$ (cf. the