# De Finetti Theorems for Quantum Conditional Probability Distributions with
Symmetry

Sven Jandura  Institute for Theoretical Physics, ETH Zurich, 8093 Zurich,
Switzerland  Ernest Y.-Z. Tan  Institute for Theoretical Physics, ETH Zurich,
8093 Zurich, Switzerland

###### Abstract

The aim of device-independent quantum key distribution (DIQKD) is to study
protocols that allow the generation of a secret shared key between two parties
under minimal assumptions on the devices that produce the key. These devices
are merely modeled as black boxes and mathematically described as conditional
probability distributions. A major obstacle in the analysis of DIQKD protocols
is the huge space of possible black box behaviors. De Finetti theorems can
help to overcome this problem by reducing the analysis to black boxes that
have an iid structure. Here we show two new de Finetti theorems that relate
conditional probability distributions in the quantum set to de Finetti
distributions (convex combinations of iid distributions), that are themselves
in the quantum set. We also show how one of these de Finetti theorems can be
used to enforce some restrictions onto the attacker of a DIQKD protocol.
Finally we observe that some desirable strengthenings of this restriction, for
instance to collective attacks only, are not straightforwardly possible.

##  1 Introduction

The aim of quantum key distribution is to establish a shared key between two
parties, commonly called Alice and Bob, that is unknown to any third party,
commonly called Eve. To achieve this goal, Alice and Bob can share an
entangled quantum state and use the correlated outcomes of measurements on
this state to generate a secure key pair via a postprocessing protocol. If Eve
has tampered with the shared state, Alice and Bob either notice this and abort
the protocol, or are able to generate a secure key pair anyway[1, 2, 3]. In
device-independent quantum key distribution (DIQKD) we assume that Eve has not
only control over the shared state, but is also able to manipulate the devices
that Alice and Bob use to measure the state. As long as the devices are not
manipulated in a way that sends information out of Alice’s and Bob’s
laboratories through channels other than those controlled by Alice and Bob,
there are still protocols that allow for the generation of a shared secret key
[4, 5, 6, 7, 8].

In the device-independent context, the devices of Alice and Bob are treated as
black boxes and modeled by a conditional probability distribution $P_{AB|XY}$.
Alice and Bob can give inputs $x$ and $y$ respectively to the box, and receive
outputs $a$ and $b$ with probability $P_{AB|XY}(ab|xy)$. We will often write
$P(ab|xy)$ instead of $P_{AB|XY}(ab|xy)$ when the random variables $A$, $B$,
$X$ and $Y$ are implicitly understood. In the device dependent case the inputs
corresponds to the choice of measurement basis, and the outputs to the results
of the measurement. We will denote the sets of possible inputs by
$\mathcal{X}$ and $\mathcal{Y}$, and the sets of outputs by $\mathcal{A}$ and
$\mathcal{B}$. If the inputs and outputs are strings of length $n$, i.e.
$\mathcal{X}=\hat{\mathcal{X}}^{n}$ and analogously for $\mathcal{Y}$,
$\mathcal{A}$ and $\mathcal{B}$ we call $P_{AB|XY}$ an $n$-round box. If
$Q_{\hat{A}\hat{B}|\hat{X}\hat{Y}}$ is a box with inputs and outputs in
$\hat{\mathcal{X}},\hat{\mathcal{Y}},\hat{\mathcal{A}},\hat{\mathcal{B}}$ we
denote by $Q^{\otimes n}_{AB|XY}$ the $n$-round iid box with

$Q^{\otimes n}(ab|xy)=\prod_{i=1}^{n}Q(a_{i}b_{i}|x_{i}y_{i}).$ (1)

For a large class of DIQKD protocols, those with one-way postprocessing [3],
the entropy accumulation theorem (EAT) [9] can be used to essentially reduce
the analysis of arbitrary boxes (obeying time-ordered behaviour) to the iid
scenario [8]. Alternatively, the techniques in [10, 11] can be used to obtain
security proofs for this class of protocols even when the boxes accept all
inputs in parallel, though the resulting asymptotic keyrates are lower than in
the iid case. There are however protocols that don’t only use one-way
postprocessing (broadly referred to as advantage distillation protocols [12,
13, 14, 15, 3, 16]), and hence do not admit a security proof via these
approaches. In the security proof of those protocols, so-called de Finetti
theorems may be a promising tool, as they were in the case of device-dependent
QKD [17]. De Finetti theorems allow us to relate the entries of an arbitrary
permutation invariant box to the entries of a de Finetti box (a convex
combination of iid boxes). De Finetti theorems where originally developed for
random variables [18] and then extended to quantum states [19, 20, 21, 3] and
boxes [22, 23]. For example, in [22] it was shown that for each $\mathcal{A}$
and $\mathcal{X}$ there exists a de Finetti box $\tau_{A|X}$ such that for all
permutation invariant boxes $P_{A|X}$ it holds that

$\forall a,x\qquad P(a|x)\leq(n+1)^{|\mathcal{X}|(|\mathcal{A}|-1)}\tau(a|x).$
(2)

(Here we treat the inputs and outputs of Alice and Bob as lumped together to a
single input and output).

Not all boxes $P_{AB|XY}$ describe processes that are physically possible if
we assume that no information can leave the laboratories of Alice and Bob. All
boxes must then be such that Bob gains no information about the Alice’s input
from his output, and vice versa. We refer to boxes satisfying this constraint
as non-signaling:

######  Definition 1.

A box $P_{AB|XY}$ is non-signaling if

$\displaystyle\forall b,y,x,x^{\prime}\qquad\sum_{a}P(ab|xy)$
$\displaystyle=\sum_{a}P(ab|x^{\prime}y)$ (3) $\displaystyle\forall
a,x,y,y^{\prime}\qquad\sum_{b}P(ab|xy)$
$\displaystyle=\sum_{b}P(ab|xy^{\prime}).$ (4)

If we furthermore assume that the boxes are described by quantum theory, we
can describe the distribution $P_{AB|XY}$ by some quantum state shared between
Alice and Bob and some POVMs describing their measurements.

######  Definition 2.

A box $P_{AB|XY}$ is quantum if there are Hilbert spaces $\mathcal{H}_{A}$,
$\mathcal{H}_{B}$, a state
$\rho_{AB}\in\mathrm{End}\left(\mathcal{H}_{A}\otimes\mathcal{H}_{B}\right)$,
for each $x$ a POVM $\left\\{E^{a,x}|a\right\\}$ and for each $y$ a POVM
$\left\\{F^{b,y}|b\right\\}$ such that

$P(ab|xy)=\mathrm{tr}\left[\rho_{AB}\left(E^{a,x}\otimes
F^{b,y}\right)\right].$ (5)

The set of quantum boxes is a proper subset of the set of non-signaling boxes.
That both sets are not identical is demonstrated by the Popescue-Rohrlich box
[24].

For the de Finetti theorems for boxes in [22, 23], the de Finetti boxes cannot
be restricted to the quantum set even if the original permutation invariant
boxes are quantum. However, many security proofs for DIQKD protocols exploit
the properties of the quantum set [5, 6, 7, 25]. In this paper we show two de
Finetti theorems for Clauser-Horne-Shimony-Holt (CHSH) symmetric quantum boxes
(see definition 4), such that the de Finetti box is quantum as well. We
further show how the first de Finetti theorem could be used in the security
proofs of DIQKD protocols.

The rest of this paper is structured as follows: In section 2.1 we show the
first de Finetti theorem (theorem 6). It is similar to eq. (2) and shows that
the entries of a CHSH symmetric quantum box are upper bounded, up to a factor
polynomial in $n$, by the entries of a fixed quantum de Finetti box. In
section 2.2 we then show the second de Finetti theorem (theorem 10), which is
closer to the original de Finetti theorems for random variables and quantum
states. It states that the marginal of the the first $k$ rounds of a $n$-round
CHSH symmetric quantum box is close to (and not just upper bounded by) a
quantum de Finetti box. Our results in this section rely on the existence of
appropriate threshold theorems (see e.g. theorem 7 below). A natural question
is whether it is possible to derive them without using the threshold theorems;
however, we show in appendix B that proving a de Finetti theorem of the first
form is essentially equivalent to proving a threshold theorem, hence it would
be a result of comparable difficulty.

In light of this, our results cannot currently be used as an alternative
method to prove threshold theorems. However, our focus is more on the
application of these results for DIQKD security proofs. Hence in section 3, we
present an application of the first de Finetti theorem to bound the diamond
distance between two channels acting on boxes. (We also elaborate there on
some difference between our results and the security proofs of [10, 11], which
were also based on threshold theorems or similar results.) The diamond
distance measures how well these two channels can be distinguished by an
attacker. Since the security of a DIQKD protocol is related to the diamond
distance between the protocol and an ideal channel [26, 27], bounds on the
diamond distance can be useful in DIQKD security proofs. We show that to prove
security of a DIQKD protocol against arbitrary (so-called coherent [28])
quantum attacks it is sufficient to prove security against an adversary who
holds an extension of a fixed quantum de Finetti box (theorem 14). However,
this extension may not be quantum itself and can only be restricted to the
non-signaling set.

In section 4 we show that the result from section 3 cannot be strengthened to
restrict the attacker further to collective attacks [28] (attacks where the
black box can be described by an iid quantum state and iid measurements for
Alice and Bob, see definition 15). For this, we construct two channels that
cannot be distinguished at all using boxes compatible with collective attacks,
but can be distinguished if arbitrary quantum boxes are available (theorem
16). This shows that the theorem from section 3 cannot be immediately used to
conclude security against coherent attacks from security against collective
attacks.

##  2 De Finetti Theorems for boxes with CHSH symmetry

###  2.1 The first de Finetti theorem

Let us first define de Finetti boxes and CHSH symmetry:

######  Definition 3.

A $n$-round box $\tau_{AB|XY}$ is called de Finetti if it is the convex
combination of iid boxes.

######  Definition 4.

An $n$-round box $P_{AB|XY}$ with single round inputs and outputs in
$\mathcal{A}=\mathcal{B}=\mathcal{X}=\mathcal{Y}=\\{0,1\\}$ is called CHSH
symmetric if

$P(ab|xy)=P(a^{\prime}b^{\prime}|x^{\prime}y^{\prime})\qquad\text{ whenever
}\left\lVert a\oplus b\oplus xy\right\rVert_{0}=\left\lVert a^{\prime}\oplus
b^{\prime}\oplus x^{\prime}y^{\prime}\right\rVert_{0}.$ (6)

Here $\left\lVert x\right\rVert_{0}$ denotes the number of non-zero entries of
a $n$-bit string $x$.

If for an index $i$ we have $a_{i}\oplus b_{i}=x_{i}y_{i}$ we say that the
CHSH game is won in round $i$ [29]. Thus, definition 4 basically states that a
box is CHSH symmetric if its entries $P(ab|xy)$ only depends on how many
indices the CHSH game was won. Our definition of CHSH symmetry differs
slightly from the one in [22], where it is only required that
$P(ab|xy)=P(a^{\prime}b^{\prime}|x^{\prime}y^{\prime})$ whenever $a\oplus
b\oplus xy=a^{\prime}\oplus b^{\prime}\oplus x^{\prime}y^{\prime}$. Our
definition agrees with the definition in [22] for permutation symmetric boxes
— essentially, we have implicitly incorporated the constraint of permutation
symmetry into definition 4 itself.

Of course an attacker can initially manipulate the boxes of Alice and Bob such
that they do not possess CHSH symmetry. However, Alice and Bob can run the
following procedure to enforce CHSH symmetry: First Alice chooses a random
permutation $\pi$ and transmits it to Bob over the authenticated channel, then
Alice and Bob permute their inputs and outputs according to $\pi$. If we view
the original box as a conditional probability distribution $P_{ABE|XYZ}$ for
Alice, Bob and Eve we can view $\pi$ as additional knowledge of Eve and
describe the box after the permutation has been applied by
$\tilde{P}_{ABEE^{\prime}|XYZ}$. Then the marginal $\tilde{P}_{AB|XY}$ has
permutation symmetry. To go from permutation symmetry to CHSH symmetry Alice
and Bob apply the depolarization protocol described in appendix A of [30] to
each round. If the box in the honest implementation of the DIQKD protocol has
CHSH symmetry it is unchanged by this depolarization protocol. It is important
to note that only the marginal box of Alice and Bob has CHSH symmetry after
this protocol: from the perspective of Eve, who knows the permutation $\pi$
and the random bits chosen in the depolarization protocol in [30], the box may
not have CHSH symmetry.

It was shown in [22] that a de Finetti theorem holds for CHSH symmetric boxes:

######  Theorem 5 (Corollary 6 in [22]).

For each number $n$ of rounds there is an $n$-round CHSH symmetric de Finetti
box $\tau_{AB|XY}$ such that for all CHSH symmetric boxes $P_{AB|XY}$ it holds
that

$P(ab|xy)\leq(n+1)\tau(ab|xy).$ (7)

Theorem 7 was derived for all CHSH symmetric boxes $P_{AB|XY}$, even if they
are not quantum. However, the de Finetti box $\tau_{AB|XY}$ constructed in the
theorem is also not quantum. The main result we derive in this section is a de
Finetti theorem for _quantum_ CHSH symmetric boxes, hence resolving this
issue:

######  Theorem 6.

For each number $n$ of rounds there is an $n$-round CHSH symmetric quantum de
Finetti box $\tau_{AB|XY}$ such that for all CHSH symmetric quantum boxes
$P_{AB|XY}$ it holds that

$P(ab|xy)\leq(n+1)^{2}\tau(ab|xy).$ (8)

