ρρ σσ λλ ΛΛ μμ νν ψψ ϕϕ φφ ππ αα ϵϵ εε δδ ωω ∗* DRAFT TRASH EXCLUDED cited

# Parallelization of Sequential Quantum Channel Discrimination in the Non-
Asymptotic Regime

Bjarne Bergh Department of Applied Mathematics and Theoretical Physics,
University of Cambridge, United KingdomCorresponding author<EMAIL_ADDRESS>Nilanjana Datta11footnotemark: 1 Robert Salzmann11footnotemark: 1 Mark M.
Wilde Hearne Institute for Theoretical Physics, Department of Physics and
Astronomy, and Center for Computation and Technology, Louisiana State
University, Baton Rouge, Louisiana 70803, USASchool of Electrical and Computer
Engineering, Cornell University, Ithaca, New York 14850, USA

###### Abstract

We investigate the performance of parallel and sequential quantum channel
discrimination strategies for a finite number of channel uses. It has recently
been shown that, in the asymmetric setting with asymptotically vanishing type
I error probability, sequential strategies are asymptotically not more
powerful than parallel ones. We extend this result to the non-asymptotic
regime with finitely many channel uses, by explicitly constructing a parallel
strategy for any given sequential strategy, and bounding the difference in
their performances, measured in terms of the decay rate of the type II error
probability per channel use.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries, Notation, and Previous Results
    1. 2.1 Notation
    2. 2.2 Quantum Information Measures
    3. 2.3 Quantum State Discrimination
    4. 2.4 Quantum Channel Discrimination
  3. 3 Parallelizing an $n$-Shot Sequential Protocol
    1. 3.1 A Simple One-Shot Version of the Chain Rule
    2. 3.2 Non-Asymptotic Bounds for the Smooth Max-Relative Entropy
    3. 3.3 Proof of our main result (Theorem 7)
  4. 4 A Simple Example
  5. 5 Discussion and Outlook
  6. A Proofs of AEP Bounds
    1. A.1 Proof of 10 (Petz–Rényi Continuity Bound in $\alpha$)
    2. A.2 Proof of 15 (AEP Convergence Bound)

##  1 Introduction

Binary quantum state discrimination is one of the oldest and most studied
tasks in quantum information theory [Hel69, Hol72]. The task involves
determining the state of a quantum system, given the side information that it
is in one of two possible states. This is done by performing suitable
measurements on the state. This task has been studied in both the $n$-shot
regime, in which a finite number ($n$) of identical copies of the unknown
state are available, and in the asymptotic limit in which one assumes that an
infinite number of copies are available (i.e. $n\to\infty$). The task of
binary state discrimination, which can be viewed as that of binary hypothesis
testing for quantum states, is a fundamental primitive of quantum information
theory since many other information processing tasks can be reduced to it.
Known results for this problem now include optimal decision strategies and the
behavior of the error probabilities of misidentification in both these finite
and asymptotic regimes [helstrom_quantum_1976, Kho79, HP91, ON00, Nag06,
Aud+07, Hay07, Aud+08, NS09, AMV12, BK15]. There are generally two possible
errors that can be incurred: the system is inferred to be in the second state
when it is actually in the first (type I error) or vice versa (type II error).
There are two different settings in which the state discrimination task is
usually studied: in the symmetric setting, the probabilities of these two
errors are treated on an equal footing, while in the asymmetric setting, one
minimizes the probability of type II error under the constraint that the type
I error is below a given threshold.

Similar in nature, but a lot less understood, is the task of binary quantum
channel discrimination: given an unknown quantum channel as a black box and
the side information that it is one of two possible channels, the task is to
determine the channel’s identity [CDP08, DFY09, Hay09, Har+10]. The additional
complexity here comes from the fact that, on top of finding the best
measurement to perform on the output of the channel, we also have to figure
out which quantum states to send as input to the channel. Say we are given
access to $n$ copies of the channel (i.e. we are given $n$ identical black
boxes, each of which can be used once); then there are different strategies
(sometimes also called protocols) in which we could set up our decision
experiment – the so-called parallel and sequential (or adaptive) strategies.
In a parallel strategy one prepares a joint state, usually entangled between
the input systems of all the $n$ copies of the channel and an additional
reference (or memory) system. This state is then fed as input to all the $n$
channels at once (with the state of the reference system being left
undisturbed). Finally, a binary positive operator-valued measure (POVM) is
performed on the joint state at the output of the channels and the reference
system in order to arrive at a decision for the channel’s identity. In a
sequential strategy, on the other hand, one prepares a state of the input
system of a single copy of the channel (again usually entangled with a
reference system) which is fed into the first copy of the channel, with the
state of the reference system being left undisturbed. The input to the next
use of the channel is then chosen depending on the output of the first channel
and the state of our reference system. This is done, most generally, by
subjecting the latter to an arbitrary quantum operation (or channel), which we
call a preparation operation. This step is repeated for each successive use of
the channel until all the $n$ black-boxes have been used. Then a binary POVM
is performed on the joint state of the output of the last use of the channel
and the reference system. See Figure 1 for a depiction of an adaptive or
sequential strategy.

One particularly interesting question is whether and to what degree sequential
(or adaptive) strategies give an advantage over parallel ones. Note that any
parallel strategy can be written as a sequential strategy by taking all but
one channel input as part of the reference system, and then choosing each
preparation operation such that it extracts the next part of the joint input
state for the next channel use and replaces it by the output of the previous
channel use. However, the converse is not true, and so sequential strategies
are more general. Parallel strategies are conceptually a lot simpler than
sequential ones – aside from the measurement, everything is specified just by
the joint input state – in contrast to sequential strategies, in which after
each channel use we can perform an arbitrary quantum operation to prepare the
input to the next use of the channel. It is thus interesting to determine to
what degree parallel strategies can still be optimal. It is known that in
certain cases sequential strategies can give an advantage over parallel ones.
In [Har+10] the authors constructed an example in which a sequential strategy
with only two channel uses could be used to discriminate the channels with
certainty, which is not possible with a parallel strategy, even if arbitrarily
many channel uses are allowed.

Interestingly, _asymptotically_ , there are multiple known cases in which
sequential strategies give no advantage over parallel ones, i.e. the optimal
exponential decay rate of the error probability per channel use is the same in
the asymptotic limit. For example, this is the case both in the symmetric and
asymmetric settings when the channels are classical [Hay09] or classical-
quantum [Wil+20, SHW21]. For arbitrary quantum channels, the recently shown
chain rule for the quantum relative entropy [Fan+20] and the characterization
of asymmetric channel discrimination in terms of amortized relative entropy
[Wil+20, WW19a], also implies that in the asymmetric setting, in the
asymptotic limit where we also require the type I error to vanish, sequential
strategies give no advantage over parallel ones (i.e. the optimal asymptotic
exponential decay rate of the type II error per channel use is the same for
parallel and sequential strategies; see section 2 below for more details).
This is in contrast to the symmetric setting in which the example of [SHW21]
shows that there always is an advantage of sequential strategies, also in the
asymptotic limit.

In this paper, our aim is to move from these purely asymptotic results to
statements comparing sequential and parallel strategies for finite $n$. In our
main result (5 and Theorem 7) we relate the type I and type II errors of an
arbitrary sequential strategy with those of a suitably chosen parallel
strategy. Specifically, given a sequential strategy with $n$ channel uses, we
construct a parallel strategy with $m$ channel uses (where $m$ can be chosen
at will), such that for arbitrary fixed type I errors of the two strategies,
we find an explicit bound on the difference between their type II error decay
rates. This difference goes to zero in a suitably chosen asymptotic limit
$m,n\to\infty$ if also the type I error vanishes, hence also implying the
known asymptotic equivalence in the asymmetric case. Our result answers the
following interesting question which is of practical relevance: Given a
sequential strategy involving $n$ uses of the channel, if one instead employs
a parallel strategy with $m$ channel uses, how much worse are the errors going
to be?

On the way to proving our main theorem, we also prove the following two
technical results: First, a slightly refined bound on the difference between
the Petz–Rényi relative entropy $D_{\alpha}$ and the Umegaki relative entropy
$D$ (10), and secondly, a bound on the convergence speed in the asymptotic
equipartition property of the smoothed max-relative entropy (15), which turns
out to be better suited to our application than previous results (see 13 and
14 for a detailed explanation of the differences).

We start by introducing all of the required notation and previous results in
Section 2. Then we state and prove our main theorem (Theorem 7) in Section 3.
Section 4 illustrates our result with a simple example.

##  2 Preliminaries, Notation, and Previous Results

###  2.1 Notation

We write $\mathcal{H}$ for a complex finite-dimensional Hilbert space, and
$\mathcal{B}\left(\mathcal{H}\right)$ for the set of linear operators acting
on $\mathcal{H}$. We write $\mathscr{P}\\!\left(\mathcal{H}\right)$ for the
set of positive semi-definite operators acting on $\mathcal{H}$. For
$A,B\in\mathscr{P}\\!\left(\mathcal{H}\right)$ we further write $A\ll B$ if
$\textrm{supp}\left(A\right)\subseteq\textrm{supp}\left(B\right)$ and
$A\not\ll B$ if
$\textrm{supp}\left(A\right)\not\subseteq\textrm{supp}\left(B\right)$. Let
$\mathcal{D}\left(\mathcal{H}\right)$ denote the set of density matrices,
i.e., the set of positive semi-definite operators with trace one. A quantum
channel (in this paper usually denoted as $\mathcal{E}$ or $\mathcal{F}$) is a
completely positive trace preserving map between density operators. We will
label different quantum systems by capital Roman letters ($A$, $B$, $C$, etc.)
and often use these letters interchangeably with the corresponding Hilbert
space or set of density matrices (i.e., we write
$\rho\in\mathcal{D}\left(A\right)$ instead of
$\rho\in\mathcal{D}\left(\mathcal{H}_{A}\right)$ and $\mathcal{E}:A\to B$
instead of
$\mathcal{E}:\mathcal{D}\left(\mathcal{H}_{A}\right)\to\mathcal{D}\left(\mathcal{H}_{B}\right)$).
We write $\log$ for the logarithm to the base two.

###  2.2 Quantum Information Measures

For $\rho\in\mathcal{D}\left(\mathcal{H}\right)$ and
$\sigma\in\mathscr{P}\\!\left(\mathcal{H}\right)$ the (Umegaki) quantum
relative entropy is defined as [Ume62]

$D(\rho\|\sigma)\coloneqq\Tr(\rho(\log\rho-\log\sigma)),$ (1)

if $\rho\ll\sigma$ and $D(\rho\|\sigma)\coloneqq\infty$ if
$\rho\not\ll\sigma$. One of its most important properties is the data-
processing inequality [Lin75], which states that for every quantum channel
$\mathcal{E}$:

$D(\rho\|\sigma)\geq D(\mathcal{E}(\rho)\|\mathcal{E}(\sigma))\,.$ (2)

A self-contained proof can be found e.g. in [KW20]. More generally, we call a
function of $\rho$ and $\sigma$ a divergence if it satisfies the data-
processing inequality.

Below we also make use of the binary entropy, which is the Shannon entropy of
a classical random variable that takes two possible values. It is uniquely
specified by the probability $p\in[0,1]$ of one of the values and is given by

$h(p)\coloneqq-p\log p-(1-p)\log(1-p)\,.$ (3)

It satisfies

$0\leq h(p)\leq 1\qquad\forall\,p\in[0,1]\,.$ (4)

####  2.2.1 Fidelity and Sine Distance

For two quantum states $\rho,\sigma\in\mathcal{D}\left(\mathcal{H}\right)$, we
define the fidelity as [Uhl76]

$F(\rho,\sigma)\coloneqq\Tr(\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}).$ (5)

Note that this is sometimes also called the square root fidelity due to
different conventions on whether to include a square or not. We define the
sine distance as [Ras02, Ras03, GLN05, Ras06]

$P(\rho,\sigma)\coloneqq\sqrt{1-F(\rho,\sigma)^{2}},$ (6)

which satisfies the properties of a metric (especially the triangle
inequality) and also the data-processing inequality (see, e.g., [KW20]). This
quantity is also known as the purified distance.

####  2.2.2 (Smoothed) Max-Divergence

For $\rho\in\mathcal{D}\left(\mathcal{H}\right)$ and
$\sigma\in\mathscr{P}\\!\left(\mathcal{H}\right)$, define the quantum max-
divergence (or the max-relative entropy) as [Dat09]

$D_{\max}(\rho\|\sigma)\coloneqq\log\inf\Set{\lambda\in\mathbb{R}}{\rho\leq\lambda\sigma}\,.$
(7)

The quantum max-divergence also satisfies the data-processing inequality
[Dat09]. Let

$B^{\circ}_{\varepsilon}(\rho)\coloneqq\Set{\tilde{\rho}\in\mathcal{D}\left(\mathcal{H}\right)missing}{P(\rho,\tilde{\rho})\leq\varepsilon}$
(8)

be the $\varepsilon$-ball of _normalized_ states around $\rho$ in sine
distance. Then, we define the smoothed max-divergence as [Dat09]

$D_{\max}^{\varepsilon}(\rho\|\sigma)\coloneqq
D_{\max}^{\varepsilon,\circ}(\rho\|\sigma)=\inf_{\tilde{\rho}\in
B^{\circ}_{\varepsilon}(\rho)}D_{\max}(\tilde{\rho}\|\sigma).$ (9)

Note that this is sometimes defined differently in the literature, where one
allows the infimum to also include sub-normalized states.

####  2.2.3 Rényi Divergences

Let $\rho\in\mathcal{D}\left(\mathcal{H}\right)$ and
$\sigma\in\mathscr{P}\\!\left(\mathcal{H}\right)$ be two operators such that
$\rho\ll\sigma$. The definitions below can sometimes also be extended with
finite values to the case where $\rho\not\ll\sigma$ (see the references below
or also [KW20]), however this is not going to be relevant for our work. For
every $\alpha\in[0,1)\cup(1,2]$ define the _Petz–Rényi divergence_ as [Pet86]:

$D_{\alpha}(\rho\|\sigma)\coloneqq\frac{1}{\alpha-1}\log\Tr(\rho^{\alpha}\sigma^{1-\alpha})\,.$
(10)

