Protocol

# Smooth min-entropy lower bounds for approximation chains

Ashutosh Marwah(1)(1)(1)email<EMAIL_ADDRESS>and Frédéric Dupuis
Département d’informatique et de recherche opérationnelle,
Université de Montréal,
Montréal QC, Canada

###### Abstract

For a state $\rho_{A_{1}^{n}B}$, we call a sequence of states
$(\sigma_{A_{1}^{k}B}^{(k)})_{k=1}^{n}$ an approximation chain if for every
$1\leq k\leq n$,
$\rho_{A_{1}^{k}B}\approx_{\epsilon}\sigma_{A_{1}^{k}B}^{(k)}$. In general, it
is not possible to lower bound the smooth min-entropy of such a
$\rho_{A_{1}^{n}B}$, in terms of the entropies of $\sigma_{A_{1}^{k}B}^{(k)}$
without incurring very large penalty factors. In this paper, we study such
approximation chains under additional assumptions. We begin by proving a
simple entropic triangle inequality, which allows us to bound the smooth min-
entropy of a state in terms of the Rényi entropy of an arbitrary auxiliary
state while taking into account the smooth max-relative entropy between the
two. Using this triangle inequality, we create lower bounds for the smooth
min-entropy of a state in terms of the entropies of its approximation chain in
various scenarios. In particular, utilising this approach, we prove an
approximate version of entropy accumulation and also provide a solution to the
source correlation problem in quantum key distribution.

###### Contents

  1. 1 Introduction
  2. 2 Background and Notation
  3. 3 Triangle inequality for the smooth min-entropy
  4. 4 Approximately independent registers
    1. 4.1 Weak approximate asymptotic equipartition
    2. 4.2 Simple security proof for sequential device independent quantum key distribution
  5. 5 Approximate entropy accumulation
    1. 5.1 Divergence bound for approximately equal states
    2. 5.2 Bounding the channel divergence for two channels close to each other
    3. 5.3 Proof of the approximate entropy accumulation theorem
    4. 5.4 Limitations and further improvements
  6. 6 Source Correlations
    1. 6.1 Security proof for BB84 with source correlations
    2. 6.2 Imperfect measurements
    3. 6.3 Discussion and future work
  7. Acknowledgments
  8. A Entropic triangle inequalities cannot be improved much
  9. B Bounds for $D^{\\#}_{\alpha}$ of the form in Lemma  necessarily diverge in the limit $\alpha=1$
  10. C Transforming lemmas for EAT from $\tilde{H}^{\downarrow}_{\alpha}$ to $\tilde{H}^{\uparrow}_{\alpha}$
  11. D Dimension bounds for conditional Rényi entropies
  12. E Bounds on the size of the side information are necessary for the approximate entropy accumulation theorem
  13. F Classical approximate entropy accumulation
  14. G Proof of Theorem

##  1 Introduction

One-shot information theory investigates the behaviour of tasks in
communication and cryptography under general unstructured processes, as
opposed to independent and identically distributed (i.i.d) processes, where
the states or the tasks themselves have a certain tensor product structure.
This is crucial for information theoretically secure cryptography, where one
cannot place any kind of assumption on the actions of the adversary (see, for
example, [TLGR12, KWW12]). To prove security for such protocols, a common
strategy is to show that some smooth min-entropy is sufficiently large. For
this reason, the smooth min-entropy [Ren06, RK05] is one of the most important
quantities in one-shot information theory.

The smooth min-entropy $H^{\epsilon}_{\min}(K|E)_{\rho}$ for the classical-
quantum state $\rho=\sum_{k}p(k)\ket{k}\bra{k}\otimes\rho_{E|k}$ characterises
the amount of randomness one can extract from the classical register $K$
independent of the adversary’s register $E$ [TRSS10]. It behaves very
differently from the von Neumann conditional entropy, which characterises
tasks in the i.i.d setting, and the difference between the two can be very
large. Roughly speaking, the smooth min-entropy places a much higher weight on
the worst possible scenario of the conditioning register, whereas the von
Neumann entropy places an equal weight on all possible scenarios.

An important and interesting argument, which works with the von Neumann
conditional entropy but fails with the smooth min-entropy, is that of proving
lower bounds on the entropy using an _approximation chain_. We call a sequence
of states(2)(2)(2)For $n$ quantum registers $(X_{1},X_{2},\cdots,X_{n})$, the
notation $X_{i}^{j}$ refers to the set of registers
$(X_{i},X_{i+1},\cdots,X_{j})$. $(\sigma^{(k)}_{A_{1}^{k}B})_{k=1}^{n}$ an
$\epsilon$-approximation chain for the state $\rho_{A_{1}^{n}B}$ if for every
$k$, we can approximate the partial state $\rho_{A_{1}^{k}B}$ as
$\|{\rho_{A_{1}^{k}B}-\sigma^{(k)}_{A_{1}^{k}B}}\|_{1}\leq{\epsilon}$. If one
can further prove that these states satisfy
$H(A_{k}|A_{1}^{k-1}B)_{\sigma^{(k)}}\geq c$ for some $c>0$ sufficiently
large, then the following simple argument shows that $H(A_{1}^{n}|B)_{\rho}$
is large:

$\displaystyle H(A_{1}^{n}|B)_{\rho}$
$\displaystyle=\sum_{k=1}^{n}H(A_{k}|A_{1}^{k-1}B)_{\rho}$
$\displaystyle\geq\sum_{k=1}^{n}\left(H(A_{k}|A_{1}^{k-1}B)_{\sigma^{(k)}}-g(\epsilon)\right)$
$\displaystyle\geq n(c-g(\epsilon))$

where we used continuity of the von Neumann conditional entropy in the second
line ($g(\epsilon)=O(\epsilon\log\frac{|A|}{\epsilon})$ is a “small” function
of $\epsilon$). It is well known that a similar argument is not possible with
the smooth min-entropy. Consequently, identities for the smooth min-entropy,
like the chain rules [VDTR13], are much more restrictive. Tools like entropy
accumulation [DFR20, MFSR22] also seem quite rigid, in the sense that they
cannot be applied unless certain (Markov chain or non-signalling) conditions
apply. It is also not clear how one could relax the conditions for such tools.
In this paper, we consider scenarios consisting of approximation chains,
similar to the above, along with additional conditions and prove lower bounds
on the appropriate smooth min-entropies.

We begin by considering the scenario of _approximately independent registers_
, that is, a state $\rho_{A_{1}^{n}B}$, which for every $1\leq k\leq n$
satisfies

$\displaystyle\frac{1}{2}\left\|\rho_{A_{1}^{k}B}-\rho_{A_{k}}\otimes\rho_{A_{1}^{k-1}B}\right\|_{1}\leq\epsilon.$
(1)

for some small $\epsilon>0$ and arbitrarily large $n$ (in particular
$n\gg\frac{1}{\epsilon}$). That is, for every $k$, the system $A_{k}$ is
almost independent of the system $B$ and everything else, which came before
it. For simplicity, let us further assume that for all $k$ the state
$\rho_{A_{k}}=\rho_{A_{1}}$. Intuitively, one expects that the smooth min-
entropy (with the smoothing parameter depending on $\epsilon$ and not on
$n$)(3)(3)(3)The smoothing parameter must depend on $\epsilon$ in such a
scenario. This can be seen by considering the probability distribution
$P_{A_{1}^{n}B}$ such that $B$ is $0$ with probability $\epsilon$ and $1$
otherwise and $A_{1}^{n}$ is a random $n$-bit string if $B=1$ and constant if
$B=0$.  for such a state will be large and close to $\approx
n(H(A_{1})-g^{\prime}(\epsilon))$ (for some small function
$g^{\prime}(\epsilon)$). However, it is not possible to prove this result
using techniques, which rely only on the triangle inequality and smoothing.
The triangle inequality, in general, can only be used to bound the difference
between $\rho_{A_{1}^{n}B}$ and $\otimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B}$
by $n\epsilon$, which will result in a trivial bound when
$n\gg\frac{1}{\epsilon}$ (4)(4)(4)Consider the distribution
$Q_{A_{1}^{2n}B_{1}^{2n}}$, where for every $i\in[2n]$, the bit $B_{i}$ is
chosen independently and is equal to $0$ with probability $\epsilon$ and is
$1$ otherwise. The bit $A_{i}$ is chosen randomly if $B_{i}=1$, otherwise it
is chosen to be equal to $A_{i-1}$. In this case, $Q_{A_{k}}$ is the uniformly
random distribution for bits and Eq. 1 is satisfied. Let
$I=|\\{i\in[n]:A_{2i-1}=A_{2i}\\}|$. Then, for $Q_{A_{1}^{2n}B_{1}^{2n}}$,
this value concentrates around $\frac{n(1+\epsilon)}{2}$, whereas for
$\prod_{i=1}^{2n}Q_{A_{i}}\cdot Q_{B_{1}^{2n}}$, it concentrates around
$\frac{n}{2}$. This shows that
$\left\|Q_{A_{1}^{2n}B_{1}^{2n}}-\prod_{i=1}^{2n}Q_{A_{i}}\cdot
Q_{B_{1}^{2n}}\right\|_{1}\rightarrow 2$.. In this paper, we show how one can
instead use a bound on the smooth max-relative entropy between these two
states to prove a lower bound for the smooth min-entropy in this scenario.

While an upper bound of $n\epsilon$ is trivial and meaningless for the trace
distance for large $n$, it is still a meaningful bound for the relative
entropy between two states, which is unbounded in general. We can show that
the above approximation conditions (Eq. 1) also imply that relative entropy
distance between $\rho_{A_{1}^{n}B}$ and
$\otimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B}$ is $nf(\epsilon)$ for some
small function $f(\epsilon)$. The substate theorem [JRS02] allows us to
transform this relative entropy bound into a smooth max-relative entropy
bound. For two general states $\rho_{AB}$ and $\eta_{AB}$, such that
$d:=D^{\delta}_{\max}(\rho_{AB}||\eta_{AB})$, we can easily bound the smooth
min-entropy of $\rho$ in terms of the min-entropy of $\eta$ by observing that

$\displaystyle\rho_{AB}\approx_{\delta}\tilde{\rho}_{AB}\leq
2^{d}\eta_{AB}\leq
2^{-(H_{\min}(A|B)_{\eta}-d)}\operatorname{\mathds{1}}_{A}\otimes\sigma_{B}$

for some state $\sigma_{B}$, which satisfies
$D_{\max}(\eta_{AB}||\operatorname{\mathds{1}}_{A}\otimes\sigma_{B})=-H_{\min}(A|B)_{\eta}$.
This implies that

$H_{\min}^{\delta}(A|B)_{\rho}\geq
H_{\min}(A|B)_{\eta}-D^{\delta}_{\max}(\rho_{AB}||\eta_{AB}).$

We call this a _triangle inequality_ , since it is based on the triangle
inequality property of $D_{\max}$. We can further improve this smooth min-
entropy triangle inequality to (Lemma 3.5)

$\displaystyle H_{\min}^{\epsilon+\delta}(A|B)_{\rho}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}(\rho_{AB}||\eta_{AB})-\frac{g_{1}(\delta,\epsilon)}{\alpha-1}$
(2)

for some function $g_{1}$, $\epsilon+\delta<1$ and $1<\alpha\leq 2$. Our
general strategy for the scenarios considered in this paper is to first bound
the “one-shot information theoretic” distance (the smooth max-relative entropy
distance) between the real state $\rho$ ($\rho_{A_{1}^{n}B}$ in the above
scenario) and a virtual, but _nicer_ state, $\eta$
($\otimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B}$ above) by $nf(\epsilon)$ for
some small $f(\epsilon)$. Then, we use Eq. 2 above to reduce the problem of
bounding the smooth min-entropy on state $\rho$ to that of bounding a
$\alpha$-Rényi entropy on the state $\eta$. Using this strategy, in Corollary
4.4, we prove that for states satisfying the approximately independent
registers assumptions, we have for
$\delta=O\left(\epsilon\log\frac{|A|}{\epsilon}\right)$ that

$\displaystyle H_{\min}^{\delta^{\frac{1}{4}}}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq
n\left(H(A_{1})_{\rho}-O(\delta^{\frac{1}{4}})\right)-O\left(\frac{1}{\delta^{3/4}}\right).$
(3)

In the second scenario, we consider approximate entropy accumulation. In the
setting for entropy accumulation, a sequence of channels
$\operatorname{\mathcal{M}}_{k}:R_{k-1}\rightarrow A_{k}B_{k}R_{k}$ for $1\leq
k\leq n$ sequentially act on a state $\rho_{R_{0}E}$ to produce the state
$\rho_{A_{1}^{n}B_{1}^{n}E}=\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})$.
It is assumed that the channels $\operatorname{\mathcal{M}}_{k}$ are such that
the Markov chain $A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow
B_{k}$ is satisfied for every $k$. This ensures that the register $B_{k}$ does
not reveal any additional information about $A_{1}^{k-1}$ than what was
previously revealed by $B_{1}^{k-1}E$. The entropy accumulation theorem
[DFR20], then provides a tight lower bound for the smooth min-entropy
$H^{\delta}_{\min}(A_{1}^{n}|B_{1}^{n}E)$. We consider an approximate version
of the above setting where the channels $\operatorname{\mathcal{M}}_{k}$
themselves do not necessarily satisfy the Markov chain condition, but they can
be $\epsilon$-approximated by a sequence of channels
$\operatorname{\mathcal{M}}^{\prime}_{k}$, which satisfies certain Markov
chain conditions. Such relaxations are important to understand the behaviour
of cryptographic protocols, like device-independent quantum key distribution
[Eke91, AFDF+18], which are implemented with imperfect devices [JK23, Tan23].
Once again we can model this scenario as an approximation chain: for every
$1\leq k\leq n$, the state produced in the $k$th step satisfies

$\displaystyle\rho_{A_{1}^{k}B_{1}^{k}ER_{k}}=\operatorname{\mathcal{M}}_{k}(\rho_{A_{1}^{k-1}B_{1}^{k-1}ER_{k-1}})\approx_{\epsilon}\operatorname{\mathcal{M}}^{\prime}_{k}(\rho_{A_{1}^{k-1}B_{1}^{k-1}ER_{k-1}}):=\sigma^{(k)}_{A_{1}^{k}B_{1}^{k}ER_{k}}.$
(4)

Moreover, the assumptions on the channel
$\operatorname{\mathcal{M}}^{\prime}_{k}$ guarantee that the state
$\sigma^{(k)}_{A_{1}^{k}B_{1}^{k}ER_{k}}$ satisfies the Markov chain condition
$A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow B_{k}$, and so the
chain rules and bounds used for entropy accumulation apply for it too. Roughly
speaking, we use the chain rules for divergences [FF21] to show that the
divergence distance between the states
$\rho_{A_{1}^{n}B_{1}^{n}E}=\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})$
and the virtual state
$\sigma_{A_{1}^{n}B_{1}^{n}E}=\operatorname{\mathcal{M}}^{\prime}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\prime}_{1}(\rho_{R_{0}E})$
is relatively small, and then reduce the problem of lower bounding the smooth
min-entropy of $\rho_{A_{1}^{n}B_{1}^{n}E}$ to that of lower bounding an
$\alpha$-Rényi entropy of $\sigma_{A_{1}^{n}B_{1}^{n}E}$, which can be done by
using the chain rules developed for entropy accumulation(5)(5)(5)The channel
divergence bounds we are able to prove are too weak for this idea to work as
stated here. The actual proof is more complicated. However, this idea works in
the classical case. . In Theorem 5.1, we show the following smooth min-entropy
lower bound for the state $\rho_{A_{1}^{n}B_{1}^{n}E}$ for sufficiently small
$\epsilon$ and an arbitrary $\delta>0$

$\displaystyle
H_{\min}^{\delta}(A_{1}^{n}|B_{1}^{n}E)_{\rho}\geq\sum_{k=1}^{n}\inf_{\omega_{R_{k}\tilde{R}_{k}}}$
$\displaystyle
H(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}-nO(\epsilon^{\frac{1}{24}})-O\left(\frac{1}{\epsilon^{\frac{1}{24}}}\right)$
(5)

where the infimum is over all possible input states
$\omega_{R_{k}\tilde{R}_{k}}$, and the dimensions $|A|$ and $|B|$ are assumed
constant while using the asymptotic notation.

We also use the techniques developed above to provide a solution for the
source correlation problem in quantum key distribution (QKD) [PCLN+22]. For
security proofs of QKD protocols, it is assumed that the states produced by
Alice’s source are independent in each round. However, in practical
implementations this is not entirely true, since physical devices have an
internal quantum memory, which may cause the states across multiple rounds to
be correlated with each other. The challenge is to prove security for QKD with
such an imperfect and correlated source. We show that it is possible to
securely implement QKD by simply measuring the output of the source in the
preparation basis for a small random set of indices and conditioning on the
relative deviation of the observed output being less than some small threshold
$\epsilon$ from the expected output. Using the results of [BF10], this source
test guarantees with high probability that the relative frequency of errors,
or the average error per round, in the conditioned state is $\approx\epsilon$.
We can once again show that the final state of the QKD protocol implemented on
this state is only $nf(\epsilon)$ (for some small function $f(\epsilon)$) far
in smooth max-relative entropy distance from the final state of the protocol
if it were conducted on perfect states. This allows us to reduce the security
proof under a correlated source to that of the QKD protocol which uses perfect
states. In Theorem 6.3, we show that a BB84 protocol, which tests its source
in the above manner is secure and the error loss due to source correlations is
$O(\sqrt{h(\epsilon)})$ (where $h$ is the binary entropy) per round. We also
consider the source test with imperfect measurements and demonstrate how these
may be taken into account in the analysis.

Lastly, we note that the sections on approximate entropy accumulation (Sec. 5)
and source correlations (Sec. 6) are independent of each other and can be read
as such.

##  2 Background and Notation

For $n$ quantum registers $(X_{1},X_{2},\cdots,X_{n})$, the notation
$X_{i}^{j}$ refers to the set of registers $(X_{i},X_{i+1},\cdots,X_{j})$. We
use the notation [n] to denote the set $\\{1,2,\cdots,n\\}$. For a register
$A$, $|A|$ represents the dimension of the underlying Hilbert space. If $X$
and $Y$ are Hermitian operators, then the operator inequality $X\geq Y$
denotes the fact that $X-Y$ is a positive semidefinite operator and $X>Y$
denotes that $X-Y$ is a strictly positive operator. A quantum state refers to
a positive semidefinite operator with unit trace. We will denote the set of
registers a quantum state describes (equivalently, its Hilbert space) using a
subscript. For example, a quantum state on the register $A$ and $B$, will be
written as $\rho_{AB}$ and its partial states on registers $A$ and $B$, will
be denoted as $\rho_{A}$ and $\rho_{B}$. The identity operator on register $A$
is denoted using $\operatorname{\mathds{1}}_{A}$. A classical-quantum state on
registers $X$ and $B$ is given by
$\rho_{XB}=\sum_{x}p(x)\ket{x}\bra{x}\otimes\rho_{B|x}$, where $\rho_{B|x}$
are normalized quantum states on register $B$.

The term “channel” is used for completely positive trace preserving (CPTP)
linear maps between two spaces of Hermitian operators. A channel
$\operatorname{\mathcal{N}}$ mapping registers $A$ to $B$ will be denoted by
$\operatorname{\mathcal{N}}_{A\rightarrow B}$. We write $\text{supp}(X)$ to
denote the support of the Hermitian operator $X$ and use $X\ll Y$ to denote
that $\text{supp}(X)\subseteq\text{supp}(Y)$.