The maximal probability with which any single round quantum box can win the
CHSH game is $w=\frac{2+\sqrt{2}}{4}$ [31]. This value is called the quantum
value of the CHSH game. To prove theorem 6 we need the following
specialization of a theorem from [32] to the CHSH case. It says that the
probability that the fraction of won CHSH games is larger than a certain
threshold (namely the value of the CHSH game) is exponentially small in $n$.
Such theorems are commonly referred to as _threshold theorems_.111To be
precise, theorem 7 is a “perfect” threshold theorem, in that the exponent in
the bound (9) is such that the bound is, up to a factor polynomial in $n$,
equal to $\binom{n}{k}w^{k}(1-w)^{n-k}$, the probability to win exactly $k$
games if a single game is won with probability $w$. “Imperfect” threshold
theorems can be roughly described as giving bounds of the more general form
$e^{-n\Delta(k/n)}$, where $\Delta$ is some potentially “looser” way to
quantify the distance from $k/n$ to $w$ [33]. Our first de Finetti theorem
(theorem 6) and its generalization (theorem 21) both require a perfect
threshold theorem. However, the proof of our second de Finetti theorem
(theorem 10) still holds with an imperfect threshold theorem, though the
resulting bound would be weaker.

######  Theorem 7 (Theorem 5 in [32]).

Let $P_{AB|XY}$ be an $n$-round box with single round inputs and outputs in
$\\{0,1\\}$. Let $\mu$ be the uniform probability distribution on
$\\{0,1\\}^{2}$ and $K=||A\oplus B\oplus XY\oplus\mathbf{1}||_{0}$ the number
of won instances of the CHSH game. Let $w=\frac{2+\sqrt{2}}{4}$ the quantum
value of the CHSH game. Then for $k>wn$

$\mathrm{Pr}_{P_{AB|XY},\mu^{\otimes n}}[K\geq k]\leq
e^{-nD(k/n,1-k/n||w,1-w)},$ (9)

where $\mathrm{Pr}_{P_{AB|XY},\mu^{\otimes n}}$ denotes the probability
measure in which $X$ and $Y$ are sampled from $\mu^{\otimes n}$ and $A$ and
$B$ are sampled using $P_{AB|XY}$ and

$D(p,1-p||q,1-q)=p\ln\left(\frac{p}{q}\right)+(1-p)\ln\left(\frac{1-p}{1-q}\right)$
(10)

denotes the relative entropy.

Note that the box $P_{AB|XY}$ in theorem 7 does not have to be CHSH symmetric.
However, if $P_{AB|XY}$ is CHSH symmetric then we can describe it completely
by $n+1$ parameters $\\{p_{0},p_{1},\dots,p_{n}\\}$, which we define as
follows: for each $k\in\\{0,...,n\\}$, take any $a,b,x,y\in\\{0,1\\}^{n}$ such
that $k=||a\oplus b\oplus xy\oplus\mathbf{1}||_{0}$ (in other words, $a,b,x,y$
win exactly $k$ instances of the CHSH game). Then define

$p_{k}=\binom{n}{k}2^{n}P(ab|xy).$ (11)

By CHSH symmetry, all combinations of $a,b,x,y$ with the same value of $k$
have the same value of $P(ab|xy)$, so the expression (11) is indeed well-
defined. The normalization factor $\binom{n}{k}2^{n}$ is chosen to give these
parameters a simple interpretation: namely, $p_{k}$ is in fact equal to the
probability of winning exactly $k$ CHSH games for the box $P(ab|xy)$
(regardless of the input distribution). To see this, notice that for fixed
$x$, $y$ and $k$ there are exactly $\binom{n}{k}2^{n}$ pairs $a,b$ such that
$k=||a\oplus b\oplus xy\oplus 1||_{0}$ [22]. Therefore for any probability
measure $\mu$ on the $n$-round inputs $x$ and $y$, we indeed have

$\displaystyle\mathrm{Pr}_{P_{AB|XY},\mu}[K=k]$
$\displaystyle=\sum_{\begin{subarray}{c}a,b,x,y\\\ k=||a\oplus b\oplus
xy\oplus\mathbf{1}||_{0}\end{subarray}}P(ab|xy)\mu(xy)$
$\displaystyle=\sum_{xy}\binom{n}{k}2^{n}\frac{p_{k}}{\binom{n}{k}2^{n}}\mu(xy)$
(12) $\displaystyle=p_{k}$

where in the second equality we used that the summand does not depend on $a$
and $b$, and for a fixed $x$ and $y$ there are $\binom{n}{k}2^{n}$ possible
$a$ and $b$ with $\left\lVert a\oplus b\oplus
xy\oplus\mathbf{1}\right\rVert_{0}=k$. Theorem 7 then implies

$\sum_{l\geq k}p_{l}\leq e^{-nD(k/n,1-k/n||w,1-w)}.$ (13)

To prove theorem 6 we need one further ingredient:

######  Lemma 8.

Let $a,b\in\mathbb{R}$ with $a<b$ and $f:[a,b]\rightarrow\mathbb{R}^{+}_{0}$
be a concave function that attains its maximum at some $x^{*}\in[a,b]$. Then
$\forall n\in\mathbb{N}$,

$\frac{1}{n+1}(b-a)f(x^{*})^{n}\leq\int_{a}^{b}f(x)^{n}\mathrm{d}x\leq(b-a)f(x^{*})^{n}$
(14)

The proof is given in appendix A. Now we are ready to prove theorem 6:

###### Proof of theorem 6.

Let $w=\frac{2+\sqrt{2}}{4}$ be the quantum value of the CHSH game and define
for $p\in[1-w,w]$ the single round box $Q(p)_{AB|XY}$ as

$Q(p)(ab|xy)=\begin{cases}p/2&\text{ if }a\oplus b=xy\\\ (1-p)/2&\text{ if
}a\oplus b\neq xy\end{cases}$ (15)

Now set

$\tau_{AB|XY}=\frac{1}{2w-1}\int_{1-w}^{w}Q(p)_{AB|XY}^{\otimes
n}\mathrm{d}p.$ (16)

$\tau_{AB|XY}$ is quantum because each $p\in[1-w,w]$ $Q(p)_{AB|XY}^{\otimes
n}$ is quantum. Further $\tau_{AB|XY}$ is de Finetti by construction. Let
$a,b,x,y\in\\{0,1\\}^{n}$ and let $k=\left\lVert a\oplus b\oplus
xy\oplus\mathbf{1}\right\rVert_{0}$ be the number of won CHSH games of
$a,b,x,y$. Let $\alpha=k/n$ and set

$f(p)=\frac{1}{2}p^{\alpha}(1-p)^{1-\alpha}.$ (17)

Then

$\tau(ab|xy)=\frac{1}{2w-1}\int_{1-w}^{w}2^{-n}p^{k}(1-p)^{n-k}\mathrm{d}p=\frac{1}{2w-1}\int_{1-w}^{w}f(p)^{n}\mathrm{d}p.$
(18)

Note that

$f^{\prime}(p)=\left(\frac{\alpha}{p}-\frac{1-\alpha}{1-p}\right)f(p)$ (19)

and

$\displaystyle f^{\prime\prime}(p)$
$\displaystyle=\left[\left(\frac{\alpha}{p}-\frac{1-\alpha}{1-p}\right)^{2}-\frac{\alpha}{p^{2}}-\frac{1-\alpha}{(1-p)^{2}}\right]f(p)$
$\displaystyle=-\frac{\alpha(1-\alpha)}{p^{2}(1-p)^{2}}f(p)<0.$ (20)

Therefore, $f$ is concave and its maximum on the interval $[0,1]$ occurs at
$p=\alpha$.

Since $f$ is concave, we can apply lemma 8 to eq. (18) and get

$\tau(ab|xy)\geq\frac{1}{n+1}\sup_{p\in[1-w,w]}f(p)^{n}.$ (21)

Now we turn to the box $P_{AB|XY}$. Following the earlier notation, let
$p_{k}$ denote the probability of winning exactly $k$ CHSH games with this
distribution. We observe that

  * •

If $\alpha>w$ then, the threshold theorem 7 implies

$p_{k}\leq e^{-nD(\alpha,1-\alpha||w,1-w)}.$ (22)

  * •

If $\alpha<1-w$ we can use the threshold theorem to get a bound on the minimal
number of won games, because the CHSH game has the property that winning
exactly $k$ games is just as hard as losing exactly $k$ games (and thus
winning $n-k$ games). Hence we have

$p_{k}\leq e^{-nD(\alpha,1-\alpha||1-w,w)}.$ (23)

  * •

If $\alpha\in[1-w,w]$ we can rewrite the trivial bound $p_{k}\leq 1$ in the
form

$p_{k}\leq 1=e^{-nD(\alpha,1-\alpha||\alpha,1-\alpha)}.$ (24)

Hence we can summarize the implications of the threshold theorem as

$p_{k}\leq\sup_{p\in[1-w,w]}e^{-nD(\alpha,1-\alpha||p,1-p)}.$ (25)

We can simplify the term in the supremum by inserting the definition of
relative entropy:

$e^{-nD(\alpha,1-\alpha||p,1-p)}=\left(\frac{p}{\alpha}\right)^{\alpha
n}\left(\frac{1-p}{1-\alpha}\right)^{(1-\alpha)n}=\frac{f(p)^{n}}{f(\alpha)^{n}}.$
(26)

Now recall that by equation (11), $P(ab|xy)$ is related to $p_{k}$ by

$P(ab|xy)=\frac{p_{k}}{2^{n}\binom{n}{k}}.$ (27)

It is a well known identity of the Beta function that

$\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}t^{k}(1-t)^{n-k}\mathrm{d}t=2^{n}(n+1)\int_{0}^{1}f(p)^{n}\mathrm{d}p\leq
2^{n}(n+1)f(\alpha)^{n}$ (28)

where for the last inequality we used lemma 8 and the fact that the maximum of
$f$ on $[0,1]$ is $f(\alpha)$. Inserting eq. (28) followed by (25)–(26) into
eq. (27) gives

$P(ab|xy)\leq(n+1)p_{k}f(\alpha)^{n}\leq(n+1)\sup_{p\in[1-w,w]}f(p)^{n}.$ (29)

Combining eq. (21) and eq. (29) yields $P(ab|xy)\leq(n+1)^{2}\tau(ab|xy)$, as
desired. ∎

The arguments in the proof of theorem 6 are not specific to CHSH symmetry. In
fact, in appendix B we show that we get such a de Finetti theorem whenever a
threshold theorem analogous to theorem 7 holds.

###  2.2 The second de Finetti theorem

The de Finetti theorem discussed in the previous section is similar to the de
Finetti theorems for boxes shown in [22]; they show that the entries of some
given box are _upper bounded_ by the entries of a de Finetti box. The original
de Finetti theorems for random variables and quantum states are of a different
flavor: They show that the marginal on the first $k$ rounds of an arbitrary
$n$-round permutation invariant state is _close_ to a de Finetti state if
$k\ll n$. In this section we show a theorem of this type for CHSH symmetric
boxes. We use the following distance measure on the space of boxes:

######  Definition 9.

Let $P_{A|X}$ and $Q_{A|X}$ be two boxes with the same input set $\mathcal{X}$
and output set $\mathcal{A}$. Their distance is

$\left\lVert
P_{A|X}-Q_{A|X}\right\rVert=\max_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}|P(a|x)-Q(a|x)|.$
(30)

This distance is just the $\ell^{1}$ distance of the probability distributions
of $a$, maximized over the input $x$. Now we can state the de Finetti theorem:

######  Theorem 10.

Let $P_{AB|XY}$ be an $n$-round CHSH symmetric quantum box. Denote by
$P^{k}_{AB|XY}$ the marginal of the first $k$ rounds. There is a $k$-round
CHSH symmetric quantum de Finetti box $\tau_{AB|XY}$ such that

$\left\lVert
P^{k}_{AB|XY}-\tau_{AB|XY}\right\rVert\leq\left(C\sqrt{\ln(n/k)}+4\right)\sqrt{\frac{k}{n}}+\frac{4k}{n}=\mathcal{O}\left(\sqrt{\ln(n/k)\frac{k}{n}}\right)$
(31)

with $C=\frac{2}{\sqrt{2-\sqrt{2}}}\approx 2.6$.

For the proof of theorem 10 we first note that the distance between two CHSH
symmetric boxes is just the $\ell^{1}$ distance between the distributions of
the wins and losses of the CHSH game, which are independent from the input
into the box.

######  Lemma 11.

Let $P_{AB|XY}$ and $Q_{AB|XY}$ be CHSH symmetric $n$-round boxes and
$W=A\oplus B\oplus XY\oplus\mathbf{1}\in\\{0,1\\}^{n}$ be the random variable
that indicates in which rounds the CHSH game was won. Let $P_{W}$ and $Q_{W}$
the distribution of $W$. Then

$\left\lVert P_{AB|XY}-Q_{AB|XY}\right\rVert=\left\lVert
P_{W}-Q_{W}\right\rVert_{1}.$ (32)

###### Proof.

For all $x,y$

$P(ab|xy)=2^{-n}P_{W}(a\oplus b\oplus xy\oplus\mathbf{1})$ (33)

so

$\sum_{a,b}|P(ab|xy)-Q(ab|xy)|=\sum_{a,w}2^{-n}|P_{W}(w)-Q_{W}(w)|=\left\lVert
P_{W}-Q_{W}\right\rVert_{1}.$ (34)

∎

Another ingredient for the proof of theorem 10 is a bound on the
$\ell^{1}$-distance between two binomial distributions:

######  Lemma 12.