Similarly, for every $\alpha\in(0,1)\cup(1,2]$ define the _geometric Rényi
divergence_ as [Mat13]:

$\widehat{D}_{\alpha}(\rho\|\sigma)\coloneqq\frac{1}{\alpha-1}\log\Tr\\!\left(\sigma^{1\over
2}(\sigma^{-{1\over 2}}\rho\sigma^{-{1\over 2}})^{\alpha}\sigma^{1\over
2}\right)\,.$ (11)

It was shown in [Mat13] that the geometric Rényi divergence is the largest
Rényi divergence for every $\alpha\in(0,1)\cup(1,2]$, and so

$D_{\alpha}(\rho\|\sigma)\leq\widehat{D}_{\alpha}(\rho\|\sigma)\,.$ (12)

####  2.2.4 Channel Divergences

For every given divergence $\mathbf{D}$ for states, one can define an
associated channel divergence [Led+18] by performing a (stabilized)
maximization over all input states, i.e. with $\mathcal{E},\mathcal{F}:A\to B$
being quantum channels

$\mathbf{D}(\mathcal{E}\|\mathcal{F})\coloneqq\sup_{\rho_{RA}\in\mathcal{D}\left(R\otimes
A\right)}\mathbf{D}\big{(}(\textrm{id}_{R}\otimes\mathcal{E})(\rho)\|(\textrm{id}_{R}\otimes\mathcal{F})(\rho)\big{)}.$
(13)

Since $\mathbf{D}$ satisfies the data-processing inequality by definition, the
supremum can be restricted to pure states such that the reference system $R$
is isomorphic to the channel input system $A$.

Specifically relevant later will be the max channel divergence, which has the
following simple representation (see [Día+18, Definition 19] and [Wil+20,
Lemma 12]):

$D_{\max}(\mathcal{E}\|\mathcal{F})\coloneqq\sup_{\psi_{RA}}D_{\max}\big{(}(\textrm{id}_{R}\otimes\mathcal{E})(\psi)\|(\textrm{id}_{R}\otimes\mathcal{F})(\psi)\big{)}=D_{\max}\big{(}(\textrm{id}_{R}\otimes\mathcal{E})(\Phi)\|(\textrm{id}_{R}\otimes\mathcal{F})(\Phi)\big{)},$
(14)

where $R\simeq A$ and $\Phi=\Phi_{RA}$ is a maximally entangled state. Hence,
the max channel divergence is easily computable as a semidefinite program
(SDP).

###  2.3 Quantum State Discrimination

In binary quantum state discrimination, a quantum system with Hilbert space
$\mathcal{H}$, is prepared in one of two states $\rho$ or $\sigma$, and the
objective is to perform a binary POVM $\\{\Pi,\IdentityMatrix-\Pi\\}$ (where
$\IdentityMatrix$ denotes the identity operator acting on $\mathcal{H}$ and
$\Pi\in{\mathcal{B}}({\mathcal{H}})$ satisfying $0\leq\Pi\leq\IdentityMatrix$)
in order to guess which state was prepared (see [BK15] for a review).
Performing this measurement comes with the possibility of making an error of
mis-identification. Generally one defines the type I and type II error
probabilities, respectively, as

$\displaystyle\alpha(\Pi,\rho,\sigma)$
$\displaystyle\coloneqq\Tr((\IdentityMatrix-\Pi)\rho),$ (15)
$\displaystyle\beta(\Pi,\rho,\sigma)$
$\displaystyle\coloneqq\Tr(\Pi\sigma)\,.$ (16)

In the rest of the paper, we refer to the above simply as the type I and type
II errors. It is easy to see from the definition that different choices of
$\Pi$ lead to different trade-offs between the type I and type II errors.

In the asymmetric setting, we are interested in finding the optimal type II
error while keeping the type I error below a threshold (usually denoted as
$\varepsilon$). This optimal type II error is then given as

$\beta_{\varepsilon}(\rho\|\sigma)\coloneqq\min_{\begin{subarray}{c}0\leq\Pi\leq\IdentityMatrix\\\
\Tr(\Pi\rho)\geq 1-\varepsilon\end{subarray}}\Tr(\Pi\sigma).$ (17)

The negative logarithm of this optimal type II error is called the hypothesis
testing relative entropy [BD10, BD11, WR12]:

$D_{H}^{\varepsilon}(\rho\|\sigma)\coloneqq-\log\beta_{\varepsilon}(\rho\|\sigma).$
(18)

It is also known as the smooth min-relative entropy [AJW19, WW19]. The
hypothesis testing relative entropy satisfies the data-processing inequality
[WR12] and can be related to other entropic quantities. We will make use of
the following known relations:

######  Lemma 1 (Upper bound on $D_{H}^{\varepsilon}$ [WR12]).

Let $\rho,\sigma\in\mathcal{D}\left(\mathcal{H}\right)$ be quantum states.
Then for all $\varepsilon\in[0,1)$

$D_{H}^{\varepsilon}(\rho\|\sigma)\leq\frac{1}{1-\varepsilon}\big{(}D(\rho\|\sigma)+h(\varepsilon)\big{)},$
(19)

where $h(\varepsilon)$ is the binary entropy function.

######  Lemma 2 (Relation to smoothed max-divergence [Ans+19, Theorem 4]).

Let $\rho\in\mathcal{D}\left(\mathcal{H}\right)$ and
$\sigma\in\mathscr{P}\\!\left(\mathcal{H}\right)$. Then, for
$\varepsilon\in(0,1)$ and $\delta\in(0,1-\varepsilon^{2})$:

$D_{H}^{1-\varepsilon^{2}-\delta}(\rho\|\sigma)-\log(4(1-\varepsilon^{2})\over\delta^{2})\leq
D_{\max}^{\varepsilon}(\rho\|\sigma)\leq
D_{H}^{1-\varepsilon^{2}}(\rho\|\sigma)-\log(1-\varepsilon^{2}).$ (20)

######  Remark 3.

Note that [Ans+19] defines the smoothed max-divergence using sub-normalized
smoothing; however, the proof of this lemma goes through also when restricting
to normalized states. Note also that the arXiv version of [Ans+19] has a typo
in the admissible range of $\delta$, which is corrected in the published
version.

Note that the last relation can be slightly tightened if we can assume $n$ to
be large enough:

######  Lemma 4 (Better for large/small $\varepsilon$, but only for $n$ large
enough).

If

$\frac{\log(1-\varepsilon)}{n}\leq\quantity(\frac{\log
3}{2})^{2}\quad\text{and}\quad\frac{\log(\varepsilon)}{n}\leq\quantity(\frac{\log
3}{2})^{2}$ (21)

then with $\Upsilon=\Upsilon(\rho\|\sigma)$

$\displaystyle\frac{1}{n}D^{\varepsilon}_{H}(\rho^{\otimes n}\|\sigma^{\otimes
n})$ $\displaystyle\leq
D(\rho\|\sigma)+4\log(\Upsilon)\sqrt{\frac{-\log(1-\varepsilon)}{n}}-\frac{\log(1-\varepsilon)}{n}$
(22) $\displaystyle\frac{1}{n}D^{\varepsilon}_{H}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\geq
D(\rho\|\sigma)-4\log(\Upsilon)\sqrt{\frac{-\log(\varepsilon)}{n}}+\frac{\log(\varepsilon)}{n}$
(23)

###### Proof.

From [KW20, Prop. 4.68 and Prop 4.69] we have the following relations between
hypothesis testing and Rényi entropies:

$\displaystyle D^{\varepsilon}_{H}(\rho\|\sigma)$
$\displaystyle\leq\bar{D}_{\alpha}(\rho\|\sigma)+\frac{\alpha}{\alpha-1}\log(\frac{1}{1-\varepsilon})$
$\displaystyle\qquad\forall\,\alpha$ $\displaystyle\in(1,\infty)$ (24)
$\displaystyle D^{\varepsilon}_{H}(\rho\|\sigma)$
$\displaystyle\geq\bar{D}_{\alpha}(\rho\|\sigma)+\frac{\alpha}{\alpha-1}\log(\frac{1}{\varepsilon})$
$\displaystyle\qquad\forall\,\alpha$ $\displaystyle\in(0,1)$ (25)

Also, from [AMV12, Lemma 2.3] (see also [Tom12, Lemma 6.3]) we have for
$\delta\in(0,{\log 3\over 4\log\Upsilon(\rho\|\sigma)})$:

$\displaystyle\bar{D}_{1+\delta}(\rho\|\sigma)$ $\displaystyle\leq
D(\rho\|\sigma)+4\delta[\log\Upsilon(\rho\|\sigma)]^{2}$ (26)
$\displaystyle\bar{D}_{1-\delta}(\rho\|\sigma)$ $\displaystyle\geq
D(\rho\|\sigma)-4\delta[\log\Upsilon(\rho\|\sigma)]^{2}$ (27)

In the following we prove the upper bound of our lemma, the lower bound works
analogously. We choose $\alpha=1+\delta=1+\frac{1}{2\mu\sqrt{n}}$, where

$\mu=\log(\Upsilon)(-\log(1-\varepsilon))^{-1/2}$ (28)

Combining the above relations we find

$\displaystyle\frac{1}{n}D^{\varepsilon}_{H}(\rho^{\otimes n}\|\sigma^{\otimes
n})$ $\displaystyle\leq\frac{1}{n}\bar{D}_{1+\delta}(\rho^{\otimes
n}\|\sigma^{\otimes n})-\frac{1}{n}(1+\frac{1}{\delta})\log(1-\varepsilon)$
(29)
$\displaystyle=\bar{D}_{1+\delta}(\rho\|\sigma)-\frac{1}{n}(1+\frac{1}{\delta})\log(1-\varepsilon)$
(30) $\displaystyle\leq
D(\rho\|\sigma)+4\delta(\log\Upsilon)^{2}-\frac{1}{n\delta}\log(1-\varepsilon)-\frac{1}{n}\log(1-\varepsilon)$
(31)
$\displaystyle=D(\rho\|\sigma)+4\log(\Upsilon)\sqrt{\frac{-\log(1-\varepsilon)}{n}}-\frac{\log(1-\varepsilon)}{n}$
(32)

∎

###  2.4 Quantum Channel Discrimination

Let $\mathcal{E}$ and $\mathcal{F}$ be two quantum channels, each taking
system $A$ to system $B$. In the discrimination setting we will generally use
inputs to the channels that are entangled with a reference system. To simplify
notation we will usually _not_ make the identity channel on the reference
system explicit. Hence, if $\rho_{RA}\in\mathcal{D}\left(R\otimes A\right)$ is
a state, we will write

$\mathcal{E}(\rho)\coloneqq\mathcal{E}_{A\to
B}(\rho_{RA})=(\textrm{id}_{R}\otimes\mathcal{E}_{A\to B})(\rho_{RA}),$ (33)

and similarly also for $\mathcal{F}$.

Figure 1: Illustration of a general sequential protocol with $n$ uses of the
black-box channel. The top row makes use of the given blackbox
$\mathcal{E}|\mathcal{F}$, which is either $\mathcal{E}$ or $\mathcal{F}$,
while the bottom row depicts the memory system $R$. At various stages in the
protocol, the green states $\rho$ occur if the channel is $\mathcal{E}$ and
the purple states $\sigma$ occur if the channel is $\mathcal{F}$.

The most general channel discrimination protocol will choose input states
based on the outputs of previous channel uses. This is called a sequential
protocol. A general sequential channel discrimination protocol with $n$ uses
of the black-box channel ($\mathcal{E}$ or $\mathcal{F}$), can be fully
specified by an initial state $\rho_{1}=\sigma_{1}\in\mathcal{D}\left(R\otimes
A\right)$, a set of $n-1$ CPTP maps $\Lambda_{i}:R\otimes B\to R\otimes A$,
that transform the state before it is fed into the next black-box channel, and
a final binary POVM $\\{\Pi,\IdentityMatrix-\Pi\\}$ on $R\otimes B$. We will
assume the size of reference system $R$ to be fixed and identical throughout
the protocol (this is without loss of generality). The protocol consists of
alternating applications of the black-box channel and the preparation CPTP
maps $\Lambda_{i}$ (see Figure 1). We define:

$\rho_{i}\coloneqq\Lambda_{i}(\mathcal{E}(\rho_{i-1})),\qquad\sigma_{i}\coloneqq\Lambda_{i}(\mathcal{F}(\sigma_{i-1})),\qquad\text{for
}i\in\\{2,\ldots,n\\},$ (34)

and so the final state before the action of the POVM will be
$\mathcal{E}(\rho_{n})$ if the channel is $\mathcal{E}$ and
$\mathcal{F}(\sigma_{n})$ if the channel is $\mathcal{F}$. The
distinguishability of the channels then comes down to the distinguishability
of the two states $\mathcal{E}(\rho_{n})$ and $\mathcal{F}(\sigma_{n})$. We
will be focussing again on the asymmetric setting, with the main object of
study being the hypothesis testing relative entropy
$D_{H}^{\varepsilon}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))$. We
write the optimal sequential type II error rate for a given finite number of
channel uses $n$ as [CMW16]

$\sup_{\rho_{1},\\{\Lambda_{i}\\}_{i}}\frac{1}{n}D^{\varepsilon}_{H}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))$
(35)

where the supremum is over every initial input state $\rho_{1}=\sigma_{1}$ and
all subsequent input preparation CPTP maps $\\{\Lambda_{i}\\}_{i=2}^{n}$. It
was shown in [KW21, Prop. 3] that this is computable as a semi-definite
program.

####  2.4.1 Asymptotic Equivalence of Sequential and Parallel Strategies

It has been shown recently [Wil+20, WW19a] that asymptotically, when the
number of channel uses goes to infinity, the best exponential decay rate of
the type II error (per channel use) such that the type I error still goes to
zero is given by the amortized Umegaki channel divergence, i.e.

$\lim_{\varepsilon\to
0}\lim_{n\to\infty}\sup_{\rho_{1},\\{\Lambda_{i}\\}_{i}}\frac{1}{n}D^{\varepsilon}_{H}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))=D^{A}(\mathcal{E}\|\mathcal{F})\,$
(36)

where

$D^{A}(\mathcal{E}\|\mathcal{F})\coloneqq\sup_{\rho,\sigma\in\mathcal{D}\left(R\otimes
A\right)}\big{[}D(\mathcal{E}(\rho)\|\mathcal{F}(\sigma))-D(\rho\|\sigma)\big{]}.$
(37)