The trace norm is defined as
$\left\|X\right\|_{1}:=\operatorname{tr}\big{(}\left(X^{\dagger}X\right)^{\frac{1}{2}}\big{)}$.
The fidelity between two positive operators $P$ and $Q$ is defined as
$F(P,Q)=\left\|\sqrt{P}\sqrt{Q}\right\|_{1}^{2}$. The generalised fidelity
between two subnormalised states $\rho$ and $\sigma$ is defined as

$\displaystyle
F_{\ast}(\rho,\sigma):=\left(\left\|\sqrt{\rho}\sqrt{\sigma}\right\|_{1}+\sqrt{(1-\operatorname{tr}\rho)(1-\operatorname{tr}\sigma)}\right)^{2}.$
(6)

The purified distance between two subnormalised states $\rho$ and $\sigma$ is
defined as

$\displaystyle P(\rho,\sigma)=\sqrt{1-F_{\ast}(\rho,\sigma)}.$ (7)

We will also use the diamond norm distance as a measure of the distance
between two channels. For a linear transform
$\operatorname{\mathcal{N}}_{A\rightarrow B}$ from operators on register $A$
to operators on register $B$, the diamond norm distance is defined as

$\displaystyle\left\|\operatorname{\mathcal{N}}_{A\rightarrow
B}\right\|_{\diamond}:=\max_{X_{AR}:\left\|X_{AR}\right\|_{1}\leq
1}\left\|\operatorname{\mathcal{N}}_{A\rightarrow B}(X_{AR})\right\|_{1}$ (8)

where the supremum is over all Hilbert spaces $R$ (fixing $|R|=|A|$ is
sufficient) and operators $X_{AR}$ such that $\left\|X_{AR}\right\|_{1}\leq
1$.

Throughout this paper, we use base $2$ for both the functions $\log$ and
$\exp$. We follow the notation in Tomamichel’s book [Tom16] for Rényi
entropies. For $\alpha\in(0,1)\cup(1,2)$, the Petz $\alpha$-Rényi relative
entropy between the positive operators $P$ and $Q$ is defined as

$\displaystyle\bar{D}_{\alpha}(P||Q)=\begin{cases}\frac{1}{\alpha-1}\log\operatorname{tr}\frac{\left(P^{\alpha}Q^{1-\alpha}\right)}{\operatorname{tr}(P)}&\text{
if }(\alpha<1\text{ and }P\not\perp Q)\text{ or }(P\ll Q)\\\ \infty&\text{
else}.\end{cases}$ (9)

The sandwiched $\alpha$-Rényi relative entropy for
$\alpha\in(0,1)\cup(1,\infty)$ between the positive operator $P$ and $Q$ is
defined as

$\displaystyle\tilde{D}_{\alpha}(P||Q)=\begin{cases}\frac{1}{\alpha-1}\log\frac{\operatorname{tr}(Q^{-\frac{\alpha^{\prime}}{2}}PQ^{-\frac{\alpha^{\prime}}{2}})^{\alpha}}{\operatorname{tr}(P)}&\text{
if }(\alpha<1\text{ and }P\not\perp Q)\text{ or }(P\ll Q)\\\ \infty&\text{
else}.\end{cases}$ (10)

where $\alpha^{\prime}=\frac{\alpha-1}{\alpha}$. In the limit
$\alpha\rightarrow\infty$, the sandwiched divergence becomes equal to the max-
relative entropy, $D_{\max}$, which is defined as

$\displaystyle D_{\max}(P||Q):=\inf\left\\{\lambda\in\mathbb{R}:P\leq
2^{\lambda}Q\right\\}.$ (11)

In the limit of $\alpha\rightarrow 1$, both the Petz and the sandwiched
relative entropies equal the quantum relative entropy, $D(P||Q)$, which is
defined as

$\displaystyle D(P||Q):=\begin{cases}\frac{\operatorname{tr}\left(P\log
P-P\log Q\right)}{\operatorname{tr}(P)}&\text{ if }(P\ll Q)\\\ \infty&\text{
else}.\end{cases}$ (12)

Given any divergence $\mathbb{D}$, we can define the (stabilised) channel
divergence based on $\mathbb{D}$ between two channels
$\operatorname{\mathcal{N}}_{A\rightarrow B}$ and
$\operatorname{\mathcal{M}}_{A\rightarrow B}$ as [CMW16, LKDW18]

$\displaystyle\mathbb{D}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}):=\sup_{\rho_{AR}}\mathbb{D}(\operatorname{\mathcal{N}}_{A\rightarrow
B}(\rho_{AR})||\operatorname{\mathcal{M}}_{A\rightarrow B}(\rho_{AR}))$ (13)

where $R$ is reference register of arbitrary size ($|R|=|A|$ can be chosen
when $\mathbb{D}$ satisfies the data processing inequality).

We can use the divergences defined above to define the following conditional
entropies for the subnormalized state $\rho_{AB}$:

$\displaystyle\bar{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$
$\displaystyle:=\sup_{\sigma_{B}}-\bar{D}_{\alpha}(\rho_{AB}||\operatorname{\mathds{1}}_{A}\otimes\sigma_{B})$
$\displaystyle\tilde{H}_{\alpha}^{\uparrow}(A|B)_{\rho}$
$\displaystyle:=\sup_{\sigma_{B}}-\tilde{D}_{\alpha}(\rho_{AB}||\operatorname{\mathds{1}}_{A}\otimes\sigma_{B})$
$\displaystyle\bar{H}_{\alpha}^{\downarrow}(A|B)_{\rho}$
$\displaystyle:=-\bar{D}_{\alpha}(\rho_{AB}||\operatorname{\mathds{1}}_{A}\otimes\rho_{B})$
$\displaystyle\tilde{H}_{\alpha}^{\downarrow}(A|B)_{\rho}$
$\displaystyle:=-\tilde{D}_{\alpha}(\rho_{AB}||\operatorname{\mathds{1}}_{A}\otimes\rho_{B})$

for appropriate $\alpha$ in the domain of the divergences. The supremum in the
definition for $\bar{H}_{\alpha}^{\uparrow}$ and
$\tilde{H}_{\alpha}^{\uparrow}$ is over all quantum states $\sigma_{B}$ on
register $B$.

For $\alpha\rightarrow 1$, all these conditional entropies are equal to the
von Neumann conditional entropy $H(A|B)$.
$\tilde{H}_{\infty}^{\uparrow}(A|B)_{\rho}$ is usually called the min-entropy.
The min-entropy is usually denoted as $H_{\min}(A|B)_{\rho}$ and for a
subnormalised state can also be defined as

$\displaystyle H_{\min}(A|B)_{\rho}$
$\displaystyle:=\sup\left\\{\lambda\in\mathbb{R}:\text{ there exists state
}\sigma_{B}\text{ such that }\rho_{AB}\leq
2^{-\lambda}\operatorname{\mathds{1}}_{A}\otimes\sigma_{B}\right\\}.$ (14)

For the purpose of smoothing, define the $\epsilon$-ball around the
subnormalised state $\rho$ as the set

$\displaystyle B_{\epsilon}(\rho)=\\{\tilde{\rho}\geq
0:P(\rho,\tilde{\rho})\leq\epsilon\text{ and
}\operatorname{tr}\tilde{\rho}\leq 1\\}.$ (15)

We define the smooth max-relative entropy as

$\displaystyle D_{\max}^{\epsilon}(\rho||\sigma)=\min_{\tilde{\rho}\in
B_{\epsilon}(\rho)}D_{\max}(\tilde{\rho}||\sigma)$ (16)

The smooth min-entropy of $\rho_{AB}$ is defined as

$\displaystyle H_{\min}^{\epsilon}(A|B)_{\rho}=\max_{\tilde{\rho}\in
B_{\epsilon}(\rho)}H_{\min}(A|B)_{\tilde{\rho}}.$ (17)

##  3 Triangle inequality for the smooth min-entropy

In this section, we derive a simple triangle inequality (Lemma 3.5) for the
smooth min-entropy of the form in Eq. 2. This Lemma is a direct consequence of
the following triangle inequality for $\tilde{D}_{\alpha}$.

######  Lemma 3.1.

Let $\rho$ and $\eta$ be subnormalised states and $Q$ be a positive operator,
then for $\alpha>1$, we have

$\displaystyle\tilde{D}_{\alpha}(\rho||Q)\leq\tilde{D}_{\alpha}(\eta||Q)+\frac{\alpha}{\alpha-1}D_{\max}(\rho||\eta)+\frac{1}{\alpha-1}\log\frac{\operatorname{tr}(\eta)}{\operatorname{tr}(\rho)}$

and for $\alpha<1$ if one of $\tilde{D}_{\alpha}(\eta||Q)$ and
$D_{\max}(\rho||\eta)$ is finite (otherwise we cannot define their
difference), we have

$\displaystyle\tilde{D}_{\alpha}(\rho||Q)\geq\tilde{D}_{\alpha}(\eta||Q)-\frac{\alpha}{1-\alpha}D_{\max}(\rho||\eta)-\frac{1}{1-\alpha}\log\frac{\operatorname{tr}(\eta)}{\operatorname{tr}(\rho)}.$

###### Proof.

If $D_{\max}(\rho||\eta)=\infty$, then both statements are true trivially.
Otherwise, we have that $\rho\leq 2^{D_{\max}(\rho||\eta)}\eta$ and also
$\rho\ll\eta$. Now, if $\rho\not\ll Q$ then $\eta\not\ll Q$. Hence, for
$\alpha>1$ if $\tilde{D}_{\alpha}(\rho||Q)=\infty$, then
$\tilde{D}_{\alpha}(\eta||Q)=\infty$, which means the Lemma is also satisfied
in this condition. For $\alpha<1$, if $\tilde{D}_{\alpha}(\rho||Q)=\infty$,
then the Lemma is also trivially satisfied. For the remaining cases we have,

$\displaystyle 2^{(\alpha-1)\tilde{D}_{\alpha}(\rho||Q)}$
$\displaystyle=\frac{\operatorname{tr}\left(Q^{-\frac{\alpha-1}{2\alpha}}\rho
Q^{-\frac{\alpha-1}{2\alpha}}\right)^{\alpha}}{\operatorname{tr}(\rho)}$
$\displaystyle\leq\frac{\operatorname{tr}\left(Q^{-\frac{\alpha-1}{2\alpha}}2^{D_{\max}(\rho||\eta)}\eta
Q^{-\frac{\alpha-1}{2\alpha}}\right)^{\alpha}}{\operatorname{tr}(\rho)}$
$\displaystyle=\frac{\operatorname{tr}(\eta)}{\operatorname{tr}(\rho)}2^{\alpha
D_{\max}(\rho||\eta)}2^{(\alpha-1)\tilde{D}_{\alpha}(\eta||Q)}$

where we used the fact that $\operatorname{tr}(f(X))$ is monotone increasing
if the function $f$ is monotone increasing. Dividing by $(\alpha-1)$ now gives
the result. ∎

We define smooth $\alpha$-Rényi conditional entropy as follows to help us
amplify the above inequality.

######  Definition 3.2 ($\epsilon$-smooth $\alpha$-Rényi conditional entropy).

For $\alpha\in(1,\infty]$ and $\epsilon\in[0,1]$, we define the
$\epsilon$-smooth $\alpha$-Rényi conditional entropy as

$\displaystyle\tilde{H}^{\uparrow}_{\alpha,\epsilon}(A|B)_{\rho}:=\max_{\tilde{\rho}_{AB}\in
B_{\epsilon}(\rho_{AB})}\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\tilde{\rho}}.$
(18)

######  Lemma 3.3.

For $\alpha\in(1,\infty]$ and $\epsilon\in[0,1)$, and states $\rho_{AB}$ and
$\eta_{AB}$ we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha,\epsilon}(A|B)_{\rho}\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}(\rho_{AB}||\eta_{AB})-\frac{1}{\alpha-1}\log\frac{1}{1-\epsilon^{2}}.$

###### Proof.

Let $\tilde{\rho}_{AB}\in B_{\epsilon}(\rho_{AB})$ be a subnormalised state
such that
$D_{\max}(\tilde{\rho}_{AB}||\eta_{AB})=D^{\epsilon}_{\max}(\rho_{AB}||\eta_{AB})$.
Using Lemma 3.1 for $\alpha>1$, we have that for every state $\sigma_{B}$, we
have

$\displaystyle\tilde{D}_{\alpha}(\tilde{\rho}_{AB}||\operatorname{\mathds{1}}_{A}\otimes\sigma_{B})$
$\displaystyle\leq\tilde{D}_{\alpha}(\eta_{AB}||\operatorname{\mathds{1}}_{A}\otimes\sigma_{B})+\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}({\rho}_{AB}||\eta_{AB})+\frac{1}{\alpha-1}\log\frac{1}{1-\epsilon^{2}}$
(19)

where we used the fact that $\tilde{\rho}_{AB}\in B_{\epsilon}(\rho_{AB})$
which implies that $\operatorname{tr}(\tilde{\rho}_{AB})\geq 1-\epsilon^{2}$.
Since, the above bound is true for arbitrary states $\sigma_{B}$, we can
multiply it by $-1$ and take the supremum to derive

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\tilde{\rho}}\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}(\rho_{AB}||\eta_{AB})-\frac{1}{\alpha-1}\log\frac{1}{1-\epsilon^{2}}.$

The desired bound follows by using the fact that
$\tilde{H}^{\uparrow}_{\alpha,\epsilon}(A|B)_{{\rho}}\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\tilde{\rho}}$.
∎

######  Lemma 3.4.

For a state $\rho_{AB}$, $\epsilon\in[0,1)$, and $\delta\in(0,1)$ such that
$\epsilon+\delta<1$ and $\alpha\in(1,2]$, we have

$\displaystyle
H_{\min}^{\epsilon+\delta}(A|B)_{\rho}\geq\tilde{H}^{\uparrow}_{\alpha,\epsilon}(A|B)_{\rho}-\frac{g_{0}(\delta)}{\alpha-1}$

where $g_{0}(x):=-\log(1-\sqrt{1-x^{2}})$.

###### Proof.

First, note that

$\displaystyle H_{\min}^{\epsilon+\delta}(A|B)_{\rho}$
$\displaystyle\geq\sup_{\tilde{\rho}\in
B_{\epsilon}(\rho_{AB})}H_{\min}^{\delta}(A|B)_{\tilde{\rho}}.$ (20)

To prove this, consider a $\tilde{\rho}_{AB}\in B_{\epsilon}(\rho_{AB})$ and
$\rho^{\prime}_{AB}\in B_{\delta}(\tilde{\rho}_{AB})$ such that
$H_{\min}(A|B)_{{\rho^{\prime}}}=H^{\delta}_{\min}(A|B)_{\tilde{\rho}}$. Then,
using the triangle inequality for the purified distance, we have

$\displaystyle P(\rho_{AB},\rho^{\prime}_{AB})$ $\displaystyle\leq
P(\rho_{AB},\tilde{\rho}_{AB})+P(\tilde{\rho}_{AB},\rho^{\prime}_{AB})$
$\displaystyle\leq\epsilon+\delta$

which implies that $H_{\min}^{\epsilon+\delta}(A|B)_{\rho}\geq
H_{\min}(A|B)_{{\rho^{\prime}}}=H^{\delta}_{\min}(A|B)_{\tilde{\rho}}$. Since,
this is true for all $\tilde{\rho}\in B_{\epsilon}(\rho_{AB})$ the bound in
Eq. 20 is true.

Using this, we have

$\displaystyle H_{\min}^{\epsilon+\delta}(A|B)_{\rho}$
$\displaystyle\geq\sup_{\tilde{\rho}\in
B_{\epsilon}(\rho_{AB})}H_{\min}^{\delta}(A|B)_{\tilde{\rho}}$
$\displaystyle\geq\sup_{\tilde{\rho}\in
B_{\epsilon}(\rho_{AB})}\left\\{\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\tilde{\rho}}-\frac{g_{0}(\delta)}{\alpha-1}\right\\}$
$\displaystyle=\tilde{H}^{\uparrow}_{\alpha,\epsilon}(A|B)_{\rho}-\frac{g_{0}(\delta)}{\alpha-1}$

where we have used [DFR20, Lemma B.10](6)(6)(6)This Lemma is also valid for
subnormalised states as long as
$\delta\in(0,\sqrt{2\operatorname{tr}(\tilde{\rho})-\operatorname{tr}(\tilde{\rho})^{2}})$
according to [DFR20, Lemma B.4]. (originally proven in [TCR09]) in the second
step. ∎

We can combine these two lemmas to derive the following result.

######  Lemma 3.5.

For $\alpha\in(1,2]$, $\epsilon\in[0,1)$, and $\delta\in(0,1)$ such that
$\epsilon+\delta<1$ and two states $\rho$ and $\eta$, we have

$\displaystyle H_{\min}^{\epsilon+\delta}(A|B)_{\rho}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}(\rho_{AB}||\eta_{AB})-\frac{g_{1}(\delta,\epsilon)}{\alpha-1}$
(21)

where $g_{1}(x,y):=-\log(1-\sqrt{1-x^{2}})-\log(1-y^{2})$.

###### Proof.

We can combine Lemmas 3.3 and 3.4 as follows to derive the bound in the Lemma:

$\displaystyle H_{\min}^{\epsilon+\delta}(A|B)_{\rho}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha,\epsilon}(A|B)_{\rho}-\frac{g_{0}(\delta)}{\alpha-1}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}(\rho_{AB}||\eta_{AB})-\frac{1}{\alpha-1}\left(g_{0}(\delta)+\log\frac{1}{1-\epsilon^{2}}\right).$

∎

We can use the asymptotic equipartition theorem for smooth min-entropy and
max-relative entropy [TCR09, Tom12, TH13] to derive the following novel
triangle inequality for the von Neumann conditional entropy. Although we do
not use this inequality in this paper, we believe it is interesting and may
prove useful in the future.

######  Corollary 3.6.

For $\alpha\in(1,2]$ and states $\rho_{AB}$ and $\eta_{AB}$, we have that

$\displaystyle H(A|B)_{\rho}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D(\rho_{AB}||\eta_{AB}).$
(22)

###### Proof.

Using Lemma 3.5 with $\alpha\in(1,2]$, the states $\rho^{\otimes n}_{AB}$, and
$\eta^{\otimes n}_{AB}$ and any $\epsilon>0$ and $\delta>0$ satisfying the
conditions for the Lemma, we get

$\displaystyle H_{\min}^{\epsilon+\delta}(A_{1}^{n}|B_{1}^{n})_{\rho^{\otimes
n}}\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n})_{\eta^{\otimes
n}}-\frac{\alpha}{\alpha-1}D^{\epsilon}_{\max}(\rho_{AB}^{\otimes
n}||\eta^{\otimes n}_{AB})-\frac{g_{1}(\delta,\epsilon)}{\alpha-1}$
$\displaystyle\Rightarrow$
$\displaystyle\frac{1}{n}H_{\min}^{\epsilon+\delta}(A_{1}^{n}|B_{1}^{n})_{\rho^{\otimes
n}}\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}\frac{1}{n}D^{\epsilon}_{\max}(\rho_{AB}^{\otimes
n}||\eta^{\otimes
n}_{AB})-\frac{1}{n}\frac{g_{1}(\delta,\epsilon)}{\alpha-1}.$

Taking the limit of the above for $n\rightarrow\infty$, we get

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}H_{\min}^{\epsilon+\delta}(A_{1}^{n}|B_{1}^{n})_{\rho^{\otimes
n}}\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\lim_{n\rightarrow\infty}\frac{\alpha}{\alpha-1}\frac{1}{n}D^{\epsilon}_{\max}(\rho_{AB}^{\otimes
n}||\eta^{\otimes
n}_{AB})-\lim_{n\rightarrow\infty}\frac{1}{n}\frac{g_{1}(\delta,\epsilon)}{\alpha-1}$
$\displaystyle\Rightarrow$ $\displaystyle
H(A|B)_{\rho}\geq\tilde{H}^{\uparrow}_{\alpha}(A|B)_{\eta}-\frac{\alpha}{\alpha-1}D(\rho_{AB}||\eta_{AB})$