Let $k\in\mathbb{N}$ and $p,q\in(0,1)$. Denote by $P=\mathrm{Binom}(k,p)$ and
$Q=\mathrm{Binom}(k,q)$ the binomial distributions with $k$ trials and success
probabilities $p$ and $q$. Then

$\left\lVert P-Q\right\rVert_{1}\leq 2\sqrt{\frac{n}{\min\\{q,1-q\\}}}|p-q|.$
(35)

###### Proof.

Denote by $P_{0}$ and $Q_{0}$ the Bernoulli distributions with success
probability $p$ and $q$ respectively. We use Pinsker’s inequality and the
reverse Pinsker’s inequality (Lemma 4.1 in [34]) to calculate

$\displaystyle\left\lVert P-Q\right\rVert_{1}$
$\displaystyle\leq\sqrt{2D(P||Q)}$ Pinsker’s inequality
$\displaystyle=\sqrt{2nD(P_{0}||Q_{0})}$ additivity of relative entropy
$\displaystyle\leq\sqrt{\frac{n\left\lVert
P_{0}-Q_{0}\right\rVert_{1}^{2}}{\min\\{q,1-q\\}}}$ reverse Pinsker’s
inequality $\displaystyle=2\sqrt{\frac{n}{\min\\{q,1-q\\}}}|p-q|.$ (36)

∎

Now we are ready to prove the de Finetti theorem:

###### Proof of theorem 10.

Denote by $p_{N}$ the probability that Alice and Bob win exactly $N$ CHSH
games on the box $P_{AB|XY}$. Then $W=A\oplus B\oplus XY\oplus\mathbf{1}$ has
a permutation invariant distribution $P_{W}$ with

$\sum_{w:\sum_{i}w_{i}=N}P_{W}(w)=p_{N}.$ (37)

By the the de Finetti theorem for random variables [18] we have

$\left\lVert
P^{k}_{W}-\sum_{N=0}^{n}p_{N}\mathrm{Binom}\left(k,\frac{N}{n}\right)\right\rVert\leq\frac{4k}{n}.$
(38)

where $P^{k}_{W}$ denotes the distribution of the first $k$ bits of $W$.

For $p\in[0,1]$ denote by $Q(p)_{AB|XY}$ the single-round box with CHSH
winning probability $p$. Then by lemma 11 and eq. (38)

$\left\lVert
P^{k}_{AB|XY}-\sum_{N=0}^{n}p_{N}Q\left(\frac{N}{n}\right)^{\otimes
k}\right\rVert\leq\frac{4k}{n}$ (39)

The box $\sum_{N=0}^{n}p_{N}Q\left(\frac{N}{n}\right)^{\otimes k}$ is CHSH
symmetric and de Finetti, but not quantum. The problems are the terms with
$N>nw$ and $N<n(1-w)$, where $w=\frac{2+\sqrt{2}}{4}$. We define a quantum
CHSH symmetric de Finetti box as

$\tau_{AB|XY}=\sum_{N=0}^{n}p_{N}\begin{cases}Q(w)^{\otimes k}&\text{ if
}N>wn\\\ Q\left(\frac{N}{n}\right)^{\otimes k}&\text{ if }N\in[(1-w)n,wn]\\\
Q(1-w)^{\otimes k}&\text{ if }N<(1-w)n\end{cases}.$ (40)

We will show

$\left\lVert\tau_{AB|XY}-\sum_{N=0}^{n}p_{N}Q\left(\frac{N}{n}\right)^{\otimes
k}\right\rVert\leq\left(C\sqrt{\ln(n/k)}+4\right)\sqrt{\frac{k}{n}}.$ (41)

The statement of theorem 10 then follows by combining this bound and the bound
in eq. (39) using the triangle inequality.

Let $\delta>0$. We split the sum in the definition of $\tau_{AB|XY}$ to obtain

$\displaystyle\left\lVert\tau_{AB|XY}-\sum_{N=0}^{n}p_{N}Q\left(\frac{N}{n}\right)^{\otimes
k}\right\rVert$ $\displaystyle\leq\sum_{N\in[wn,n]}p_{N}\left\lVert
Q(w)^{\otimes k}-Q\left(\frac{N}{n}\right)^{\otimes k}\right\rVert$
$\displaystyle+\sum_{N\in[0,(1-w)n]}p_{N}\left\lVert Q(1-w)^{\otimes
k}-Q\left(\frac{N}{n}\right)^{\otimes k}\right\rVert$ (42)
$\displaystyle\leq\sum_{N\in[wn,(w+\delta)n]}p_{N}\left\lVert Q(w)^{\otimes
k}-Q(w+\delta)^{\otimes k}\right\rVert$
$\displaystyle+\sum_{N\in[(1-w-\delta)n,(1-w)n]}p_{N}\left\lVert
Q(1-w)^{\otimes k}-Q(1-w-\delta)^{\otimes k}\right\rVert$
$\displaystyle+2\sum_{N\in[0,(1-w-\delta)n]\cup[(w+\delta)n,n]}p_{N}$

where in the last line we used $\left\lVert
P_{AB|XY}-Q_{AB|XY}\right\rVert\leq 2$ for all normalized boxes $P_{AB|XY}$
and $Q_{AB|XY}$. We start by bounding the terms with $N\in[wn,(w+\delta)n]$
and $N\in[(1-w-\delta)n,(1-w)n]$ using lemma 12:

$\displaystyle\left\lVert Q(w)^{\otimes k}-Q(w+\delta)^{\otimes
k}\right\rVert\leq\frac{2}{\sqrt{1-w}}\sqrt{k}\delta=2C\sqrt{k}\delta$ (43)

where we used $\frac{2}{\sqrt{1-w}}=\frac{4}{\sqrt{2-\sqrt{2}}}=2C$.
Analogously we find

$\left\lVert Q(1-w)^{\otimes k}-Q(1-w-\delta)^{\otimes k}\right\rVert\leq
2C\sqrt{k}\delta$ (44)

so that by $\sum_{N}p_{N}=1$

$\displaystyle\sum_{N\in[wn,(w+\delta)n]}p_{N}\left\lVert Q(w)^{\otimes
k}-Q(w+\delta)^{\otimes k}\right\rVert$
$\displaystyle+\sum_{N\in[(1-w-\delta)n,(1-w)n]}p_{N}\left\lVert
Q(1-w)^{\otimes k}-Q(1-w-\delta)^{\otimes k}\right\rVert$ $\displaystyle\leq
2C\sqrt{k}\delta.$ (45)

Now we turn to the terms with $N>(w+\delta)n$ and $N<(1-w-\delta)n$. By the
threshold theorem for the CHSH game (theorem 7) it holds that

$\displaystyle\sum_{N>(w+\delta)n}p_{N}$ $\displaystyle\leq
e^{-nD(w+\delta,1-w-\delta||w,1-w)}$ (46) $\displaystyle\leq
e^{-2n\delta^{2}}$ (47)

where in the last step we used Pinsker’s inequality, i.e $D(p,1-p||q,1-q)\geq
2|p-q|^{2}$. Analogously also

$\sum_{N<(1-w-\delta)n}p_{N}\leq e^{-2n\delta^{2}}.$ (48)

Putting together the bounds for $N\in[wn,(w+\delta)n]$ and $N>(w+\delta)n$ we
find

$\displaystyle\left\lVert\tau_{AB|XY}-\sum_{N=0}^{n}p_{N}Q\left(\frac{N}{n}\right)^{\otimes
k}\right\rVert$ $\displaystyle\leq 2C\sqrt{k}\delta+4e^{-2n\delta^{2}}.$ (49)

Now we choose

$\delta=\frac{1}{2}\sqrt{\frac{\ln(n/k)}{n}}.$ (50)

and obtain

$\left\lVert\tau_{AB|XY}-\sum_{N=0}^{n}p_{N}Q\left(\frac{N}{n}\right)^{\otimes
k}\right\rVert\leq\left(C\sqrt{\ln(n/k)}+4\right)\sqrt{\frac{k}{n}}.$ (51)

This completes the proof. ∎

The choice of $\delta$ in eq. (50) is not optimal, it does not give the
minimal possible error term in theorem 10. However, the improvement that can
be achieved by choosing $\delta$ optimally does not change the
$\mathcal{O}\left(\sqrt{\ln(n/k)k/n}\right)$ behavior. To see this, choose

$\delta=\frac{1/2\sqrt{\ln(n/k)}+\beta}{\sqrt{n}}$ (52)

for some $\beta>-\sqrt{\ln(n/k)}/2$. Then the error term is given by

$\epsilon:=2C\sqrt{k}\delta+4e^{-2n\delta^{2}}=\left(C\sqrt{\ln(n/k)}+2C\beta+4e^{-2\beta^{2}-2\beta\sqrt{\ln(n/k)}}\right)\sqrt{k/n}.$
(53)

The optimal $\beta$ is such that
$C^{\prime}=2C\beta+4e^{-2\beta^{2}-2\beta\sqrt{\ln(n/k)}}$ is minimized. A
numerical optimization shows that for $\ln(n/k)=0$ the minimum of $C^{\prime}$
is achieved at $\beta=0$, so $C^{\prime}=4$. As $\ln(n/k)$ increases the
minimum of $C^{\prime}$ decreases slowly, at $\ln(n/k)=10$ it is given by
$C^{\prime}\approx 2.03$, and at $\ln(n/k)=100$ by $C^{\prime}=0.96$. As
$\ln(n/k)\rightarrow\infty$ it converges $C^{\prime}\rightarrow 0$, which can
be seen by choosing $\beta=\left(\ln(n/k)\right)^{-1/4}$. Regardless of the
choice of $\beta$ the error is always at least $C\sqrt{\ln(n/k)k/n}$.

##  3 Bound on the diamond distance between channels

In this section we show how our first de Finetti theorem (theorem 6) may be
applied in DIQKD security proofs. This result, and the proof of it, are
analogous to theorem 25 in [22], except that we use theorem 6 as the de
Finetti theorem, rather than the statement in eq. 2. We remark that the works
[10, 11] also used threshold theorems (of somewhat different forms) to obtain
DIQKD security proofs. However, their proof techniques currently only apply to
protocols using one-way postprocessing, and yield lower asymptotic keyrates
compared to the iid case. In contrast, the results we derive here could be
applied to all protocols having the appropriate symmetry properties. While
they currently do not yield a full reduction to the iid case, our hope is that
it would be possible to develop them further to obtain security proofs that
are more generally applicable and yield higher asymptotic keyrates compared to
[10, 11], as was the case for de Finetti theorems in device-dependent QKD
[17].

Here we consider channels on boxes of the following form: A channel
$\mathcal{E}$ that acts on boxes of the form $P_{A|X}$ and outputs a random
variable $R$ as its result is described by a probability distribution
$P^{\mathcal{E}}_{X}$ on $X$, and a conditional probability distribution
$P^{\mathcal{E}}_{R|AX}$ which determines the result $R$ given $A$ and
$\mathcal{X}$. When acting on $P_{A|X}$ the channel produces a distribution on
$R$ given by

$\mathcal{E}(P_{A|X})(r)=\sum_{x,a}P^{\mathcal{E}}_{X}(x)P_{A|X}(a|x)P^{\mathcal{E}}_{R|AX}(r|ax).$
(54)

This definition is general enough to capture all protocols in a parallel DIQKD
scenario, where all bits of the $n$-bit input $\mathcal{X}$ are entered at the
same time into the box. It does not cover all protocols that are possible in a
sequential DIQKD scenario [8], where some of the input bits are only given to
the box after some output bits have been received. In such a sequential
scenario is is in principle possible to construct channels where the input to
the box in some round depends on the output of the box in previous rounds.

If we consider boxes $P_{AE|XZ}$, where the additional $E,Z$ interface is held
by Eve, we can also apply the channel $\mathcal{E}$ only to the $A,X$
interface to obtain a box with input $Z$ and outputs $R$ and $E$. We will
denote this box by
$\left(\mathcal{E}\otimes\mathrm{id}\right)(P_{AE|XZ})_{RE|Z}$.

We define the distance between two channels $\mathcal{E}$ and $\mathcal{F}$ by
how well Eve can distinguish the boxes
$\left(\mathcal{E}\otimes\mathrm{id}\right)(P_{AE|XZ})_{RE|Z}$ and
$\left(\mathcal{F}\otimes\mathrm{id}\right)(P_{AE|XZ})_{RE|Z}$ if she is also
given access to $R$. Then she can choose her input $Z$ dependent on $R$. This
leads to the following definition [22, 35]:

######  Definition 13.

Let $\mathcal{E}$ and $\mathcal{F}$ be two channels acting on boxes of the
form $P_{A|X}$. The distinguishablity of $\mathcal{E}$ and $\mathcal{F}$ using
the box $P_{AE|XZ}$ is given by

$\displaystyle\left\lVert\left(\mathcal{E}-\mathcal{F}\right)\otimes\mathrm{id}\left(P_{AE|XZ}\right)\right\rVert$
$\displaystyle=\sum_{r}\max_{z}\sum_{e}\left|\sum_{a,x}P_{AE|XZ}(ae|xz)\left(P^{\mathcal{E}}_{X}(x)P^{\mathcal{E}}_{R|AX}(r|ax)-P^{\mathcal{F}}_{X}(x)P^{\mathcal{F}}_{R|AX}(r|ax)\right)\right|.$
(55)

We define the diamond distance between the channels with respect to some set
$\mathcal{P}$ of boxes to be the following:

$\displaystyle||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathcal{P}}=\sup_{P_{AE|XZ}\in\mathcal{P}}\left\lVert\left(\mathcal{E}-\mathcal{F}\right)\otimes\mathrm{id}\left(P_{AE|XZ}\right)\right\rVert.$
(56)