Note that the dimension of the reference system $R$ in this last supremum can
be arbitrarily large.

The chain rule from [Fan+20] states that this amortized divergence is in fact
equal to the regularized channel divergence, i.e.

$D^{A}(\mathcal{E}\|\mathcal{F})=D^{\text{reg}}(\mathcal{E}\|\mathcal{F})\coloneqq\lim_{n\to\infty}\frac{1}{n}\sup_{\nu\in\mathcal{D}\left(R^{\otimes
n}\otimes A^{\otimes n}\right)}D(\mathcal{E}^{\otimes
n}(\nu)\|\mathcal{F}^{\otimes n}(\nu)),$ (38)

the latter of which can be achieved by parallel protocols, as a consequence of
[WW19a, Theorem 3]. Note that the reference system $R$ in the latter
optimization can be chosen isomorphic to $A$. Hence, asymptotically (and in
the regime in which the type I error goes to zero) sequential strategies offer
no advantage over parallel ones. We provide a finite $n$ version of this
statement, by giving explicit bounds on how much the error probabilities of
sequential and parallel strategies can differ for a finite number of channel
uses.

##  3 Parallelizing an $n$-Shot Sequential Protocol

We state our main result in two forms, first in a simple manner that
illustrates the main idea and structure of the result, and secondly a more
detailed theorem that gives the best possible bound and states in detail what
one can choose as a parallel input state.

Remember that there is a tradeoff in minimizing the type I and type II errors.
In the context of a strategy, for a given type I error $\alpha$ we will write
the best achievable type II error as $\beta(\alpha)$. We are especially
interested in the exponential decay rate of the type II error with the number
of channel uses, i.e. if some strategy involving $n$ uses of the channel has
type II error $\beta(\alpha)$, we are interested in the quantity
$-\frac{1}{n}\log(\beta(\alpha))$. Our main result compares this error decay
rate per channel use between sequential and parallel strategies:

######  Corollary 5 (Main result, simple version).

Let $\mathcal{E},\mathcal{F}:A\to B$ be two quantum channels such that
$D_{\max}(\mathcal{E}\|\mathcal{F})<\infty$. Let there be a sequential
discrimination protocol with $n$ channel uses, that – for an arbitrary type I
error $\alpha_{S}$ – achieves type II error $\beta_{S}(\alpha_{S})$. Then,
there exists a parallel protocol with $m$ channel uses and with a type II
error function $\beta_{P}(\alpha_{P})$ such that for all $\alpha_{S}$ and
$\alpha_{P}$ the type II error rates per channel use obey the following
relation:

$-\frac{1}{m}\log(\beta_{P}(\alpha_{P}))\geq-\frac{1-\alpha_{S}}{n}\log(\beta_{S}(\alpha_{S}))-\frac{Cn}{\sqrt{m}}\log(8\over\alpha_{P})-\frac{1}{n}.$
(39)

That is, the type II error rate of the parallel protocol is essentially as
least as good as the sequential one modulo an additional error term, which
decays as $m\to\infty$. We have

$C\coloneqq 7\log(2^{D_{2}(\mathcal{E}\|\mathcal{F})}+2)\leq
7\log(2^{D_{\max}(\mathcal{E}\|\mathcal{F})}+2)\,.$ (40)

######  Remark 6.

If we take the limit $m\to\infty$ in (39), then $n\to\infty$, and finally
$\alpha_{S}\to 0$ and $\alpha_{P}\to 0$ (note that of course the state $\nu$
will change with $n,m$, $\alpha_{S}$ and $\alpha_{P}$), we find that
asymptotically the parallel strategy has better or at least equal type II
error decay than the sequential one, and hence our result also implies the
known result that, asymptotically (and with $\alpha\to 0$), sequential
strategies offer no advantage over parallel ones.

The following is the more refined version of our result, with a tighter bound
and a description of the parallel input state:

######  Theorem 7 (Main result, technical version).

Let $\mathcal{E},\mathcal{F}:A\to B$ be quantum channels such that
$D_{\max}(\mathcal{E}\|\mathcal{F})<\infty$. Given any sequential protocol
with $n$ channel uses and associated states
$\rho_{i},\sigma_{i}\in\mathcal{D}\left(R_{S}\otimes A\right)$, $i=1,\ldots,n$
(see above for the definition of this notation), define
$\ell\in\\{1,\ldots,n\\}$ as the step in the protocol where the
distinguishability increases the most, i.e.

$\ell\coloneqq\operatorname*{\arg\max}_{k=1,\ldots,n}\Big{[}D(\mathcal{E}(\rho_{k})\|\mathcal{F}(\sigma_{k}))-D(\rho_{k}\|\sigma_{k})\Big{]}\,.$
(41)

Then, for all $\alpha_{P}\in(0,1]$, $\alpha_{S}\in[0,1]$, and
$m\in\mathbb{N}$, there exists a state $\nu\in\mathcal{D}\left(R^{\otimes
m}\otimes A^{\otimes m}\right)$ such that

$\frac{1}{m}D_{H}^{\alpha_{P}}\big{(}\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes
m}(\nu)\big{)}\geq\frac{1-\alpha_{S}}{n}D_{H}^{\alpha_{S}}\big{(}\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n})\big{)}-\frac{c^{\prime}_{\ell}}{\sqrt{m}}\quantity[\log(4\over\alpha_{P})+K]\\\
-\frac{1}{m}\quantity[\log(1\over\alpha_{P})-\log(1-\frac{\alpha_{P}}{4})]-\frac{h(\alpha_{S})}{n}\,.$
(42)

where

$K\coloneqq\frac{\ln(2)\log^{2}(3)}{8}\cosh(\log(3)\over 2)\leq 0.29$ (43)

and $c^{\prime}_{\ell}$ depends on the pair of channels $\mathcal{E}$,
$\mathcal{F}$ and can be bounded as follows

$\displaystyle c^{\prime}_{\ell}$
$\displaystyle\coloneqq{4\over\log(3)}\inf_{{\gamma_{1},\gamma_{2}\in(0,1]}}\quantity[c_{\gamma_{1}}(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))+c_{\gamma_{2}}(\rho_{\ell}\|\sigma_{\ell})]$
(44)
$\displaystyle\leq{8\ell\over\log(3)}\inf_{\gamma\in(0,1]}\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})$
(45)
$\displaystyle\leq{8n\over\log(3)}\inf_{\gamma\in(0,1]}\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\,.$
(46)

where

$\displaystyle c_{\gamma}(\rho\|\sigma)$
$\displaystyle\coloneqq\frac{1}{\gamma}\log(2^{\gamma
D_{1+\gamma}(\rho\|\sigma)}+2^{-\gamma D_{1-\gamma}(\rho\|\sigma)}+1),$ (47)
$\displaystyle\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})$
$\displaystyle\coloneqq\frac{1}{\gamma}\log(2^{\gamma\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})}+2)\,.$
(48)

Moreover, if

$m\geq\log(4\over\alpha_{P})\quantity(\frac{4}{\log(3)\sqrt{2\ln(2)}})^{2}$
(49)

then we have the following tighter bound

$\frac{1}{m}D_{H}^{\alpha_{P}}\big{(}\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes
m}(\nu)\big{)}\geq\frac{1-\alpha_{S}}{n}D_{H}^{\alpha_{S}}\big{(}\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n})\big{)}-\frac{c_{\ell}}{\sqrt{m}}\sqrt{\log(4\over\alpha_{P})}\\\
-\frac{1}{m}\quantity[\log(1\over\alpha_{P})-\log(1-\frac{\alpha_{P}}{4})]-\frac{h(\alpha_{S})}{n}\,.$
(50)

where $c_{\ell}$ is defined in a similar way as $c^{\prime}_{\ell}$ but with
different numerical constants $K_{1}$ and $K_{2}$:

$\displaystyle K_{1}$ $\displaystyle\coloneqq 2\sqrt{2\ln(2)\cosh(\log(3)\over
2)}\leq 2.72\qquad\qquad K_{2}\coloneqq 2\sqrt{2\ln(2)}\leq 2.36\,.$ (51)
$\displaystyle c_{\ell}$
$\displaystyle\coloneqq\inf_{{\gamma_{1},\gamma_{2}\in(0,1]}}\quantity[K_{1}c_{\gamma_{1}}(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))+K_{2}c_{\gamma_{2}}(\rho_{\ell}\|\sigma_{\ell})]$
(52)
$\displaystyle\leq\ell(K_{1}+K_{2})\inf_{\gamma\in(0,1]}\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})$
(53) $\displaystyle\leq
n(K_{1}+K_{2})\inf_{\gamma\in(0,1]}\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\,.$
(54)

The parallel input state $\nu$ can be chosen as either:

  * •

The optimizer in the smoothing of the max-divergence
$D^{\varepsilon}_{\max}(\rho_{l}^{\otimes m}\|\sigma_{l}^{\otimes m})$, where
$\varepsilon=\frac{1}{2}\left(1-\sqrt{1-\alpha_{P}}\right)$, i.e.:

$\nu=\tilde{\nu}_{R_{S}^{m}A^{m}}\coloneqq\operatorname*{\arg\min}_{\tilde{\rho}\in
B^{\circ}_{\varepsilon}(\rho_{\ell}^{\otimes
m})}D_{\max}(\tilde{\rho}\|\sigma_{\ell}^{\otimes m})\,.$ (55)

Note that the reference system $R_{S}$ depends on the sequential protocol and
can be arbitrarily large, and hence also $\tilde{\nu}$ might have an
arbitrarily large reference system.

  * •

The canonical (or any other) purification of the $A^{m}$-marginal
$\tilde{\nu}_{A^{m}}=\Tr_{R_{S}^{m}}(\tilde{\nu}_{R_{S}^{m}A^{m}})$. That is,
we can choose $\nu=\outerproduct{\psi_{R^{m}A^{m}}}{\psi_{R^{m}A^{m}}}$, with

$\ket{\psi_{R^{m}A^{m}}}=\IdentityMatrix_{R^{m}}\otimes\sqrt{\tilde{\nu}_{A^{m}}}\ket{\Phi_{R^{m}A^{m}}}$
(56)

where $R$ is isomorphic to $A$ and $\ket{\Phi_{R^{m}A^{m}}}$ is an
unnormalized maximally entangled state.

######  Remark 8.

The constraint $D_{\max}(\mathcal{E}\|\mathcal{F})<\infty$ is necessary in
general, as the example of [Har+10, SHW21] shows that one can otherwise
construct channels $\mathcal{E}$, $\mathcal{F}$ and a sequential strategy with
only two channel uses, such that for all $\alpha_{S}\in[0,1]$

$D_{H}^{\alpha_{S}}(\mathcal{E}(\rho_{2})\|\mathcal{F}(\sigma_{2}))=\infty,$
(57)

whereas for all $m$, one can find a sufficiently small $\alpha_{P}$ such that
for all $\nu\in\mathcal{D}\left(R\otimes A^{\otimes m}\right)$

$D_{H}^{\alpha_{P}}(\mathcal{E}^{\otimes m}(\nu)\|\mathcal{F}^{\otimes
m}(\nu))<\infty.$ (58)

Hence a relation like (50) cannot hold in this case. Note that, even in this
example, the Stein exponent, i.e. the optimal exponential decay rate of the
type II error such that the type I error still goes to zero, is still
identical for the parallel and sequential strategies, as it is infinite also
for the optimal parallel strategy. This follows from

$D_{\max}(\mathcal{E}\|\mathcal{F})=\infty\quad\Rightarrow\quad
D(\mathcal{E}\|\mathcal{F})=D^{\mathrm{reg}}(\mathcal{E}\|\mathcal{F})=\infty\,.$
(59)

Figure 2: Illustration of a key step in our proof, the construction of the
parallel input state. We start by picking a single step
$\ell\in\\{1,\ldots,n\\}$ out of the sequential protocol, where the
distinguishability increase
$D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})$
is maximal (this corresponds to the step from the orange to the dotted grey
line in the diagram). Now consider $m$ copies of the sequential strategy in
parallel. We construct our parallel input state $\nu$ starting from $m$ copies
of the input state of the sequential strategy at this step $\ell$ if the
channel was $\mathcal{E}$ (this is $\rho_{\ell}^{\otimes m})$. $\nu$ is then
smoothed a bit to reduce its distance to $\sigma_{\ell}^{\otimes m}$ (which is
the input state that we would have if the channel was $\mathcal{F}$). The
degree to which we smooth depends on the type I error $\alpha_{P}$ we want to
achieve with the parallel strategy. Having a small type I error means that the
state $\nu$ is very close to $\rho_{\ell}^{\otimes m}$, whereas allowing for a
larger type I error will move the state closer to $\sigma_{\ell}^{\otimes m}$.

The remainder of this section proves Theorem 7. The general idea of the proof
will be the following: We will start by moving from the hypothesis testing
relative entropy of the sequential strategy to normal relative entropy using
1. Then, we will see that by using an amortization argument (equations
(97)–(100) below), we can bound the performance of the sequential strategy by
the performance of just one of its steps, the step where the
distinguishability of the two states (that occur if the channel is either
$\mathcal{E}$ or $\mathcal{F}$) increases the most. We then consider $m$
parallel copies of this step, and construct a parallel input state using a
chain rule for the smoothed max relative entropy (9), see Figure 2 below for
an illustration of this step. The smoothed max relative entropies can be
related to the normal relative entropies we used in the amortization argument
by non-asymptotic bounds we present in 15. Finally we connect to hypothesis
testing relative entropy of a parallel protocol using 2.

The following two subsections present lemmas we will use as part of our proof
of Theorem 7.

###  3.1 A Simple One-Shot Version of the Chain Rule

The following is a variant of [Fan+20, Prop. 3.2], where smoothing the max-
divergence only over normalized states and restricting to the case of a single
input system makes things considerably simpler.

######  Lemma 9.

Let $\mathcal{E}$ and $\mathcal{F}$ be arbitrary quantum channels from system
$A$ to system $B$, and let $\rho\in\mathcal{D}\left(A\right)$,
$\sigma\in\mathscr{P}\\!\left(A\right)$. Then for all
$\varepsilon,\varepsilon^{\prime}\in[0,1]$ there exists a state $\nu\in
B_{\varepsilon}^{\circ}(\rho)$ such that