which proves the claim. ∎

##  4 Approximately independent registers

In this section, we introduce our technique for using the smooth min-entropy
triangle inequality for considering approximations by studying a state
$\rho_{A_{1}^{n}B}$ such that for every $k\in[n]$

$\displaystyle\left\|\rho_{A_{1}^{k}B}-\rho_{A_{k}}\otimes\rho_{A_{1}^{k-1}B}\right\|_{1}\leq\epsilon.$
(23)

We assume that the registers $A_{k}$ all have the same dimension equal to
$|A|$. One should think of the registers $A_{k}$ as the secret information
produced during some protocol, which also provides the register $B$ to an
adversary. We would like to prove that $H^{f(\epsilon)}_{\min}(A_{1}^{n}|B)$
is large (lower bounded by $\Omega(n)$) under the above _approximate
independence conditions_ for some reasonably small function $f$ of $\epsilon$
and close to $nH(A_{1})$, if we assume the states $\rho_{A_{k}}$ are
identical. Let us first examine the case when the states above are completely
classical. To show that in this case the smooth min-entropy is high, we will
show that the set where the conditional probability
$\rho(a_{1}^{n}|b):=\frac{\rho(a_{1}^{n}b)}{\rho(b)}$ can be large, has a
small probability using the Markov inequality. We will use the following lemma
for this purpose.

######  Lemma 4.1.

Suppose $p,q$ are probability distributions on $\mathcal{X}$ such that
$\frac{1}{2}\left\|p-q\right\|_{1}\leq\epsilon$, then $S\subseteq\mathcal{X}$
defined as $S:=\\{x\in\mathcal{X}:p(x)\leq(1+\epsilon^{1/2})q(x)\\}$ is such
that $q(S)\geq 1-\epsilon^{1/2}$ and $p(S)\geq 1-\epsilon^{1/2}-\epsilon$.

###### Proof.

For $S^{c}:=\mathcal{X}\setminus S$, where $S$ is the set defined above we
have that

$\displaystyle\epsilon\geq\frac{1}{2}\left\|p-q\right\|_{1}$
$\displaystyle=\max_{H\subseteq\mathcal{X}}|p(H)-q(H)|$ $\displaystyle\geq
q(S^{c})\left|\frac{p(S^{c})}{q(S^{c})}-1\right|$ $\displaystyle\geq
q(S^{c})\left(\frac{p(S^{c})}{q(S^{c})}-1\right)$
$\displaystyle=q(S^{c})\left(\frac{\sum_{x\in S^{c}}p(x)}{\sum_{x\in
S^{c}}q(x)}-1\right)$ $\displaystyle\geq q(S^{c})\left(\frac{\sum_{x\in
S^{c}}(1+\epsilon^{\frac{1}{2}})q(x)}{\sum_{x\in S^{c}}q(x)}-1\right)$
$\displaystyle\geq q(S^{c})\epsilon^{\frac{1}{2}}$

which implies that $q(S^{c})\leq\epsilon^{\frac{1}{2}}$. Now, the statement of
the Lemma follows. ∎

We will also assume for the sake of simplicity that $\rho_{A_{k}}$ are
identical for all $k\in[n]$. Using the Lemma above, for every $k\in[n]$, we
know that the set

$\displaystyle B_{k}:$
$\displaystyle=\left\\{(a_{1}^{n},b):\rho(a_{1}^{k},b)>(1+\sqrt{\epsilon})\rho(a_{1}^{k-1},b)\rho(a_{k})\right\\}$
$\displaystyle=\left\\{(a_{1}^{n},b):\rho(a_{k}|a_{1}^{k-1},b)>(1+\sqrt{\epsilon})\rho(a_{k})\right\\}$

satisfies $\Pr_{\rho}(B_{k})\leq 2\sqrt{\epsilon}$. We can now define
$L=\sum_{k=1}^{n}\chi_{B_{k}}$, which is a random variable that simply counts
the number of bad sets $B_{k}$ an element $(a_{1}^{n},b)$ belongs to. Using
the Markov inequality, we have

$\displaystyle\Pr_{\rho}\left[L>n\epsilon^{\frac{1}{4}}\right]\leq\frac{\operatorname{\mathbb{E}}_{\rho}[L]}{n\epsilon^{\frac{1}{4}}}\leq
2\epsilon^{\frac{1}{4}}.$

We can define the bad set
$\mathcal{B}:=\left\\{(a_{1}^{n},b):L(a_{1}^{n},b)>n\epsilon^{\frac{1}{4}}\right\\}$,
then we can define the subnormalised distribution $\tilde{\rho}_{A_{1}^{n}B}$
as

$\displaystyle\tilde{\rho}_{A_{1}^{n}B}(a_{1}^{n},b)=\begin{cases}\rho_{A_{1}^{n}B}(a_{1}^{n},b)&(a_{1}^{n},b)\not\in\mathcal{B}\\\
0&\text{else}\end{cases}.$

We have
$P(\tilde{\rho}_{A_{1}^{n}B},\rho_{A_{1}^{n}B})\leq\sqrt{2}\epsilon^{1/8}$.
Further, note that for every $(a_{1}^{n},b)\not\in\mathcal{B}$, we have

$\displaystyle\rho(a_{1}^{n}|b)$
$\displaystyle=\prod_{k=1}^{n}\rho(a_{k}|a_{1}^{k-1},b)$
$\displaystyle=\prod_{k:(a_{1}^{n},b)\not\in
B_{k}}\rho(a_{k}|a_{1}^{k-1},b)\prod_{k:(a_{1}^{n},b)\in
B_{k}}\rho(a_{k}|a_{1}^{k-1},b)$
$\displaystyle\leq(1+\sqrt{\epsilon})^{n}\prod_{k:(a_{1}^{n},b)\not\in
B_{k}}\rho_{A_{k}}(a_{k})$
$\displaystyle\leq(1+\sqrt{\epsilon})^{n}2^{-n(1-\epsilon^{\frac{1}{4}})H_{\min}(A_{1})}$

where in the third line we have used the fact that if $(a_{1}^{n},b)\not\in
B_{k}$, then
$\rho(a_{k}|a_{1}^{k-1}b)\leq(1+\sqrt{\epsilon})\rho_{A_{k}}(a_{k})$ and in
the last line we have used the fact that for
$(a_{1}^{k},b)\not\in\mathcal{B}$, we have $|\\{k\in[n]:(a_{1}^{n},b)\not\in
B_{k}\\}|=n-L(a_{1}^{n},b)\geq n(1-\epsilon^{\frac{1}{4}})$, that all the
states $\rho_{A_{k}}$ are identical and
$2^{-H_{\min}(A_{k})}=\max_{a_{k}}\rho_{A_{k}}(a_{k})$. Note that we have
essentially proven and used a $D_{\max}$ bound above. This proves the
following lower bound for the smooth min-entropy of $\rho$

$\displaystyle H^{\sqrt{2}\epsilon^{\frac{1}{8}}}_{\min}(A_{1}^{n}|B)\geq
n(1-\epsilon^{\frac{1}{4}})H_{\min}(A_{1})-n\log(1+\sqrt{\epsilon}).$ (24)

The right-hand side above can be improved to get the Shannon entropy $H$
instead of the min-entropy $H_{\min}$. However, we will not pursue this here,
since this bound is sufficient for the purpose of our discussion.

Although, we are unable to generalise the classical argument above to the
quantum case, it provides a great amount of insight into the approximately
independent registers problem. Two important examples of distributions, which
satisfy the approximate independence conditions above were mentioned in
Footnotes (3) and (4) earlier. To create the first distribution, we flip a
biased coin $B$, which is $0$ with probability $\epsilon$ and $1$ otherwise.
If $B=0$, then $A_{1}^{n}$ is set to the constant all zero string otherwise it
is sampled randomly and independently. For this distribution, once the bad
event ($B=0$) is removed, the new distribution has a high min-entropy. On the
other hand, for the second distribution, $Q_{A_{1}^{2n}B_{1}^{2n}}$, we have
that the random bits $B_{i}$ are chosen independently, with each being equal
to $0$ with probability $\epsilon$ and $1$ otherwise. If the bit $B_{i}$ is
$0$, then $A_{i}$ is set equal to $A_{i-1}$ otherwise it is sampled
independently. In this case, there is no small probability (small as a
function of $\epsilon$) event, that one can simply remove, so that the
distribution becomes i.i.d. However, we expect that with high probability the
number of $B_{i}=0$ is close to $2n\epsilon$. Given that the distribution
samples all the other $A_{i}$ independently, the smooth min-entropy for the
distribution should be close to $2n(1-\epsilon)H(A_{1})$. The above argument
shows that any distribution satisfying the approximate independence conditions
in Eq. 23 can be handled by combining the methods used for these two example
distributions, that is, deleting the bad part of the distribution and
recognising that the probability for every element in the rest of the space
behaves independently on average.

The above classical argument is difficult to generalise to quantum states
primarily because the quantum equivalents of Lemma 4.1 are not as nice and
simple. Furthermore, quantum conditional probabilities themselves are also
difficult to use. Fortunately, the substate theorem serves as the perfect tool
for developing a smooth max-relative entropy bound, which we can then use with
the min-entropy triangle inequality. The quantum substate theorem [JRS02,
JN11] provides an upper bound on the smooth max relative entropy
$D^{\epsilon}_{\max}(\rho||\sigma)$ between two states in terms of their
relative entropy $D(\rho||\sigma)$.

######  Theorem 4.2 (Quantum substate theorem [JN11]).

Let $\rho$ and $\sigma$ be two states on the same Hilbert space. Then for any
$\epsilon\in(0,1)$, we have

$\displaystyle
D^{\sqrt{\epsilon}}_{\max}(\rho||\sigma)\leq\frac{D(\rho||\sigma)+1}{\epsilon}+\log\frac{1}{1-\epsilon}.$
(25)

In this section, we will also frequently use the multipartite mutual
information [Wat60, Hor94, CMS02]. For a state $\rho_{X_{1}^{n}}$, the
multipartite mutual information between the registers
$(X_{1},X_{2},\cdots,X_{n})$ is defined as

$\displaystyle
I(X_{1}:X_{2}:\cdots:X_{n})_{\rho}:=D(\rho_{X_{1}^{n}}||\rho_{X_{1}}\operatorname{\otimes}\rho_{X_{2}}\operatorname{\otimes}\cdots\operatorname{\otimes}\rho_{X_{n}}).$
(26)

In other words, it is the relative entropy between $\rho_{X_{1}^{n}}$ and
$\rho_{X_{1}}\operatorname{\otimes}\rho_{X_{2}}\operatorname{\otimes}\cdots\operatorname{\otimes}\rho_{X_{n}}$.
It can easily be shown that the multipartite mutual information satisfies the
following identities:

$\displaystyle I(X_{1}:X_{2}:\cdots:X_{n})_{\rho}$
$\displaystyle=\sum_{k=1}^{n}H(X_{k})_{\rho}-H(X_{1}\cdots\ X_{n})_{\rho}$
(27) $\displaystyle=\sum_{k=2}^{n}I(X_{k}:X_{1}^{k-1}).$ (28)

Going back to proving a bound for the quantum approximately independent
registers problem, note that using the Alicki-Fannes-Winter (AFW) bound [AF04,
Win16] for mutual information [Wil13, Theorem 11.10.4], Eq. 23 implies that
for every $k\in[n]$

$\displaystyle
I(A_{k}:A_{1}^{k-1}B)_{\rho}\leq\epsilon\log|A|+g_{2}\left(\frac{\epsilon}{2}\right)$
(29)

where $g_{2}(x):=(x+1)\log(x+1)-x\log(x)$. With this in mind, we can now focus
our efforts on proving the following theorem.

######  Theorem 4.3.

Let registers $A_{k}$ have dimension $|A|$ for all $k\in[n]$. Suppose a
quantum state $\rho_{A_{1}^{n}B}$ is such that for every $k\in[n],$ we have

$\displaystyle I(A_{k}:A_{1}^{k-1}B)_{\rho}\leq\epsilon$ (30)

for some $0<\epsilon<1$. Then, we have that

$\displaystyle H_{\min}^{\epsilon^{\frac{1}{4}}+\epsilon}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k})_{\rho}-3n\epsilon^{\frac{1}{4}}\log(1+2|A|)$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\epsilon^{3/4}}-\frac{2\log(1+2|A|)}{\epsilon^{1/4}}\left(\log(1-\sqrt{\epsilon})+g_{1}(\epsilon,\epsilon^{\frac{1}{4}})\right)$
(31)

where $g_{1}(x,y):=-\log(1-\sqrt{1-x^{2}})-\log(1-y^{2})$. In particular, when
all the states $\rho_{A_{k}}$ are identical, we have

$\displaystyle H_{\min}^{\epsilon^{\frac{1}{4}}+\epsilon}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq
n\left(H(A_{1})_{\rho}-3\epsilon^{\frac{1}{4}}\log(1+2|A|)\right)$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\epsilon^{3/4}}-\frac{2\log(1+2|A|)}{\epsilon^{1/4}}\left(\log(1-\sqrt{\epsilon})+g_{1}(\epsilon,\epsilon^{\frac{1}{4}})\right).$
(32)

###### Proof.

First note that we have,

$\displaystyle I(A_{1}:A_{2}:\cdots:A_{n}:B)$
$\displaystyle=D(\rho_{A_{1}^{n}B}||\bigotimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B})$
$\displaystyle=\sum_{k=1}^{n}I(A_{k}:A_{1}^{k-1}B)$ $\displaystyle\leq
n\epsilon.$

Using the substate theorem, we now have

$\displaystyle
D_{\max}^{\epsilon^{\frac{1}{4}}}\left(\rho_{A_{1}^{n}B}\middle\|\bigotimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B}\right)$
$\displaystyle\leq\frac{D(\rho_{A_{1}^{n}B}||\bigotimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B})+1}{\sqrt{\epsilon}}-\log(1-\sqrt{\epsilon})$
$\displaystyle\leq
n\sqrt{\epsilon}+\frac{1}{\sqrt{\epsilon}}-\log(1-\sqrt{\epsilon}).$ (33)

We now define the auxiliary state
$\eta_{A_{1}^{n}B}:=\bigotimes_{k=1}^{n}\rho_{A_{k}}\otimes\rho_{B}$. Using
Lemma 3.5, for $\alpha\in(1,2)$, we can transform the smooth min-entropy into
an $\alpha$-Rényi entropy on the auxiliary product state $\eta_{A_{1}^{n}B}$
as follows:

$\displaystyle H$
${}_{\min}^{\epsilon^{\frac{1}{4}}+\epsilon}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B)_{\eta}-\frac{\alpha}{\alpha-1}D^{\epsilon^{\frac{1}{4}}}_{\max}(\rho_{A_{1}^{n}B}||\eta_{A_{1}^{n}B})-\frac{g_{1}(\epsilon,\epsilon^{\frac{1}{4}})}{\alpha-1}$
$\displaystyle=\sum_{k=1}^{n}\tilde{H}^{\uparrow}_{\alpha}(A_{k})_{\rho}-\frac{\alpha}{\alpha-1}D^{\epsilon^{\frac{1}{4}}}_{\max}(\rho_{A_{1}^{n}B}||\eta_{A_{1}^{n}B})-\frac{g_{1}(\epsilon,\epsilon^{\frac{1}{4}})}{\alpha-1}$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k})_{\rho}-n(\alpha-1)\log^{2}(1+2|A|)-\frac{\alpha}{\alpha-1}D^{\epsilon^{\frac{1}{4}}}_{\max}(\rho_{A_{1}^{n}B}||\eta_{A_{1}^{n}B})-\frac{g_{1}(\epsilon,\epsilon^{\frac{1}{4}})}{\alpha-1}$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k})_{\rho}-n(\alpha-1)\log^{2}(1+2|A|)-\frac{\alpha}{\alpha-1}n\sqrt{\epsilon}-\frac{\alpha}{\alpha-1}\frac{1}{\sqrt{\epsilon}}-\frac{\alpha}{\alpha-1}\log(1-\sqrt{\epsilon})-\frac{g_{1}(\epsilon,\epsilon^{\frac{1}{4}})}{\alpha-1}.$

In the third line above, we have used [DFR20, Lemma B.9] (which is an
improvement of [TCR09, Lemma 8]), which is valid as long as
$\alpha<1+\frac{1}{\log(1+2|A|)}$. We will select
$\alpha=1+\frac{\epsilon^{1/4}}{\log(1+2|A|)}$ for which the above $\alpha$
bound is satisfied, this gives us

$\displaystyle H_{\min}^{\epsilon^{\frac{1}{4}}+\epsilon}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k})_{\rho}-3n\epsilon^{\frac{1}{4}}\log(1+2|A|)-\frac{2\log(1+2|A|)}{\epsilon^{3/4}}$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\epsilon^{1/4}}\left(\log(1-\sqrt{\epsilon})+g_{1}(\epsilon,\epsilon^{\frac{1}{4}})\right).$

∎

We can now plug the bound in Eq. 29 to derive the following Corollary.

######  Corollary 4.4.

Let registers $A_{k}$ have dimension $|A|$ for all $k\in[n]$. Suppose a
quantum state $\rho_{A_{1}^{n}B}$ is such that for every $k\in[n],$ we have

$\displaystyle\left\|\rho_{A_{1}^{k}B}-\rho_{A_{k}}\otimes\rho_{A_{1}^{k-1}B}\right\|_{1}\leq\epsilon.$
(34)

Then, we have that for
$\delta=\epsilon\log|A|+g_{2}\left(\frac{\epsilon}{2}\right)$ such that
$0<\delta<1$,

$\displaystyle H_{\min}^{\delta^{\frac{1}{4}}+\delta}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k})_{\rho}-3n\delta^{\frac{1}{4}}\log(1+2|A|)$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\delta^{3/4}}-\frac{2\log(1+2|A|)}{\delta^{1/4}}\left(\log(1-\sqrt{\delta})+g_{1}(\delta,\delta^{\frac{1}{4}})\right)$
(35)

where $g_{1}(x,y)=-\log(1-\sqrt{1-x^{2}})-\log(1-y^{2})$ and
$g_{2}(x)=(x+1)\log(x+1)-x\log(x)$. In particular, when all the states
$\rho_{A_{k}}$ are identical, we have

$\displaystyle H_{\min}^{\delta^{\frac{1}{4}}+\delta}(A_{1}^{n}|B)_{\rho}$
$\displaystyle\geq
n\left(H(A_{1})_{\rho}-3\delta^{\frac{1}{4}}\log(1+2|A|)\right)$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\delta^{3/4}}-\frac{2\log(1+2|A|)}{\delta^{1/4}}\left(\log(1-\sqrt{\delta})+g_{1}(\delta,\delta^{\frac{1}{4}})\right).$
(36)

###  4.1 Weak approximate asymptotic equipartition

We can modify the proof of Theorem 4.3 to prove a _weak_ approximate
asymptotic equipartition property (AEP).

######  Theorem 4.5.

Let registers $A_{k}$ have dimension $|A|$ for all $k\in[n]$ and the registers
$B_{k}$ have dimension $|B|$ for all $k\in[n]$. Suppose a quantum state
$\rho_{A_{1}^{n}B_{1}^{n}E}$ is such that for every $k\in[n],$ we have

$\displaystyle\left\|\rho_{A_{1}^{k}B_{1}^{k}E}-\rho_{A_{k}B_{k}}\otimes\rho_{A_{1}^{k-1}B_{1}^{k-1}E}\right\|_{1}\leq\epsilon.$
(37)