Similarly to the usual diamond distance between quantum channels, the above
definition of diamond distance with respect to some set $\mathcal{P}$ is a
measure of how distinguishable the channels are with respect to a
distinguisher that can only use boxes from $\mathcal{P}$. Simple choices of
$\mathcal{P}$ include for instance the sets of quantum or non-signaling boxes.
For the following main theorem of this section we will however take
$\mathcal{P}$ to be the set of quantum boxes $P_{ABE|XYZ}$ such that the
marginal $P_{AB|XY}$ has CHSH symmetry, and denote the diamond distance with
respect to this $\mathcal{P}$ as
$||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathrm{quantum,CHSH}}$. Note that if
the action of the channels $\mathcal{E},\mathcal{F}$ can be described by Alice
and Bob first performing the depolarizing procedure described above, this
restriction causes no change in the diamond distance as compared to choosing
$\mathcal{P}$ to be the entire set of quantum boxes $P_{ABE|XYZ}$.

######  Theorem 14.

Let $\mathcal{E}$ and $\mathcal{F}$ two channels on $n$-round boxes of the
form $P_{AB|XY}$, and let $\tau_{AB|XY}$ be the de Finetti box from theorem 6.
Then

$||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathrm{quantum,CHSH}}\leq(n+1)^{2}\sup_{\tau_{ABE|XYZ}}\left\lVert(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(\tau_{ABE|XYZ})\right\rVert$
(57)

where the supremum is taken over all non-signaling boxes that have the
marginal $\tau_{AB|XY}$.

Theorem 14 can be seen as a version of the postselection theorem for quantum
channels [17]. It allows to bound the distance between two channels by the
distinguishability of the channels if Eve is restricted to extensions of a
fixed de Finetti box. This could potentially be a useful tool in security
proofs of DIQKD protocols, because a protocol is defined to be secure if its
diamond distance to an ideal protocol is small [26, 27]. However, there is a
caveat: Although the box $\tau_{AB|XY}$ is quantum, the extension
$\tau_{ABE|XYZ}$ can in general be a non-signaling box. Furthermore, we will
show in section 4 that an adversary who has access to arbitrary non-signaling
extensions of $\tau_{AB|XY}$ can actually be strictly better at distinguishing
channels than an adversary who has only access to collective attack boxes.
Hence theorem 14 does not immediately yield security against coherent attacks
from security against collective attacks.

###### Proof of theorem 14.

Let $P_{ABE|XYZ}$ be a quantum box whose marginal $P_{AB|XY}$ has CHSH
symmetry. Let $R_{AB|XY}$ be such that

$\tau_{AB|XY}=\frac{1}{(n+1)^{2}}P_{AB|XY}+\left(1-\frac{1}{(n+1)^{2}}\right)R_{AB|XY}.$
(58)

By theorem 6 all entries of $R_{AB|XY}$ are positive. Because the non-
signaling condition is linear and $\tau_{AB|XY}$ and $P_{AB|XY}$ are non-
signaling, $R_{AB|XY}$ is also non-signaling. Now we define an extension
$\tau_{ABE|XYZ}$ of $\tau_{AB|XY}$ as follows: The box has one more possible
outcome for Eve then the box $P_{ABE|XYZ}$. We will call this additional
outcome $e^{*}$. The box $\tau_{ABE|XYZ}$ then works as follows: With
probability $(n+1)^{-2}$ the box acts just like $P_{ABE|XYZ}$, and with
probability $1-(n+1)^{-2}$ it always returns $e^{*}$ to Eve and acts like
$R_{AB|XY}$ for Alice and Bob. Formally, this is given by

$\tau(abe|xyz)=\begin{cases}\frac{1}{(n+1)^{2}}P(abe|xyz)&\text{ if }e\neq
e^{*}\\\ \left(1-\frac{1}{(n+1)^{2}}\right)R(ab|xy)&\text{ if
}e=e^{*}\end{cases}.$ (59)

Since $\tau_{ABE|XYZ}$ is the linear combination of two non-signaling boxes it
is non-signaling itself. Furthermore, by eq. (58) it is an extension of
$\tau_{AB|XY}$. Finally, it holds that

$\displaystyle||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(\tau_{ABE|XYZ})||$
$\displaystyle=\sum_{r}\max_{z}\sum_{e}\left|\sum_{a,b,x,y}\tau(abe|xyz)\left(P^{\mathcal{E}}(xy)P^{\mathcal{E}}(r|abxy)-P^{\mathcal{F}}(xy)P^{\mathcal{F}}(r|abxy)\right)\right|$
$\displaystyle\geq\sum_{r}\max_{z}\sum_{e\neq
e^{*}}\left|\sum_{a,b,x,y}\tau(abe|xyz)\left(P^{\mathcal{E}}(xy)P^{\mathcal{E}}(r|abxy)-P^{\mathcal{F}}(xy)P^{\mathcal{F}}(r|abxy)\right)\right|$
$\displaystyle=(n+1)^{-2}\sum_{r}\max_{z}\sum_{e\neq
e^{*}}\left|\sum_{a,b,x,y}P(abe|xyz)\left(P^{\mathcal{E}}(xy)P^{\mathcal{E}}(r|abxy)-P^{\mathcal{F}}(xy)P^{\mathcal{F}}(r|abxy)\right)\right|$
$\displaystyle=(n+1)^{-2}||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(P_{ABE|XYZ})||.$
(60)

Hence for all $P_{ABE|XYZ}$

$||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(P_{ABE|XYZ})||\leq(n+1)^{2}\sup_{\tau_{ABE|XYZ}}||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(\tau_{ABE|XYZ})||.$
(61)

Taking the supremum over all $P_{ABE|XYZ}$ with CHSH symmetric marginal
$P_{AB|XY}$ yields the claim. ∎

##  4 Impossibility of bounding the diamond distance by restriction to
collective attacks

Theorem 14 shows that to bound the diamond distance between two channels
$\mathcal{E}$ and $\mathcal{F}$ it is sufficient to restrict the attacker to
non-signaling extensions of a fixed de Finetti box. There are many desirable
strengthenings of this result: For example, one could restrict the attacker
only to quantum extensions of the de Finetti box. One could also further
restrict the attacker to use only quantum extensions of iid boxes, instead of
the fixed de Finetti box. Finally, one could also restrict the attacker to
collective attack boxes (defined below), as would be desirable to conclude
security against coherent attacks directly from security against collective
attacks. In this section we will see that a theorem like theorem 14 does not
hold for this strongest restriction. It remains open whether such a theorem
holds for one of the other strengthenings mentioned above.

We start by defining the boxes that an attacker is allowed to use in
collective attacks. While there is potentially some flexibility in defining
this, here we use a definition that essentially corresponds to the boxes
considered in the security proofs of [5, 16], up to a collective measurement
on Eve’s side-information:

######  Definition 15.

An $n$-round quantum box $P_{ABE|XYZ}$ is a collective attack box if there are

  * •

single round Hilbert spaces $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ for Alice
and Bob and a Hilbert space $\mathcal{H}_{E}$ for Eve and

  * •

a state $\rho_{ABE}\in\mathrm{End}\left(\mathcal{H}_{A}^{\otimes
n}\otimes\mathcal{H}_{B}^{\otimes n}\otimes\mathcal{H}_{E}\right)$ such that
the marginal $\rho_{AB}$ is iid and

  * •

for each $x$ a POVM $\\{E^{a,x}\in\mathrm{End}(\mathcal{H}_{A})|a\\}$, for
each $y$ a POVM $\\{F^{b,y}\in\mathrm{End}(\mathcal{H}_{B})|b\\}$ and for each
$z$ a POVM $\\{G^{e,z}\in\mathrm{End}(\mathcal{H}_{E})|e\\}$

such that

$P(abe|xyz)=\mathrm{tr}\left[\rho_{ABE}\left(E^{a_{1},x_{1}}\otimes...\otimes
E^{a_{n},x_{n}}\otimes F^{b_{1},y_{1}}\otimes...\otimes F^{b_{n},y_{n}}\otimes
G^{e,z}\right)\right].$ (62)

We remark on two aspects of the above definition. Firstly, note that we assume
the Hilbert spaces of Alice and Bob can be split into $n$ rounds, but assume
no internal structure of Eve’s Hilbert space. However, since the state
$\rho_{AB}$ is iid and thus has an iid purification, the state $\rho_{ABE}$ is
related by a local operation on Eve’s system to this iid purification. Since
we assume nothing about $G^{e,z}$ except that it is a valid POVM, we can
absorb this local operation into $G^{e,z}$ and thus describe any collective
attack box also with a state $\rho_{ABE}$ that is iid. Collective attack boxes
can thus be seen as boxes that are essentially iid, up to Eve performing a
local operation on her systems followed by a joint measurement. Secondly, the
fact that the definition inherently incorporates this measurement means that
Eve’s system is forced to be a box rather than a genuine quantum state.
However, for the purposes of computing diamond distance, this in fact does not
make a difference (as long as arbitrary POVMs $G^{e,z}$ are allowed in the
definition) — observe that the process of a distinguisher producing a guess
for the channel can be described as it performing a POVM on its systems, and
the optimal such POVM essentially induces a valid choice of $G^{e,z}$ in the
above definition.

A crucial observation on collective attack boxes is the following: Consider
the box $P^{e,z}_{AB|XY}$ which described the outcomes of Alice and Bob
conditioned on Eve inputting $z$ and getting outcome $e$. It is given by

$\displaystyle P^{e,z}_{AB|XY}(ab|xy)$
$\displaystyle=\frac{P_{ABE|XYZ}(abe|xyz)}{P_{E|Z}(e|z)}$
$\displaystyle=\mathrm{tr}\left[\rho^{e,z}_{AB}\left(E^{a_{1},x_{1}}\otimes...\otimes
E^{a_{n},x_{n}}\otimes F^{b_{1},y_{1}}\otimes...\otimes
F^{b_{n},y_{n}}\right)\right]$ (63)

where $\rho^{e,z}_{AB}$ is a valid state,

$\rho^{e,z}_{AB}=\frac{\mathrm{tr}_{E}\left[\rho_{ABE}\left(\mathrm{id}_{A}\otimes\mathrm{id}_{B}\otimes
G^{e,z}\right)\right]}{\mathrm{tr}\left[\rho_{ABE}\left(\mathrm{id}_{A}\otimes\mathrm{id}_{B}\otimes
G^{e,z}\right)\right]}.$ (64)

Because $\sum_{a}E^{a,x}=\sum_{B}F^{b,y}=\mathrm{id}$ we see that
$P^{e,z}_{AB|XY}$ is not only non-signaling between Alice and Bob, but also
between the individual rounds. This means that for example
$\sum_{a_{1}}P^{e,z}_{AB|XY}(a_{1}a_{2}...a_{n}b|xy)$ does not depend on
$x_{1}$.

The following main result of this section exploits this insight:

######  Theorem 16.

For each $n>1$ there exist two channels $\mathcal{E}$ and $\mathcal{F}$ acting
on $n$-round boxes of the form $P_{AB|XY}$ such that
$||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(P_{ABE|XYZ})||=0$ for all
collective attack boxes $P_{ABE|XYZ}$, but
$||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathrm{quantum,CHSH}}\neq 0$.

Theorem 16 shows that a statement like theorem 14 cannot hold if we maximize
only over collective attack boxes instead of all non-signaling extensions of
the fixed de Finetti box (not even for, say, an exponential prefactor instead
of $(n+1)^{2}$). This shows that an attacker who has access to any non-
signaling extension of the fixed de Finetti box is stronger than an attacker
who has only access to collective attack boxes.

In the proof of theorem 16 we will use that all collective attack boxes are
non-signaling between the rounds of Alice and Bob, and that the non-signaling
condition is linear. The following lemma will be crucial. It states that for
each linear subspace of the probability distributions on some set, there are
two channels (which act on probability distributions, not yet on boxes), that
cannot be distinguished by any probability distribution in the linear
subspace:

######  Lemma 17.

Let $\mathcal{X}$ be some finite set. We treat the unnormalized probability
distributions on $\mathcal{X}$ as an orthant of an $|\mathcal{X}|$ dimensional
real vector space. Let $\mathcal{P}$ be some linear subspace in this vector
space, and $Q=(Q(x))_{x\in\mathcal{X}}\not\in\mathcal{P}$. Then there are two
conditional probability distributions $P^{\mathcal{E}}_{R|X}$ and
$P^{\mathcal{F}}_{R|X}$ such that the following holds: Denote for a
probability distribution $P$ on $\mathcal{X}$ by $\mathcal{E}(P)$ and
$\mathcal{F}(P)$ the distributions on $\mathcal{R}$ which are obtained by
first sampling $x$ using $P$ and the sampling $r$ using
$P^{\mathcal{E}}_{R|X}$ and $P^{\mathcal{F}}_{R|X}$, i.e.
$\mathcal{E}(P)(r)=\sum_{x}P(x)P^{\mathcal{E}}(r|x)$. Then

$\mathcal{E}(P)=\mathcal{F}(P)$ (65)

for all $P\in\mathcal{P}$ and

$\mathcal{E}(Q)\neq\mathcal{F}(Q).$ (66)

###### Proof.

There exists a vector $\Delta=(\Delta_{x})_{x\in\mathcal{X}}$ with
$|\Delta_{x}|\leq 1$ for all $x$ and $\Delta\cdot P=0$ for all
$P\in\mathcal{P}$ and $\Delta\cdot Q\neq 0$. Take $\mathcal{R}=\\{0,1\\}$ and