$D^{\varepsilon+\varepsilon^{\prime}}_{\max}(\mathcal{E}(\rho)\|\mathcal{F}(\sigma))\leq
D^{\varepsilon}_{\max}(\rho\|\sigma)+D^{\varepsilon^{\prime}}_{\max}(\mathcal{E}(\nu)\|\mathcal{F}(\nu))\,.$
(60)

Moreover, $\nu$ can be chosen as

$\nu=\operatorname*{\arg\min}_{\tilde{\rho}\in
B^{\circ}_{\varepsilon}(\rho)}D_{\max}(\tilde{\rho}\|\sigma)\,.$ (61)

###### Proof.

Let $\nu\in B^{\circ}_{\varepsilon}(\rho)$ be an optimizer in
$D_{\max}^{\varepsilon}(\rho\|\sigma)$, i.e.

$\nu\leq 2^{D_{\max}^{\varepsilon}(\rho\|\sigma)}\sigma.$ (62)

Since $\mathcal{F}$ is a positive map this implies

$\mathcal{F}(\nu)\leq
2^{D_{\max}^{\varepsilon}(\rho\|\sigma)}\mathcal{F}(\sigma)\,.$ (63)

Furthermore, let $\tau\in B^{\circ}_{\varepsilon^{\prime}}(\mathcal{E}(\nu))$
be an optimizer such that

$\tau\leq
2^{D_{\max}^{\varepsilon^{\prime}}(\mathcal{E}(\nu)\|\mathcal{F}(\nu))}\mathcal{F}(\nu)\,.$
(64)

Combining the last two equations we get

$\tau\leq
2^{D_{\max}^{\varepsilon^{\prime}}(\mathcal{E}(\nu)\|\mathcal{F}(\nu))+D_{\max}^{\varepsilon}(\rho\|\sigma)}\mathcal{F}(\sigma)\,.$
(65)

It remains to show that
$P(\tau,\mathcal{E}(\rho))\leq\varepsilon+\varepsilon^{\prime}$ (where $P$ is
the sine distance). This follows from

$P(\tau,\mathcal{E}(\rho))\leq
P(\tau,\mathcal{E}(\nu))+P(\mathcal{E}(\nu),\mathcal{E}(\rho))\leq\varepsilon^{\prime}+P(\nu,\rho)\leq\varepsilon^{\prime}+\varepsilon\,.$
(66)

where we used the triangle inequality and the data-processing inequality for
the sine distance (see e.g. [KW20]). ∎

###  3.2 Non-Asymptotic Bounds for the Smooth Max-Relative Entropy

The asymptotic equipartition property [TCR09] states that

$\lim_{n\to\infty}\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes
n}\|\sigma^{\otimes n})=D(\rho\|\sigma)\quad\forall\varepsilon\in(0,1)\,.$
(67)

For our proof of Theorem 7 we will require a bound on the speed of this
convergence. Results in this direction have appeared before in the literature,
however none of the previous results turn out to be directly applicable for
our purposes (see 13 and 14 below). To prove our result we follow the
established path using quantum Rényi divergences. One key ingredient is a
bound on the distance between the Petz–Rényi divergence and relative entropy,
where the following is a slight refinement of [Tom12, Lemma 6.3]:

######  Lemma 10.

Let $\rho,\sigma\in\mathcal{D}\left(\mathcal{H}\right)$ be quantum states. For
$\gamma\in(0,1]$, define

$c_{\gamma}(\rho\|\sigma)\coloneqq\frac{1}{\gamma}\log(2^{\gamma
D_{1+\gamma}(\rho\|\sigma)}+2^{-\gamma D_{1-\gamma}(\rho\|\sigma)}+1)\,.$ (68)

Then, for all $\gamma\in(0,1]$ and $\delta\in(0,\frac{\gamma}{2}]$:

$\displaystyle D_{1+\delta}(\rho\|\sigma)$ $\displaystyle\leq
D(\rho\|\sigma)+\ln(2)\delta(c_{\gamma}(\rho\|\sigma))^{2}$ (69)
$\displaystyle\leq D(\rho\|\sigma)+\delta(c_{\gamma}(\rho\|\sigma))^{2}$ (70)

Furthermore, if $D(\rho\|\sigma)<\infty$, then for all $\gamma\in(0,1]$ and
$\delta\in(0,\frac{\gamma}{2}]$

$D_{1-\delta}(\rho\|\sigma)\geq
D(\rho\|\sigma)-\ln(2)\delta(c_{\gamma}(\rho\|\sigma))^{2}\cosh(\ln(2)\delta
c_{\gamma}(\rho\|\sigma))\,.$ (71)

and for all $\delta\in(0,\frac{\log 3}{2c_{\gamma}(\rho\|\sigma)}]$:

$\displaystyle D_{1-\delta}(\rho\|\sigma)$ $\displaystyle\geq
D(\rho\|\sigma)-\ln(2)\cosh(\log(3)/2)\delta(c_{\gamma}(\rho\|\sigma))^{2}$
(72) $\displaystyle\geq
D(\rho\|\sigma)-\delta(c_{\gamma}(\rho\|\sigma))^{2}\,.$ (73)

The proof of this lemma appears in Appendix A.1.

######  Remark 11.

The previously known bound [Tom12, Lemma 6.3] states only an analogue of (70)
and follows from 10 after setting $\gamma=1/2$. Note that in its analogue of
(70), [Tom12, Lemma 6.3] also has a stronger constraint on the range of
$\delta$, which turns out not to be necessary.

Using 10 we can then establish a bound on the convergence speed in the
asymptotic equipartition property:

######  Lemma 12.

Let $\rho,\sigma\in\mathcal{D}\left(\mathcal{H}\right)$ be quantum states, and
for $\gamma\in(0,1]$, take $c_{\gamma}(\rho\|\sigma)$ as in (68). Then, for
all $\varepsilon\in(0,1]$ and $n\in\mathbb{N}$:

$\displaystyle\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\geq
D(\rho\|\sigma)-\frac{c_{\gamma}(\rho\|\sigma)}{\sqrt{n}}\quantity[\frac{\ln(2)\log(3)}{2}\cosh(\log(3)\over
2)+\frac{4}{\log(3)}\log(1\over 1-\varepsilon)],$ (74)
$\displaystyle\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\leq
D(\rho\|\sigma)+\frac{c_{\gamma}(\rho\|\sigma)}{\sqrt{n}}\quantity[\frac{\ln(2)\log(3)}{2}+\frac{4}{\log(3)}\log(1\over\varepsilon)]+\frac{1}{n}\log(1\over
1-\varepsilon^{2}),$ (75)

which implies

$\displaystyle\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\geq
D(\rho\|\sigma)-\frac{4c_{\gamma}(\rho\|\sigma)}{\sqrt{n}}\log(2\over
1-\varepsilon),$ (76)
$\displaystyle\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\leq
D(\rho\|\sigma)+\frac{4c_{\gamma}(\rho\|\sigma)}{\sqrt{n}}\log(2\over\varepsilon)+\frac{1}{n}\log(1\over
1-\varepsilon^{2})\,.$ (77)

These bounds can be tightened by adding a condition on $n$ to be large enough.
Define first the numerical constants

$K_{1}=2\sqrt{2\ln(2)\cosh(\log(3)\over 2)}\leq 2.72,\qquad\qquad
K_{2}=2\sqrt{2\ln(2)}\leq 2.36\,.$ (78)

Then, if

$n\geq\log(1\over 1-\varepsilon)\quantity(\frac{8}{\log(3)K_{1}})^{2},$ (79)

we have the stronger bound

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\geq
D(\rho\|\sigma)-\frac{K_{1}}{\sqrt{n}}c_{\gamma}(\rho\|\sigma)\sqrt{\log(1\over
1-\varepsilon)},$ (80)

and similarly, if

$n\geq\log(1\over\varepsilon)\quantity(\frac{8}{\gamma
c_{\gamma}(\rho\|\sigma)K_{2}})^{2},$ (81)

it holds that

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\leq
D(\rho\|\sigma)+\frac{K_{2}}{\sqrt{n}}c_{\gamma}(\rho\|\sigma)\sqrt{\log(1\over\varepsilon)}+\frac{1}{n}\log(1\over
1-\varepsilon^{2})\,.$ (82)

Remember that $\gamma c_{\gamma}(\rho\|\sigma)\geq\log(3)$, and hence (81) is
also always satisfied if

$n\geq\log(1\over\varepsilon)\quantity(\frac{8}{\log(3)K_{2}})^{2}\,.$ (83)

The proof of this lemma appears in appendix A.2.

######  Remark 13.

Our 15 can be seen an extension of [Tom12, Theorem 6.4], where a similar bound
to (82) is shown (however with a worse constant and different smoothing
convention). An equivalent of (80) is shown in [Tom12] only for the smoothed
conditional min entropy and not for the (more general) smoothed max-relative
entropy.

######  Remark 14.

Another already existing bound of the AEP convergence is the so-called second
order expansion [TH13], which gives a tight asymptotic characterization also
of the second-order $\sqrt{n}$ term in the convergence to the relative
entropy. There, the second-order term is shown to be proportional to the
square root of the relative entropy variance

$V(\rho\|\sigma)\coloneqq\Tr(\rho(\log(\rho)-\log(\sigma)-D(\rho\|\sigma))^{2})\,.$
(84)

Later in the proof of Theorem 7, we want to apply these convergence bounds to
the case in which $\rho=\rho_{n}$ and $\sigma=\sigma_{n}$ are the states in a
sequential protocol, and we would like to obtain a bound on the convergence
parameter in $n$. We will see that by using chain rules for the geometric
relative Rényi entropy (or the max relative entropy) we will be able to show
that $c_{\gamma}(\rho_{n}\|\sigma_{n})=\mathcal{O}(n)$, while we are not aware
of any way of obtaining such a bound for $V(\rho_{n}\|\sigma_{n})$, and hence
cannot directly use second order asymptotics.

######  Lemma 15.

Let $\rho$ and $\sigma$ be quantum states, and let $\varepsilon\in(0,1)$. Let
$c(\rho\|\sigma)$ be defined as in (LABEL:eq:c_rho_sigma). Then, for all $n$:

$\displaystyle\frac{1}{n}D_{\max}^{\varepsilon}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\leq
D(\rho\|\sigma)+\frac{4\sqrt{2}}{\sqrt{n}}c(\rho\|\sigma)\log(1\over\varepsilon^{2})+\frac{1}{n}\log(1\over
1-\varepsilon^{2}),$ (85)
$\displaystyle\frac{1}{n}D_{\max}^{\varepsilon}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\geq
D(\rho\|\sigma)-\quantity(\frac{4\sqrt{2}}{\sqrt{n}}c(\rho\|\sigma)+\frac{1}{n})\log(4\over
1-\varepsilon^{2})\,.$ (86)

###### Proof.

The upper bound is immediate from combining the upper bound in (20) with
(LABEL:eq:n_shot_steins_uppper). For the lower bound, we combine the lower
bound in (20) with (LABEL:eq:n_shot_steins_lower), to find for any
$\delta\in(0,1-\varepsilon^{2})$

$\frac{1}{n}D_{\max}^{\varepsilon}(\rho^{\otimes n}\|\sigma^{\otimes n})\geq
D(\rho\|\sigma)-\frac{4\sqrt{2}}{\sqrt{n}}c\log(1\over
1-\varepsilon^{2}-\delta)-\frac{1}{n}\log(4(1-\varepsilon^{2})\over\delta^{2})+{2\over
n},$ (87)

where we abbreviated $c(\rho\|\sigma)$ as $c$. By taking the derivative of the
right hand side with respect to $\delta$, we find that the right-hand side is
stationary for

$-\frac{4\sqrt{2}}{\sqrt{n}}c{1\over
1-\varepsilon^{2}-\delta}+\frac{2}{n\delta}=0$ (88)

which is equivalent to

$\delta=\frac{1-\varepsilon^{2}-\delta}{\sqrt{8n}c}$ (89)

and hence

$\delta=\frac{1-\varepsilon^{2}}{1+\sqrt{8n}c}\,.$ (90)

We further find the second derivative of the right-hand side to be

$\log(e)\quantity[-\frac{4\sqrt{2}c}{\sqrt{n}}\frac{1}{(1-\varepsilon^{2}-\delta)^{2}}-\frac{2}{n\delta^{2}}]$
(91)

which is negative for all $\delta\in(0,1-\varepsilon^{2})$ and hence the
function is concave in that range and the stationary point we just found is a
global maximum. For simplicity let us define $K\coloneqq\sqrt{8n}c$. To
simplify the right-hand side of (87) at the optimal value of $\delta$, let us
look at the two $\delta$-dependent terms, multiplied by $n$:

$2K\log(1-\varepsilon^{2}-\delta)+\log(\delta^{2}\over
4(1-\varepsilon^{2}))=(2K+1)\log(1-\varepsilon^{2})+2K\log(K\over
1+K)+2\log(1\over 2(1+K))$ (92)

The last two terms we can write as

$\displaystyle 2(1+K)\quantity[{K\over 1+K}\log(K\over 1+K)+{1\over
1+K}\log(1\over 1+K)-{1\over 1+K}]$
$\displaystyle=2(1+K)\quantity[-h\quantity(1\over 1+K)-{1\over 1+K}]$
$\displaystyle\geq-4(1+K),$ (93)

where $h$ is the binary entropy function. Putting everything together, (87)
with the optimal value of $\delta$ then becomes

$\displaystyle\frac{1}{n}D_{\max}^{\varepsilon}(\rho^{\otimes
n}\|\sigma^{\otimes n})$ $\displaystyle\geq
D(\rho\|\sigma)-\frac{1}{n}\quantity[(2K+1)\log(1\over
1-\varepsilon^{2})+4(1+K)-2]$ (94)
$\displaystyle=D(\rho\|\sigma)-\frac{(2K+1)}{n}\log(4\over
1-\varepsilon^{2}),$ (95)

which is the claimed statement. ∎

###  3.3 Proof of our main result (Theorem 7)

###### Proof.

We start by applying 1 to
$D_{H}^{\alpha_{S}}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))$:

$\frac{1}{n}D_{H}^{\alpha_{S}}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))\leq\frac{1}{n}\frac{1}{1-\alpha_{S}}\big{(}D(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))+h(\alpha_{S})\big{)}\,.$
(96)