Then, we have that for
$\delta=\epsilon\log\left(|A||B|\right)+g_{2}\left(\frac{\epsilon}{2}\right)$
such that $0<\delta<1$,

$\displaystyle
H_{\min}^{\delta^{\frac{1}{4}}+\delta}(A_{1}^{n}|B_{1}^{n}E)_{\rho}$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k}|B_{k})_{\rho}-3n\delta^{\frac{1}{4}}\log(1+2|A|)$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\delta^{3/4}}-\frac{2\log(1+2|A|)}{\delta^{1/4}}\left(\log(1-\sqrt{\delta})+g_{1}(\delta,\delta^{\frac{1}{4}})\right)$
(38)

where $g_{1}(x,y)=-\log(1-\sqrt{1-x^{2}})-\log(1-y^{2})$ and
$g_{2}(x)=(x+1)\log(x+1)-x\log(x)$. In particular, when all the states
$\rho_{A_{k}B_{k}}$ are identical, we have

$\displaystyle
H_{\min}^{\delta^{\frac{1}{4}}+\delta}(A_{1}^{n}|B_{1}^{n}E)_{\rho}$
$\displaystyle\geq
n\left(H(A_{1}|B_{1})_{\rho}-3\delta^{\frac{1}{4}}\log(1+2|A|)\right)$
$\displaystyle\qquad-\frac{2\log(1+2|A|)}{\delta^{3/4}}-\frac{2\log(1+2|A|)}{\delta^{1/4}}\left(\log(1-\sqrt{\delta})+g_{1}(\delta,\delta^{\frac{1}{4}})\right).$
(39)

###### Proof.

To prove this, we use the auxiliary state
$\eta_{A_{1}^{n}B_{1}^{n}E}:=\bigotimes\rho_{A_{k}B_{k}}\otimes\rho_{E}$.
Then, we have

$\displaystyle D(\rho_{A_{1}^{n}B_{1}^{n}E}||\eta_{A_{1}^{n}B_{1}^{n}E})$
$\displaystyle=I(A_{1}B_{1}:A_{2}B_{2}:\cdots:A_{n}B_{n}:E)_{\rho}$
$\displaystyle=\sum_{k=1}^{n}I(A_{k}B_{k}:A_{1}^{k-1}B_{1}^{k-1}E)_{\rho}$
$\displaystyle\leq
n\left(\epsilon\log\left(|A||B|\right)+g\left(\frac{\epsilon}{2}\right)\right)=n\delta$

where we used the AFW bound for mutual information in the last line [Wil13,
Theorem 11.10.4]. The rest of the proof follows the proof of Theorem 4.3, only
difference being that now we have
$\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\eta}=\sum_{k=1}^{n}\tilde{H}^{\uparrow}_{\alpha}(A_{k}|B_{k})_{\rho}$.
∎

We call this generalisation _weak_ because the smoothing term ($\delta$)
depends on size of the side information $|B|$. In Sec. E, we show that under
the assumptions of the theorem, some sort of bound on the dimension of the
registers $B$ is necessary otherwise one cannot have a non-trivial bound on
the smooth min-entropy.

###  4.2 Simple security proof for sequential device independent quantum key
distribution

The approximately independent register scenario and the associated min-entropy
lower bound can be used to provide simple “proof of concept” security proofs
for cryptographic protocols. In this section, we will briefly sketch a proof
for sequential device independent quantum key distribution (DIQKD) to
demonstrate this idea. The protocol for sequential DIQKD used in [AF20] is
presented as Protocol 1.

Sequential DIQKD protocol
Parameters: • $\omega_{\text{exp}}$ is the expected winning probability for
the honest implementation of the device • $n\geq 1$ is the number of rounds in
the protocol • $\gamma\in(0,1]$ is the fraction of test rounds Protocol: 1.
For every $0\leq i\leq n$ perform the following steps: (a) Alice chooses a
random $T_{i}\in\\{0,1\\}$ with $\Pr[T_{i}=1]=\gamma$. (b) Alice sends $T_{i}$
to Bob. (c) If $T_{i}=0$, Alice and Bob set the questions
$(X_{i},Y_{i})=(0,2)$, otherwise they sample $(X_{i},Y_{i})$ uniformly at
random from $\\{0,1\\}$. (d) Alice and Bob use their device with the questions
$(X_{i},Y_{i})$ and obtain the outputs $A_{i},B_{i}$. 2. Alice announces her
questions $X_{1}^{n}$ to Bob. 3. Error correction: Alice and Bob use an error
correction procedure, which lets Bob obtain the raw key $\tilde{A}_{1}^{n}$
(if the error correction protocol succeeds, then
$A_{1}^{n}=\tilde{A}_{1}^{n}$). In case the error correction protocol aborts,
they abort the QKD protocol too. 4. Parameter Estimation: Bob uses $B_{1}^{n}$
and $\tilde{A}_{1}^{n}$ to compute the average winning probability
$\omega_{\text{avg}}$ on the test rounds. He aborts if
$\omega_{\text{avg}}<\omega_{\text{exp}}$ 5. Privacy Amplification: Alice and
Bob use a privacy amplification protocol to create a secret key $K$ from
$A_{1}^{n}$ (using $\tilde{A}_{1}^{n}$ for Bob).

We consider a simple model for DIQKD, where Eve (the adversary) distributes a
state $\rho^{(0)}_{E_{A}E_{B}E}$ between Alice and Bob at the beginning of the
protocol. Alice and Bob then use their states sequentially as given in
Protocol 1. The $k$th round of the protocol produces the questions
$X_{k},Y_{k}$ and $T_{k}$, the answers $A_{k}$ and $B_{k}$ and transforms the
shared state from $\rho^{(k-1)}_{E_{A}E_{B}E}$ to $\rho^{(k)}_{E_{A}E_{B}E}$.

Given the questions and answers of the previous rounds, the state shared
between Alice and Bob and their devices in each round can be viewed as a
device for playing the CHSH game. Suppose in the $k$th round, the random
variables produced in the previous $k-1$ rounds are
$r_{k-1}:=x_{1}^{k-1},y_{1}^{k-1},t_{1}^{k-1},a_{1}^{k-1},b_{1}^{k-1}$ and
that the state shared between Alice and Bob is
$\rho^{(k-1)}_{E_{A}E_{B}E|r_{k-1}}$. We can then define $\Pr[W_{k}|r_{k-1}]$
to be the winning probability of the CHSH game played by Alice and Bob using
the state and their devices in the $k$th round. Note that Alice’s device
cannot distinguish whether the CHSH game is played in a round or is used for
key generation. We can further take an average over all the previous round’s
random variables to derive the probability of winning the $k$th game

$\displaystyle\Pr[W_{k}]=\operatorname{\mathbb{E}}_{r_{k-1}}\left[\Pr[W_{k}|r_{k-1}]\right].$
(40)

Alice and Bob randomly sample a subset of the rounds (using the random
variable $T_{k}$) and play the CHSH game on this subset. If the average
winning probability of CHSH game on this subset is small, they abort the
protocol. For simplicity and brevity, we will assume here that the state
$\rho^{(0)}_{E_{A}E_{B}E}$ distributed between Alice and Bob at the start of
the protocol by Eve has an average winning probability at least
$\omega_{{\text{exp}}}$, that is,

$\displaystyle\frac{1}{n}\sum_{k=1}^{n}\Pr[W_{k}]\geq\omega_{{\text{exp}}}-\delta$
(41)

for some small $\delta>0$. Using standard sampling arguments it can be argued
that either this is true or the protocol aborts with high probability.

For any shared state $\sigma_{E_{A}E_{B}E}$ (where $E_{A}$ is held by Alice,
$E_{B}$ is held by Bob and $E$ is held by the adversary) and local measurement
devices, if Alice and Bob win the CHSH game with a probability
$\omega\in(\frac{3}{4},\frac{2+\sqrt{2}}{4}]$, then Alice’s answer $A$ to the
game is random given the questions $X,Y$ and the register $E$ held by
adversary. This is quantified by the following entropic bound [PAB+09] (see
[AF20, Lemma 5.3] for the following form)

$\displaystyle H(A|XYE)\geq
f(\omega)=\begin{cases}1-h\left(\frac{1}{2}+\frac{1}{2}\sqrt{16\omega(\omega-1)+3}\right)&\text{if
}\omega\in[\frac{3}{4},\frac{2+\sqrt{2}}{4}]\\\ 0&\text{if
}\omega\in[0,\frac{3}{4})\end{cases}$ (42)

where $h(\cdot)$ is the binary entropy. The function $f$ is convex over the
interval $\left[0,\frac{2+\sqrt{2}}{4}\right]$. We plot it in the interval
$[\frac{3}{4},\frac{2+\sqrt{2}}{4}]$ in Figure 2.

Figure 2: The lower bound in Eq. 42 for the interval
$[\frac{3}{4},\frac{2+\sqrt{2}}{4}]$

For $\epsilon>0$, we choose the parameter
$\omega_{\text{exp}}\in[\frac{3}{4}+\delta,\frac{2+\sqrt{2}}{4}]$ to be large
enough so that

$\displaystyle
1-f(\omega_{\text{exp}}-\delta)=h\left(\frac{1}{2}+\frac{1}{2}\sqrt{16(\omega_{\text{exp}}-\delta)(\omega_{\text{exp}}-\delta-1)+3}\right)\leq\epsilon^{4}.$
(43)

We will now use Eq. 42 to bound the von Neumann entropy of the answers given
Eve’s information for the sequential DIQKD protocol. We have

$\displaystyle H(A_{1}^{n}|X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)$
$\displaystyle=\sum_{k=1}^{n}H(A_{k}|A_{1}^{k-1}X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)$
$\displaystyle\overset{(1)}{=}\sum_{k=1}^{n}H(A_{k}|A_{1}^{k-1}X_{1}^{k}Y_{1}^{k}T_{1}^{k}E)$
$\displaystyle\overset{(2)}{=}\sum_{k=1}^{n}H(A_{k}|X_{k}Y_{k}R_{k-1}E)$
$\displaystyle=\sum_{k=1}^{n}\operatorname{\mathbb{E}}_{r_{k-1}\sim
R_{k-1}}\left[H(A_{k}|X_{k}Y_{k}E)_{\rho^{(k)}_{|r_{k-1}}}\right]$
$\displaystyle\overset{(3)}{\geq}\sum_{k=1}^{n}\operatorname{\mathbb{E}}_{r_{k-1}\sim
R_{k-1}}\left[f\left(\Pr[W_{k}|r_{k-1}]\right)\right]$
$\displaystyle\geq\sum_{k=1}^{n}f\left(\Pr[W_{k}]\right)$ $\displaystyle\geq
nf\left(\frac{1}{n}\sum_{k=1}^{n}\Pr[W_{k}]\right)$ $\displaystyle\geq
nf(\omega_{\text{exp}}-\delta)\geq n(1-\epsilon^{4})$

where in (1) we have used the fact that the questions sampled in the rounds
after the $k$th round are independent of the random variables in the previous
rounds, in (2) we use the fact that Alice’s answers are independent of the
random variable $T_{k}$ given the question $X_{k}$ and we also grouped the
random variables generated in the previous round into the random variable
$R_{k-1}:=A_{1}^{k-1}B_{1}^{k-1}X_{1}^{k-1}Y_{1}^{k-1}T_{1}^{k-1}$, in (3) we
use the bound in Eq. 42, and in the next two steps we use convexity of $f$. If
instead of the von Neumann entropy on the left-hand side above we had the
smooth min-entropy, then the bound above would be sufficient to prove the
security of DIQKD. However, this argument cannot be easily generalised to the
smooth min-entropy because a chain rule like the one used in the first step
does not exist for the smooth min-entropy (entropy accumulation [DFR20,
MFSR22] generalises exactly such an argument). We can use the argument used
for the approximately independent register case to transform this von Neumann
entropy bound to a smooth min-entropy bound.

This bound results in the following bound on the multipartite mutual
information

$\displaystyle I(A_{1}:\cdots:A_{n}:X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)$
$\displaystyle=\sum_{k=1}^{n}H(A_{k})+H(X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)-H(A_{1}^{n}X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)$
$\displaystyle=\sum_{k=1}^{n}H(A_{k})-H(A_{1}^{n}|X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)$
$\displaystyle\leq n-n(1-\epsilon^{4})=n\epsilon^{4}$

where we have used the dimension bound $H(A_{k})\leq 1$ for every $k\in[n]$.
This is the same as the multipartite mutual information bound we derived while
analysing approximately independent registers in Theorem 4.3. We can simply
use the smooth min-entropy bound derived there here as well. This gives us the
bound

$\displaystyle H^{2\epsilon}_{\min}(A_{1}^{n}|X_{1}^{n}Y_{1}^{n}T_{1}^{n}E)$
$\displaystyle\geq\sum_{k=1}^{n}H(A_{k})-3n\epsilon\log
5-O\left(\frac{1}{\epsilon^{3}}\right)$ $\displaystyle=n(1-3\epsilon\log
5)-O\left(\frac{1}{\epsilon^{3}}\right)$ (44)

where we have used the fact that the answers $A_{k}$ can always be assumed to
be uniformly distributed [PAB+09, AF20]. For every $\epsilon>0$, we can choose
a sufficiently large $n$ so that this bound is large and positive.

We note that this method is only able to provide “proof of concept” or
existence type security proofs. This proof method couples the value of the
security parameter for privacy amplification $\epsilon$ with the average
winning probability, which is not desirable. The parameter $\epsilon$ is
chosen according to the security requirements of the protocol and is typically
very small. For such values of $\epsilon$, the average winning probability of
the protocol will have to be extremely close to the maximum and we cannot
realistically expect practical implementations to achieve such high winning
probabilities. However, we do expect that this method will make it easier to
create “proof of concept” type proofs for new cryptographic protocols in the
future.

##  5 Approximate entropy accumulation

Figure 3: The setting for entropy accumulation and Theorem 5.1. For $k\in[n]$,
the channels $\operatorname{\mathcal{M}}_{k}$ are repeatedly applied to the
registers $R_{k-1}$ to produce the “secret” information $A_{k}$ and the side
information $B_{k}$.

In general, it is very difficult to estimate the smooth min-entropy of states
produced during cryptographic protocols. The entropy accumulation theorem
(EAT) [DFR20] provides a tight and simple lower bound for the smooth min-
entropy $H^{\epsilon}_{\min}(A_{1}^{n}|B_{1}^{n}E)_{\rho}$ of sequential
processes, under certain Markov chain conditions. The state
$\rho_{A_{1}^{n}B_{1}^{n}E}$ in the setting for EAT is produced by a
sequential process of the form shown in Figure 3. The parties implementing the
protocol begin with the registers $R_{0}$ and $E$. In the context of a
cryptographic protocol, the register $R_{0}$ is usually held by the honest
parties, whereas the register $E$ is held by the adversary. Then, in each
round $k\in[n]$ of the process, a channel
$\operatorname{\mathcal{M}}_{k}:R_{k-1}\rightarrow A_{k}B_{k}R_{k}$ is applied
on the register $R_{k-1}$ to produce the registers $A_{k},B_{k}$ and $R_{k}$.
The registers $A_{1}^{n}$ usually contain a partially secret raw key and the
registers $B_{1}^{n}$ contain the side information about $A_{1}^{n}$ revealed
to the adversary during the protocol. EAT requires that for every $k\in[n]$,
the side information $B_{k}$ satisfies the Markov chain
$A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow B_{k}$, that is, the
side information revealed in the $k$th round does not reveal anything more
about the secret registers of the previous rounds than was already known to
the adversary through $B_{1}^{k-1}E$. Under this assumption, EAT provides the
following lower bound for the smooth min-entropy

$\displaystyle
H^{\epsilon}_{\min}(A_{1}^{n}|B_{1}^{n}E)_{\rho}\geq\sum_{k=1}^{n}\inf_{\omega_{R_{k-1}R}}H(A_{k}|B_{k}R)_{\operatorname{\mathcal{M}}_{k}(\omega_{R_{k-1}R})}-c\sqrt{n}$
(45)

where the infimum is taken over all input states to the channels
$\operatorname{\mathcal{M}}_{k}$ and $c>0$ is a constant depending only on
$|A|$ (size of registers $A_{k}$) and $\epsilon$. We will state and prove an
approximate version of EAT. Consider the sequential process in Figure 3 again.
Now, suppose that the channels $\operatorname{\mathcal{M}}_{k}$ do not
necessarily satisfy the Markov chain conditions mentioned above, but each of
the channels $\operatorname{\mathcal{M}}_{k}$ can be $\epsilon$-approximated
by $\operatorname{\mathcal{M}}^{\prime}_{k}$ which satisfy the Markov chain
$A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow B_{k}$ for a certain
collection of inputs. The approximate entropy accumulation theorem below
provides a lower bound on the smooth min-entropy in such a setting. The proof
of this theorem again uses the technique based on the smooth min-entropy
triangle inequality developed in the previous section. In this setting too, we
have a chain of approximations. For each $k\in[n]$, we have

$\rho_{A_{1}^{k}B_{1}^{k}E}=\operatorname{tr}_{R_{k}}\circ\operatorname{\mathcal{M}}_{k}(\rho_{A_{1}^{k-1}B_{1}^{k-1}E})\approx_{\epsilon}\operatorname{tr}_{R_{k}}\circ\operatorname{\mathcal{M}}^{\prime}_{k}(\rho_{A_{1}^{k-1}B_{1}^{k-1}E})=:\sigma^{(k)}_{A_{1}^{k}B_{1}^{k}E}.$

According to the Markov chain assumption for the channels
$\operatorname{\mathcal{M}}^{\prime}_{k}$, the state
$\sigma^{(k)}_{A_{1}^{k}B_{1}^{k}E}$, satisfies the Markov chain
$A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow B_{k}$. Therefore, we
expect that the register $A_{k}$ adds some entropy to the smooth min-entropy
$H^{\epsilon^{\prime}}_{\min}(A_{1}^{n}|B_{1}^{n}E)_{\rho}$ and that the
information leaked through $B_{1}^{n}$ is not too large. We show that this is
indeed the case in the approximate entropy accumulation theorem.

The approximate entropy accumulation theorem can be used to analyse and prove
the security of cryptographic protocols under certain imperfections. For
example, the entropy accumulation theorem can be used to prove the security of
sequential device independent quantum key distribution (DIQKD) protocols
[AFDF+18]. In these protocols, the side information $B_{k}$ produced during
each of the rounds are the questions used during the round to play a non-local
game, like the CHSH game. In the ideal case, these questions are sampled
independently of everything which came before. As an example of an
imperfection, we can imagine that some physical effect between the memory
storing the secret bits $A_{1}^{k-1}$ and the device producing the questions
may lead to a small correlation between the side information produced during
the $k$th round and the secret bits $A_{1}^{k-1}$ (also see [JK23, Tan23]).
The approximate entropy accumulation theorem below can be used to prove
security of DIQKD under such imperfections. We do not, however, pursue this
example here and leave the applications of this theorem for future work.

######  Theorem 5.1.

For $k\in[n]$, let the registers $A_{k}$ and $B_{k}$ be such that
$|A_{k}|=|A|$ and $|B_{k}|=|B|$. For $k\in[n]$, let
$\operatorname{\mathcal{M}}_{k}$ be channels from $R_{k-1}\rightarrow
R_{k}A_{k}B_{k}$ and

$\displaystyle\rho_{A_{1}^{n}B_{1}^{n}E}=\operatorname{tr}_{R_{n}}\circ\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})$
(46)

be the state produced by applying these maps sequentially. Suppose the
channels $\operatorname{\mathcal{M}}_{k}$ are such that for every $k\in[n]$,
there exists a channel $\operatorname{\mathcal{M}}^{\prime}_{k}$ from
$R_{k-1}\rightarrow R_{k}A_{k}B_{k}$ such that

  1. 1.