$\displaystyle P^{\mathcal{E}}(0|x)$ $\displaystyle=\frac{1+\Delta_{x}}{2}$
(67) $\displaystyle P^{\mathcal{E}}(1|x)$
$\displaystyle=\frac{1-\Delta_{x}}{2}$ (68) $\displaystyle
P^{\mathcal{F}}(0|x)$ $\displaystyle=\frac{1-\Delta_{x}}{2}$ (69)
$\displaystyle P^{\mathcal{F}}(1|x)$ $\displaystyle=\frac{1+\Delta_{x}}{2}.$
(70)

Then for $P$ any probability distribution on $\mathcal{X}$

$\displaystyle||\mathcal{E}(P)-\mathcal{F}(P)||_{1}$
$\displaystyle=\sum_{r}\left|\sum_{x}P(x)(P^{\mathcal{E}}(r|x)-P^{\mathcal{F}}(r|x))\right|$
$\displaystyle=|P\cdot\Delta|+|P\cdot(-\Delta)|$
$\displaystyle=2|P\cdot\Delta|.$ (71)

Hence for all $P\in\mathcal{P}$

$||\mathcal{E}(P)-\mathcal{F}(P)||_{1}=0$ (72)

and

$||\mathcal{E}(Q)-\mathcal{F}(Q)||_{1}\neq 0.$ (73)

∎

We will now construct two channels $\mathcal{E}$ and $\mathcal{F}$ that act on
boxes $P_{A|X}$ (i.e. we consider only Alice) that cannot be distinguished by
any collective attack box, but that can be distinguished by a certain quantum
box that is not a collective attack box. We will then see how to modify this
construction to include Bob and to ensure that the box used to distinguish
both channels has CHSH symmetry on the marginal of Alice and Bob.

######  Lemma 18.

For each $n>1$ there are two channels $\mathcal{E}$ and $\mathcal{F}$ that act
on $n$-round boxes $P_{AE|XZ}$ such that
$||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(P_{AE|XZ})||=0$ for all
collective attack boxes $P_{AE|XZ}$, but
$||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathrm{quantum,CHSH}}\neq 0$

###### Proof.

We first construct the channels $\mathcal{E}$ and $\mathcal{F}$, then show
that Eve cannot distinguish them if she is restricted to collective attack
boxes, and finally show that there is a quantum box (naturally not a
collective attack box) that can be used to distinguish both channels. We
construct the channels $\mathcal{E}$ and $\mathcal{F}$ as follows, depending
on a parameter $m>n/2$. For both channels, Alice does the following steps:

  1. 1.

She enters uniformly random inputs $x_{1},...,x_{n}$ into the inputs of her
box.

  2. 2.

She collects the outputs $a_{1},...,a_{n}$.

  3. 3.

She calculates

$t=\sum_{i=1}^{m}x_{i}$ (74)

and

$w=\sum_{i=m+1}^{n}a_{i}.$ (75)

Now consider the linear subspace $\mathcal{P}$ of probability distributions on
the $(w,t)$ given by the linear constraints

$\frac{P(w,t)}{2^{-m}\binom{m}{t}}=\frac{P(w,t^{\prime})}{2^{-m}\binom{m}{t^{\prime}}}$
(76)

for all $w,t,t^{\prime}$ and take a $Q\not\in\mathcal{P}$ (a specific $Q$ will
be constructed below). Alice constructs the channels $\mathcal{E}$ and
$\mathcal{F}$ by applying the conditional probability distributions
$P^{\mathcal{E}}_{R|WT}$ and $P^{\mathcal{F}}_{R|WT}$ from lemma 66 to her
result $(w,t)$ from step 75.

Now we prove that Eve cannot distinguish $\mathcal{E}$ and $\mathcal{F}$ if
she uses a collective attack box $P_{AE|XZ}$. For this, we use that for all
$e$ and $z$ $P^{e,z}_{A|X}$ is non-signaling between the rounds of Alice. In
particular, the outputs of the rounds $m+1,...n$ cannot depend on the inputs
in the rounds $1,...,m$, so $W$ and $T$ are independent when generated using
$P^{e,z}_{A|X}$. Hence

$\frac{P^{e,z}_{WT}(wt)}{{2^{-m}\binom{m}{t}}}=P^{e,z}_{W|T}(w|t)=P^{e,z}_{W|T}(w|t^{\prime})=\frac{P^{e,z}_{WT}(wt^{\prime})}{{2^{-m}\binom{m}{t^{\prime}}}}$
(77)