Note now that we can write

$\displaystyle D(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))$
$\displaystyle=D(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))-D(\rho_{n}\|\sigma_{n})+D(\rho_{n}\|\sigma_{n})$
(97)
$\displaystyle=D(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))-D(\rho_{n}\|\sigma_{n})+D(\Lambda_{n}(\mathcal{E}(\rho_{n-1}))\|\Lambda_{n}(\mathcal{F}(\sigma_{n-1})))$
(98) $\displaystyle\leq
D(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))-D(\rho_{n}\|\sigma_{n})+D(\mathcal{E}(\rho_{n-1})\|\mathcal{F}(\sigma_{n-1}))$
(99)
$\displaystyle\leq\ldots\leq\sum_{k=1}^{n}\Big{[}D(\mathcal{E}(\rho_{k})\|\mathcal{F}(\sigma_{k}))-D(\rho_{k}\|\sigma_{k})\Big{]}$
(100)

where we used the definition of $\rho_{k}$ and $\sigma_{k}$, the data-
processing inequality, and the fact that $\rho_{1}=\sigma_{1}$. Let us use the
index $\ell$ for the step in the sequential protocol where this amortized
difference is the largest, i.e.

$\ell=\operatorname*{\arg\max}_{k\in\\{1,\ldots,n\\}}\Big{[}D(\mathcal{E}(\rho_{k})\|\mathcal{F}(\sigma_{k}))-D(\rho_{k}\|\sigma_{k})\Big{]}\,.$
(101)

Then,

$\frac{1}{n}D(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))\leq
D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})\,.$
(102)

We can convert this to smoothed max-relative entropies by using 15. We will
proceed with the bound requiring a condition on $m$ (or $n$ as it is called in
15); the $m$-independent bound is achieved in complete analogy by just taking
the alternative statements from 15. We get:

$D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})\leq\frac{1}{m}\Big{(}D_{\max}^{\varepsilon_{1}}\big{(}\mathcal{E}^{\otimes
m}(\rho_{\ell}^{\otimes m})\|\mathcal{F}^{\otimes m}(\sigma_{\ell}^{\otimes
m})\big{)}-D_{\max}^{{\varepsilon_{2}}}\big{(}\rho_{\ell}^{\otimes
m}\|\sigma_{\ell}^{\otimes m}\big{)}\Big{)}\\\
+\frac{1}{\sqrt{m}}\quantity[K_{1}c_{\gamma_{1}}\big{(}\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell})\big{)}\sqrt{\log(1\over
1-\varepsilon_{1})}+K_{2}c_{\gamma_{2}}(\rho_{\ell}\|\sigma_{\ell})\sqrt{\log(1\over\varepsilon_{2})}]+\frac{1}{m}\log(1\over
1-\varepsilon_{2}^{2})$ (103)

where $\gamma_{1},\gamma_{2}\in(0,1]$ and
$\varepsilon_{1},\varepsilon_{2}\in(0,1)$ are arbitrary. It will be very
convenient to choose $1-\varepsilon_{1}=\varepsilon_{2}\eqqcolon\varepsilon$,
which is almost optimal as $K_{1}\approx K_{2}$ and
$c_{\gamma}\big{(}\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell})\big{)}\approx
c_{\gamma}(\rho_{\ell}\|\sigma_{\ell})$ for large $\ell$ (which is the regime
we are most interested in). Then,

$D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})\leq\frac{1}{m}\Big{(}D_{\max}^{1-\varepsilon}\big{(}\mathcal{E}^{\otimes
m}(\rho_{\ell}^{\otimes m})\|\mathcal{F}^{\otimes m}(\sigma_{\ell}^{\otimes
m})\big{)}-D_{\max}^{{\varepsilon}}\big{(}\rho_{\ell}^{\otimes
m}\|\sigma_{\ell}^{\otimes m}\big{)}\Big{)}\\\
+\frac{c_{\ell}}{\sqrt{m}}\sqrt{\log(1\over\varepsilon)}+\frac{1}{m}\log(1\over
1-\varepsilon^{2})$ (104)

where

$c_{\ell}\coloneqq\inf_{\gamma_{1},\gamma_{2}\in(0,1]}\quantity[K_{1}c_{\gamma_{1}}\big{(}\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell})\big{)}+K_{2}c_{\gamma_{2}}(\rho_{\ell}\|\sigma_{\ell})]$
(105)

and the conditions on $m$ from 15 will be satisfied if

$m\geq\log(1\over\varepsilon)\quantity(\frac{8}{\log(3)K_{2}})^{2}\,.$ (106)

Taking $\varepsilon\leq 1/2$, we can apply 9 to (104). We then get a state
$\tilde{\nu}\in B^{\circ}_{\varepsilon}(\rho_{\ell}^{\otimes m})$ such that:

$D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})\leq\frac{1}{m}D_{\max}^{1-2\varepsilon}\big{(}\mathcal{E}^{\otimes
m}(\tilde{\nu})\|\mathcal{F}^{\otimes
m}(\tilde{\nu})\big{)}+\frac{c_{\ell}}{\sqrt{m}}\sqrt{\log(1\over\varepsilon)}+\frac{1}{m}\log(1\over
1-\varepsilon^{2})$ (107)

Note that
$\tilde{\nu}=\tilde{\nu}_{R_{S}^{m}A^{m}}\in\mathcal{D}\left(R_{S}^{\otimes
m}\otimes A^{\otimes m}\right)$ is the first of the two possible choices for
$\nu$ given in Theorem 7. For the other one, let
$\tilde{\nu}_{R^{\prime}R_{S}^{m}A^{m}}$ be a purification of
$\tilde{\nu}_{R_{S}^{m}A^{m}}$, and hence also a purification of
$\tilde{\nu}_{A^{m}}$. As the smoothed max-divergence satisfies the data-
processing inequality (see e.g. [KW20, Prop. 4.60]) we have

$D_{\max}^{1-2\varepsilon}\big{(}\mathcal{E}^{\otimes
m}(\tilde{\nu}_{R_{S}^{m}A^{m}})\|\mathcal{F}^{\otimes
m}(\tilde{\nu}_{R_{S}^{m}A^{m}})\big{)}\leq
D_{\max}^{1-2\varepsilon}\big{(}\mathcal{E}^{\otimes
m}(\tilde{\nu}_{R^{\prime}R_{S}^{m}A^{m}})\|\mathcal{F}^{\otimes
m}(\tilde{\nu}_{R^{\prime}R_{S}^{m}A^{m}})\big{)}\,.$ (108)

Now, let $\nu$ be the canonical purification of $\tilde{\nu}_{A^{m}}$, as
specified in Theorem 7. Since all purifications are equivalent up to an
isometry on the purifying system (see, e.g., [KW20]) on which the channels
$\mathcal{E}^{\otimes m}$ and $\mathcal{F}^{\otimes m}$ act as an identity,
and since the smoothed max-divergence is invariant under isometries, we have

$D_{\max}^{1-2\varepsilon}\big{(}\mathcal{E}^{\otimes
m}(\tilde{\nu}_{R^{\prime}R_{S}^{m}A^{m}})\|\mathcal{F}^{\otimes
m}(\tilde{\nu}_{R^{\prime}R_{S}^{m}A^{m}})\big{)}=D_{\max}^{1-2\varepsilon}\big{(}\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes m}(\nu)\big{)}\,.$ (109)

We will proceed with $\nu$ as the chosen state, but note that everything works
analogously by choosing $\tilde{\nu}$. We now further apply the upper bound
from 2 to find:

$D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})\leq\frac{1}{m}D_{H}^{1-(1-2\varepsilon)^{2}}\big{(}\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes m}(\nu)\big{)}\\\
+\frac{c_{\ell}}{\sqrt{m}}\sqrt{\log(1\over\varepsilon)}+\frac{1}{m}\quantity[\log(1\over
1-\varepsilon^{2})+\log(1\over 1-(1-2\varepsilon)^{2})].$ (110)

To get our desired expression we set $\alpha_{P}\coloneqq
1-(1-2\varepsilon)^{2}$, or equivalently
$\varepsilon=\frac{1}{2}(1-\sqrt{1-\alpha_{P}})$. Using the estimates

$\frac{1-\sqrt{1-\alpha_{P}}}{2}\geq\frac{\alpha_{P}}{4}$ (111)

and

$1-\varepsilon^{2}=\frac{1+\sqrt{1-\alpha_{P}}}{2}+\frac{\alpha_{P}}{4}\geq
1-\frac{\alpha_{P}}{4},$ (112)

we arrive at the expression

$D(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))-D(\rho_{\ell}\|\sigma_{\ell})\leq\frac{1}{m}D_{H}^{\alpha_{P}}\big{(}\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes m}(\nu)\big{)}\\\
+\frac{c_{\ell}}{\sqrt{m}}\sqrt{\log(4\over\alpha_{P})}+\frac{1}{m}\quantity[\log(1\over\alpha_{P})-\log(1-\frac{\alpha_{P}}{4})],$
(113)

which we can insert into (102) and then (96) to get

$\frac{1}{n}D_{H}^{\alpha_{S}}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))\leq\frac{1}{1-\alpha_{S}}\Bigg{[}\frac{1}{m}D_{H}^{\alpha_{P}}(\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes
m}(\nu))+\frac{c_{\ell}}{\sqrt{m}}\sqrt{\log(4\over\alpha_{P})}\\\
+\frac{1}{m}\quantity[\log(1\over\alpha_{P})-\log(1-\frac{\alpha_{P}}{4})]+\frac{h(\alpha_{S})}{n}\Bigg{]},$
(114)

which leads to the desired statement in (50).

For the bounds on $c_{\ell}$, we start with

$\displaystyle c_{\gamma}(\mathcal{E}(\rho_{l})\|\mathcal{F}(\sigma_{l}))$
$\displaystyle=\frac{1}{\gamma}\log(2^{\gamma
D_{1+\gamma}(\mathcal{E}(\rho_{l})\|\mathcal{F}(\sigma_{l}))}+2^{-\gamma
D_{1-\gamma}(\mathcal{E}(\rho_{l})\|\mathcal{F}(\sigma_{l}))}+1)$ (115)
$\displaystyle\leq\frac{1}{\gamma}\log(2^{\gamma\widehat{D}_{1+\gamma}(\mathcal{E}(\rho_{l})\|\mathcal{F}(\sigma_{l}))}+2)\,.$
(116)

Now, by repeated use of the chain rule for the geometric Rényi divergence
relative entropy [fang_geometric_2019, Thm 3.4] we get

$\displaystyle\widehat{D}_{1+\gamma}(\mathcal{E}(\rho_{\ell})\|\mathcal{F}(\sigma_{\ell}))$
$\displaystyle\leq\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})+\widehat{D}_{1+\gamma}(\rho_{\ell}\|\sigma_{\ell})$
(117)
$\displaystyle=\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})+\widehat{D}_{1+\gamma}(\Lambda_{i}(\mathcal{E}(\rho_{\ell-1}))\|\Lambda_{i}(\mathcal{F}(\sigma_{\ell-1})))$
(118)
$\displaystyle\leq\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})+\widehat{D}_{1+\gamma}(\mathcal{E}(\rho_{\ell-1})\|\mathcal{F}(\sigma_{\ell-1}))$
(119)
$\displaystyle\leq\ldots\leq\ell\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})\,.$
(120)

Defining the corresponding channel quantity

$\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\coloneqq\frac{1}{\gamma}\quantity(2^{\gamma\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})}+2)$
(121)

we find that

$c_{\gamma}(\mathcal{E}(\rho_{l})\|\mathcal{F}(\sigma_{l}))\leq\frac{1}{\gamma}\log(2^{\ell\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})}+2)\leq\frac{\ell}{\gamma}\log(2^{\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})}+2)=\ell\,\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\,.$
(122)

Using the same argument we find that also
$\widehat{D}_{1+\gamma}(\rho_{k}\|\sigma_{k})\leq\ell\widehat{D}_{1+\gamma}(\mathcal{E}\|\mathcal{F})$
and hence also

$c_{\gamma}(\rho_{l}\|\sigma_{l})\leq\ell\,\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\,.$
(123)

Thus,

$c_{\ell}\leq\ell(K_{1}+K_{2})\inf_{\gamma\in(0,1]}\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\leq
n(K_{1}+K_{2})\inf_{\gamma\in(0,1]}\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\,.$
(124)

∎

####  3.3.1 Proof of 5

###### Proof.

5 follows from (42) by making the following estimates

$\displaystyle h(\alpha_{S})$ $\displaystyle\leq 1$ (125) $\displaystyle K$
$\displaystyle\leq 1$ (126) $\displaystyle c^{\prime}_{\ell}$
$\displaystyle\leq\frac{8n}{\log(3)}\widehat{c}_{2}(\mathcal{E}\|\mathcal{F})\approx
5.05\,n\,\widehat{c}_{1}(\mathcal{E}\|\mathcal{F})\leq
6\,n\,\widehat{c}_{1}(\mathcal{E}\|\mathcal{F})$ (127)
$\displaystyle-\log(1-{\alpha_{P}\over 4})$ $\displaystyle\leq 1$ (128)

Combining all of these we can bound the error term by

$\frac{6n}{\sqrt{m}}\widehat{c}_{1}(\mathcal{E}\|\mathcal{F})\log(8\over\alpha_{P})+\frac{1}{m}\log(2\over\alpha_{P})+\frac{1}{n}\leq\frac{7n}{\sqrt{m}}\widehat{c}_{1}(\mathcal{E}\|\mathcal{F})\log(8\over\alpha_{P})+\frac{1}{n}$
(129)

where we used that $\widehat{c}_{\gamma}(\mathcal{E}\|\mathcal{F})\geq 1$ for
all $\gamma\in(0,1]$. Note finally that
$\widehat{D}_{2}(\mathcal{E}\|\mathcal{F})=D_{2}(\mathcal{E}\|\mathcal{F})\leq
D_{\max}(\mathcal{E}\|\mathcal{F})$, which leads to the desired expression of
$C$ in (39). ∎

##  4 A Simple Example