$\operatorname{\mathcal{M}}^{\prime}_{k}$ $\epsilon$-approximates
$\operatorname{\mathcal{M}}_{k}$ in the diamond norm:

$\displaystyle\frac{1}{2}\left\|\operatorname{\mathcal{M}}_{k}-\operatorname{\mathcal{M}}^{\prime}_{k}\right\|_{\diamond}\leq\epsilon$
(47)

  2. 2.

For every choice of a sequence of channels
$\operatorname{\mathcal{N}}_{i}\in\\{\operatorname{\mathcal{M}}_{i},\operatorname{\mathcal{M}}^{\prime}_{i}\\}$
for $i\in[k-1]$, the state
$\operatorname{\mathcal{M}}^{\prime}_{k}\circ\operatorname{\mathcal{N}}_{k-1}\circ\cdots\circ\operatorname{\mathcal{N}}_{1}(\rho_{R_{0}E})$
satisfies the Markov chain

$\displaystyle A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow B_{k}.$
(48)

Then, for $0<\delta,\epsilon_{1},\epsilon_{2}<1$ such that
$\epsilon_{1}+\epsilon_{2}<1$,
$\alpha\in\left(1,1+\frac{1}{\log(1+2|A|)}\right)$ and $\beta>1$, we have

$\displaystyle
H_{\min}^{\epsilon_{1}+\epsilon_{2}}(A_{1}^{n}|B_{1}^{n}E)_{\rho}\geq\sum_{k=1}^{n}\inf_{\omega_{R_{k}\tilde{R}_{k}}}$
$\displaystyle
H(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}-n(\alpha-1)\log^{2}(1+2|A|)$
$\displaystyle-\frac{\alpha}{\alpha-1}n\log\left(1+\delta\left(2^{\frac{\alpha-1}{\alpha}2\log(|A||B|)}-1\right)\right)$
$\displaystyle-\frac{\alpha}{\alpha-1}nz_{\beta}(\epsilon,\delta)-\frac{1}{\alpha-1}\left(g_{1}(\epsilon_{2},\epsilon_{1})+\frac{\alpha
g_{0}(\epsilon_{1})}{\beta-1}\right).$ (49)

where

$\displaystyle
z_{\beta}(\epsilon,\delta):=\frac{\beta+1}{\beta-1}\log\left(\left(1+\sqrt{(1-\delta)\epsilon}\right)^{\frac{\beta}{\beta+1}}+\left(\frac{\sqrt{(1-\delta)\epsilon}}{\delta^{\beta}}\right)^{{\frac{1}{\beta+1}}}\right)$
(50)

and $g_{1}(x,y)=-\log(1-\sqrt{1-x^{2}})-\log(1-y^{2})$ and the infimum in Eq.
49 is taken over all input states to the channels
$\operatorname{\mathcal{M}}^{\prime}_{k}$.

For the choice of $\beta=2$, $\delta=\epsilon^{\frac{1}{8}}$, we have

$\displaystyle z_{2}(\epsilon,\delta)\leq
3\log\left(\left(1+\epsilon^{\frac{1}{2}}\right)^{\frac{2}{3}}+\epsilon^{\frac{1}{12}}\right).$

We also have that

$\displaystyle\log\left(1+\delta
2^{\frac{\alpha-1}{\alpha}2\log(|A||B|)}\right)\leq(|A||B|)^{2}\epsilon^{\frac{1}{8}}.$

Finally, if we define
$\epsilon_{r}:=(|A||B|)^{2}\epsilon^{\frac{1}{8}}+3\log\left(\left(1+\epsilon^{\frac{1}{2}}\right)^{\frac{2}{3}}+\epsilon^{\frac{1}{12}}\right)$,
and choose $\alpha=\sqrt{\epsilon_{r}}$, we get the bound

$\displaystyle
H_{\min}^{\epsilon_{1}+\epsilon_{2}}(A_{1}^{n}|B_{1}^{n}E)_{\rho}\geq\sum_{k=1}^{n}\inf_{\omega_{R_{k}\tilde{R}_{k}}}$
$\displaystyle
H(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}$
$\displaystyle-n\sqrt{\epsilon_{r}}(\log^{2}(1+2|A|)+2)-\frac{1}{\sqrt{\epsilon_{r}}}\left(g_{1}(\epsilon_{2},\epsilon_{1})+2g_{0}(\epsilon_{1})\right)$
(51)

The entropy loss per round in the above bound behaves as
$\sim\epsilon^{\frac{1}{24}}$. This dependence on $\epsilon$ is indeed very
poor. In comparison, we can carry out a similar proof argument for classical
probability distributions to get a dependence of $O(\sqrt{\epsilon})$ (Theorem
F.1). The exponent of $\epsilon$ in our bound seems to be almost a factor of
$12$ off from the best possible bound. Roughly speaking, while carrying out
the proof classically, we can bound the relevant channel divergences in the
proof by $O\left(\epsilon\right)$, whereas in Eq. 51, we were only able to
bound the channel divergence by $\sim\epsilon^{1/12}$. This leads to the
deterioration of performance we see here as compared to the classical case. We
will discuss this further in Sec. 5.4.

In order to prove this theorem, we will use a channel divergence based chain
rule. Recently proven chain rules for $\alpha$-Rényi relative entropy [FF21,
Corollary 5.2] state that for $\alpha>1$ and states $\rho_{A}$ and
$\sigma_{A}$, and channels $\mathcal{E}_{A\rightarrow B}$ and
$\mathcal{F}_{A\rightarrow B}$, we have

$\displaystyle\tilde{D}_{\alpha}(\mathcal{E}_{A\rightarrow
B}(\rho_{A})||\mathcal{F}_{A\rightarrow
B}(\sigma_{A}))\leq\tilde{D}_{\alpha}(\rho_{A}||\sigma_{A})+\tilde{D}_{\alpha}^{\text{reg}}(\mathcal{E}_{A\rightarrow
B}||\mathcal{F}_{A\rightarrow B})$ (52)

where $\tilde{D}_{\alpha}^{\text{reg}}(\mathcal{E}_{A\rightarrow
B}||\mathcal{F}_{A\rightarrow
B}):=\lim_{n\rightarrow\infty}\frac{1}{n}\tilde{D}_{\alpha}(\mathcal{E}_{A\rightarrow
B}^{\otimes n}||\mathcal{F}_{A\rightarrow B}^{\otimes n})$ and
$\tilde{D}_{\alpha}(\cdot||\cdot)$ is the channel divergence.

Now observe that if we were guaranteed that for the maps in Theorem 5.1 above,
$\tilde{D}_{\alpha}^{\text{reg}}(\operatorname{\mathcal{M}}_{k}||\operatorname{\mathcal{M}}^{\prime}_{k})\leq\epsilon$
for every $k$ for some $\alpha>1$. Then, we could use the chain rule in Eq. 52
as follows

$\displaystyle\tilde{D}_{\alpha}(\operatorname{\mathcal{M}}_{n}$
$\displaystyle\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})||\operatorname{\mathcal{M}}^{\prime}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\prime}_{1}(\rho_{R_{0}E}))$
$\displaystyle\leq\tilde{D}_{\alpha}(\operatorname{\mathcal{M}}_{n-1}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})||\operatorname{\mathcal{M}}^{\prime}_{n-1}\circ\cdots\circ\operatorname{\mathcal{M}}^{\prime}_{1}(\rho_{R_{0}E}))+\tilde{D}_{\alpha}^{\text{reg}}(\operatorname{\mathcal{M}}_{n}||\operatorname{\mathcal{M}}^{\prime}_{n})$
$\displaystyle\leq\cdots$
$\displaystyle\leq\tilde{D}_{\alpha}(\rho_{R_{0}E}||\rho_{R_{0}E})+\sum_{k=1}^{n}\tilde{D}_{\alpha}^{\text{reg}}(\operatorname{\mathcal{M}}_{k}||\operatorname{\mathcal{M}}^{\prime}_{k})$
$\displaystyle\leq n\epsilon.$

Once we have the above result we can simply use the well known relation
between smooth max-relative entropy and $\alpha$-Rényi relative entropy
[Tom16, Proposition 6.5] to get the bound

$\displaystyle{D}_{\max}^{\epsilon^{\prime}}(\operatorname{\mathcal{M}}_{n}$
$\displaystyle\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})||\operatorname{\mathcal{M}}^{\prime}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\prime}_{1}(\rho_{R_{0}E}))$
$\displaystyle\leq\tilde{D}_{\alpha}(\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})||\operatorname{\mathcal{M}}^{\prime}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\prime}_{1}(\rho_{R_{0}E}))+\frac{g_{0}(\epsilon^{\prime})}{\alpha-1}$
$\displaystyle\leq n\epsilon+O(1).$

This bound can subsequently be used in Lemma 3.5 to relate the smooth min-
entropy of the real state
$\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})$
with the $\alpha-$Rényi conditional entropy of the auxiliary state
$\operatorname{\mathcal{M}}^{\prime}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\prime}_{1}(\rho_{R_{0}E})$,
for which we can use the original entropy accumulation theorem.

In order to prove Theorem 5.1, we broadly follow this idea. However, the
condition
$\left\|\operatorname{\mathcal{M}}_{k}-\operatorname{\mathcal{M}}^{\prime}_{k}\right\|_{\diamond}\leq\epsilon$
does not lead to any kind of bound on $\tilde{D}_{\alpha}^{\text{reg}}$ or any
other channel divergence. We will get around this issue by instead using mixed
channels
$\operatorname{\mathcal{M}}^{\delta}_{k}:=(1-\delta)\operatorname{\mathcal{M}}^{\prime}_{k}+\delta\operatorname{\mathcal{M}}_{k}$.
Also, instead of trying to bound channel divergence in terms of
$\tilde{D}_{\alpha}^{\text{reg}}$, we will bound the $D^{\\#}_{\alpha}$
(defined in the next section) channel divergence and use its chain rule. We
develop the relevant $\alpha$-Rényi divergence bounds for this divergence in
the next two subsections and then prove the theorem above in Sec 5.3.

###  5.1 Divergence bound for approximately equal states

We will use the sharp Rényi divergence $D^{\\#}_{\alpha}$ defined in Ref.
[FF21] (see [BSD21] for the following equivalent definition) in this section.
For $\alpha>1$ and two positive operators $P$ and $Q$, it is defined

$\displaystyle D^{\\#}_{\alpha}(P||Q):=\min_{A\geq P}\hat{D}_{\alpha}(A||Q)$
(53)

where $\hat{D}_{\alpha}(A||Q)$ is the $\alpha$-Rényi geometric divergence
[Mat18]. For $\alpha>1$, it is defined as

$\displaystyle\hat{D}_{\alpha}(A||Q)=\begin{cases}\frac{1}{\alpha-1}\log\operatorname{tr}\left(Q\left(Q^{-\frac{1}{2}}AQ^{-\frac{1}{2}}\right)^{\alpha}\right)&\text{if
}A\ll Q\\\ \infty&\text{otherwise.}\end{cases}$ (54)

$A$ in the optimisation above is any operator $A\geq P$. In general, such an
operator $A$ is unnormalised. We will prove a bound on $D^{\\#}_{\alpha}$
between two states in terms of the distance between them and their max-
relative entropy. In order to prove this bound, we require the following
simple generalisation of the pinching inequality (see for example [Tom16,
Section 2.6.3]).

######  Lemma 5.2 (Asymmetric pinching).

For $t>0$, a positive semidefinite operator $X\geq 0$ and orthogonal
projections $\Pi$ and $\Pi_{\perp}=\operatorname{\mathds{1}}-\Pi$, we have
that

$\displaystyle X\leq(1+t)\Pi
X\Pi+\left(1+\frac{1}{t}\right)\Pi_{\perp}X\Pi_{\perp}.$ (55)

###### Proof.

We will write the positive matrix $X$ as the block matrix

$\displaystyle X=\begin{pmatrix}X_{1}\ X_{2}\\\ X_{2}^{\ast}\
X_{3}\end{pmatrix}$

where the blocks are partitioned according to the direct sum
$\operatorname{\text{im}}(\Pi)\oplus\operatorname{\text{im}}(\Pi_{\perp})$.
Then, the statement in the Lemma is equivalent to proving that

$\displaystyle\begin{pmatrix}X_{1}\ &X_{2}\\\ X_{2}^{\ast}\
&X_{3}\end{pmatrix}\leq\begin{pmatrix}(1+t)X_{1}\ &0\\\ 0\
&0\end{pmatrix}+\begin{pmatrix}0\ &0\\\ 0\
&\left(1+\frac{1}{t}\right)X_{3}\end{pmatrix}$

which is equivalent to proving that

$\displaystyle 0\leq\begin{pmatrix}tX_{1}\ &-X_{2}\\\ -X_{2}^{\ast}\
&\frac{1}{t}X_{3}\end{pmatrix}.$

This is true because

$\displaystyle\begin{pmatrix}tX_{1}\ &-X_{2}\\\ -X_{2}^{\ast}\
&\frac{1}{t}X_{3}\end{pmatrix}=\begin{pmatrix}-t^{1/2}\ &0\\\ 0\
&t^{-1/2}\end{pmatrix}\begin{pmatrix}X_{1}\ &X_{2}\\\ X_{2}^{\ast}\
&X_{3}\end{pmatrix}\begin{pmatrix}-t^{1/2}\ &0\\\ 0\
&t^{-1/2}\end{pmatrix}\geq 0$

since $X\geq 0$. ∎

######  Lemma 5.3.

Let $\epsilon>0$ and $\alpha\in(1,\infty)$, $\rho$ and $\sigma$ be two
normalized quantum states on the Hilbert space $\mathbb{C}^{n}$ such that
$\frac{1}{2}\left\|\rho-\sigma\right\|_{1}\leq\epsilon$ and also
$D_{\max}(\rho||\sigma)\leq d<\infty$, then we have the bound

$\displaystyle
D^{\\#}_{\alpha}(\rho||\sigma)\leq\frac{\alpha+1}{\alpha-1}\log\left((1+\sqrt{\epsilon})^{\frac{\alpha}{\alpha+1}}+\left(2^{\alpha
d}\sqrt{\epsilon}\right)^{\frac{1}{\alpha+1}}\right).$ (56)

Note: For a fixed $\alpha\in(1,\infty)$, this upper bound tends to zero as
$\epsilon\rightarrow 0$. On the other hand, for a fixed $\epsilon\in(0,1)$,
the upper bound tends to infinity as $\alpha\rightarrow 1$ (that is, the bound
becomes trivial). In Appendix B, we show that a bound of this form for
$D^{\\#}_{\alpha}$ necessarily diverges for $\epsilon>0$ as $\alpha\rightarrow
1$.

###### Proof.

Since, $D_{\max}(\rho||\sigma)<\infty$, we have that $\rho\ll\sigma$. We can
assume that $\sigma$ is invertible. If it was not, then we could always
restrict our vector space to the subspace $\text{supp}(\sigma)$.

Let $\rho-\sigma=P-Q$, where $P\geq 0$ is the positive part of the matrix
$\rho-\sigma$ and $Q\geq 0$ is its negative part. We then have that
$\operatorname{tr}(P)=\operatorname{tr}(Q)\leq\epsilon$.

Further, let

$\displaystyle\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}=\sum_{i=1}^{n}\lambda_{i}\ket{x_{i}}\bra{x_{i}}$
(57)

be the eigenvalue decomposition of
$\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}$. Define the real vector
$q\in\mathbb{R}^{n}$ as

$\displaystyle q(i):=\bra{x_{i}}\sigma\ket{x_{i}}.$

Note that $q$ is a probability distribution. Observe that

$\displaystyle\mathbb{E}_{I\sim q}\left[\lambda_{I}\right]$
$\displaystyle=\sum_{i=1}^{n}\lambda_{i}\bra{x_{i}}\sigma\ket{x_{i}}$
$\displaystyle=\operatorname{tr}\left(\sigma\sum_{i=1}^{n}\lambda_{i}\ket{x_{i}}\bra{x_{i}}\right)$
$\displaystyle=\operatorname{tr}\left(\sigma\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}\right)$
$\displaystyle=\operatorname{tr}(P)$ $\displaystyle\leq\epsilon.$

Also, observe that $\lambda_{i}\geq 0$ for all $i\in[n]$ because
$\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}\geq 0$. Let’s define

$\displaystyle S:=\\{i\in[n]:\lambda_{i}\leq\sqrt{\epsilon}\\}.$ (58)

Since, $\lambda_{i}\geq 0$ for all $i\in[n]$, we can use the Markov inequality
to show:

$\displaystyle\Pr_{q}(I\in S^{c})$
$\displaystyle=\Pr_{q}(\lambda_{I}>\sqrt{\epsilon})$
$\displaystyle\leq\frac{\operatorname{\mathbb{E}}_{I\sim
q}\left[\lambda_{I}\right]}{\sqrt{\epsilon}}$
$\displaystyle\leq\sqrt{\epsilon}.$

Thus, if we define the projectors $\Pi:=\sum_{i\in S}\ket{x_{i}}\bra{x_{i}}$
and $\Pi_{\perp}:=\sum_{i\in
S^{c}}\ket{x_{i}}\bra{x_{i}}=\operatorname{\mathds{1}}-\Pi$, we have

$\displaystyle\operatorname{tr}(\sigma\Pi_{\perp})$ $\displaystyle=\sum_{i\in
S^{c}}\bra{x_{i}}\sigma\ket{x_{i}}$ $\displaystyle=\Pr_{q}(I\in S^{c})$
$\displaystyle\leq\sqrt{\epsilon}.$ (59)

Moreover, by the definition of set $S$ (Eq. 58) we have

$\displaystyle\Pi\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}\Pi$
$\displaystyle=\sum_{i\in S}\lambda_{i}\ket{x_{i}}\bra{x_{i}}$
$\displaystyle\leq\sqrt{\epsilon}\Pi$ (60)

and using $D_{\max}(\rho||\sigma)\leq d$, we have that

$\displaystyle\sigma^{-\frac{1}{2}}\rho\sigma^{-\frac{1}{2}}\leq
2^{d}\operatorname{\mathds{1}}.$ (61)

Now, observe that since $\sigma^{-\frac{1}{2}}\rho\sigma^{-\frac{1}{2}}\geq
0$, for an arbitrary $t>0$, using Lemma 5.2 we have

$\displaystyle\sigma^{-\frac{1}{2}}\rho\sigma^{-\frac{1}{2}}$
$\displaystyle\leq(1+t)\Pi\sigma^{-\frac{1}{2}}\rho\sigma^{-\frac{1}{2}}\Pi+\left(1+\frac{1}{t}\right)\Pi_{\perp}\sigma^{-\frac{1}{2}}\rho\sigma^{-\frac{1}{2}}\Pi_{\perp}$
$\displaystyle\leq(1+t)\Pi\left(\operatorname{\mathds{1}}+\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}\right)\Pi+\left(1+\frac{1}{t}\right)2^{d}\Pi_{\perp}$
$\displaystyle\leq(1+t)(1+\sqrt{\epsilon})\Pi+\left(1+\frac{1}{t}\right)2^{d}\Pi_{\perp}$

where we have used $\rho\leq\sigma+P$ to bound the first term and Eq. 61 to
bound the second term in the second line, and Eq. 60 to bound
$\Pi\sigma^{-\frac{1}{2}}P\sigma^{-\frac{1}{2}}\Pi$ in the last step.