The box $P^{e,z}$ therefore satisfies eq. (76), and hence
$||(\mathcal{E}-\mathcal{F})(P^{e,z}_{A|X})||=0$ by lemma 66. Since this holds
for all $e$ and $z$ we have also
$||(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(P_{AE|XZ})||=0$.

Finally we construct a box $Q_{A|X}$ that allows Eve to distinguish the
channels $\mathcal{E}$ and $\mathcal{F}$ with a nonzero advantage over
guessing. Notice that here Eve does not keep any system (neither quantum not
classical) for herself and can distinguish the channels only from their result
$R$. $Q_{A|X}$ can then be an arbitrary conditional probability distribution.
Take $Q_{A|X}$ such that the result is surely $a=(1,1,...,1)$ if
$\sum_{i}x_{i}>n/2$ and surely $a=(0,0,...,0)$ otherwise. Then if $t>n/2$

$\frac{Q_{WT}(n-m,t)}{2^{-m}\binom{m}{t}}=Q_{W|T}(n-m|t)=1$ (78)

and if $t<m-n/2$

$\frac{Q_{WT}(n-m,t)}{2^{-m}\binom{m}{t}}=Q_{W|T}(n-m|t)=0$ (79)

so eq. (76) does not hold. ∎

Now we can adapt the statement of lemma 18 to prove theorem 16.

###### Proof of theorem 16.

First we generalize the construction in lemma 18 to boxes for which also Bob
has an input, i.e. boxes of the form $P_{AB|XY}$. For this, we take the
channels $\mathcal{E}$ and $\mathcal{F}$ such that they act like in lemma 18
on Alice’s inputs and outputs, and give an arbitrary input $Y$ and ignore the
output $B$ for Bob. Clearly, both channels still cannot be distinguished with
collective attack boxes, but can be distinguished by a box $Q_{AB|XY}$, which
acts like the box $Q_{A|X}$ from lemma 18 on $A$ and $X$ and arbitrarily on
$B$ and $Y$. However, $Q_{AB|XY}$ does not have CHSH symmetry. Using the
depolarizing procedure in [30] we can construct a box $\tilde{Q}_{ABE|XY}$
such that the marginal $\tilde{Q}_{AB|XY}$ has CHSH symmetry and there is an
output $e^{*}$ for Eve (corresponding to the case in which the depolarizing
protocol does nothing), such that $\tilde{Q}^{e^{*}}_{AB|XY}=Q_{AB|XY}$. Then
to distinguish $\mathcal{E}$ and $\mathcal{F}$ using $\tilde{Q}_{ABE|XY}$ Eve
first checks $E$. If $E=e^{*}$ she distinguishes $\mathcal{E}$ and
$\mathcal{F}$ as in lemma 18, otherwise she just guesses randomly. Because the
probability that $E=e^{*}$ is nonzero, we have
$\left\lVert(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(\tilde{Q}_{ABE|XY})\right\rVert>0$.
∎

Several remarks are in order. Firstly, the diamond norm
$||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathrm{quantum,CHSH}}$ between the
channels $\mathcal{E}$ and $\mathcal{F}$ from theorem 16 is exponentially
small in $n$, because Eve only tries to distinguish $\mathcal{E}$ and
$\mathcal{F}$ in the case when the depolarizing protocol does nothing. This
means that while a theorem in the same form as theorem 14 cannot hold for
collective attack boxes, it is entirely possible that there is, for example, a
theorem that yields a bound of the form

$||\mathcal{E}-\mathcal{F}||_{\Diamond}^{\mathrm{quantum,CHSH}}\leq
f(n)\sup_{P_{ABE|XYZ}}\left\lVert(\mathcal{E}-\mathcal{F})\otimes\mathrm{id}(P_{ABE|XYZ})\right\rVert+g(n),$
(80)

where $g(n)\rightarrow 0$ as $n\rightarrow\infty$. Such a result could be
sufficient to allow security proof reductions to collective attacks.

Secondly, the results of this section relied only on the fact that collective
attack boxes are non-signaling between the rounds. This property arose
entirely from the fact that Alice and Bob’s measurements act on different
Hilbert spaces in different rounds, and hence also holds more generally, i.e.
even if the measurements in each round are different, or the states are
entangled across rounds. This seems to suggest that in DIQKD, imposing an
assumption that different rounds have different Hilbert spaces may already be
a fairly strong restriction by itself222For comparison, in device-dependent
QKD, this assumption is often implicitly imposed by default. This perhaps
suggests a possible source of what appear to be greater challenges in non-iid
DIQKD security proofs as compared to device-dependent QKD. It may also
indicate that the default assumptions in device-dependent QKD could be
stronger than they initially appear., even if we allow many other non-iid
behaviours across states in different rounds, such as classical correlations
or even entanglement. Whether this assumption seems reasonable may depend on
the protocol — for instance, it seems unsatisfactory if each honest party has
to use a single device for all inputs/outputs (as in [8], which used the EAT
to avoid this assumption, for one-way protocols at least), but if each honest
party has access to $n$ devices that are “well isolated” from each other, it
might be more plausible.

Thirdly, we remark that all sequential DIQKD protocols naturally fulfill a
certain form of non-signaling constraints between the individual rounds of
Alice and Bob: Alice and Bob’s inputs in one round cannot influence the
outputs in preceding rounds. Theorem 16 does not rule out that a result like
theorem 14 exists for channels with such a sequential structure. However, such
a sequential structure appears rather incompatible with permutation symmetry,
so exploiting such sequential structures might require different techniques
from those used in this paper.

##  5 Conclusion

In this paper we proved two de Finetti theorems for quantum conditional
probability distributions with CHSH symmetry. The advantage of these theorems
over similar de Finetti theorems [22, 23] is that the de Finetti boxes are in
the quantum set. The first de Finetti theorem states that the entries of a
CHSH symmetric box are upper bounded, up to a polynomial factor in $n$, by the
entries of a fixed de Finetti box. This theorem is actually not restricted to
boxes with CHSH symmetry but can be applied to arbitrary symmetries if a
corresponding threshold theorem is available. The second de Finetti theorem
states that the marginal of the first $k$ rounds of an $n$ round CHSH
symmetric box is close to (and not just upper bounded by) a de Finetti box.

We further showed that the first de Finetti theorem can be used to obtain a
bound on the diamond distance between two channels acting on boxes.
Specifically, an attacker who tries to distinguish two channels $\mathcal{E}$
and $\mathcal{F}$ can be restricted to non-signaling extensions of a fixed
quantum de Finetti box without decreasing the distinguishability between both
channels by more than a polynomial factor. Because the security of DIQKD
protocols is defined in terms of the distance between the channel given by the
protocol and an ideal channel this statement might be useful in security
proofs. However our theorem does not immediately allow to conclude security
against coherent attacks from security against collective attacks: A
straightforward strengthening of it to bound the diamond distance between two
channels by the distinguishability using collective attack boxes does not
hold. Based on some insights in our proof approach, we speculate that in
DIQKD, assuming that boxes in different rounds act on different Hilbert spaces
may already be a fairly strong constraint, even if we allow correlations or
entanglement between states in different rounds.

## Acknowledgements

We thank Renato Renner for useful suggestions and feedback on this project, as
well as Srijita Kundu for guidance on threshold theorems.

## Funding

This project was funded by the Swiss National Science Foundation via the
National Center for Competence in Research for Quantum Science and Technology
(QSIT), the Air Force Office of Scientific Research (AFOSR) via grant
FA9550-19-1-0202, and the QuantERA project eDICT.

##  Appendix A Proof of lemma 8

###### Proof of lemma 8.

The second inequality follows directly because $f$ is non-negative and attains
its maximum at $x^{*}$. The idea for the first inequality is to replace $f$ by
a piecewise linear function that equals 0 at $a$ and $b$, and equals
$f(x^{*})$ at $x^{*}$. By concavity this piecewise linear function is always
smaller than $f$ itself. Writing this out explicitly: By concavity and non-
negativity we have for all $x\in[a,x^{*}]$

$\displaystyle f(x)$
$\displaystyle=f\left(\frac{x-a}{x^{*}-a}x^{*}+\frac{x^{*}-x}{x^{*}-a}a\right)$
$\displaystyle\geq\frac{x-a}{x^{*}-a}f(x^{*})+\frac{x^{*}-x}{x^{*}-a}f(a)$
$\displaystyle\geq\frac{x-a}{x^{*}-a}f(x^{*}).$ (81)

Therefore we have

$\int_{a}^{x^{*}}f(x)^{n}\mathrm{d}x\geq
f(x^{*})^{n}\int_{a}^{x^{*}}\left(\frac{x-a}{x^{*}-a}\right)^{n}\mathrm{d}x=\frac{1}{n+1}(x^{*}-a)f(x^{*})^{n}.$
(82)

Analogously it follows

$\int_{x^{*}}^{b}f(x)^{n}\mathrm{d}x\geq\frac{1}{n+1}(b-x^{*})f(x^{*})^{n},$
(83)

so together

$\int_{a}^{b}f(x)^{n}\mathrm{d}x=\int_{a}^{x^{*}}f(x)^{n}\mathrm{d}x+\int_{x^{*}}^{b}f(x)^{n}\mathrm{d}x\geq\frac{1}{n+1}(b-a)f(x^{*})^{n}.$
(84)

∎

##  Appendix B A de Finetti theorem for general symmetries

In this section we will show that for arbitrary games a threshold theorem such
as theorem 7 can always be used to prove a de Finetti theorem similar to
theorem 6. Conversely, we will also see that a de Finetti theorem implies a
threshold theorem. This means that proving a de Finetti theorem for some
symmetry is just as hard as proving a threshold theorem for the game
associated with that symmetry.

###  B.1 Statement of the main theorem

Throughout this section we will only consider boxes with a single interface
and with a single round input set $\mathcal{X}$ and a single round output set
$\mathcal{A}$. CHSH symmetric boxes can be described like this by treating the
two parties Alice and Bob as one, so the input and output sets are
$\mathcal{A}=\mathcal{X}=\\{0,1\\}^{2}$. We consider the following
generalization of CHSH symmetry:

######  Definition 19.

  1. 1.

Let $d\in\mathbb{N}$ and let
$w:\mathcal{A}\times\mathcal{X}\rightarrow\\{1,\dotsc,d\\}$ be some function.
We will call $w$ the predicate function of the symmetry. For
$a\in\mathcal{A}^{n}$ and $x\in\mathcal{X}^{n}$ we define
$\mathrm{freq}^{w}(a,x)=(\frac{k_{1}}{n},\dots,\frac{k_{d}}{n})\in\Delta^{d}$
with $k_{r}=|\left\\{i|w(a_{i},x_{i})=r\right\\}|$ . Here $\Delta^{d}$ denotes
the $d$-dimensional simplex.

  2. 2.

We say an $n$-round box $P_{A|X}$ has $w$-symmetry if
$P(a|x)=P(a^{\prime}|x^{\prime})$ whenever
$\mathrm{freq}^{w}(a,x)=\mathrm{freq}^{w}(a^{\prime},x^{\prime})$, for all
$a,a^{\prime}\in\mathcal{A}^{n}$ and $x,x^{\prime}\in\mathcal{X}^{n}$.

CHSH symmetry is an example of $w$-symmetry with $w((a,b),(x,y))=1$ if
$a\oplus b=xy$ and $w((a,b),(x,y))=2$ if $a\oplus b\neq xy$. The definition of
$w$-symmetry is an extension of the symmetries considered in [22] for
permutation invariant boxes, where only certain predicate functions $w$ where
considered, namely those where for each pair $x$, $x^{\prime}$ either the
images of $w(\cdot,x)$ and $w(\cdot,x^{\prime})$ are disjoint or $w(\cdot,x)$
and $w(\cdot,x^{\prime})$ are identical up to a permutation of the elements of
$\mathcal{A}$.

Instead of the set of quantum single round CHSH boxes, we will in this section
consider a general convex set $\mathcal{Q}$ of single round boxes $Q_{A|X}$.
If we view $\mathcal{Q}$ as a convex subset in
$\mathbb{R}^{|\mathcal{A}||\mathcal{X}|}$ we can consider its affine hull: the
smallest affine superset of $\mathcal{Q}$. Throughout this section we will
denote the dimension of the affine hall by $d^{\prime}$. For the CHSH
symmetric case, $\mathcal{Q}$ is the set of CHSH symmetric quantum boxes, and
$d^{\prime}=1$.

In the CHSH symmetric case it was crucial that the expected number of wins of
$n$-rounds of the CHSH games is between $\frac{2-\sqrt{2}}{4}$ and
$\frac{2+\sqrt{2}}{4}$ when the games are played with iid quantum boxes. In
our generalization the interval $[\frac{2-\sqrt{2}}{4},\frac{2+\sqrt{2}}{4}]$
will be replaced by a set of expected frequencies $\mathcal{F}_{\mu}$:

######  Definition 20.

Let $\mu$ be a probability distribution on $\mathcal{X}$, $\mathcal{Q}$ a
convex set of single round boxes and $w$ a predicate function. The set of
expected frequencies is

$\mathcal{F}_{\mu}=\left\\{\left(\left.\sum_{\begin{subarray}{c}a,x\\\
w(a,x)=r\end{subarray}}Q(a|x)\mu(x)\right)_{r=1...d}\right|Q_{A|X}\in\mathcal{Q}\right\\}\subseteq\Delta^{d}.$
(85)

In the CHSH symmetric case it is
$\mathcal{F}_{\mu}=\\{(p,1-p)|p\in[(2-\sqrt{2})/4,(2+\sqrt{2})/4]\\}$
regardless of $\mu$. We can now state the main theorem of this section:

######  Theorem 21.

Let $w:\mathcal{A}\times\mathcal{X}\rightarrow[d]$ be a predicate function and
$\mathcal{Q}$ a convex subset of single round boxes with an affine hull of
dimension $d^{\prime}$. Let $\mathcal{F}_{\mu}$ be the set of expected
frequencies. There exists a de Finetti state
$\tau_{A|X}\in\mathrm{conv}\left(\left\\{Q_{A|X}^{\otimes
n}|Q_{A|X}\in\mathcal{Q}\right\\}\right)$ independent of $w$ such that the
following hold:

  1. 1.

Let $P_{A|X}$ be an $n$-round box, let $\mu$ be a probability measure on
$\mathcal{X}$, and take any $f\in\Delta^{d}$. Suppose there exists some $C>0$
such that

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C\exp\left(-\inf_{f^{\prime}\in\mathcal{F}_{\mu}}D(f||f^{\prime})n\right).$
(86)

Then

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C\binom{n+d^{\prime}}{d^{\prime}}(n+1)^{d-1}\mathrm{Pr}_{\tau_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right].$ (87)

  2. 2.

Let $P_{A|X}$ be an $n$-round box with $w$-symmetry and let each box
$Q_{A|X}\in\mathcal{Q}$ have $w$-symmetry. Let $C$ be such that for all
$f\in\Delta^{d}$ there is a $\mu>0$ such that eq. (86) holds. Then

$P(a|x)\leq C\binom{n+d^{\prime}}{d^{\prime}}(n+1)^{d-1}\tau(a|x)\qquad\forall
a\in\mathcal{A}^{n},x\in\mathcal{X}^{n}.$ (88)

  3. 3.

Let $P_{A|X}$ be an $n$-round box for which eq. (88) holds. Then

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C\binom{n+d^{\prime}}{d^{\prime}}(n+1)^{d-1}\exp\left(-\inf_{f^{\prime}\in\mathcal{F}_{\mu}}D(f||f^{\prime})n\right).$
(89)

Qualitatively, we can interpret the equations and statements in theorem 21 as
follows:

  * •

The condition (86) is a perfect threshold theorem, written in a form similar
to eq. (25) (which was for the CHSH case). It states that the probability to
obtain a frequency distribution $f$ outside of the set $\mathcal{F}_{\mu}$ of
expected frequencies decays exponentially with $n$ and with the distance from
$f$ to $\mathcal{F}_{\mu}$, as measured by the relative entropy.

  * •

Part 1 of theorem 21 states that if we have such a threshold theorem, then the
probability of obtaining the frequencies $f$ using the box $P_{A|X}$ can be
bounded by the probability of obtaining $f$ using the de Finetti box
$\tau_{A|X}$, up to a polynomial factor. We have chosen to state this part of
the theorem separately because it does not require $P_{A|X}$ to be
$w$-symmetric.

  * •

Part 2 asserts that if we have the further condition that $P_{A|X}$ and all
boxes in $\mathcal{Q}$ are $w$-symmetric, then we can get a de Finetti theorem
analogous to theorem 6 in the CHSH case. We will derive part 2 from part 1 by
expressing the entries of $P_{A|X}$ and $\tau_{A|X}$ in terms of their
respective probabilities of obtaining $\mathrm{freq}^{w}(a,x)=f$, which is
possible by $w$-symmetry.

  * •

Finally part 3 shows the other direction of the equivalence between a
threshold theorem and a de Finetti theorem: A box $P_{A|X}$ satisfying the de-
Finetti theorem statement (88) also satisfies a threshold theorem, albeit with
a larger prefactor than in eq. (86).

To prove theorem 21, we first show some preparatory lemmas in sections B.2 and
B.3, then combine them in section B.4. Some insight can be gained into the
proof structure by writing a slightly different proof of theorem 6 (the CHSH
case), in order to draw analogies to parts 1 and 2 of theorem 21 separately.
This version of the proof proceeds as follows: first prove eq. (21) as before,
giving a lower bound on $\tau(a|x)$. However, we reorder the proof after that
point. Namely, observe that combining (25), (26) and (28) gives

$p_{k}\leq(n+1)2^{n}\binom{n}{k}\sup_{p\in[1-w,w]}f(p)^{n}.$ (90)

Putting together (21) and (90) gives

$p_{k}\leq(n+1)^{2}2^{n}\binom{n}{k}\tau(ab|xy).$ (91)

The symmetry condition has not been used up to this point. We now use it to
relate $p_{k}$ to $P(ab|xy)$ via (11), which yields the desired inequality
$P(ab|xy)\leq(n+1)^{2}\tau(ab|xy)$.

The proof in the subsequent sections basically follows the same structure as
the above version. First, eq. (21) is generalized to lemma 25 in section B.2.
Next, eq. (90) is replaced by lemma 120 in section B.3, bounding the
probability of obtaining some outcome frequency in terms of a supremum over
iid boxes (the $2^{n}\binom{n}{k}$ factor in (90) counts different ways to
achieve the specified frequency). These lemmas are combined to obtain part 1
of theorem 21, which is the generalization of (91). Finally, the symmetries
are invoked to relate the box distribution to the probabilities of obtaining
some outcome frequencies, analogous to (11), to yield part 2 of theorem 21.

###  B.2 Construction and properties of the de Finetti box

In this section we will construct the de Finetti box $\tau_{A|X}$ and show
that this $\tau(a|x)$ is at most polynomially smaller then $Q^{\otimes
n}(a|x)$, for all $Q\in\mathcal{Q}$. Before that we need to prove some
preparatory lemmas:

The following lemma and proof are adopted from [36].

######  Lemma 22 (Matrix Determinant Lemma).

Let $A\in\mathbb{R}^{n\times n}$ be an invertible matrix and
$v\in\mathbb{R}^{n}$. Then

$\det(A-vv^{T})=\det(A)(1-v^{T}A^{-1}v)$ (92)

###### Proof.

We calculate $\det(A-vv^{T})$ as the determinant of a block matrix:

$\displaystyle\det(A-vv^{T})$ $\displaystyle=\det\left(\begin{matrix}A&v\\\
v^{T}&1\end{matrix}\right)$
$\displaystyle=\det\left[\left(\begin{matrix}A&0\\\
v^{T}&1\end{matrix}\right)\left(\begin{matrix}I&A^{-1}v\\\
0&I-v^{T}A^{-1}v\end{matrix}\right)\right]$
$\displaystyle=\det(A)(1-v^{T}A^{-1}v)$ (93)

∎

######  Lemma 23.

Let $\alpha_{1},...\alpha_{n}\geq 0$ with $\sum_{i}\alpha_{i}\leq 1$. The map
$f:\left(\mathbb{R}^{+}_{0}\right)^{n}\rightarrow\mathbb{R}^{+}_{0}$ given by

$f(x_{1},..,x_{n})=\prod_{i=1}^{n}x_{i}^{\alpha_{i}}$ (94)

is concave.

###### Proof.

First assume that all $\alpha_{i}>0$ and $\sum_{i}\alpha_{i}<1$. To show that
$f$ is concave we compute the Hesse matrix:

$(Hf)_{ij}=\frac{\partial^{2}}{\partial x_{i}\partial
x_{j}}f=\frac{\partial}{\partial
x_{j}}\left(\frac{\alpha_{i}}{x_{i}}f\right)=\left(-\frac{\alpha_{i}}{x_{i}^{2}}\delta_{ij}+\frac{\alpha_{i}\alpha_{j}}{x_{i}x_{j}}\right)f=:-A_{ij}f$
(95)

with
$A=\left(\frac{\alpha_{i}}{x_{i}^{2}}\delta_{ij}-\frac{\alpha_{i}\alpha_{j}}{x_{i}x_{j}}\right)_{1\leq
i,j\leq 1}$. To show that $f$ is concave it is sufficient to show that $A$ is
positive definite. Let $A^{(k)}$ be the upper left $k\times k$ block of $A$.
By Sylvester’s criterion $A$ is positive definite if $\det(A^{(k)})>0$ for all
$k\in\\{1,\dotsc,n\\}$.

Let $B^{(k)}=\left(\frac{\alpha_{i}}{x_{i}^{2}}\delta_{ij}\right)_{1\leq
i,j\leq k}$ and $v^{(k)}=\left(\frac{\alpha_{i}}{x_{i}}\right)_{1\leq i\leq
k}$. Then

$A^{(k)}=B^{(k)}-v^{(k)}(v^{(k)})^{T}.$ (96)

By lemma 92 we calculate

$\displaystyle\det(A^{(k)})$
$\displaystyle=\det(B^{(k)})\left(1-(v^{(k)})^{T}{(B^{(k)})}^{-1}v^{(k)}\right)$
$\displaystyle=\det(B^{(k)})\left(1-\sum_{i=1}^{k}\left(\frac{\alpha_{i}}{x_{i}}\right)^{2}\frac{x_{i}^{2}}{\alpha_{i}}\right)$
$\displaystyle=\det(B^{(k)})\left(1-\sum_{i=1}^{k}\alpha_{i}\right)>0$ (97)

where the last inequality follows from $\det(B^{(k)})>0$ and
$\sum_{i=1}^{k}\alpha_{i}\leq\sum_{i=1}^{n}\alpha_{i}<1$. Hence $f$ is
concave.

Now assume the general setting where also $\alpha_{i}=0$ and
$\sum_{i}\alpha_{i}=1$ is allowed. For each $i$ choose a sequence
$(\alpha^{(m)}_{i})_{m\in\mathbb{N}}$ such that $\alpha^{(m)}_{i}>0$,
$\sum_{i}\alpha^{(m)}_{i}<1$ and
$\alpha^{(m)}_{i}\xrightarrow{m\rightarrow\infty}\alpha_{i}$. Let

$f^{(m)}(x_{1}...x_{n})=\prod_{i=1}^{n}x_{i}^{\alpha^{(m)}_{i}}.$ (98)

By continuity

$f^{(m)}(x_{1}...x_{n})\xrightarrow{m\rightarrow\infty}f(x_{1}...x_{n}).$ (99)

Now let
$x=(x_{1},...x_{n}),y=(y_{1}...y_{n})\in\left(\mathbb{R}^{+}_{0}\right)^{n}$
and $\lambda\in[0,1]$. Then

$\displaystyle f(\lambda x+(1-\lambda)y)$
$\displaystyle=\lim_{m\rightarrow\infty}f^{(m)}(\lambda x+(1-\lambda)y)$
$\displaystyle\geq\lim_{m\rightarrow\infty}\lambda
f^{(m)}(x)+(1-\lambda)f^{(m)}(y)$ $\displaystyle=\lambda
f(x)+(1-\lambda)f(y).$ (100)

∎

The following lemma is the generalization of lemma 8.

######  Lemma 24.

Let $C\subseteq\mathbb{R}^{d}$ be a bounded convex set, and denote by
$\mathrm{vol}(C)$ the volume of $C$ (under the Lebesgue measure). Then for any
$n\in\mathbb{N}$ and any concave function $f:C\rightarrow\mathbb{R}^{+}_{0}$,
we have

$\int_{C}f(x)^{n}\mathrm{d}x\geq\mathrm{vol}(C)\binom{n+d}{d}^{-1}\left(\sup_{x\in
C}f(x)\right)^{n}.$ (101)

The proof idea is similar to that of lemma 8 (assuming for simplicity that $f$
attains its supremum at some point $x^{*}\in C$): We will lower bound $f$ by a
function that is zero on the boundary of $C$, takes the value $f(x^{*})$ at
$x^{*}$, and is determined on the rest of $C$ by “interpolating linearly”
between the values at $x^{*}$ and the boundary of $C$. (Geometrically, the
graph of this new function is basically the surface of a convex cone.)

###### Proof.

Take any $\epsilon>0$. There exists some $x^{*}\in C$ such that
$f(x^{*})\geq\sup_{x\in C}f(x)-\epsilon$. We evaluate the integrals using
spherical coordinates centered on this point: Let
$S^{d-1}\subseteq\mathbb{R}^{d}$ be the $(d-1)$-sphere, and let $\mu$ be the
surface measure on $S^{d-1}$ with respect to the usual Lebesgue measure on
$\mathbb{R}^{d}$. Since integrals are unchanged by including points on the
boundary, we can evaluate the integrals using the closure of $C$ instead,
denoted as $\operatorname{cl}(C)$. This is a convex compact set, hence there
is a “radius function” $R:S^{d-1}\rightarrow\mathbb{R}^{+}_{0}$ such that

$\operatorname{cl}(C)=\\{x^{*}+r\Omega|\Omega\in
S^{d-1},r\in[0,R(\Omega)]\\}.$ (102)

Then

$\mathrm{vol}(C)=\int_{S^{d-1}}\int_{0}^{R(\Omega)}r^{d-1}\mathrm{d}r\mu(\mathrm{d}\Omega)=\frac{1}{d}\int_{S^{d-1}}R(\Omega)^{d}\mu(\mathrm{d}\Omega).$
(103)

Since

$\displaystyle f(x^{*}+r\Omega)$
$\displaystyle=f\left(\frac{r}{R(\Omega)}\left(x^{*}+R(\Omega)\Omega\right)+\frac{R(\Omega)-r}{R(\Omega)}x^{*}\right)$
$\displaystyle\geq\frac{r}{R(\Omega}f(x^{*}+R(\Omega)\Omega)+\frac{R(\Omega)-r}{R(\Omega)}f(x^{*})$
$\displaystyle\text{Concavity of }f$
$\displaystyle\geq\frac{R(\Omega)-r}{R(\Omega)}f(x^{*})$
$\displaystyle\text{Positivity of }f$ (104)

we have

$\displaystyle\int_{C}f(x)^{n}\mathrm{d}x$
$\displaystyle=\int_{S^{d-1}}\int_{0}^{R(\Omega)}r^{d-1}f(x^{*}+r\Omega)\mathrm{d}r\mu(\mathrm{d}\Omega)$
$\displaystyle\geq
f(x^{*})^{n}\int_{S^{d-1}}\int_{0}^{R(\Omega)}r^{d-1}\left(\frac{R(\Omega)-r}{R(\Omega)}\right)^{n}\mathrm{d}r\mu(\mathrm{d}\Omega)$
by eq. (104)
$\displaystyle=f(x^{*})^{n}\int_{S^{d-1}}R(\Omega)^{d}\int_{0}^{1}u^{d-1}(1-u)^{n}\mathrm{d}u\mu(\mathrm{d}\Omega).$
(105)

Using the property of the beta function

$\int_{0}^{1}u^{d-1}(1-u)^{n}=\frac{1}{n+d}\binom{n+d-1}{d-1}^{-1}=\frac{1}{d}\binom{n+d}{d}^{-1}$
(106)

we find by eq. (105) and eq. (103)

$\int_{C}f(x)^{n}\mathrm{d}x\geq\frac{1}{d}\binom{n+d}{d}^{-1}f(x^{*})^{n}\int_{S^{d-1}}R(\Omega)^{d}\mu(\mathrm{d}\Omega)=\binom{n+d}{d}^{-1}\mathrm{vol}(C)f(x^{*})^{n}.$
(107)

Recalling that $f(x^{*})\geq\sup_{x\in C}f(x)-\epsilon$, and $\epsilon>0$ was
arbitrary, this implies the desired result. ∎

When we maximize $Q^{\otimes n}(a|x)$ over $Q\in\mathcal{Q}$ while keeping $a$
and $x$ fixed, the maximum is achieved for a different $Q$ for each $a$ and
$x$. However, the next lemma states that if we average over $Q$ we are at most
a polynomial factor below that maximal value of $Q^{\otimes n}(a|x)$, no
matter what $a$ and $x$ are.

######  Lemma 25.

There is a de Finetti state
$\tau_{A|X}\in\mathrm{conv}\left(\left\\{Q^{\otimes
n}|Q\in\mathcal{Q}\right\\}\right)$ such that for all $a\in\mathcal{A}^{n}$,
$x\in\mathcal{X}^{n}$

$\tau(a|x)\geq\binom{n+d^{\prime}}{d^{\prime}}^{-1}\sup_{Q\in\mathcal{Q}}Q^{\otimes
n}(a|x),$ (108)

where $d^{\prime}$ is the dimension of the affine hull of $\mathcal{Q}$.

###### Proof.

We view $\mathcal{Q}$ as a bounded convex subset of
$\mathbb{R}^{|\mathcal{A}||\mathcal{X}|}$. Because the affine hull of
$\mathcal{Q}$ has dimension $d^{\prime}$ there exists a bounded convex set
$C\subseteq\mathbb{R}^{d^{\prime}}$ and a bijective linear map
$C\ni\phi\mapsto Q_{\phi}\in\mathcal{Q}$. Choose

$\tau_{A|X}=\frac{1}{\mathrm{vol}(C)}\int_{C}Q_{\phi}^{\otimes
n}\mathrm{d}\phi.$ (109)

Now fix $a\in\mathcal{A}^{n}$ and $x\in\mathcal{X}^{n}$ and for
$a^{\prime}\in\mathcal{A}$ and $x^{\prime}\in\mathcal{X}$ let
$f_{a^{\prime}x^{\prime}}=|\\{i|a_{i}=a^{\prime}\text{ and
}x_{i}=x^{\prime}\\}|/n$ be the frequency of the pair
$(a^{\prime},x^{\prime})$ in $(a,x)$. Then

$\phi\mapsto\left(Q_{\phi}^{\otimes
n}(a|x)\right)^{1/n}=\prod_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X}}Q_{\phi}(a^{\prime}|x^{\prime})^{f_{a^{\prime}x^{\prime}}}$
(110)