The following simple example illustrates the separation between parallel and
sequential strategies for finite number of channel uses and the use of our
bound. It is inspired by the already mentioned example from [Har+10, SHW21]
that shows a separation between sequential and parallel channel discrimination
when treating errors symmetrically. As mentioned in 8, their example has
$D_{\max}(\mathcal{E}\|\mathcal{F})=\infty$ and hence our theorem does not
immediately apply, which is why we have to smooth $\mathcal{F}$ a little bit
first.

Define the channels
$\mathcal{E},\mathcal{F}:\mathcal{B}\left(\mathbb{C}^{2}\otimes\mathbb{C}^{2}\right)\to\mathcal{B}\left(\mathbb{C}^{2}\right)$:

$\displaystyle\mathcal{E}(\rho\otimes\omega)$
$\displaystyle\coloneqq\outerproduct{0}{0}\braket{0}{\omega}{0}+\outerproduct{0}{0}\braket{0}{\rho}{0}\braket{1}{\omega}{1}+\frac{\IdentityMatrix}{2}\braket{11}{\rho\otimes\omega}{11}$
(130) $\displaystyle\mathcal{F}(\rho\otimes\omega)$
$\displaystyle\coloneqq(1-\varepsilon)\quantity[\outerproduct{+}{+}\braket{0}{\omega}{0}+\outerproduct{1}{1}\braket{+}{\rho}{+}\braket{1}{\omega}{1}+\frac{\IdentityMatrix}{2}\braket{-1}{\rho\otimes\omega}{-1}]+\varepsilon\frac{\IdentityMatrix}{2}\Tr[\rho\otimes\omega].$
(131)

It is easy to see that

$\displaystyle\mathcal{E}\Big{(}\mathcal{E}\big{(}\outerproduct{00}{00}\big{)}\otimes\outerproduct{1}{1}\Big{)}$
$\displaystyle=\outerproduct{0}{0},$ (132)
$\displaystyle\mathcal{F}\Big{(}\mathcal{F}\big{(}\outerproduct{00}{00}\big{)}\otimes\outerproduct{1}{1}\Big{)}$
$\displaystyle=(1-\delta(\varepsilon))\outerproduct{1}{1}+\delta(\varepsilon)\outerproduct{0}{0}\,.$
(133)

where $\delta(\varepsilon)=1/4(3\varepsilon-\varepsilon^{2})$ such that
crucially $\delta(0)=0$. Hence, for $\varepsilon=0$ the above gives a
sequential strategy that makes the channels perfectly distinguishable with
just two channel uses. For all $\varepsilon\in(0,1)$, we will have
$D_{\max}(\mathcal{E}\|\mathcal{F})<\infty$ and can apply our theorem. The
above sequential strategy has $\rho_{1}=\sigma_{1}=\outerproduct{00}{00}$ and
$\rho_{2}=\outerproduct{01}{01}$,
$\sigma_{2}=(1-\varepsilon/2)\outerproduct{+1}{+1}+\varepsilon/2\outerproduct{-1}{-1}$.
Interestingly

$\displaystyle
D(\mathcal{E}(\rho_{1})\|\mathcal{F}(\sigma_{1}))-D(\rho_{1}\|\sigma_{1})$
$\displaystyle=D(\outerproduct{0}{0}\|(1-\varepsilon/2)\outerproduct{+}{+}+\varepsilon/2\outerproduct{-}{-})$
(134) $\displaystyle=-\frac{1}{2}\quantity[\log(\varepsilon\over
2)+\log(1-{\varepsilon\over 2})],$ (135) $\displaystyle
D(\mathcal{E}(\rho_{2})\|\mathcal{F}(\sigma_{2}))-D(\rho_{2}\|\sigma_{2})$
$\displaystyle=\log(\delta(\varepsilon))+\frac{1}{2}\quantity[\log(\varepsilon\over
2)+\log(1-{\varepsilon\over 2})],$ (136)

where one finds that the first one is always larger and so it is actually the
first step that increases the distinguishability the most (when measured in
terms of relative entropy). Hence we have $\ell=1$ in Theorem 7. Also, as
$\rho_{1}=\sigma_{1}$ our parallel input state in Theorem 7 will just be
$\nu=\rho_{1}^{\otimes m}$ as this is what achieves the minimum in the
smoothed max-divergence (for all $\varepsilon^{\prime}$)

$D_{\max}^{\varepsilon^{\prime}}(\rho_{1}^{\otimes m}\|\sigma_{1}^{\otimes
m})=0\,.$ (137)

Figure 3: Illustration of the performances of a pair of a simple sequential
and parallel strategy for a specific pair of channels (see (130) and (131) for
the definitions of the channels $\mathcal{E}$ and $\mathcal{F}$,
respectively). We compare a fixed sequential strategy (constant black line) to
(i) our lower bound on the performance of a parallel strategy (yellow line)
and (ii) the actual performance of a parallel strategy (red and green lines),
which are plotted as functions of the number of of parallel channel uses $m$.
The black line shows the value of (138), i.e. the type II error exponent for
the given sequential strategy with two channel uses and type I error
$\alpha_{S}=0$. The yellow line shows the lower bound on the parallel strategy
from our theorem (i.e. the right-hand side of (50)), choosing
$\alpha_{P}=2^{-5}$. For this specific example we can calculate the parallel
input state $\nu$ of our theorem, and while we cannot explicitly find the
optimal POVM and corresponding type II error (i.e. we cannot explicitly
calculate the left-hand side of (50)), we can bound it from above and below
using second order asymptotics of the hypothesis testing relative entropy,
which is shown in the red and green lines, corresponding to the values of
(141) and (140). We see that for small $m$ the sequential strategy is better,
whereas it is not optimal for large $m$ and hence is eventually surpassed by
the parallel strategy.

To illustrate our theorem, we want to compare the given sequential strategy to
the parallel one from our theorem; i.e. we want to compare the two quantities

$\displaystyle\frac{1}{2}D^{0}_{H}(\mathcal{E}(\rho_{2})\|\mathcal{F}(\sigma_{2}))$
$\displaystyle=-\frac{1}{2}\log(\delta(\varepsilon)),$ (138)
$\displaystyle\frac{1}{m}D^{\alpha_{P}}_{H}(\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes m}(\nu))$
$\displaystyle=\frac{1}{m}D^{\alpha_{P}}_{H}((\mathcal{E}(\rho_{1}))^{\otimes
m}\|(\mathcal{F}(\rho_{1}))^{\otimes m}).$ (139)

While the hypothesis testing relative entropy
$D_{H}^{\alpha_{P}}(\mathcal{E}^{\otimes m}(\nu)\|\mathcal{F}^{\otimes
m}(\nu))$ can in principle be calculated as an SDP, the calculation is not
feasible for large $m$. Instead we can obtain upper and lower bounds on it
based on the second order asymptotics of the convergence to the relative
entropy $D(\mathcal{E}(\rho_{1})\|\mathcal{F}(\rho_{1}))$ [Li14] (this only
works here because our input state is a tensor product). Define
$\rho=\mathcal{E}(\rho_{1})$, $\sigma=\mathcal{F}(\rho_{1})$. Then [Li14, Thm.
5]:

$\displaystyle\frac{1}{m}D^{\alpha_{P}}_{H}(\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes m}(\nu))$ $\displaystyle\geq
D(\rho\|\sigma)+\sqrt{V\over
n}\Phi^{-1}\quantity(\alpha_{P}-\frac{1}{\sqrt{n}}\frac{CT^{3}}{\sqrt{V^{3}}}),$
(140) $\displaystyle\frac{1}{m}D^{\alpha_{P}}_{H}(\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes m}(\nu))$ $\displaystyle\leq
D(\rho\|\sigma)+\sqrt{V\over
n}\Phi^{-1}\quantity(\alpha_{P}+\frac{1}{\sqrt{n}}\quantity(\frac{CT^{3}}{\sqrt{V^{3}}}+2)),$
(141)

where $\Phi^{-1}$ is the inverse of the cumulative distribution function of
the standard normal distribution, $C\leq 0.4784$, and

$\displaystyle V$
$\displaystyle=V(\rho\|\sigma)=\Tr[\rho(\log\rho-\log\sigma-D(\rho\|\sigma))^{2}],$
(142) $\displaystyle T^{3}$
$\displaystyle=T^{3}(\rho\|\sigma)=\sum_{i,j}\lambda_{i}\lvert\innerproduct{x_{i}}{y_{j}}\lvert^{2}\lvert\log(\lambda_{i})-\log(\mu_{j})-D(\rho\|\sigma)\lvert^{3}$
(143)

for spectral decompositions
$\rho=\sum_{i}\lambda_{i}\outerproduct{x_{i}}{x_{i}}$ and
$\sigma=\sum_{j}\mu_{j}\outerproduct{y_{i}}{y_{i}}$.

Figure 3 depicts the quantities appearing in our theorem with the above
definitions of $\mathcal{E}$ and $\mathcal{F}$, choosing
$\varepsilon=2^{-50}$, $\alpha_{S}=0$, and $\alpha_{P}=2^{-5}$. For $c_{\ell}$
in Theorem 7 we used (52) with a numerical optimization over $\gamma_{1}$. One
finds that there is a region of $m$ for which the sequential strategy is
better, and the parallel one is lower bounded fairly tightly by our bound. The
given sequential strategy involves only two channel uses, and is not
necessarily optimal; hence it eventually gets surpassed by the parallel one
for large $m$.

##  5 Discussion and Outlook

In this final section, we discuss several pathways in which our result could
be improved or extended, potentially addressing different open problems in
quantum channel discrimination.

First of all, one might hope to be able to remove the factor of $1-\alpha_{S}$
appearing in (50), perhaps at the cost of an additional error term
proportional to $\log(1-\alpha_{S})$. If this additional error term decays in
$m$ and $n$ (say, as long as $\alpha_{S}$ is bounded away from one), this
would prove the strong converse property for quantum channel discrimination.
To see this, assume we would be able to show something along the lines of the
following equation:

$\frac{1}{m}D_{H}^{\alpha_{P}}(\mathcal{E}^{\otimes
m}(\nu)\|\mathcal{F}^{\otimes
m}(\nu))\overset{?}{\geq}\frac{1}{n}D_{H}^{\alpha_{S}}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n}))-\frac{C_{1}n}{\sqrt{m}}\log(8\over\alpha_{P})-\frac{C_{2}}{n}\log(1\over
1-\alpha_{S})$ (144)

Now, fixing any $\alpha_{S}\in(0,1)$ and taking limits (in this order)
$m\to\infty,n\to\infty,\alpha_{P}\to 0$, we find that for an arbitrary
$\alpha_{S}\in(0,1)$

$D^{\text{reg}}(\mathcal{E}\|\mathcal{F})=\lim_{\alpha_{P}\to
0}\lim_{n\to\infty}D^{\alpha_{P}}_{H}(\mathcal{E}^{\otimes
n}\|\mathcal{F}^{\otimes
n})\overset{?}{\geq}\limsup_{n\to\infty}\frac{1}{n}D_{H}^{\alpha_{S}}(\mathcal{E}(\rho_{n})\|\mathcal{F}(\sigma_{n})),$
(145)

i.e. allowing a finite type I error $\alpha_{S}\in(0,1)$ does not improve the
best achievable type II error rate. This is precisely the strong converse
property. Establishing the strong converse property for quantum channel
discrimination is an important and very interesting open problem, which
despite serious efforts is still unsolved. Significant progress has been made
in [FF21a], and another recent attempt was made in [FGW22].

One might hope to obtain such a variant of our bound without the factor
$1-\alpha_{S}$, by – instead of transitioning from hypothesis testing entropy
to relative entropy in (96) – moving to an $\alpha$-Rényi relative entropy
instead and subsequently employing the known relations between Rényi relative
entropies and smoothed max-relative entropies. It turns out that this will at
some point require bounding the difference between Rényi relative entropies of
order $1-\alpha$ and $1+\alpha$. This is possible using 10, however at the
cost of an error term $(c_{\gamma}(\rho_{n}\|\sigma_{n}))^{2}$, which will
scale quadratically in $n$. As this does not pick up any dependence in $m$,
such an approach will not lead to anything useful in the asymptotic limit, and
is hence unsuccessful.

One further interesting question deals with the relation between $\ell$ and
$n$ in Theorem 7. One might hope that an optimal sequential strategy achieves
the maximum possible distinguishability gain per channel use, i.e.

$D^{A}(\mathcal{E}\|\mathcal{F})=\sup_{\rho,\sigma\in\mathcal{D}\left(R\otimes
A\right)}D(\mathcal{E}(\rho)\|\mathcal{F}(\sigma))-D(\rho\|\sigma),$ (146)

after some finite number of channel uses, or at least comes very close to it.
If that was the case, one could bound $\ell$ by a constant and would remove
the dependence on $n$ in (39). However, note that the supremum in (146) goes
over arbitrarily large reference systems $R$ and hence does not need to be
achieved, and we are not aware of any bounds on the system size $R$ to get
close to the optimum value. Alternatively, since
$D^{A}(\mathcal{E}\|\mathcal{F})=D^{\text{reg}}(\mathcal{E}\|\mathcal{F})$
also a bound on the speed of convergence of the regularized channel divergence
would do, which we are however also not aware of (Ref. [FF21a] proves such a
bound for the sandwiched Rényi divergence, which unfortunately cannot be
extended straightforwardly to relative entropy). Hence, for now we have to
assume that $\ell$ can in general be $n$, and that to adequately simulate a
sequential strategy with $n$ channel uses, one might need to employ more than
$n^{2}$ parallel channel uses to keep the error term in our bound small.

While our result becomes quite powerful in the asymmetric asymptotic setting,
Theorem 7 can in principle be applied for any combination of type I and II
errors. Hence, it could be interesting to apply it to scenarios where the type
I error decays with $m$, say as $\alpha_{P}=2^{-km}$ for some constant $k$. In
this case, one would want to apply (50), to have at least a chance of the
error term being bounded, however – depending on $k$ – the corresponding
condition (49) might not always be fulfilled. It would be interesting to see
whether this condition on $m$ could perhaps be relaxed, to allow for a wider
range of $k$ in this specific scenario.

As mentioned already in 14, our bounds could be significantly tightened if we
were able to employ second order expansions, which however requires
controlling the variance of the relative entropy $V(\rho_{n}\|\sigma_{n})$ in
$n$, which we are unable to do. This seems to be again related to the strong
converse problem, as second order expansions for the hypothesis testing
relative entropy imply the strong converse property. Already for the parallel
case, if one was able to show