We will define
$A_{t}:=(1+t)(1+\sqrt{\epsilon})\sigma^{\frac{1}{2}}\Pi\sigma^{\frac{1}{2}}+\left(1+\frac{1}{t}\right)2^{d}\sigma^{\frac{1}{2}}\Pi_{\perp}\sigma^{\frac{1}{2}}$.
Above, we have shown that $A_{t}\geq\rho$ for every $t>0$. Therefore, for each
$t>0$, $D^{\\#}_{\alpha}(\rho||\sigma)\leq\hat{D}_{\alpha}(A_{t}||\sigma)$. We
will now bound $\hat{D}_{\alpha}(A_{t}||\sigma)$ for $\alpha\in(1,\infty)$ as:

$\displaystyle\hat{D}_{\alpha}(A_{t}||\sigma)$
$\displaystyle=\frac{1}{\alpha-1}\log\operatorname{tr}\left(\sigma\left(\sigma^{-\frac{1}{2}}A_{t}\sigma^{-\frac{1}{2}}\right)^{\alpha}\right)$
$\displaystyle=\frac{1}{\alpha-1}\log\operatorname{tr}\left(\sigma\left((1+t)(1+\sqrt{\epsilon})\Pi+\left(1+\frac{1}{t}\right)2^{d}\Pi_{\perp}\right)^{\alpha}\right)$
$\displaystyle=\frac{1}{\alpha-1}\log\operatorname{tr}\left(\sigma\left((1+t)^{\alpha}(1+\sqrt{\epsilon})^{\alpha}\Pi+\left(1+\frac{1}{t}\right)^{\alpha}2^{d\alpha}\Pi_{\perp}\right)\right)$
$\displaystyle=\frac{1}{\alpha-1}\log\left((1+t)^{\alpha}(1+\sqrt{\epsilon})^{\alpha}\operatorname{tr}\left(\sigma\Pi\right)+\left(1+\frac{1}{t}\right)^{\alpha}2^{d\alpha}\operatorname{tr}\left(\sigma\Pi_{\perp}\right)\right)$
$\displaystyle\leq\frac{1}{\alpha-1}\log\left((1+t)^{\alpha}(1+\sqrt{\epsilon})^{\alpha}+\left(1+\frac{1}{t}\right)^{\alpha}2^{d\alpha}\sqrt{\epsilon}\right)$

where in the last line we use $\operatorname{tr}(\sigma\Pi)\leq 1$ and
$\operatorname{tr}(\sigma\Pi_{\perp})\leq\sqrt{\epsilon}$ (Eq. 59). Finally,
since $t>0$ was arbitrary, we can choose the $t>0$ which minimizes the right-
hand side. For this choice of $t_{\min}=\left(\frac{2^{\alpha
d}\sqrt{\epsilon}}{\left(1+\sqrt{\epsilon}\right)^{\alpha}}\right)^{\frac{1}{\alpha+1}}$,
we get

$\displaystyle\hat{D}_{\alpha}(A_{t_{\min}}||\sigma)$
$\displaystyle\leq\frac{\alpha+1}{\alpha-1}\log\left((1+\sqrt{\epsilon})^{\frac{\alpha}{\alpha+1}}+2^{\frac{\alpha}{\alpha+1}d}\epsilon^{\frac{1}{2(\alpha+1)}}\right)$

which proves the required bound. ∎

###  5.2 Bounding the channel divergence for two channels close to each other

Suppose there are two channels $\operatorname{\mathcal{N}}$ and
$\operatorname{\mathcal{M}}$ mapping registers from the space $A$ to $B$ such
that
$\frac{1}{2}\left\|\operatorname{\mathcal{N}}-\operatorname{\mathcal{M}}\right\|_{\diamond}\leq\epsilon$.
In general, the channel divergence between two such channels can be infinite
because there may be states $\rho$ such that
$\operatorname{\mathcal{N}}(\rho)\not\ll\operatorname{\mathcal{M}}(\rho)$. In
order to get around this issue, we will use the $\delta-$mixed channel,
$\operatorname{\mathcal{M}}_{\delta}$. For $\delta\in(0,1)$, we define
$\operatorname{\mathcal{M}}_{\delta}$ as

$\displaystyle\mathcal{M}_{\delta}:=(1-\delta)\mathcal{M}+\delta\mathcal{N}.$

This guarantees that
$D_{\max}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}_{\delta})\leq\log\frac{1}{\delta}$,
which is enough to ensure that the divergences we are interested in are
finite. Moreover, by mixing $\operatorname{\mathcal{M}}$ with
$\operatorname{\mathcal{N}}$, we only decrease the distance:

$\displaystyle\frac{1}{2}\left\|\mathcal{M}_{\delta}-\operatorname{\mathcal{N}}\right\|_{\diamond}$
$\displaystyle=\frac{1}{2}\left\|(1-\delta)\operatorname{\mathcal{M}}+\delta\operatorname{\mathcal{N}}-\operatorname{\mathcal{N}}\right\|_{\diamond}$
$\displaystyle=(1-\delta)\frac{1}{2}\left\|\operatorname{\mathcal{M}}-\operatorname{\mathcal{N}}\right\|_{\diamond}$
$\displaystyle\leq(1-\delta)\epsilon.$ (62)

We will now show that
$D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}_{\delta})$
is small for an appropriately chosen $\delta$. By the definition of channel
divergence, we have that

$\displaystyle
D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}_{\delta})=\sup_{\rho_{AR}}D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}(\rho_{AR})||\operatorname{\mathcal{M}}_{\delta}(\rho_{AR}))$

where $R$ is an arbitrary reference system
($\operatorname{\mathcal{N}},\operatorname{\mathcal{M}}_{\delta}$ map register
$A$ to register $B$). We will show that for every $\rho_{AR}$,
$D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}(\rho_{AR})||\operatorname{\mathcal{M}}_{\delta}(\rho_{AR}))$
is small. Note that

$\displaystyle\operatorname{\mathcal{M}}_{\delta}(\rho_{AR})$
$\displaystyle=(1-\delta)\operatorname{\mathcal{M}}(\rho_{AR})+\delta\operatorname{\mathcal{N}}(\rho_{AR})$
$\displaystyle\geq\delta\operatorname{\mathcal{N}}(\rho_{AR})$

which implies that
$D_{\max}(\operatorname{\mathcal{N}}(\rho_{AR})||\operatorname{\mathcal{M}}_{\delta}(\rho_{AR}))\leq\log\frac{1}{\delta}$.
Also, using Eq. 62 have that

$\displaystyle\frac{1}{2}\left\|\mathcal{M}_{\delta}(\rho_{AR})-\operatorname{\mathcal{N}}(\rho_{AR})\right\|_{1}\leq(1-\delta)\epsilon.$

Using Lemma 5.3, we have for every $\alpha\in(1,\infty)$

$\displaystyle
D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}(\rho_{AR})||\operatorname{\mathcal{M}}_{\delta}(\rho_{AR}))\leq\frac{\alpha+1}{\alpha-1}\log\left(\left(1+\sqrt{(1-\delta)\epsilon}\right)^{\frac{\alpha}{\alpha+1}}+\left(\frac{\sqrt{(1-\delta)\epsilon}}{\delta^{\alpha}}\right)^{{\frac{1}{\alpha+1}}}\right).$

Since, this is true for all $\rho_{AR}$, for every $\alpha\in(1,\infty)$ we
have

$\displaystyle
D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}_{\delta})\leq\frac{\alpha+1}{\alpha-1}\log\left(\left(1+\sqrt{(1-\delta)\epsilon}\right)^{\frac{\alpha}{\alpha+1}}+\left(\frac{\sqrt{(1-\delta)\epsilon}}{\delta^{\alpha}}\right)^{{\frac{1}{\alpha+1}}}\right).$

Note that since $\delta$ was arbitrary, we can choose it appropriately to make
sure that the above bound is small, for example by choosing
$\delta=\epsilon^{\frac{1}{4\alpha}}$, we get the bound

$\displaystyle
D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}_{\delta})\leq\frac{\alpha+1}{\alpha-1}\log\left((1+\sqrt{\epsilon})^{\frac{\alpha}{\alpha+1}}+\epsilon^{\frac{1}{4(\alpha+1)}}\right)$

which is a small function of $\epsilon$ in the sense that it tends to $0$ as
$\epsilon\rightarrow 0$. We summarise the bound derived above in the following
lemma.

######  Lemma 5.4.

Let $\epsilon>0$. Suppose channels $\operatorname{\mathcal{N}}$ and
$\operatorname{\mathcal{M}}$ from register $A$ to $B$ are such that
$\frac{1}{2}\left\|\operatorname{\mathcal{N}}-\operatorname{\mathcal{M}}\right\|_{\diamond}\leq\epsilon$.
For $\delta\in(0,1)$, we can define the mixed channel
$\operatorname{\mathcal{M}}_{\delta}:=(1-\delta)\mathcal{M}+\delta\mathcal{N}$.
Then, for every $\alpha\in(1,\infty)$, we have the following bound on the
channel divergence

$\displaystyle
D^{\\#}_{\alpha}(\operatorname{\mathcal{N}}||\operatorname{\mathcal{M}}_{\delta})\leq\frac{\alpha+1}{\alpha-1}\log\left(\left(1+\sqrt{(1-\delta)\epsilon}\right)^{\frac{\alpha}{\alpha+1}}+\left(\frac{\sqrt{(1-\delta)\epsilon}}{\delta^{\alpha}}\right)^{{\frac{1}{\alpha+1}}}\right).$
(63)

###  5.3 Proof of the approximate entropy accumulation theorem

We use the mixed channels defined in the previous section to define the
auxiliary state
$\operatorname{\mathcal{M}}^{\delta}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\delta}_{1}(\rho_{R_{0}E})$
for our proof. It is easy to show using the divergence bounds in Sec. 5.2 and
the chain rule for $D^{\\#}_{\alpha}$ entropies that the relative entropy
distance between the real state and this choice of the auxiliary state is
small. However, the state
$\operatorname{\mathcal{M}}^{\delta}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\delta}_{1}(\rho_{R_{0}E})$
does not necessarily satisfy the Markov chain conditions required for entropy
accumulation. Thus, we also need to reprove the entropy lower bound on this
state by modifying the approach used in the proof of the original entropy
accumulation theorem.

###### Proof of Theorem 5.1.

Using Lemma 5.4, for every $\delta\in(0,1)$ and for each $k\in[n]$ we have
that for every $\beta>1$, the mixed maps
$\operatorname{\mathcal{M}}^{\delta}_{k}:=(1-\delta)\operatorname{\mathcal{M}}^{\prime}_{k}+\delta\operatorname{\mathcal{M}}_{k}$
satisfy

$\displaystyle
D^{\\#}_{\beta}(\operatorname{\mathcal{M}}_{k}||\operatorname{\mathcal{M}}^{\delta}_{k})$
$\displaystyle\leq\frac{\beta+1}{\beta-1}\log\left(\left(1+\sqrt{(1-\delta)\epsilon}\right)^{\frac{\beta}{\beta+1}}+\left(\frac{\sqrt{(1-\delta)\epsilon}}{\delta^{\beta}}\right)^{{\frac{1}{\beta+1}}}\right)$
$\displaystyle:=z_{\beta}(\epsilon,\delta)$ (64)

where we defined the right-hand side above as $z_{\beta}(\epsilon,\delta)$.
This can be made “small” by choosing $\delta=\epsilon^{\frac{1}{4\beta}}$ as
was shown in the previous section. We use these maps to define the auxiliary
state as

$\displaystyle\sigma_{A_{1}^{n}B_{1}^{n}E}:=\operatorname{\mathcal{M}}^{\delta}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\delta}_{1}(\rho_{R_{0}E}).$
(65)

Now, we have that for $\beta>1$ and $\epsilon_{1}>0$

$\displaystyle D^{\epsilon_{1}}_{\max}$
$\displaystyle(\rho_{A_{1}^{n}B_{1}^{n}E}||\sigma_{A_{1}^{n}B_{1}^{n}E})$
$\displaystyle\leq\tilde{D}_{\beta}(\rho_{A_{1}^{n}B_{1}^{n}E}||\sigma_{A_{1}^{n}B_{1}^{n}E})+\frac{g_{0}(\epsilon_{1})}{\beta-1}$
$\displaystyle\leq
D^{\\#}_{\beta}(\rho_{A_{1}^{n}B_{1}^{n}E}||\sigma_{A_{1}^{n}B_{1}^{n}E})+\frac{g_{0}(\epsilon_{1})}{\beta-1}$
$\displaystyle=D^{\\#}_{\beta}(\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})||\operatorname{\mathcal{M}}^{\delta}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\delta}_{1}(\rho_{R_{0}E}))+\frac{g_{0}(\epsilon_{1})}{\beta-1}$
$\displaystyle\leq
D^{\\#}_{\beta}(\operatorname{\mathcal{M}}_{n-1}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})||\operatorname{\mathcal{M}}^{\delta}_{n-1}\circ\cdots\circ\operatorname{\mathcal{M}}^{\delta}_{1}(\rho_{R_{0}E}))+D^{\\#}_{\beta}(\operatorname{\mathcal{M}}_{n}||\operatorname{\mathcal{M}}^{\delta}_{n})+\frac{g_{0}(\epsilon_{1})}{\beta-1}$
$\displaystyle\leq\cdots$
$\displaystyle\leq\sum_{k=1}^{n}D^{\\#}_{\beta}(\operatorname{\mathcal{M}}_{k}||\operatorname{\mathcal{M}}^{\delta}_{k})+\frac{g_{0}(\epsilon_{1})}{\beta-1}$
$\displaystyle\leq
nz_{\beta}(\epsilon,\delta)+\frac{g_{0}(\epsilon_{1})}{\beta-1}$ (66)

where the first line follows from [Tom16, Proposition 6.5], the second line
follows from [FF21, Proposition 3.4], fourth line follows from the chain rule
for $D^{\\#}_{\beta}$ [FF21, Proposition 4.5], and the last line follows from
Eq. 64.

For $\epsilon_{2}>0$ and $\alpha\in(1,1+\frac{1}{\log(1+2|A|)})$, we can plug
the above in the bound provided by Lemma 3.5 to get

$\displaystyle
H_{\min}^{\epsilon_{1}+\epsilon_{2}}(A_{1}^{n}|B_{1}^{n}E)_{\rho}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\sigma}-\frac{\alpha}{\alpha-1}nz_{\beta}(\epsilon,\delta)$
$\displaystyle\qquad-\frac{1}{\alpha-1}\left(g_{1}(\epsilon_{2},\epsilon_{1})+\frac{\alpha
g_{0}(\epsilon_{1})}{\beta-1}\right).$ (67)

We have now reduced our problem to lower bounding
$\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\sigma}$. Note that we
cannot directly use the entropy accumulation here, since the mixed maps
$\operatorname{\mathcal{M}}^{\delta}_{k}=(1-\delta)\operatorname{\mathcal{M}}^{\prime}_{k}+\delta\operatorname{\mathcal{M}}_{k}$,
which means that with $\delta$ probability the $B_{k}$ register may be
correlated with $A_{1}^{k-1}$ even given $B_{1}^{k-1}E$, and it may not
satisfy the Markov chain required for entropy accumulation.

The application of the maps $\operatorname{\mathcal{M}}^{\delta}_{k}$ can be
viewed as applying the channel $\operatorname{\mathcal{M}}^{\prime}_{k}$ with
probability $1-\delta$ and the channel $\operatorname{\mathcal{M}}_{k}$ with
probability $\delta$. We can define the channels
$\operatorname{\mathcal{N}}_{k}$ which map the registers $R_{k-1}$ to
$R_{k}A_{k}B_{k}C_{k}$, where $C_{k}$ is a binary register. The action of
$\operatorname{\mathcal{N}}_{k}$ can be defined as:

  1. 1.

Sample the classical random variable $C_{k}\in\\{0,1\\}$ independently.
$C_{k}=1$ with probability $1-\delta$ and $0$ otherwise.

  2. 2.

If $C_{k}=1$ apply the map $\operatorname{\mathcal{M}}^{\prime}_{k}$ on
$R_{k-1}$, else apply $\operatorname{\mathcal{M}}_{k}$ on $R_{k-1}$.

Let us call
$\theta_{A_{1}^{n}B_{1}^{n}C_{1}^{n}E}=\operatorname{\mathcal{N}}_{n}\circ\cdots\circ\operatorname{\mathcal{N}}_{1}(\rho_{R_{0}E})$.
Clearly
$\operatorname{tr}_{C_{1}^{n}}\left(\theta_{A_{1}^{n}B_{1}^{n}C_{1}^{n}E}\right)=\sigma_{A_{1}^{n}B_{1}^{n}E}$.
Thus, we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\sigma}$
$\displaystyle=\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}C_{1}^{n}E)_{\theta}.$
(68)

We will now focus on lower bounding
$\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}C_{1}^{n}E)_{\theta}$. Using
[Tom16, Proposition 5.1], we have that

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}C_{1}^{n}E)_{\theta}=\frac{\alpha}{1-\alpha}\log\sum_{c_{1}^{n}}\theta(c_{1}^{n})\exp\left(\frac{1-\alpha}{\alpha}\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta_{|c_{1}^{n}}}\right).$

We will show that for a given $c_{1}^{n}$, the conditional entropy
$\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta_{|c_{1}^{n}}}$
accumulates whenever the “good” map $\operatorname{\mathcal{M}}^{\prime}_{k}$
is used and loses some entropy for the rounds where the “bad” map
$\operatorname{\mathcal{M}}_{k}$ is used. The fact that $c_{1}^{n}$ contains
far more $1$s than $0$s with a large probability then allows us to prove a
lower bound on
$\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}C_{1}^{n}E)_{\theta}$.

######  Claim 5.5.

Define
$h_{k}:=\inf_{\omega_{R_{k}\tilde{R}_{k}}}\tilde{H}^{\downarrow}_{\alpha}(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}$
where the infimum is over all states $\omega_{R_{k}\tilde{R}_{k}}$ for a
register $\tilde{R}_{k}$, which is isomorphic to $R_{k}$, and
$s:=\log(|A||B|^{2})$. Then, we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta_{|c_{1}^{n}}}\geq\sum_{k=1}^{n}\left(\delta({c_{k},1})h_{k}-\delta({c_{k},0})s\right)$
(69)

where $\delta({x,y})$ is the Kronecker delta function ($\delta({x,y})=1$ if
$x=y$ and $0$ otherwise).

###### Proof.

We will prove the statement

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k}|B_{1}^{k}E)_{\theta_{|c_{1}^{k}}}\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k-1}E)_{\theta_{|c_{1}^{k-1}}}+\left(\delta({c_{k},1})h_{k}-\delta({c_{k},0})s\right)$

then the claim will follow inductively. We will consider two cases: when
$c_{k}=0$ and when $c_{k}=1$. First suppose, $c_{k}=0$ then
$\theta_{A_{1}^{k}B_{1}^{k}E|c_{1}^{k}}=\operatorname{tr}_{R_{k}}\circ\operatorname{\mathcal{M}}_{k}^{R_{k-1}\rightarrow
R_{k}A_{k}B_{k}}\left(\theta_{R_{k-1}A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k}}\right)$.
In this case, we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k}|B_{1}^{k}E)_{\theta_{|c_{1}^{k}}}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k}E)_{\theta_{|c_{1}^{k}}}-\log|A|$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k-1}E)_{\theta_{|c_{1}^{k}}}-\log\left(|A||B|^{2}\right)$
$\displaystyle=\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k-1}E)_{\theta_{|c_{1}^{k-1}}}-s$

where in the first line we have used the dimension bound in Lemma D.1, in the
second line we have used the dimension bound in Lemma D.3 and in the last line
we have used
$\theta_{A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k}}=\theta_{A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k-1}}$.