is a concave map by lemma 23 and by the linearity of $\phi\mapsto Q_{\phi}$.
Hence by lemma 101

$\displaystyle\tau(a|x)$
$\displaystyle=\frac{1}{\mathrm{vol}(C)}\int_{C}Q_{\phi}^{\otimes
n}(a|x)\mathrm{d}\phi$
$\displaystyle\geq\binom{n+d^{\prime}}{d^{\prime}}^{-1}\sup_{\phi\in
C}Q_{\phi}^{\otimes n}(a|x)$
$\displaystyle=\binom{n+d^{\prime}}{d^{\prime}}^{-1}\sup_{Q\in\mathcal{Q}}Q^{\otimes
n}(a|x).$ (111)

∎

###  B.3 Bounding $P_{A|X}$ by iid boxes

In this section we will show that a threshold theorem of the form of eq. (86)
implies that $P(a|x)$ can be bound by $Q^{\otimes n}(a|x)$ up to a polynomial
factor. Together with lemma 25 this will yield the proof for theorem 21 in the
next section.

######  Lemma 26.

Let $n=k_{1}+k_{2}+...+k_{d}$ with $k_{1},..,k_{d}\in\mathbb{N}$. Then

$(n+1)^{-(d-1)}\prod_{r=1}^{d}\left(\frac{n}{k_{r}}\right)^{k_{r}}\leq\binom{n}{k_{1},k_{2},...,k_{d}}\leq\prod_{r=1}^{d}\left(\frac{n}{k_{r}}\right)^{k_{r}}.$
(112)

Here $\binom{n}{k_{1},k_{2},...,k_{d}}=n!/(k_{1}!...k_{d}!)$ is the
multinomial coefficient.

###### Proof.

Let us first prove the inequality for $d=2$, when the multinomial coefficient
is just a binomial coefficient. It is a property of the Beta function that

$\int_{0}^{1}x^{k_{1}}(1-x)^{k_{2}}=\frac{1}{n+1}\binom{n}{k_{1}}^{-1}$ (113)

The integrand on the left hand side is maximized at $x=\frac{k_{1}}{n}$. Hence

$\frac{1}{n+1}\left(\frac{k_{1}}{n}\right)^{k_{1}}\left(\frac{k_{2}}{n}\right)^{k_{2}}\leq\int_{0}^{1}x^{k_{1}}(1-x)^{k_{2}}\leq\left(\frac{k_{1}}{n}\right)^{k_{1}}\left(\frac{k_{2}}{n}\right)^{k_{2}},$
(114)

by lemma 8. Combining eq. (113) and eq. (114) gives

$\frac{1}{n+1}\left(\frac{n}{k_{1}}\right)^{k_{1}}\left(\frac{n}{k_{2}}\right)^{k_{2}}\leq\binom{n}{k_{1}}\leq\left(\frac{n}{k_{1}}\right)^{k_{1}}\left(\frac{n}{k_{2}}\right)^{k_{2}}.$
(115)

Now we prove the lemma for general $d\geq 2$. For this, observe that

$\displaystyle\binom{n}{k_{1},...,k_{d}}$
$\displaystyle=\binom{n}{k_{1}}\binom{n-k_{1}}{k_{2}}\binom{n-k_{1}-k_{2}}{k_{3}}...\binom{n-k_{1}-...-k_{d-2}}{k_{d-1}}$
$\displaystyle=\prod_{r=1}^{d-1}\binom{n-\sum_{i=1}^{r-1}k_{i}}{k_{r}}.$ (116)

Applying eq. (115) to each binomial coefficient completes the proof since

$\displaystyle\prod_{r=1}^{d-1}\left(\frac{n-\sum_{i=1}^{r-1}k_{i}}{k_{r}}\right)^{k_{r}}\left(\frac{n-\sum_{i=1}^{r-1}k_{i}}{n-\sum_{i=1}^{r}k_{i}}\right)^{n-\sum_{i=1}^{r}k_{i}}$
$\displaystyle=\frac{1}{\prod_{r=1}^{d-1}k_{r}^{k_{r}}}\frac{\prod_{r=1}^{d-1}\left(n-\sum_{i=1}^{r-1}k_{i}\right)^{n-\sum_{i=1}^{r-1}k_{i}}}{\prod_{r=1}^{d-1}\left(n-\sum_{i=1}^{r}k_{i}\right)^{n-\sum_{i=1}^{r}k_{i}}}$
(117) $\displaystyle=\prod_{r=1}^{d}\left(\frac{n}{k_{r}}\right)^{k_{r}}.$
(118)

by a telescoping product argument. ∎

######  Lemma 27.

Let $P_{A|X}$ be a n-round box. If

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C\exp\left(-\inf_{f^{\prime}\in\mathcal{F}_{\mu}}D(f||f^{\prime})n\right)$
(119)

then

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C(n+1)^{d-1}\sup_{Q\in\mathcal{Q}}\mathrm{Pr}_{Q^{\otimes n},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right].$ (120)

###### Proof.

This is actually just a statement on the two right hand sides. Let
$f=(\frac{k_{1}}{n},...\frac{k_{d}}{n})\in\Delta^{d}$, let $Q\in\mathcal{Q}$
and let

$f^{\prime}=\left(\sum_{\begin{subarray}{c}a,x\\\
w(a,x)=r\end{subarray}}Q(a|x)\mu(x)\right)_{r=1...d}\in\Delta^{d}$ (121)

be the element of $\mathcal{F}_{\mu}$ belonging to $Q$. Then