$V(\mathcal{E}^{\otimes n}(\nu)\|\mathcal{F}^{\otimes n}(\nu))=\mathcal{O}(n)$
(147)

where $\nu\in\mathcal{D}\left(R^{\otimes n}\otimes A^{\otimes n}\right)$ is
any joint input state, this would be a very significant step towards proving
the strong converse for quantum channel discrimination. Conversely, examples
where this scales faster than linearly in $n$ are quite likely to lend
themselves to counterexamples for the strong converse property. We are not
aware of any such examples: we leave this question open for further
investigation.

Finally, we believe that it should be possible to generalize our result to the
infinite dimensional setting with only minor modifications. This requires
quite a bit of care to ensure that all of the previous results we employ also
hold in infinite dimensions. However, all proofs performed explicitly in this
paper generalize with minor modifications.

Acknowledgements—Bjarne Bergh acknowledges support from the UK Engineering and
Physical Sciences Research Council (EPSRC) under grant number EP/V52024X/1.
Robert Salzmann acknowledges support from the Cambridge Commonwealth, European
and International Trust. Mark M. Wilde acknowledges support from the National
Science Foundation under grant no. 1907615.

## References

  * [AJW19] Anurag Anshu, Rahul Jain and Naqueeb Ahmad Warsi  “One Shot Entanglement Assisted Classical and Quantum Communication over Noisy Quantum Channels: A Hypothesis Testing and Convex Split Approach”  In _IEEE Transactions on Information Theory_ 65.2, 2019, pp. 1287–1306  DOI: 10.1109/TIT.2018.2851297
  * [AMV12] Koenraad M.. Audenaert, Milan Mosonyi and Frank Verstraete  “Quantum State Discrimination Bounds for Finite Sample Size”  In _Journal of Mathematical Physics_ 53.12, 2012, pp. 122205  DOI: 10.1063/1.4768252
  * [Ans+19] Anurag Anshu, Mario Berta, Rahul Jain and Marco Tomamichel  “A Minimax Approach to One-Shot Entropy Inequalities”  In _Journal of Mathematical Physics_ 60.12, 2019, pp. 122201  DOI: 10.1063/1.5126723
  * [Aud+07] K… Audenaert, J. Calsamiglia, R. Muñoz-Tapia, E. Bagan, Ll. Masanes, A. Acin and F. Verstraete  “Discriminating States: The Quantum Chernoff Bound”  In _Physical Review Letters_ 98.16, 2007, pp. 160501  DOI: 10.1103/PhysRevLett.98.160501
  * [Aud+08] K… Audenaert, M. Nussbaum, A. Szkola and F. Verstraete  “Asymptotic Error Rates in Quantum Hypothesis Testing”  In _Communications in Mathematical Physics_ 279.1, 2008, pp. 251–283  DOI: 10.1007/s00220-008-0417-5
  * [BD10] Francesco Buscemi and Nilanjana Datta  “The Quantum Capacity of Channels with Arbitrarily Correlated Noise”  In _IEEE Transactions on Information Theory_ 56.3, 2010, pp. 1447–1460  DOI: 10.1109/TIT.2009.2039166
  * [BD11] Fernando G… Brandao and Nilanjana Datta  “One-Shot Rates for Entanglement Manipulation Under Non-entangling Maps”  In _IEEE Transactions on Information Theory_ 57.3, 2011, pp. 1754–1760  DOI: 10.1109/TIT.2011.2104531
  * [BK15] Joonwoo Bae and Leong-Chuan Kwek  “Quantum State Discrimination and Its Applications”  In _Journal of Physics A: Mathematical and Theoretical_ 48.8, 2015, pp. 083001  DOI: 10.1088/1751-8113/48/8/083001
  * [CDP08] Giulio Chiribella, Giacomo M. D’Ariano and Paolo Perinotti  “Memory Effects in Quantum Channel Discrimination”  In _Physical Review Letters_ 101.18, 2008, pp. 180501  DOI: 10.1103/PhysRevLett.101.180501
  * [CMW16] Tom Cooney, Milán Mosonyi and Mark M. Wilde  “Strong Converse Exponents for a Quantum Channel Discrimination Problem and Quantum-Feedback-Assisted Communication”  In _Communications in Mathematical Physics_ 344.3, 2016, pp. 797–829  DOI: 10.1007/s00220-016-2645-4
  * [Dat09] Nilanjana Datta  “Min- and Max- Relative Entropies and a New Entanglement Monotone”  In _IEEE Transactions on Information Theory_ 55.6, 2009, pp. 2816–2826  DOI: 10.1109/TIT.2009.2018325
  * [DFY09] Runyao Duan, Yuan Feng and Mingsheng Ying  “Perfect Distinguishability of Quantum Operations”  In _Physical Review Letters_ 103.21 American Physical Society, 2009, pp. 210501  DOI: 10.1103/PhysRevLett.103.210501
  * [Día+18] María García Díaz, Kun Fang, Xin Wang, Matteo Rosati, Michalis Skotiniotis, John Calsamiglia and Andreas Winter  “Using and Reusing Coherence to Realize Quantum Processes”  In _Quantum_ 2, 2018, pp. 100  DOI: 10.22331/q-2018-10-19-100
  * [Fan+20] Kun Fang, Omar Fawzi, Renato Renner and David Sutter  “A Chain Rule for the Quantum Relative Entropy”  In _Physical Review Letters_ 124.10, 2020, pp. 100501  DOI: 10.1103/PhysRevLett.124.100501
  * [FF21] Kun Fang and Hamza Fawzi  “Geometric Rényi Divergence and Its Applications in Quantum Channel Capacities”  In _Communications in Mathematical Physics_ 384.3, 2021, pp. 1615–1677  DOI: 10.1007/s00220-021-04064-4
  * [FF21a] Hamza Fawzi and Omar Fawzi  “Defining Quantum Divergences via Convex Optimization”  In _Quantum_ 5, 2021, pp. 387  DOI: 10.22331/q-2021-01-26-387
  * [FGW22] Kun Fang, Gilad Gour and Xin Wang  “Towards the Ultimate Limits of Quantum Channel Discrimination”  arXiv, 2022  DOI: 10.48550/arXiv.2110.14842
  * [GLN05] Alexei Gilchrist, Nathan K. Langford and Michael A. Nielsen  “Distance Measures to Compare Real and Ideal Quantum Processes”  In _Physical Review A_ 71.6, 2005, pp. 062310  DOI: 10.1103/PhysRevA.71.062310
  * [Har+10] Aram W. Harrow, Avinatan Hassidim, Debbie W. Leung and John Watrous  “Adaptive versus Nonadaptive Strategies for Quantum Channel Discrimination”  In _Physical Review A_ 81.3 American Physical Society, 2010, pp. 032339  DOI: 10.1103/PhysRevA.81.032339
  * [Hay07] Masahito Hayashi  “Error Exponent in Asymmetric Quantum Hypothesis Testing and Its Application to Classical-Quantum Channel Coding”  In _Physical Review A_ 76.6, 2007, pp. 062301  DOI: 10.1103/PhysRevA.76.062301
  * [Hay09] Masahito Hayashi  “Discrimination of Two Channels by Adaptive Methods and Its Application to Quantum System”  In _IEEE Transactions on Information Theory_ 55.8, 2009, pp. 3807–3820  DOI: 10.1109/TIT.2009.2023726
  * [Hel69] Carl W. Helstrom  “Quantum Detection and Estimation Theory”  In _Journal of Statistical Physics_ 1.2, 1969, pp. 231–252  DOI: 10.1007/BF01007479
  * [Hol72] A.. Holevo  “An Analogue of Statistical Decision Theory and Noncommutative Probability Theory”  In _Trudy Moskovskogo Matematičeskogo Obščestva_ 26, 1972, pp. 133–149  URL: https://mathscinet.ams.org/mathscinet-getitem?mr=0365809
  * [HP91] Fumio Hiai and Dénes Petz  “The Proper Formula for Relative Entropy and Its Asymptotics in Quantum Probability”  In _Communications in Mathematical Physics_ 143.1 Springer, 1991, pp. 99–114  DOI: 10.1007/BF02100287
  * [Kho79] A.. Kholevo  “On Asymptotically Optimal Hypothesis Testing in Quantum Statistics”  In _Theory of Probability & Its Applications_ 23.2, 1979, pp. 411–415  DOI: 10.1137/1123048
  * [KW20] Sumeet Khatri and Mark M. Wilde  “Principles of Quantum Communication Theory: A Modern Approach”, 2020  arXiv: http://arxiv.org/abs/2011.04672
  * [KW21] Vishal Katariya and Mark M. Wilde  “Evaluating the Advantage of Adaptive Strategies for Quantum Channel Distinguishability”  In _Physical Review A_ 104.5, 2021, pp. 052406  DOI: 10.1103/PhysRevA.104.052406
  * [Led+18] Felix Leditzky, Eneet Kaur, Nilanjana Datta and Mark M. Wilde  “Approaches for Approximate Additivity of the Holevo Information of Quantum Channels”  In _Physical Review A_ 97.1, 2018, pp. 012332  DOI: 10.1103/PhysRevA.97.012332
  * [Li14] Ke Li  “Second-Order Asymptotics for Quantum Hypothesis Testing”  In _The Annals of Statistics_ 42.1, 2014  DOI: 10.1214/13-AOS1185
  * [Lin75] Göran Lindblad  “Completely Positive Maps and Entropy Inequalities”  In _Communications in Mathematical Physics_ 40.2, 1975, pp. 147–151  DOI: 10.1007/BF01609396
  * [Mat13] Keiji Matsumoto  “A New Quantum Version of F-Divergence”, 2013  arXiv: https://arxiv.org/abs/1311.4722v4
  * [Nag06] Hiroshi Nagaoka  “The Converse Part of The Theorem for Quantum Hoeffding Bound”, 2006  arXiv: http://arxiv.org/abs/quant-ph/0611289
  * [NS09] Michael Nussbaum and Arleta Szkoła  “The Chernoff Lower Bound for Symmetric Quantum Hypothesis Testing”  In _The Annals of Statistics_ 37.2, 2009  DOI: 10.1214/08-AOS593
  * [ON00] T. Ogawa and H. Nagaoka  “Strong Converse and Stein’s Lemma in Quantum Hypothesis Testing”  In _IEEE Transactions on Information Theory_ 46.7, 2000, pp. 2428–2433  DOI: 10.1109/18.887855
  * [Pet86] Dénes Petz  “Quasi-Entropies for Finite Quantum Systems”  In _Reports on Mathematical Physics_ 23.1, 1986, pp. 57–65  DOI: 10.1016/0034-4877(86)90067-4
  * [Ras02] A.. Rastegin  “Relative Error of State-Dependent Cloning”  In _Physical Review A_ 66.4 American Physical Society, 2002, pp. 042304  DOI: 10.1103/PhysRevA.66.042304
  * [Ras03] A.. Rastegin  “A Lower Bound on the Relative Error of Mixed-State Cloning and Related Operations”  In _Journal of Optics B: Quantum and Semiclassical Optics_ 5.6 IOP Publishing, 2003, pp. S647–S650  DOI: 10.1088/1464-4266/5/6/017
  * [Ras06] A.. Rastegin  “Sine Distance for Quantum States”  arXiv, 2006  DOI: 10.48550/arXiv.quant-ph/0602112
  * [SHW21] Farzin Salek, Masahito Hayashi and Andreas Winter  “When Are Adaptive Strategies in Asymptotic Quantum Channel Discrimination Useful?”, 2021  arXiv: http://arxiv.org/abs/2011.06569
  * [TCR09] Marco Tomamichel, Roger Colbeck and Renato Renner  “A Fully Quantum Asymptotic Equipartition Property”  In _IEEE Transactions on Information Theory_ 55.12, 2009, pp. 5840–5847  DOI: 10.1109/TIT.2009.2032797
  * [TH13] Marco Tomamichel and Masahito Hayashi  “A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks”  In _IEEE Transactions on Information Theory_ 59.11, 2013, pp. 7693–7710  DOI: 10.1109/TIT.2013.2276628
  * [Tom12] Marco Tomamichel  “A Framework for Non-Asymptotic Quantum Information Theory”, 2012  DOI: 10.3929/ethz-a-7356080
  * [Uhl76] A. Uhlmann  “The “Transition Probability” in the State Space of a ∗-Algebra”  In _Reports on Mathematical Physics_ 9.2, 1976, pp. 273–279  DOI: 10.1016/0034-4877(76)90060-4
  * [Ume62] Hisaharu Umegaki  “Conditional Expectation in an Operator Algebra. IV. Entropy and Information”  In _Kodai Mathematical Seminar Reports_ 14.2 Tokyo Institute of Technology, Department of Mathematics, 1962, pp. 59–85  DOI: 10.2996/kmj/1138844604
  * [Wil+20] Mark M. Wilde, Mario Berta, Christoph Hirche and Eneet Kaur  “Amortized Channel Divergence for Asymptotic Quantum Channel Discrimination”  In _Letters in Mathematical Physics_ 110.8, 2020, pp. 2277–2336  DOI: 10.1007/s11005-020-01297-7
  * [WR12] Ligong Wang and Renato Renner  “One-Shot Classical-Quantum Capacity and Hypothesis Testing”  In _Physical Review Letters_ 108.20, 2012, pp. 200501  DOI: 10.1103/PhysRevLett.108.200501
  * [WW19] Xin Wang and Mark M. Wilde  “Resource Theory of Asymmetric Distinguishability”  In _Physical Review Research_ 1.3, 2019, pp. 033170  DOI: 10.1103/PhysRevResearch.1.033170
  * [WW19a] Xin Wang and Mark M. Wilde  “Resource Theory of Asymmetric Distinguishability for Quantum Channels”  In _Physical Review Research_ 1.3, 2019, pp. 033169  DOI: 10.1103/PhysRevResearch.1.033169

fang_geometric_2019fang_geometric_2021
helstrom_quantum_1976helstrom_quantum_1969

##  Appendix A Proofs of AEP Bounds

###  A.1 Proof of 10 (Petz–Rényi Continuity Bound in $\alpha$)

###### Proof of 10.