Now, suppose that $c_{k}=1$. In this case, we have that
$\theta_{A_{1}^{k}B_{1}^{k}E|c_{1}^{k}}=\operatorname{tr}_{R_{k}}\circ\operatorname{\mathcal{M}}_{k}^{\prime}\left(\theta_{R_{k-1}A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k}}\right)$
and since
$\theta_{R_{k-1}A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k}}=\Phi_{k-1}\circ\Phi_{k-2}\cdots\circ\Phi_{1}(\rho_{R_{0}E})$
where each of the
$\Phi_{i}\in\\{\operatorname{\mathcal{M}}_{i},\operatorname{\mathcal{M}}^{\prime}_{i}\\}$,
using the hypothesis of the theorem we have that the state
$\theta_{A_{1}^{k}B_{1}^{k}E|c_{1}^{k}}=\operatorname{\mathcal{M}}_{k}^{\prime}\left(\theta_{R_{k-1}A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k}}\right)$
satisfies the Markov chain

$\displaystyle A_{1}^{k-1}\leftrightarrow B_{1}^{k-1}E\leftrightarrow B_{k}.$

Now, using Corollary C.5 (the $\tilde{H}^{\uparrow}_{\alpha}$ counterpart for
[DFR20, Corollary 3.5], which is the main chain rule used for proving entropy
accumulation), we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k}|B_{1}^{k}E)_{\theta_{|c_{1}^{k}}}$
$\displaystyle\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k-1}E)_{\theta_{|c_{1}^{k}}}+\inf_{\omega_{R_{k}\tilde{R}_{k}}}\tilde{H}^{\downarrow}_{\alpha}(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}$
$\displaystyle=\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k-1}E)_{\theta_{|c_{1}^{k-1}}}+h_{k}$

where in the last line we have again used
$\theta_{A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k}}=\theta_{A_{1}^{k-1}B_{1}^{k-1}E|c_{1}^{k-1}}$.
Combining these two cases, we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k}|B_{1}^{k}E)_{\theta_{|c_{1}^{k}}}\geq\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{k-1}|B_{1}^{k-1}E)_{\theta_{|c_{1}^{k-1}}}+\left(\delta({c_{k},1})h_{k}-\delta({c_{k},0})s\right).$
(70)

Using this bound $n$ times starting with
$\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta_{|c_{1}^{n}}}$
gives us the bound required in the claim. ∎

For the sake of clarity let
$l_{k}(c_{k}):=\left(\delta({c_{k},1})h_{k}-\delta({c_{k},0})s\right)$. We
will now evaluate

$\displaystyle\sum_{c_{1}^{n}}\theta(c_{1}^{n})\exp\left(\frac{1-\alpha}{\alpha}\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta_{|c_{1}^{n}}}\right)$
$\displaystyle\leq\sum_{c_{1}^{n}}\theta(c_{1}^{n})\exp\left(\frac{1-\alpha}{\alpha}\sum_{k=1}^{n}l_{k}(c_{k})\right)$
$\displaystyle=\sum_{c_{1}^{n}}\prod_{k=1}^{n}\theta(c_{k})2^{\frac{1-\alpha}{\alpha}l_{k}(c_{k})}$
$\displaystyle=\prod_{k=1}^{n}\sum_{c_{k}}\theta(c_{k})2^{\frac{1-\alpha}{\alpha}l_{k}(c_{k})}.$
(71)

Then, we have

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}C_{1}^{n}E)_{\theta}$
$\displaystyle=\frac{\alpha}{1-\alpha}\log\sum_{c_{1}^{n}}\theta(c_{1}^{n})\exp_{2}\left(\frac{1-\alpha}{\alpha}\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}E)_{\theta_{|c_{1}^{n}}}\right).$
$\displaystyle\geq\frac{\alpha}{1-\alpha}\sum_{k=1}^{n}\log\sum_{c_{k}}\theta(c_{k})2^{\frac{1-\alpha}{\alpha}l_{k}(c_{k})}$
$\displaystyle=\frac{\alpha}{1-\alpha}\sum_{k=1}^{n}\log\left((1-\delta)2^{\frac{1-\alpha}{\alpha}h_{k}}+\delta
2^{-\frac{1-\alpha}{\alpha}s}\right)$
$\displaystyle=\sum_{k=1}^{n}h_{k}-\frac{\alpha}{\alpha-1}\sum_{k=1}^{n}\log\left(1-\delta+\delta
2^{\frac{\alpha-1}{\alpha}(s+h_{k})}\right)$
$\displaystyle\geq\sum_{k=1}^{n}h_{k}-\frac{\alpha}{\alpha-1}n\log\left(1+\delta\left(2^{\frac{\alpha-1}{\alpha}(s+\log|A|)}-1\right)\right)$

where in the second line we have used Eq. 71 and in the last line we have used
the fact that $h_{k}\leq\log|A|$ for all $k\in[n]$.

We restricted the choice of $\alpha$ to the region
$\left(1,1+\frac{1}{\log(1+2|A|)}\right)$ in the theorem, so that we can now
use [DFR20, Lemma B.9] to transform the above to

$\displaystyle\tilde{H}^{\uparrow}_{\alpha}(A_{1}^{n}|B_{1}^{n}C_{1}^{n}E)_{\theta}\geq\sum_{k=1}^{n}\inf_{\omega_{R_{k}\tilde{R}_{k}}}$
$\displaystyle
H(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}-n(\alpha-1)\log^{2}(1+2|A|)$
$\displaystyle-\frac{\alpha}{\alpha-1}n\log\left(1+\delta\left(2^{\frac{\alpha-1}{\alpha}2\log(|A||B|)}-1\right)\right).$
(72)

Putting Eq. 67, Eq. 68, and Eq. 72 together, we have

$\displaystyle
H_{\min}^{\epsilon_{1}+\epsilon_{2}}(A_{1}^{n}|B_{1}^{n}E)_{\rho}\geq\sum_{k=1}^{n}\inf_{\omega_{R_{k}\tilde{R}_{k}}}$
$\displaystyle
H(A_{k}|B_{k}\tilde{R}_{k})_{\operatorname{\mathcal{M}}^{\prime}_{k}(\omega_{R_{k}\tilde{R}_{k}})}-n(\alpha-1)\log^{2}(1+2|A|)$
$\displaystyle-\frac{\alpha}{\alpha-1}n\log\left(1+\delta\left(2^{\frac{\alpha-1}{\alpha}2\log(|A||B|)}-1\right)\right)$
$\displaystyle-\frac{\alpha}{\alpha-1}nz_{\beta}(\epsilon,\delta)\frac{1}{\alpha-1}\left(g_{1}(\epsilon_{2},\epsilon_{1})+\frac{\alpha
g_{0}(\epsilon_{1})}{\beta-1}\right).$

∎

###  5.4 Limitations and further improvements

As we pointed out previously, the dependence of the entropy loss per round on
$\epsilon$ is very poor (behaves as $\sim\epsilon^{1/24}$) in this theorem.
The classical version of this theorem has a much better dependence of
$O(\sqrt{\epsilon})$ on $\epsilon$ (see Theorem F.1). The reason for the poor
performance of the quantum version is that our bound on the channel divergence
(Lemma 5.4) is very weak compared to the bound we can use classically. It
should be noted, however, that if Lemma 5.4 were to be improved in the future,
one could simply plug the new bound into our proof and derive an improvement
for Theorem 5.1.

A better bound on the channel divergence would have an additional benefit. It
could simplify the proof and the Markov chain assumption in our theorem. In
particular, it would be much easier to carry out the proof if the mixed
channels $\operatorname{\mathcal{M}}^{\delta}_{k}$ were defined as
$(1-\delta)\operatorname{\mathcal{M}}^{\prime}_{k}+\delta\tau_{A_{k}B_{k}}\otimes\operatorname{tr}_{A_{k}B_{k}}\circ\operatorname{\mathcal{M}}_{k}$
(which is what is done classically), where $\tau_{A_{k}B_{k}}$ is the
completely mixed state on registers $A_{k}B_{k}$. Here, instead of mixing the
channel $\operatorname{\mathcal{M}}^{\prime}_{k}$ with
$\operatorname{\mathcal{M}}_{k}$, we mix it with
$\tau_{A_{k}B_{k}}\otimes\operatorname{tr}_{A_{k}B_{k}}\circ\operatorname{\mathcal{M}}_{k}$,
which also keeps
$D_{\max}(\operatorname{\mathcal{M}}_{k}||\operatorname{\mathcal{M}}^{\delta}_{k})$
small enough. Moreover, this definition ensures that the registers $B_{k}$
produced by the map $\operatorname{\mathcal{M}}_{k}^{\delta}$ always satisfy
the Markov chain conditions. If it were possible to show that the divergence
between the real state
$\operatorname{\mathcal{M}}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}_{1}(\rho_{R_{0}E})$
and the auxiliary state
$\operatorname{\mathcal{M}}^{\delta}_{n}\circ\cdots\circ\operatorname{\mathcal{M}}^{\delta}_{1}(\rho_{R_{0}E})$
is small for this definition of $\operatorname{\mathcal{M}}_{k}^{\delta}$,
then one could directly use the entropy accumulation theorem for lower
bounding the entropy for the auxiliary state. We cannot do this in our proof
as this definition of the mixed channel
$\operatorname{\mathcal{M}}^{\delta}_{k}$ also increases the distance from the
original channel $\operatorname{\mathcal{M}}_{k}$ to $\epsilon+2\delta$ and
this makes the upper bound in Lemma 5.3 large (finite even in the limit
$\epsilon\rightarrow 0$).

It seems that it should be possible to weaken the assumptions for approximate
entropy accumulation. The classical equivalent of this theorem (Theorem F.1)
for instance can be proven very easily and requires a much weaker
approximation assumption. It would be interesting if one could remove the
“memory” registers $R_{k}$ from the assumptions required for approximate
entropy accumulation, since these are not typically accessible to the users in
applications.

Another troubling feature of the approximate entropy accumulation theorem
seems to be that it assumes that the size of the side information registers
$B_{k}$ is constant. One might wonder if this is necessary, since continuity
bounds like the Alicki-Fannes-Winter (AFW) inequality do not depend on the
size of the side information. It turns out that a bound on the side
information size is indeed necessary in this case. We show a simple classical
example to demonstrate this in Appendix E.

##  6 Source Correlations

Protocols in quantum cryptography often require an honest party to produce
multiple independent quantum states. As an example, quantum key distribution
(QKD) protocols [BB84, Ben92] and bit commitment protocols [KWW12, LMT20] all
require the honest participant, Alice to produce an independently chosen
quantum state from a set of states in every round of the protocol. The
security proofs for these protocols also rely on the fact that the quantum
state produced in each round of the protocol is independent of the other
rounds. However, this is a difficult property to enforce practically. All
physical devices have an internal memory, which is difficult to characterise
and control. This memory can cause the quantum states produced in different
rounds to be correlated with one another. For example, when implementing BB84
states using the polarisation of light, if the polariser is in the horizontal
polarisation ($\ket{0}$) for round $k$, and it is switched to the
$\Pi/4$-diagonal polarisation ($\ket{+}$) in the $(k+1)$th round, then it is
plausible that the state produced in the $(k+1)$th round is “tilted” towards
the horizontal (that is, has a larger component along $\ket{0}$ than
$\ket{1}$) simply due to the inertia of switching the polariser. Such
correlations between different rounds caused by an imperfect source are called
_source correlations_. Security proofs for cryptographic protocols need to
consider such correlations in order to be relevant in the real world.

We will consider the BB84-QKD protocol, which uses such an imperfect source,
here. An extensive line of research has led to techniques for proving the
security of such a QKD protocol [SP00, Ren06, TL17, DFR20, MR22]. However,
almost all of these techniques rely on _source purification_(7)(7)(7)Only
[MR22] does not use source purification, but it still requires that the states
in each round be produced independently.\- the fact that the security of this
protocol is equivalent to one where Alice sends out one half of a Bell state
in each round and randomly measures her half. When the states produced by
Alice’s source are correlated across different rounds, this equivalence step
fails and one can no longer use the above methods. In this section, we will
use the triangle inequality of Lemma 3.5 to reduce the security of the
BB84-QKD protocol with source correlations to that of the BB84 protocol with a
perfect source. Then, one can simply use the security analysis methods
developed for such protocols to complete the security proof. Although we focus
on the BB84-QKD protocol here, our technique is quite general, and we believe
it can also be applied to other cryptographic protocols.

Our method relies on randomly testing the output of the source on a small
sample of the rounds by measuring it in the preparation basis and conditioning
on the relative deviation of the observed output being less than some small
threshold $\epsilon$ from the expected output. We do not have to place any
assumptions on the source, except that it passes this source test with a non-
negligible probability. We also demonstrate how our analysis can be modified
to incorporate imperfect measurements. In comparison, [PCLN+22], which is one
of the most comprehensive treatments of source imperfections and source
correlation, makes multiple complex assumptions about Alice’s source (also see
[CLPK+23]). Among these, it assumes that the state produced by Alice in the
$k$th round can only be correlated to the states produced in the $\ell_{c}$
rounds preceding it, where $\ell_{c}$ is some known constant. Moreover, it
also assumes that Alice’s quantum states are not entangled across different
rounds. These are both, as noted by the authors in [PCLN+22], very strong
assumptions, which cannot be guaranteed in practical setups. Importantly, it
is also not possible to estimate the parameter $\ell_{c}$ experimentally. In
contrast, we provide a simpler and more general technique, which reduces the
security proof to that of a noisy version of the underlying
protocol(8)(8)(8)Following this reduction, any security proof technique for
QKD which can bound $\tilde{H}^{\uparrow}_{\alpha}$ of Alice’s raw key given
Eve’s side information can be used to complete the proof. The assumptions for
the security of the protocol will be a combination of the assumptions required
for this security proof and the assumptions used during the testing procedure
presented in Protocol 6., and itself only requires assumptions for the
measurements employed for testing. Moreover, these measurements are used at a
far smaller rate than the source itself during the protocol.

###  6.1 Security proof for BB84 with source correlations

The BB84 QKD protocol has been described in Protocol 4. In Table 1, we list
all the variables, we use for our proof and their definitions.

At the beginning of every round of the QKD protocol, Alice prepares the
classical registers $X_{i}$ and $\Theta_{i}$, and a corresponding qubit in the
register $A_{i}$. If Alice’s quantum source were perfect, she would produce
the following state during each round of the protocol

$\displaystyle\hat{\rho}_{X\Theta
A}:=\sum_{x\in\mathcal{X},\theta\in\Theta}p(x,\theta)\ket{x,\theta}\bra{x,\theta}_{X\Theta}\otimes
H^{\theta}\ket{x}\bra{x}_{A}H^{\theta}$ (73)

where $H$ is the Hadamard gate and

$\displaystyle p(x,\theta)=\begin{cases}\frac{1-\mu}{|\mathcal{X}|}&\text{if
}\theta=0\\\ \frac{\mu}{|\mathcal{X}|}&\text{if }\theta=1.\end{cases}$

BB84 QKD protocol
Parameters: • $n$ is the number of qubits sent by Alice. • $\mu\in(0,1)$ is
the probability of encoding and measurement in the $X$ basis
$\\{\ket{+},\ket{-}\\}$. • $e\in(0,\frac{1}{2})$ is the maximum error
tolerated. • $r\in(0,1)$ is the key rate of the protocol. Protocol: 1. For
every $1\leq i\leq n$ perform the following steps: (a) Alice chooses a random
bit $X_{i}\in_{R}\\{0,1\\}$ and with probability $1-\mu$ encodes it in the $Z$
basis and with probability $\mu$ in the $X$ basis. (b) Alice sends her encoded
qubit to Bob. (c) Bob measures the qubit in the $Z$ basis with probability
$1-\mu$ and $X$ basis with probability $\mu$. He records the output as
$Y_{i}$. 2. Sifting: Alice and Bob share their choice of bases for all the
rounds and discard the rounds where their choices are different. We denote the
remaining rounds by the set $S$. 3. Error correction: Alice and Bob use an
error correction procedure, which lets Bob obtain a guess $\hat{X}_{S}$ for
Alice’s raw key $X_{S}$. In case the error correction protocol aborts, they
abort the QKD protocol too. 4. Parameter estimation: Let $S_{X}$ be the set of
rounds where Alice prepared the qubit in the $X$ basis and Bob measured the
qubit in $X$ basis. Bob computes ${\hat{e}=\frac{1}{|S_{X}|}|\\{i\in
S_{X}:\hat{X}_{i}\neq Y_{i}\\}|}$. They abort if $\hat{e}>e$. 5. Privacy
Amplification: Alice chooses a random function $F$ from a set of two universal
hash functions from $|S|$ bits to $\lfloor rn\rfloor$ bits and announces it
Bob. Alice and Bob compute the final key as $F(X_{S})$ and $F(\hat{X}_{S})$
respectively.

Variable |  Definition
---|---
$\mathcal{X}$ |  The set $\\{0,1\\}$; alphabet for Alice’s random string.
${\Theta}$ |  The set $\\{0,1\\}$; alphabet for the basis string.
$X_{1}^{n}$ |  The random string chosen by Alice at the beginning of the protocol
$\Theta_{1}^{n}$ |  Alice’s choice of randomly chosen basis. $\Theta_{i}=0$ if Alice chooses $Z$ basis and $\Theta_{i}=1$ if she chooses $X$ basis
$A_{1}^{n}$ |  The quantum registers sent by Alice to Bob
$\hat{\Theta}_{1}^{n}$ |  Bob’s choice of randomly chosen basis. $\hat{\Theta}_{i}=0$ if Bob chooses $Z$ basis and $\hat{\Theta}_{i}=1$ if he chooses $X$ basis
$Y_{1}^{n}$ |  Bob’s outcomes of measuring $A_{1}^{n}$ in $\hat{\Theta}_{1}^{n}$ basis
$S$ |  The set $\\{i\in[n]:\hat{\Theta}_{i}=\Theta_{i}\\}$
$\hat{X}_{S}$ |  Bob’s guess of $X_{S}$, produced at the end of the error correction step.
$T$ |  Transcript for error correction
$\bar{X}_{1}^{n}$ |  For $i\in[n]$, $\bar{X}_{i}=X_{i}$ if $\Theta_{i}=\hat{\Theta}_{i}$ else $\bar{X}_{i}=\perp$
$\bar{Y}_{1}^{n}$ |  For $i\in[n]$, $\bar{Y}_{i}=Y_{i}$ if $\Theta_{i}=\hat{\Theta}_{i}=1$ else $\bar{Y}_{i}=\perp$
$C_{1}^{n}$ |  For $i\in[n]$, $C_{i}=X_{i}\oplus Y_{i}$ if $\Theta_{i}=\hat{\Theta}_{i}=1$ else $C_{i}=\perp$
$\hat{C}_{1}^{n}$ |  For $i\in[n]$, $\hat{C}_{i}=\hat{X}_{i}\oplus Y_{i}$ if $\Theta_{i}=\hat{\Theta}_{i}=1$ else $\hat{C}_{i}=\perp$
$E$ |  Eve’s register created after Eve processes and forwards the states $A_{1}^{n}$ to Bob
$\Upsilon$ |  The event that the protocol does not abort, i.e., $\text{freq}(\hat{C}_{1}^{n})(1)\leq e$ and $\text{hash}(X_{S})=\text{hash}(\hat{X}_{S})$.
$\Upsilon^{\prime}$ |  The event that $X_{S}=\hat{X}_{S}$
$\Upsilon^{\prime\prime}$ |  The event that $\text{freq}(C_{1}^{n})(1)\leq e$.
Table 1: Definition of variables for QKD