$\displaystyle\mathrm{Pr}_{Q^{\otimes n},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]$
$\displaystyle=\binom{n}{k_{1},...,k_{d}}\prod_{r=1}^{d}(f^{\prime}_{r})^{k_{r}}$
$\displaystyle\geq\frac{1}{(n+1)^{d-1}}\prod_{r=1}^{d}\left(\frac{nf^{\prime}_{r}}{k_{r}}\right)^{k_{r}}$
by lemma 112 $\displaystyle=\frac{1}{(n+1)^{d-1}}\exp(-D(f||f^{\prime})n).$
(122)

where the last equality follows directly from the definition of the relative
entropy

$D(f||f^{\prime})=\sum_{r=1}^{d}f_{r}(\ln(f_{r})-\ln(f^{\prime}_{r})).$ (123)

Taking the supremum over $Q$ gives

$\sup_{Q\in\mathcal{Q}}\mathrm{Pr}_{Q^{\otimes n},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\geq\frac{1}{(n+1)^{d-1}}\exp\left(-\inf_{f^{\prime}\in\mathcal{F}_{\mu}}D(f||f^{\prime})n\right)$
(124)

which completes the proof. ∎

###  B.4 Proof of theorem 21

Now we are ready to prove the general theorem 21. For this, we use lemma 25 to
show that the entries of the de Finetti box are at most smaller by a
polynomial factor then the corresponding entries of any iid box. Then we use
lemma 120 to show that the threshold theorem implies that the probability of a
frequency $f$ under $P_{A|X}$ can be bounded, up to a polynomial factor, by
probability of $f$ under some iid box (but possibly a different iid box for
each $f$). Combining both lemmas yields the proof of part 1. Part 2 will
follow from part 1 by using the definition of $w$-symmetry, and part 3 will
follow directly from lemma 112.

###### Proof of theorem 21.

  1. 1.

This part follows directly by combining lemma 120 and lemma 25. Suppose

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C\exp\left(-\inf_{f^{\prime}\in\mathcal{F}_{\mu}}D(f||f^{\prime})n\right).$
(125)

By lemma 120 we have

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C(n+1)^{d-1}\sup_{Q\in\mathcal{Q}}\mathrm{Pr}_{Q^{\otimes n},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right].$ (126)

Since by lemma 25

$\mathrm{Pr}_{Q^{\otimes n},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq\binom{n+d^{\prime}}{d^{\prime}}\mathrm{Pr}_{\tau,\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]$ (127)

it follows

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]\leq
C\binom{n+d^{\prime}}{d^{\prime}}(n+1)^{d-1}\mathrm{Pr}_{\tau,\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right].$ (128)

  2. 2.

For this part, we have by hypothesis that $P_{A|X}$ and every box in
$\mathcal{Q}$ has $w$-symmetry. Then also $\tau_{A|X}$ has $w$-symmetry. Take
any $a\in\mathcal{A}^{n},x\in\mathcal{X}^{n}$, and define
$f=\mathrm{freq}^{w}(a|x)$. Then we have

$\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]=P(a|x)\sum_{\begin{subarray}{c}a\in\mathcal{A}^{n},x\in\mathcal{X}^{n}\\\
\mathrm{freq}^{w}(a,x)=f\end{subarray}}\mu^{\otimes n}(x),$ (129)

and similarly

$\mathrm{Pr}_{\tau_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]=\tau(a|x)\sum_{\begin{subarray}{c}a\in\mathcal{A}^{n},x\in\mathcal{X}^{n}\\\
\mathrm{freq}^{w}(a,x)=f\end{subarray}}\mu^{\otimes n}(x).$ (130)

From eq. (129), eq. (130) and part 1 it follows that

$P(a|x)\leq C\binom{n+d^{\prime}}{d^{\prime}}(n+1)^{d-1}\tau(a|x).$ (131)

  3. 3.

Now assume

$P(a|x)\leq\tilde{C}\tau(a|x)$ (132)

with $\tilde{C}=C\binom{n+d^{\prime}}{d^{\prime}}(n+1)^{d-1}$. Since
$\tau(a|x)\leq\sup_{Q\in\mathcal{Q}}Q^{\otimes n}(a|x)$ it follows for
$f=\left(\frac{k_{1}}{n}...\frac{k_{d}}{n}\right)$ that

$\displaystyle\mathrm{Pr}_{P_{A|X},\mu^{\otimes
n}}\left[\mathrm{freq}^{w}(A,X)=f\right]$
$\displaystyle\leq\tilde{C}\sup_{Q\in\mathcal{Q}}\mathrm{Pr}_{Q^{\otimes
n},\mu^{\otimes n}}\left[\mathrm{freq}^{w}(A,X)=f\right]$
$\displaystyle=\tilde{C}\sup_{f^{\prime}\in\mathcal{F}_{\mu}}\binom{n}{k_{1},...,k_{d}}\prod_{r=1}^{d}(f^{\prime}_{r})^{k_{r}}$
$\displaystyle\leq\tilde{C}\sup_{f^{\prime}\in\mathcal{F}_{\mu}}\prod_{r=1}^{d}\left(\frac{nf^{\prime}_{r}}{k_{r}}\right)^{k_{r}}$
by lemma 112
$\displaystyle=\tilde{C}\exp\left(-\inf_{f^{\prime}\in\mathcal{F}_{\mu}}D(f||f^{\prime})n\right).$
(133)

∎

## References

  * Bennett and Brassard [2014] Charles H. Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  _Theoretical Computer Science_ , 560:7–11, 2014.  doi: 10.1016/j.tcs.2014.05.025.
  * Ekert [1991] Artur K. Ekert.  Quantum cryptography based on Bell’s theorem.  _Physical Review Letters_ , 67(6):661–663, 1991\.  doi: 10.1103/physrevlett.67.661.
  * Renner [2008] Renato Renner.  Security Of Quantum Key Distribution.  _International Journal of Quantum Information_ , 06(01):1–127, 2008.  doi: 10.1142/s0219749908003256.
  * Barrett et al. [2005] Jonathan Barrett, Lucien Hardy, and Adrian Kent.  No Signaling and Quantum Key Distribution.  _Physical Review Letters_ , 95(1), 2005.  doi: 10.1103/physrevlett.95.010503.
  * Acín et al. [2007] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani.  Device-Independent Security of Quantum Cryptography against Collective Attacks.  _Physical Review Letters_ , 98(23), 2007.  doi: 10.1103/physrevlett.98.230501.
  * Pironio et al. [2009] Stefano Pironio, Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, and Valerio Scarani.  Device-independent quantum key distribution secure against collective attacks.  _New Journal of Physics_ , 11(4):045021, 2009\.  doi: 10.1088/1367-2630/11/4/045021.
  * Vazirani and Vidick [2014] Umesh Vazirani and Thomas Vidick.  Fully Device-Independent Quantum Key Distribution.  _Physical Review Letters_ , 113(14), 2014.  doi: 10.1103/physrevlett.113.140501.
  * Arnon-Friedman et al. [2018] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick.  Practical device-independent quantum cryptography via entropy accumulation.  _Nature Communications_ , 9(1), 2018.  doi: 10.1038/s41467-017-02307-4.
  * Dupuis et al. [2020] Frédéric Dupuis, Omar Fawzi, and Renato Renner.  Entropy Accumulation.  _Communications in Mathematical Physics_ , 379(3):867–913, 2020.  doi: 10.1007/s00220-020-03839-5.
  * Jain et al. [2020] Rahul Jain, Carl A. Miller, and Yaoyun Shi.  Parallel Device-Independent Quantum Key Distribution.  _IEEE Transactions on Information Theory_ , 66(9):5567–5584, 2020.  doi: 10.1109/tit.2020.2986740.
  * Vidick [2017] Thomas Vidick.  Parallel DIQKD from parallel repetition, 2017.  URL https://arxiv.org/abs/1703.08508.
  * Maurer [1993] U. M. Maurer.  Secret key agreement by public discussion from common information.  _IEEE Transactions on Information Theory_ , 39(3):733–742, 1993.  doi: 10.1109/18.256484.
  * Wolf [1999] Stefan Wolf.  Information-Theoretically and Computationally Secure Key Agreement in Cryptography.  1999\.  doi: 10.3929/ethz-a-002077162.
  * Chau [2002] H. F. Chau.  Practical scheme to share a secret key through a quantum channel with a 27.6% bit error rate.  _Physical Review A_ , 66:060302(R), 2002.  doi: 10.1103/PhysRevA.66.060302.
  * Gottesman and Lo [2003] D. Gottesman and Hoi-Kwong Lo.  Proof of security of quantum key distribution with two-way classical communications.  _IEEE Transactions on Information Theory_ , 49(2):457–475, 2003.  ISSN 0018-9448.  doi: 10.1109/TIT.2002.807289.
  * Tan et al. [2020] Ernest Y.-Z. Tan, Charles C.-W. Lim, and Renato Renner.  Advantage Distillation for Device-Independent Quantum Key Distribution.  _Physical Review Letters_ , 124(2), 2020.  doi: 10.1103/physrevlett.124.020502.
  * Christandl et al. [2009] Matthias Christandl, Robert König, and Renato Renner.  Postselection Technique for Quantum Channels with Applications to Quantum Cryptography.  _Physical Review Letters_ , 102(2), 2009.  doi: 10.1103/physrevlett.102.020504.
  * Diaconis and Freedman [1980] P. Diaconis and D. Freedman.  Finite Exchangeable Sequences.  _The Annals of Probability_ , 8(4), 1980.  doi: 10.1214/aop/1176994663.
  * Hudson and Moody [1976] R. L. Hudson and G. R. Moody.  Locally normal symmetric states and an analogue of de Finetti's theorem.  _Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete_ , 33(4):343–351, 1976.  doi: 10.1007/bf00534784.
  * Caves et al. [2002] Carlton M. Caves, Christopher A. Fuchs, and Rüdiger Schack.  Unknown quantum states: The quantum de Finetti representation.  _Journal of Mathematical Physics_ , 43(9):4537–4559, 2002.  doi: 10.1063/1.1494475.
  * Christandl et al. [2007] Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner.  One-and-a-Half Quantum de Finetti Theorems.  _Communications in Mathematical Physics_ , 273(2):473–498, 2007.  doi: 10.1007/s00220-007-0189-3.
  * Arnon-Friedman and Renner [2015] Rotem Arnon-Friedman and Renato Renner.  de Finetti reductions for correlations.  _Journal of Mathematical Physics_ , 56(5):052203, 2015.  doi: 10.1063/1.4921341.
  * Christandl and Toner [2009] Matthias Christandl and Ben Toner.  Finite de Finetti theorem for conditional probability distributions describing physical theories.  _Journal of Mathematical Physics_ , 50(4):042104, 2009.  doi: 10.1063/1.3114986.
  * Popescu and Rohrlich [1994] Sandu Popescu and Daniel Rohrlich.  Quantum nonlocality as an axiom.  _Foundations of Physics_ , 24(3):379–385, 1994\.  doi: 10.1007/bf02058098.
  * Hänggi et al. [2013] Esther Hänggi, Renato Renner, and Stefan Wolf.  The impossibility of non-signaling privacy amplification.  _Theoretical Computer Science_ , 486:27–42, 2013.  doi: 10.1016/j.tcs.2012.12.014.
  * Maurer and Renner [2011] Ueli Maurer and Renato Renner.  Abstract cryptography.  In _In Innovations In Computer Science_. Tsinghua University Press, 2011.
  * Portmann and Renner [2021] Christopher Portmann and Renato Renner.  Security in Quantum Cryptography, 2021.  URL https://arxiv.org/abs/2102.00021.
  * Scarani [2012] V. Scarani.  The Device-Independent Outlook On Quantum Physics.  _Acta Physica Slovaca_ , 62, 2012.  doi: 10.2478/v10155-012-0003-4.
  * Clauser et al. [1969] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt.  Proposed Experiment to Test Local Hidden-Variable Theories.  _Physical Review Letters_ , 23(15):880–884, 1969\.  doi: 10.1103/physrevlett.23.880.
  * Masanes et al. [2006] Ll. Masanes, A. Acin, and N. Gisin.  General properties of nonsignaling theories.  _Physical Review A_ , 73(1), 2006.  doi: 10.1103/physreva.73.012112.
  * Cirel'son [1980] B. S. Cirel'son.  Quantum generalizations of Bell's inequality.  _Letters in Mathematical Physics_ , 4(2):93–100, 1980.  doi: 10.1007/bf00417500.
  * Unger [2009] Falk Unger.  A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems.  In _2009 50th Annual IEEE Symposium on Foundations of Computer Science_. IEEE, 2009.  doi: 10.1109/focs.2009.62.
  * Arnon-Friedman et al. [2016] Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick.  Non-Signaling Parallel Repetition Using de Finetti Reductions.  _IEEE Transactions on Information Theory_ , 62(3):1440–1457, 2016.  doi: 10.1109/tit.2016.2516022.
  * Götze et al. [2019] Friedrich Götze, Holger Sambale, and Arthur Sinulis.  Higher order concentration for functions of weakly dependent random variables.  _Electronic Journal of Probability_ , 24, 2019.  doi: 10.1214/19-ejp338.
  * Hänggi et al. [2010] Esther Hänggi, Renato Renner, and Stefan Wolf.  Quantum Cryptography Based Solely on Bell’s Theorem.  _EUROCRYPT_ , pages 216–234, 2010.  URL https://arxiv.org/abs/0911.4171.
  * Sarwate [2012] Anand Sarwate.  The Matrix Determinant Lemma, 2012.  URL https://ergodicity.net/2012/06/12/the-matrix-determinant-lemma/.