Note first that for (69), where we did not explicitly require
$D(\rho\|\sigma)<\infty$, we can restrict to that case, as otherwise also
$D_{1+\delta}(\rho\|\sigma)=\infty$ and the statement is trivial. Hence, we
can assume $\sigma$ to be invertible (otherwise restrict to the subspace where
$\sigma$ is supported). Define the operator $X=\rho\otimes(\sigma^{-1})^{T}$,
and the canonical purification of $\rho$ on $\mathcal{H}\otimes\mathcal{H}$:

$\ket{\phi}=\sum_{i}\sqrt{\rho}\ket{i}\otimes\ket{i}$ (148)

where $\ket{i}$ is an orthonormal basis of $\mathcal{H}$. Then, for all
$\delta\in[-1,1]$:

$D_{1+\delta}(\rho\|\sigma)=\frac{1}{\delta}\log(\braket{\phi}{X^{\delta}}{\phi})$
(149)

and

$D(\rho\|\sigma)=\braket{\phi}{\log(X)}{\phi}\,.$ (150)

For all $t>0$ and $\delta\in\mathbb{R}$, the first term in the expansion of
$t^{\delta}$ around $\delta=0$ is $\delta\ln(t)$. Hence let us write
$t^{\delta}=1+\delta\ln(t)+r_{\delta}(t)$ where $r_{\delta}(t)\coloneqq
t^{\delta}-\delta\ln(t)-1$. Since $e^{x}\geq 1+x$ for all $x\in\mathbb{R}$ we
see that

$\displaystyle r_{\delta}(t)$ $\displaystyle=t^{\delta}-\delta\ln(t)-1\leq
t^{\delta}+e^{-\delta\ln(t)}-2$ (151)
$\displaystyle=e^{\delta\ln(t)}+e^{-\delta\ln(t)}-2$ (152)
$\displaystyle=2(\cosh(\delta\ln(t))-1)\eqqcolon s_{\delta}(t)$ (153)

It is easy to see that $s_{-\delta}(t)=s_{\delta}(t)$ and
$s_{\delta}(t)=s_{\gamma\delta}(t^{1/\gamma})$ for all $\gamma\in\mathbb{R}$.
Also, it is easy to verify that $s_{\delta}(t)$ is monotonically increasing in
$t$ for $t\geq 1$ and concave in $t$ if $\delta\leq\frac{1}{2}$ and $t\geq 3$.
For all $t\geq 0$, either $t$ or $1/t$ will be larger than or equal to one,
and so we can always use the monotonicity to write

$s_{\delta}(t)=s_{\delta}\quantity(\frac{1}{t})\leq
s_{\delta}\quantity(t+\frac{1}{t})\,.$ (154)

Using this, we get for all $t\geq 0$ and $\gamma\in(0,1]$

$s_{\delta}(t)=s_{\delta/\gamma}(t^{\gamma})\leq
s_{\delta/\gamma}\quantity(t^{\gamma}+t^{-\gamma})\leq
s_{\delta/\gamma}\quantity(t^{\gamma}+t^{-\gamma}+1)\,.$ (155)

It is easy to see that real function $x+1/x$ has a global minimum for $x>0$ at
$x=1$ and hence the argument at the right hand side is guaranteed to be larger
than $3$. Hence we can use the concavity of $s_{\delta/\gamma}$ to write

$\braket{\phi}{s_{\delta}(X)}{\phi}\leq\braket{\phi}{s_{\delta/\gamma}(X^{\gamma}+X^{-\gamma}+\IdentityMatrix)}{\phi}\leq
s_{\delta/\gamma}(\braket{\phi}{X^{\gamma}+X^{-\gamma}+\IdentityMatrix}{\phi})=s_{\delta/\gamma}(2^{\gamma
c_{\gamma}(\rho\|\sigma)})$ (156)

where the inequality step is a well-known property of concave functions
(Jensen’s inequality). Finally, we use Taylor’s theorem with the Lagrange form
of the remainder to bound

$\displaystyle s_{\delta}(t)$
$\displaystyle=s_{0}(t)+\derivative{\delta}s_{\delta}(t)\big{|}_{\delta=0}\delta+\frac{1}{2}\derivative[2]{\delta}s_{\delta}(t)\big{|}_{\delta=\xi}\delta^{2}$
(157)
$\displaystyle=\delta^{2}(\ln(t))^{2}\cosh(\xi\ln(t))\leq\delta^{2}(\ln(t))^{2}\cosh(\delta\ln(t)),$
(158)

for all $t\geq 0$ and some $\xi\in(0,\delta)$, where we have used that
$s_{0}(t)=\derivative{\delta}s_{\delta}(t)|_{\delta=0}=0$. Hence,

$\braket{\phi}{s_{\delta}(X)}{\phi}\leq s_{\delta/\gamma}(2^{\gamma
c_{\gamma}(\rho\|\sigma)})\leq(\delta\ln(2)c_{\gamma}(\rho\|\sigma))^{2}\cosh(\delta\ln(2)c_{\gamma}(\rho\|\sigma))\,.$
(159)

To finally prove our claims, let us start with the case where $\delta>0$.
Then,

$\displaystyle D_{1+\delta}(\rho\|\sigma)$
$\displaystyle=\frac{1}{\delta}\log(\braket{\phi}{X^{\delta}}{\phi})=\frac{1}{\delta}\log(1+\delta\ln(2)\braket{\phi}{\log(X)}{\phi}+\braket{\phi}{r_{\delta}(X)}{\phi})$
(160)
$\displaystyle=\frac{1}{\delta}\log(1+\delta\ln(2)D(\rho\|\sigma)+\braket{\phi}{r_{\delta}(X)}{\phi})$
(161)
$\displaystyle\leq\frac{1}{\delta}\log(1+\delta\ln(2)D(\rho\|\sigma)+\braket{\phi}{s_{\delta}(X)}{\phi})$
(162)
$\displaystyle=\frac{1}{\delta}\log(1+\delta\ln(2)D(\rho\|\sigma))+\frac{1}{\delta}\log(1+\frac{\braket{\phi}{s_{\delta}(X)}{\phi}}{1+\delta\ln(2)D(\rho\|\sigma)})$
(163) $\displaystyle\leq
D(\rho\|\sigma)+\frac{1}{\delta}\log(1+\braket{\phi}{s_{\delta}(X)}{\phi})$
(164) $\displaystyle\leq
D(\rho\|\sigma)+\frac{1}{\delta}\log(1+(\delta\ln(2)c_{\gamma}(\rho\|\sigma))^{2}\cosh(\delta\ln(2)c_{\gamma}(\rho\|\sigma)))$
(165) $\displaystyle\leq
D(\rho\|\sigma)+\delta\ln(2)(c_{\gamma}(\rho\|\sigma))^{2}$ (166)

where the third to last inequality uses $\log(1+x)\leq\frac{x}{\ln(2)}$ and
(for the second term) the fact that $\delta$ is positive. The final inequality
follows from the fact that $k^{2}-\ln(1+k^{2}\cosh(k))$ is monotonically
increasing in $k$ and hence positive.

If $\delta<0$, the issue arises that $1+\delta\ln(2)D(\rho\|\sigma)$ no longer
has to be greater than $1$ (it might in fact be negative) and so we have to
apply a slightly different argument. Starting analogously, we get

$\displaystyle D_{1+\delta}(\rho\|\sigma)$
$\displaystyle=\frac{1}{\delta}\log(1+\delta\ln(2)D(\rho\|\sigma)+\braket{\phi}{r_{\delta}(X)}{\phi})$
(167)
$\displaystyle\geq\frac{1}{\delta}\log(1+\delta\ln(2)D(\rho\|\sigma)+\braket{\phi}{s_{\delta}(X)}{\phi})$
(168) $\displaystyle\geq
D(\rho\|\sigma)+\frac{1}{\delta\ln(2)}\braket{\phi}{s_{\delta}(X)}{\phi}$
(169) $\displaystyle\geq
D(\rho\|\sigma)+\delta\ln(2)(c_{\gamma}(\rho\|\sigma))^{2}\cosh(\delta\ln(2)c_{\gamma}(\rho\|\sigma))$
(170)

where we used $\log(1+x)\leq\frac{x}{\ln(2)}$ in the third inequality.
Finally, if we assume that $\left\lvert\delta\right\rvert\leq\frac{\log
3}{2c_{\gamma}(\rho\|\sigma)}$, then $\ln(2)\cosh(\ln(3)/2)<1$ and so we get

$D_{1+\delta}(\rho\|\sigma)\geq
D(\rho\|\sigma)+\delta(c_{\gamma}(\rho\|\sigma))^{2}\,.$ (171)

Note that since $c_{\gamma}(\rho\|\sigma)\geq\frac{\log(3)}{\gamma}$ the
condition $\left\lvert\delta\right\rvert\leq\gamma/2$ is automatically
fulfilled. ∎

###  A.2 Proof of 15 (AEP Convergence Bound)

###### Proof of 15.

We start with the proof of (80). We use [WW19, Prop. 4], which states that for
all $\alpha\in[0,1)$ and any $\varepsilon\in[0,1)$

$D^{\varepsilon}_{\max}(\rho\|\sigma)\geq
D_{\alpha}(\rho\|\sigma)+\frac{2}{\alpha-1}\log(1\over 1-\varepsilon)\,.$
(172)

Note that the statement in [WW19] is given for smoothing in trace-distance,
but since the trace distance is always less than the sine distance, for fixed
$\varepsilon$ the trace-distance-smoothed max-divergence is smoothed over a
larger ball, and hence also always smaller, which is why the statement for the
purified-distance-smoothed max-divergence is implied. We apply this to
$\rho^{\otimes n}$ and $\sigma^{\otimes n}$ and use the additivity of the
Petz-Rényi relative entropy to get:

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\geq
D_{\alpha}(\rho\|\sigma)+\frac{1}{n}\frac{2}{\alpha-1}\log(1\over
1-\varepsilon)$ (173)

Now, we combine this with (72) of 10 to get

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\geq
D(\rho\|\sigma)+\ln(2)\cosh(\log(3)\over
2)c_{\gamma}(\rho\|\sigma)^{2}(\alpha-1)+\frac{1}{n}\frac{2}{\alpha-1}\log(1\over
1-\varepsilon)$ (174)

together with the condition $0\leq 1-\alpha\leq\frac{\log
3}{2c_{\gamma}(\rho\|\sigma)}$. We are now free to choose $\alpha$ to optimize
the right-hand side. It is easy to see that the right-hand side will be
maximal if both terms are equal, which is achieved for

$1-\alpha=\sqrt{\frac{2\log(1\over 1-\varepsilon)}{n\ln(2)\cosh(\log(3)\over
2)c_{\gamma}(\rho\|\sigma)^{2}}}=\frac{4}{K_{1}c_{\gamma}(\rho\|\sigma)}\sqrt{\frac{\log(1\over
1-\varepsilon)}{n}}$ (175)

Hence we get

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\geq
D(\rho\|\sigma)-\frac{K_{1}}{\sqrt{n}}c_{\gamma}(\rho\|\sigma)\sqrt{\log(1\over
1-\varepsilon)}$ (176)

together with the condition

$n\geq\log(1\over 1-\varepsilon)\quantity(4\over K_{1}\log(3))^{2}\,.$ (177)

In order to get an expression without a condition on $n$ we have to choose a
different $\alpha$. Choosing

$1-\alpha=\frac{\log(3)}{2c_{\gamma}(\rho\|\sigma)\sqrt{n}}$ (178)

satisfies the condition on $1-\alpha$ for all $n$ and gives:

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\geq
D(\rho\|\sigma)-\frac{c_{\gamma}(\rho\|\sigma)}{\sqrt{n}}\quantity[\frac{\ln(2)\log(3)}{2}\cosh(\log(3)\over
2)+\frac{4}{\log(3)}\log(1\over 1-\varepsilon)]\,.$ (179)

The simplification (76) follows from $\log(3)>1$ and

$\frac{\ln(2)\log(3)}{2}\cosh(\log(3)\over 2)<1\,.$ (180)

The second equation (82) is proved very analogously. We start again with a
relation to a Rényi entropy for $\alpha>1$ [KW20, Prop. 4.61]:

$D^{\varepsilon}_{\max}(\rho\|\sigma)\leq
D_{\alpha}(\rho\|\sigma)+\frac{2}{\alpha-1}\log(1\over\varepsilon)+\log(1\over
1-\varepsilon^{2})\,.$ (181)

Note that [KW20, Prop. 4.61] uses the sandwiched Rényi divergence, which
however is always less than the Petz, and hence the above statement is
implied. We again apply this to $n$ tensor powers of $\rho$ and $\sigma$ and
combine it with (69) from 10 to obtain:

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\leq
D(\rho\|\sigma)+\ln(2)c_{\gamma}(\rho\|\sigma)^{2}(\alpha-1)+\frac{2}{n(\alpha-1)}\log(1\over\varepsilon)+\frac{1}{n}\log(1\over
1-\varepsilon^{2})$ (182)

together with the condition

$\alpha-1\leq\frac{\gamma}{2}\,.$ (183)

The right hand side is minimized again for

$\alpha-1=\sqrt{\frac{2\ln(2)\log(1\over\varepsilon)}{nc_{\gamma}(\rho\|\sigma)^{2}}}=\frac{4}{K_{2}c_{\gamma}(\rho\|\sigma)}\sqrt{\frac{\log(1\over\varepsilon)}{n}}$
(184)

which gives

$\frac{1}{n}D^{\varepsilon}_{\max}(\rho^{\otimes n}\|\sigma^{\otimes n})\leq
D(\rho\|\sigma)+\frac{K_{2}}{\sqrt{n}}c_{\gamma}(\rho\|\sigma)\sqrt{\log(1\over\varepsilon)}+\frac{1}{n}\log(1\over
1-\varepsilon^{2})$ (185)

as well as the condition

$n\geq\log(1\over\varepsilon)\quantity(\frac{8}{\gamma
c_{\gamma}(\rho\|\sigma)K_{2}})^{2}\,.$ (186)

Alternatively, choosing

$\alpha-1=\frac{\log(3)}{2c_{\gamma}(\rho\|\sigma)\sqrt{n}}$ (187)

will again give (75), and the simplified form (77) follows by the same
argument that $\log(3)>1$ and

$\frac{\ln(2)\log(3)}{2}<1\,.$ (188)

This concludes the proof. ∎