Consider the case, where Alice only has access to an imperfect quantum source
to prepare qubits for the QKD protocol above. We will assume here that the
classical randomness used by Alice is perfect. Suppose Alice and Bob use $n$
rounds for the BB84 protocol. In order, to perform the QKD protocol with the
imperfect source, we require that Alice uses her source to first perform the
source testing protocol given in Protocol 6 with $(n+m)$-total rounds. This
source testing protocol randomly selects $m$ rounds of the source output,
measures the qubit $A_{i}$ in the basis given by $\Theta_{i}$ and compares the
result with the encoded bit $X_{i}$ for these rounds. The source passes the
test if the fraction of errors is lesser than $\epsilon$, which is a source
error threshold chosen by Alice. Subsequently, Alice uses the $n$ remaining
rounds produced by the source for the BB84 protocol provided the source test
does not abort. The complete protocol is depicted in Figure 7. It should be
noted that Alice can actually run Protocol 6 concurrently with the BB84
protocol. She does not need to create all the $(n+m)$-rounds at once and store
them in a memory in order to carry out this protocol. She can classically
sample a random set $\Gamma$ of size $m$ at the start of the BB84 protocol and
for every round $i$, she can use the round as source test round if
$i\in\Gamma$ or forward the state produced to Bob if $i\not\in\Gamma$. For
theoretical purposes, this concurrent approach is equivalent to one where
Alice begins by using her source to produce all the $(n+m)$-rounds and for our
arguments we assume this is the case.

Figure 5: To perform the BB84 protocol with a perfect source, Alice simply
uses her source to produce the quantum state required and uses it for the
protocol.

Source testing protocol
Parameters: • $\epsilon$ is the source error tolerated. • $m$ is the number of
rounds on which the source is tested. • $n$ is the number of rounds produced
by the source for use in subsequent protocols. Protocol: 1. The source
produces the state $\rho_{X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$. 2. Choose
a random subset $\Gamma\subseteq[n+m]$ of size $m$, measure the quantum
registers $A_{i}$ in the basis given by $\Theta_{i}$ and let the result be
$\hat{X}_{i}$. 3. Abort the protocol (and any subsequent protocols) if the
observed error ${\frac{1}{m}|\\{k\in\Gamma:\hat{X}_{k}\neq
X_{k}\\}|>\epsilon}$. 4. Output the registers corresponding to the remaining
rounds.

Figure 7: To perform the BB84 protocol with an imperfect source, Alice first
uses Protocol 6 to test the output of her source and then uses the output of
this protocol as the source for the BB84 protocol.

Let $\rho_{X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$ be the state produced by
the imperfect source, $\Omega$ denote the event that the source test (Protocol
6) does not abort and let the output of the source test protocol conditioned
on $\Omega$ be the state
$\bar{\rho}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}|\Omega}$ (or the subnormalised
state $\bar{\rho}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega}$ depending on
the context).

We will use the analysis of quantum sampling techniques in [BF10] to examine
the source test. The main result of this paper has been summarised as the
Theorem below.

######  Theorem 6.1 (Quantum sampling [BF10]).

The relative weight of a string $x_{1}^{k}$ is defined as
$\omega(x_{1}^{k}):=\frac{1}{k}|\\{i\in[k]:x_{i}\neq 0\\}|$. Let $\Psi$ be a
sampling strategy which takes a string $a_{1}^{n}$, selects a random subset
$\Gamma\subseteq[n]$ with probability $p_{\Gamma}$, a random seed $K$ with
probability $p_{K}$ and produces an estimate $f(\Gamma,a_{\Gamma},K)$ for the
relative weight of the rest of the string $a_{\bar{\Gamma}}$. We can define
the set of strings for which this strategy provides a $\delta$-correct
estimate for $\delta>0$ given the choices $\Gamma=\gamma$ and $K=\kappa$ as

$\displaystyle
B^{\delta}_{\gamma\kappa}(\Psi):=\left\\{a_{1}^{n}:|\omega(a_{\bar{\gamma}})-f(\gamma,a_{\gamma},\kappa)|<\delta\right\\}.$
(74)

The classical maximum error probability for this strategy $\Psi$ is defined as

$\displaystyle\epsilon^{\delta}_{\text{cl}}:=\max_{a_{1}^{n}}\Pr_{\Gamma
K}[a_{1}^{n}\not\in B^{\delta}_{\Gamma K}(\Psi)].$ (75)

Define the projectors
$\Pi_{A_{1}^{n}}^{\delta|\gamma\kappa}:=\sum_{a_{1}^{n}\in
B^{\delta}_{\gamma\kappa}(\Psi)}\ket{a_{1}^{n}}\bra{a_{1}^{n}}_{A_{1}^{n}}$.
Then, for a quantum state $\rho_{A_{1}^{n}E}$, we have that the state

$\displaystyle\tilde{\rho}_{\Gamma
KA_{1}^{n}E}:=\sum_{\gamma\kappa}p(\gamma\kappa)\ket{\gamma\kappa}\bra{\gamma\kappa}_{\Gamma
K}\otimes\frac{\Pi_{A_{1}^{n}}^{\delta|\gamma\kappa}\rho_{A_{1}^{n}E}\Pi_{A_{1}^{n}}^{\delta|\gamma\kappa}}{\operatorname{tr}\left(\Pi_{A_{1}^{n}}^{\delta|\gamma\kappa}\rho_{A_{1}^{n}E}\right)}$
(76)

is $\epsilon^{\delta}_{\text{qu}}=\sqrt{\epsilon^{\delta}_{\text{cl}}}$ close
to the state $\rho_{\Gamma
KA_{1}^{n}E}:=\sum_{\gamma\kappa}p(\gamma\kappa)\ket{\gamma\kappa}\bra{\gamma\kappa}_{\Gamma
K}\otimes\rho_{A_{1}^{n}E}$ in trace distance.

Using the above theorem, we prove that
$\bar{\rho}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}|\Omega}$ has a relatively small
smooth max-relative entropy with a depolarised version of the perfect source.
The entropic triangle inequality then allows us to prove security of the BB84
protocol, which uses this state as its source state (Figure 7).

We begin by creating the smooth max-relative entropy bound described above.
Define the unitaries,

$\displaystyle V^{x,\theta}_{A}:=H^{\theta}X^{x}$ (77) $\displaystyle
V_{X\Theta A}:=\sum_{x,\theta}\ket{x,\theta}\bra{x,\theta}_{X\Theta}\otimes
V^{x,\theta}_{A}$ (78)

so that $V_{X\Theta A}\ket{x,\theta}\ket{0}$ gives the perfect encoding of the
BB84 state given $x$ and $\theta$. We also define the state

$\displaystyle\nu_{X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}:=\bigotimes_{i=1}^{n+m}V^{\dagger}_{X_{i}\Theta_{i}A_{i}}\
\rho_{X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}\
\bigotimes_{i=1}^{n+m}V_{X_{i}\Theta_{i}A_{i}}.$ (79)

Note that if $\rho$ were perfectly encoded, then $\nu$ would be the state
$\rho_{X_{1}^{n+m}\Theta_{1}^{n+m}}\otimes\left(\ket{0}\bra{0}\right)^{\otimes(n+m)}$.
Let the register $\Gamma$ represent the choice of the random subset for
sampling following the notation in Theorem 6.1. The state produced by
measuring the subset $\gamma$ of the $A$ registers of $\nu$ in the
computational ($\\{\ket{0},\ket{1}\\}$) basis can equivalently be produced by
measuring the subset $\gamma$ of the $A$ registers of $\rho$ in the basis
given by the corresponding $\Theta$ registers, adding (mod 2) the
corresponding $X$ register to the result and applying the unitaries
$V_{X\Theta A}$ on the remaining indices. Conditioning on the sampled qubits
of $\rho$ being incorrectly encoded at most an $\epsilon$ fraction of the
rounds is equivalent to measuring the corresponding random subset of the
qubits of $\nu$ in the computational basis and conditioning on the relative
weight of the result being less than $\epsilon$ (up to unitaries on the
remaining registers; formal expression is given in Eq. 89). Given this
equivalence, we can simply work with the state $\nu$ and transform the results
back to the state $\rho$ at the end.

Using Theorem 6.1, we have that for every $x_{1}^{n+m},\theta_{1}^{n+m}$ there
exists ${\eta}_{\Gamma A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}$ such that

$\displaystyle\frac{1}{2}\left\|\nu_{\Gamma
A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}-{\eta}_{\Gamma
A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}\right\|_{1}\leq\epsilon_{\text{qu}}^{\delta}$
(80)

and

$\displaystyle{\eta}_{\Gamma
A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}:=\sum_{\gamma}p(\gamma)\ket{\gamma}\bra{\gamma}\otimes{\eta}^{(\gamma)}_{A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}$
(81)

where $p(\gamma)$ is the uniform distribution over all size $m$ subsets of
$[n+m]$, and the state
${\eta}^{(\gamma)}_{A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}$ satisfies

$\displaystyle{\eta}^{(\gamma)}_{A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}=\Pi_{A_{1}^{n+m}}^{\delta|\gamma}{\eta}^{(\gamma)}_{A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}\Pi_{A_{1}^{n+m}}^{\delta|\gamma}$
(82)

for the projectors $\Pi_{A_{1}^{n+m}}^{\delta|\gamma}$ defined as in Theorem
6.1 (our sampling procedure does not require a random seed $\kappa$, so we
omit it in our analysis). Note that using Hoeffding’s bound the classical
error probability for our sampling strategy is
$2\exp(-\frac{n\delta^{2}}{n+2}m)$, which implies that
$\epsilon_{\text{qu}}^{\delta}=\sqrt{2}\exp(-\frac{n\delta^{2}}{2(n+2)}m)$. We
can also define the extended state ${\eta}_{\Gamma
X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$ as

$\displaystyle{\eta}_{\Gamma X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$
$\displaystyle:=\sum_{\gamma,x_{1}^{n+m},\theta_{1}^{n+m}}p(\gamma)p(x_{1}^{n+m},\theta_{1}^{n+m})$
$\displaystyle\qquad\qquad\ket{\gamma,x_{1}^{n+m},\theta_{1}^{n+m}}\bra{\gamma,x_{1}^{n+m},\theta_{1}^{n+m}}\otimes{\eta}^{(\gamma)}_{A_{1}^{n+m}|x_{1}^{n+m},\theta_{1}^{n+m}}$
(83)

where $p(x_{1}^{n+m},\theta_{1}^{n+m})=\prod_{i=1}^{n+m}p(x_{i},\theta_{i})$.
Since, $\nu_{\Gamma X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$ and
${\eta}_{\Gamma X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$ have the same
distributions on $X_{1}^{n+m}$ and $\Theta_{1}^{n+m}$, we also have that

$\displaystyle\frac{1}{2}\left\|\nu_{\Gamma
X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}-{\eta}_{\Gamma
X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}\right\|\leq\epsilon_{\text{qu}}^{\delta}.$
(84)

Define $\Omega^{\prime}$ to be the event that result produced by measuring the
subset of registers $A_{\gamma}$ in the computational basis, where $\gamma$ is
given by the $\Gamma$ register, has a relative weight less than $\epsilon$.
Let $\bar{\nu}_{\Gamma X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}$
be the state produced when the relative weight of the registers $A_{\gamma}$
of $\nu_{\Gamma X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$ is measured and
conditioned on $\Omega^{\prime}$, the registers $X_{\gamma}$ and
$\Theta_{\gamma}$ are traced over, and the remaining $X,\Theta$ and $A$
registers are relabelled between $1$ and $n$. Also, let $\bar{\eta}_{\Gamma
X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}$ be the state produced
when this same subnormalised channel is instead applied to ${\eta}_{\Gamma
X_{1}^{n+m}\Theta_{1}^{n+m}A_{1}^{n+m}}$. Let us consider the action of this
map on a general state
$\ket{\gamma}\bra{\gamma}\otimes\sigma_{A_{1}^{n+m}}^{(\gamma)}$, which
satisfies the condition
$\sigma_{A_{1}^{n+m}}^{(\gamma)}=\Pi_{A_{1}^{n+m}}^{\delta|\gamma}\sigma_{A_{1}^{n+m}}^{(\gamma)}\Pi_{A_{1}^{n+m}}^{\delta|\gamma}$.
For such a state, we have

$\displaystyle\sigma_{A_{1}^{n+m}}^{(\gamma)}$
$\displaystyle=\sum_{a_{1}^{n+m},\bar{a}_{1}^{n+m}\in
B^{\delta}_{\gamma}}\sigma^{(\gamma)}(a_{1}^{n+m},\bar{a}_{1}^{n+m})\ket{a_{1}^{n+m}}\bra{\bar{a}_{1}^{n+m}}.$

Let
$\hat{P}_{A_{1}^{m}}:=\sum_{a_{1}^{m}:\omega(a_{1}^{m})\leq\epsilon}\ket{a_{1}^{m}}\bra{a_{1}^{m}}$
be the (perfect) measurement operator for conditioning on the event
$\Omega^{\prime}$. Then, the state after applying the measurement and
conditioning on the $\Omega^{\prime}$ is

$\displaystyle\operatorname{tr}_{A_{\gamma}}\left(\hat{P}_{A_{\gamma}}\sigma_{A_{1}^{n+m}}^{(\gamma)}\right)$
$\displaystyle=\sum_{a_{\gamma}:\omega(a_{\gamma})\leq\epsilon}\sum_{\begin{subarray}{c}a^{\prime}_{\bar{\gamma}},\bar{a}_{\bar{\gamma}}\in\\{x_{1}^{n}:\\\
|\omega(x_{1}^{n})-\omega(a_{\gamma})|<\delta\\}\end{subarray}}\sigma^{(\gamma)}(a_{\gamma}a^{\prime}_{\bar{\gamma}},a_{\gamma}\bar{a}_{\bar{\gamma}})\ket{a^{\prime}_{\bar{\gamma}}}\bra{\bar{a}_{\bar{\gamma}}}.$

We can relabel the remaining registers to get the state
$\bar{\sigma}_{A_{1}^{n}\wedge\Omega^{\prime}}^{(\gamma)}$ which can be put
into the form

$\displaystyle\bar{\sigma}_{A_{1}^{n}\wedge\Omega^{\prime}}^{(\gamma)}$
$\displaystyle=\sum_{a_{1}^{n},\bar{a}_{1}^{n}:\in\left\\{x_{1}^{n}:\
\omega(x_{1}^{n})<\epsilon+\delta\right\\}}\bar{\sigma}^{(\gamma)}(a_{1}^{n},\bar{a}_{1}^{n})\ket{a_{1}^{n}}\bra{\bar{a}_{1}^{n}}.$
(85)

Let $Q^{w}_{A_{1}^{n}}$ be the projector on the set
$\text{span}\\{\ket{x_{1}^{n}}:\ \text{for $x_{1}^{n}$ such that
}\omega(x_{1}^{n})<w\\}$ (note that these vectors are perpendicular). Then, we
have that

$\displaystyle\bar{\sigma}_{A_{1}^{n}\wedge\Omega^{\prime}}^{(\gamma)}=Q_{A_{1}^{n}}^{\epsilon+\delta}\bar{\sigma}_{A_{1}^{n}\wedge\Omega^{\prime}}^{(\gamma)}Q_{A_{1}^{n}}^{\epsilon+\delta}$
(86)

which implies that
$\bar{\sigma}_{A_{1}^{n}\wedge\Omega^{\prime}}^{(\gamma)}\leq
Q_{A_{1}^{n}}^{\epsilon+\delta}$, since
$\bar{\sigma}_{A_{1}^{n}\wedge\Omega^{\prime}}^{(\gamma)}$ is subnormalised.

By considering
$\sigma_{A_{1}^{n+m}}^{(\gamma)}=\eta_{A_{1}^{n+m}|x_{1}^{n+m}\theta_{1}^{n+m}}^{(\gamma)}$,
we see that $\bar{\eta}$ satisfies

$\displaystyle\bar{\eta}_{\Gamma
X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}$
$\displaystyle=\sum_{\gamma,x_{1}^{n},\theta_{1}^{n}}p(\gamma)p(x_{1}^{n}\theta_{1}^{n})\ket{\gamma
x_{1}^{n}\theta_{1}^{n}}\bra{\gamma
x_{1}^{n}\theta_{1}^{n}}\otimes\bar{\eta}^{(\gamma)}_{A_{1}^{n}|x_{1}^{n}\theta_{1}^{n}\wedge\Omega^{\prime}}$
$\displaystyle\leq\sum_{\gamma,x_{1}^{n},\theta_{1}^{n}}p(\gamma)p(x_{1}^{n}\theta_{1}^{n})\ket{\gamma
x_{1}^{n}\theta_{1}^{n}}\bra{\gamma x_{1}^{n}\theta_{1}^{n}}\otimes
Q_{A_{1}^{n}}^{\epsilon+\delta}$
$\displaystyle=\rho_{\Gamma}\otimes\rho_{X\theta}^{\otimes n}\otimes
Q_{A_{1}^{n}}^{\epsilon+\delta}.$

Using the data processing inequality, we also have that

$\displaystyle\frac{1}{2}\left\|\bar{\nu}_{\Gamma
X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}-\bar{\eta}_{\Gamma
X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}\right\|_{1}\leq\epsilon_{\text{qu}}^{\delta}$
(87)

Let
$\hat{\eta}^{(\epsilon+\delta)}_{A}:=(1-\epsilon-\delta)\ket{0}\bra{0}+(\epsilon+\delta)\ket{1}\bra{1}$
or equivalently the $\hat{\eta}^{(\epsilon+\delta)}_{A}$ is the classical
probability distribution over $\\{0,1\\}$ which is $1$ with probability
$(\epsilon+\delta)$. For this distribution, a simple calculation shows that

$\displaystyle\min_{z_{1}^{n}:\omega(z_{1}^{n})<\epsilon+\delta}\bra{z_{1}^{n}}(\hat{\eta}^{(\epsilon+\delta)}_{A})^{\otimes
n}\ket{z_{1}^{n}}\geq 2^{-nh(\epsilon+\delta)}$

which implies that

$\displaystyle Q_{A_{1}^{n}}^{\epsilon+\delta}$ $\displaystyle\leq
2^{nh(\epsilon+\delta)}(\hat{\eta}^{(\epsilon+\delta)}_{A})^{\otimes n}.$

Thus, we have

$\displaystyle\bar{\eta}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}$
$\displaystyle\leq
2^{nh(\epsilon+\delta)}\left(\rho_{X\Theta}\otimes\hat{\eta}^{(\epsilon+\delta)}_{A}\right)^{\otimes
n}.$ (88)

As noted earlier, the state produced by measuring the registers $A_{\gamma}$
of $\nu$ in the computational basis is the same as the state produced by
measuring the same registers on the real state $\rho$ in the basis given by
$\Theta_{i}$, adding $X_{i}$ to the result (mod 2), and transforming the
remaining registers with
$\bigotimes_{k=1}^{n}V^{\dagger}_{X_{i}\Theta_{i}A_{i}}$. Under this
correspondence, we have that the state produced by the source test satisfies

$\displaystyle\bar{\rho}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega}=\bigotimes_{i=1}^{n}V_{X_{i}\Theta_{i}A_{i}}\bar{\nu}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}\bigotimes_{i=1}^{n}V^{\dagger}_{X_{i}\Theta_{i}A_{i}}.$
(89)

Further, for the state defined as

$\displaystyle\bar{\tilde{\rho}}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega}$
$\displaystyle:=\bigotimes_{i=1}^{n}V_{X_{i}\Theta_{i}A_{i}}\bar{\eta}_{X_{1}^{n}\Theta_{1}^{n}A_{1}^{n}\wedge\Omega^{\prime}}\bigotimes_{i=1}^{n}V^{\dagger}_{X_{i}\Theta_{i}A_{i}}$
$\displaystyle\leq
2^{nh(\epsilon+\delta)}\bigotimes_{i=1}^{n}\left(V_{X_{i}\Theta_{i}A_{i}}\