# Quantum soft-covering lemma
with applications to rate-distortion coding,
resolvability and identification via quantum channels111Date: 21 June 2023.

Touheed Anwar Atif1, S. Sandeep Pradhan1, and Andreas Winter23
1Department of Electrical Engineering and Computer Science,
University of Michigan, Ann Arbor, MI 48109, USA.
<EMAIL_ADDRESS>
2ICREA & Universitat Autònoma de Barcelona, 08193 Bellaterra (Barcelona),
Spain.
3Institute for Advanced Study, Technische Universität München,
Lichtenbergstraße 2a, 85748 Garching, Germany.
<EMAIL_ADDRESS>
###### Abstract

We propose a quantum soft-covering problem for a given general quantum channel
and one of its output states, which consists in finding the minimum rank of an
input state needed to approximate the given channel output. We then prove a
one-shot quantum covering lemma in terms of smooth min-entropies by leveraging
decoupling techniques from quantum Shannon theory. This covering result is
shown to be equivalent to a coding theorem for rate distortion under a
posterior (reverse) channel distortion criterion [Atif, Sohail, Pradhan,
arXiv:2302.00625]. Both one-shot results directly yield corollaries about the
i.i.d. asymptotics, in terms of the coherent information of the channel.

The power of our quantum covering lemma is demonstrated by two additional
applications: first, we formulate a quantum channel resolvability problem, and
provide one-shot as well as asymptotic upper and lower bounds. Secondly, we
provide new upper bounds on the unrestricted and simultaneous identification
capacities of quantum channels, in particular separating for the first time
the simultaneous identification capacity from the unrestricted one, proving a
long-standing conjecture of the last author.

##  1 Introduction

Covering and packing are two fundamental principles in information theory that
are essential to the design and analysis of coding systems achieving the
fundamental limits. Naturally, these concepts are also important in the
framework of quantum information theory and have been developed in analogy
with the classical case. Indeed, packing problems have been extensively
studied in the quantum information literature, mostly related to the design of
classical, quantum or hybrid error-correcting codes [1, 2, 3, 4]. Problems of
a covering nature have shown up naturally in other contexts, most prominently
in wiretap and similar cryptographic settings [5, 6, 7], but also in channel
and correlation synthesis and, crucially, converse theorems to identification
coding [8, 9, 10, 11, 12, 13].

The origin of this line of research can be traced back to the work of Wyner in
not one but two articles [14, 15], the first introducing the idea of
randomizing over a channel code to confound a wiretapper on a communication
channel, the second defining and solving the task of distributed agents
generating classical i.i.d. samples of local random variables $X$ and $Y$
distributed according to a joint distribution $P_{XY}$ from shared randomness;
the optimal rate of initial shared randomness is now called Wyner’s common
information. In the classical setup, this has been further developed toward
the problem of distributed channel synthesis in the classical reverse Shannon
theorem [16], and the subsequent unifying work of Cuff _et al._ [17, 18].

In the quantum setting, Ahlswede and Winter formulated a classical-quantum
soft-covering lemma, and showed that classical randomness at a rate of the
Holevo information (with respect to a classical-quantum ensemble) can generate
the output of a classical quantum channel [8]. Evolving from earlier works in
[19, 20], Winter in [10] successfully performed an information theoretic study
of quantum measurements and formulated the fundamental task of compressing or
“faithfully simulating” quantum measurements. An instrumental tool in
obtaining the result was a the classical-quantum soft-covering lemma. In both
classical and quantum settings, the problem of soft-covering has also found
applications in the quantum reverse Shannon theorem [11], generalising [10].
Recent contributions to the study of classical-quantum soft-covering also
include [21, 13, 22, 23]. [22, 23] addressed soft-covering lemma for pairwise
independent ensembles.

In the present article, we formulate and address the problem of quantum soft-
covering in its natural generality. The task can be described in simple terms
as follows: given a quantum channel $\mathcal{N}$ and one of its output states
$\mathcal{N}(\rho)$, what is the smallest rank of a quantum state $\sigma$
that reproduces or approximates the given output state,
$\mathcal{N}(\sigma)\approx\mathcal{N}(\rho)$? The approximation here is
quantified using the trace distance.

To this end, we first consider the one-shot version of the problem, where we
characterize the minimum rank in terms of smoothed quantum entropic quantities
[24]. Based on the one-shot result, we then study the quantum soft-covering
problem in an asymptotic setting, where the objective is to approximate the
output produced by $n$ independent uses of the given channel, acting on a
memoryless source. We obtain a single-letter characterization of the
asymptotically optimal rate of the quantum soft-covering problem in terms of
the coherent information, and then also study the finite block length behavior
to second order. More precisely, we obtain an achievability bound for the
specific portion of the performance limit that scales proportionally as
$1/\sqrt{n}$. Such a study was first introduced by Strassen in 1962 for the
problem of classical communication [25], and has been the topic of interest
for many works including [26, 27, 28, 29, 30, 31, 32].

In order to showcase the power of our quantum soft-covering lemma, we turn our
attention to three fundamental problems in quantum information theory. The
first is the lossy quantum source coding problem under a posterior (reverse)
channel distortion criterion formulated in [33], where a single-letter
characterization of the performance limit in terms of the coherent information
was given. Using the quantum covering results, we provide a one-shot
characterization of this problem. Moreover, using the one-shot results, we
study the asymptotic regime of the lossy source coding problem and recover the
asymptotic performance limit characterized in [33].

As the next application, we consider the quantum analogue of the channel
resolvability problem. We formulate a quantum channel resolvability problem
and show that the quantum channel resolvability rate for an arbitrary channel
is upper bounded by its strong converse quantum transmission capacity. Using
the one-shot converse to the soft-covering problem, we provide a lower bound
to the quantum resolvability rate in terms of smooth minimum entropy. This
bound also forms a new lower bound in the classical setting, where a complete
characterization of the problem is still an open question [34]. We conjecture
that, in the asymptotic setting, this lower bound is equal to the quantum
transmission capacity of the channel.

As the final application, we consider the task of classical identification via
quantum channels, and we are able to answer some of the open questions
relating to this task, utilizing the quantum soft-covering tool. In detail, we
obtain an upper bound on the so-called _simultaneous_ identification capacity
of a general quantum channel $\mathcal{N}$, which also forms a strong converse
upper bound. This bound resolves an open question concerning the separation of
the simultaneous and the unrestricted identification capacities. Finally, for
a general quantum channel, we provide another upper bound on the unrestricted
identification capacity in terms of the strong converse quantum transmission
capacity of the channel.

The rest of the paper is organized as follows. We provide some necessary
definitions and useful lemmas in Section 2. In Section 3, we formulate the
quantum soft-covering problem and provide the main results pertaining to the
one-shot (Theorem 3.3), asymptotic (Theorem 3.5) and second order
characterizations (Theorem 3.6). In Sections 4, 5, and 6, we move on to the
three information theoretic applications of the covering result: the lossy
source coding problem (Theorems 4.7 and 4.8), the channel resolvability
problem (Theorem 5.5) and identification via quantum channels (Theorems 6.3
and 6.5). The proofs for the source coding theorems are provided in the
Section 7. In Section 8 we conclude.

##  2 Preliminaries and notations

We supplement the notations in [35] with the following. Let ${\openone}_{A}$
denote the identity operator acting on a Hilbert space $A$. The set of density
operators on $A$ is denoted $\mathcal{D}(A)$, linear operators by
$\mathcal{L}(A)$, and positive semi-definite operators by $\mathcal{P}(A)$.
The set of sub-normalized states is denoted by
$\mathcal{D}_{\leq}(A)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{\rho\in\mathcal{P}(A)\mathrel{\mathop{\mathchar
58\relax}}\Tr\rho\leq 1\\}.$ We denote by ${A_{R}}$ the Hilbert space
associated with the reference space of $A$, isomorphic to $A$: ${A_{R}}\simeq
A$, in particular $\dim{A_{R}}=\dim A$. The dimension of a Hilbert space $A$
is denoted $|A|$ (recalling the cardinality of a set, and coinciding with the
cardinality of any basis of $A$). For a linear operator $\omega$, let
$|\omega|=|\operatorname{supp}\omega|$ denote its rank, namely the dimension
of its support. The fidelity between two states,
$\rho,\sigma\in\mathcal{D}(A)$, is defined as

$F(\rho,\sigma)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\|\sqrt{\rho}\sqrt{\sigma}\|_{1}^{2}=\max_{\phi,\psi}|\langle\phi|\psi\rangle|^{2},$

where $\phi$ and $\psi$ range over purifications of $\rho$ and $\sigma$,
respectively. The fidelity between two sub-normalized states
$\rho,\sigma\in\mathcal{D}_{\leq}(A)$ is defined as

$F_{\star}(\rho,\sigma)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\left[\Tr{|\sqrt{\rho}\sqrt{\sigma}|}+\sqrt{(1-\Tr\rho)(1-\Tr\sigma)}\right]^{2}.$

We define the purified distance as
$P(\rho,\sigma)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sqrt{1-F_{\star}(\rho,\sigma)}$.
Following the notation of [24], for a given sub-normalized state
$\rho\in\mathcal{D}_{\leq}(A)$, we use $\mathscr{B}^{\epsilon}(A;\rho)$ to
denote the $\epsilon$-ball of sub-normalized states around $\rho$ defined as

$\mathscr{B}^{\epsilon}(A;\rho)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{\sigma\in\mathcal{D}_{\leq}(A)\mathrel{\mathop{\mathchar
58\relax}}P(\sigma,\rho)\leq\epsilon\\},$

and when clear from the context, will omit the system and use
$\mathscr{B}(\rho).$ For a density operator $\rho\in\mathcal{D}(A)$, the von
Neumann entropy is defined as
$S(\rho)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}-\Tr{\rho\log\rho}$.
For a bipartite state $\rho^{AB}\in\mathcal{D}(A\otimes B)$, the conditional
entropy is defined as
$S(A|B)_{\rho}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}S(\rho^{AB})-S(\rho^{B})$,
where
$\rho^{B}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\Tr_{A}{\rho^{AB}}$.
For a given CPTP map $\mathcal{N}\mathrel{\mathop{\mathchar
58\relax}}A\rightarrow B$, and a state $\rho\in\mathcal{D}(B)$, we define the
set
$\mathcal{S}(\rho,\mathcal{N})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{\sigma\in\mathcal{D}(A)\mathrel{\mathop{\mathchar
58\relax}}\mathcal{N}(\sigma)=\rho\\}$ and its smoothed variant
$\mathcal{S}_{\epsilon}(\rho,\mathcal{N})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{\sigma\in\mathcal{D}(A)\mathrel{\mathop{\mathchar
58\relax}}\|\rho-\mathcal{N}(\sigma)\|_{1}\leq\epsilon\\}$. For any real $x$,
we define
$x^{+}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\max(x,0)$,
which for a more complex argument is written as $[f(x)]^{+}$.

### 2.1 Useful definitions

We recall the following definitions of the well-known information quantities.

######  Definition 2.1 (Quantum information variance).

For any two density operators $\rho,\sigma\in\mathcal{D}(A)$, such that
$\mbox{supp}\rho\subset\operatorname{supp}\sigma$, the quantum information
variance is defined as

$V(\rho\|\sigma)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\Tr[\rho(\log\rho-\log\sigma)^{2}]-D^{2}(\rho\|\sigma).$

######  Definition 2.2 (Coherent information).

For a CPTP map $\mathcal{N}\mathrel{\mathop{\mathchar 58\relax}}A\rightarrow
B$, and an input density operator $\rho\in\mathcal{D}(A)$, the coherent
information of $\mathcal{N}$ with respect to $\rho$ is defined as

$I_{c}(\rho,\mathcal{N})=I_{c}(A_{R}\rangle
B)_{\omega}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}-S(A_{R}|B)_{\omega},$

where
$\omega^{BA_{R}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mathcal{N}\otimes{\operatorname{id}})\phi^{AA_{R}}_{\rho}$,
and $\phi_{\rho}^{AA_{R}}$ is an arbitrary purification of $\rho_{A}$.

######  Definition 2.3 (Min- and max-entropy [24]).

For $\rho^{AB}\in\mathcal{D}_{\leq}(A\otimes B)$, the min- and max-entropy of
A conditioned on B of the (sub-normalized) state $\rho^{AB}$ is defined as

$\displaystyle H_{\min}(A|B)_{\rho}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sup_{\sigma^{B}\in\mathcal{D}_{\leq}(B)}\sup\\{\lambda\in\mathbb{R}\mathrel{\mathop{\mathchar
58\relax}}\rho^{AB}\leq 2^{-\lambda}{\openone}_{A}\otimes\sigma^{B}\\},$
$\displaystyle H_{\max}(A|B)_{\rho}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\max_{\sigma^{B}\in\mathcal{D}_{\leq}(B)}\log
F(\rho^{AB},{\openone}_{A}\otimes\sigma^{B}).$

######  Definition 2.4 (Smoothed entropies [24]).

For $\rho^{AB}\in\mathcal{D}_{\leq}(A\otimes B)$, and $\epsilon\in(0,1)$, the
$\epsilon$-smooth min and max-entropy of A conditioned on B of the (sub-
normalized) state $\rho^{AB}$ is defined as

$\displaystyle
H_{\min}^{\epsilon}(A|B)_{\rho}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\max_{\sigma\in\mathscr{B}^{\epsilon}(\rho)}H_{\min}(A|B)_{\sigma}\quad\text{and}\quad
H_{\max}^{\epsilon}(A|B)_{\rho}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\min_{\sigma\in\mathscr{B}^{\epsilon}(\rho)}H_{\max}(A|B)_{\sigma}.$

######  Definition 2.5 (Smoothed relative max-entropy [29]).

For a given $\rho\in\mathcal{D}(A)$ and $\omega\in\mathcal{P}(A)$, and
$\epsilon\in(0,1)$, we define the smoothed relative max-entropy as

$\displaystyle
D_{\max}^{\epsilon}(\rho\|\omega)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\min_{\sigma\in\mathscr{B}^{\epsilon}(\rho)}\inf\\{\lambda\mathrel{\mathop{\mathchar
58\relax}}\sigma\leq 2^{\lambda}\omega\\}.$

### 2.2 Useful lemmas

We need the following results that relate fidelity and trace norm.

######  Lemma 2.6 ([36], Theorem 9.3.1 [35]).

Given two states $\rho,\sigma\in\mathcal{D}(A)$, we have

$1-\sqrt{F(\rho,\sigma)}\leq\frac{1}{2}\norm{\rho-\sigma}_{1}\leq\sqrt{1-F(\rho,\sigma)}.$

######  Lemma 2.7 (Lemma 2 [33], Lemma 14 [10]).

For $\rho,\sigma\in\mathcal{D}(A)$, the following inequality holds:

$F(\psi_{\rho},\psi_{\sigma})\geq\left(1-\frac{1}{2}\norm{{\rho}-{\sigma}}_{1}\right)^{2},$
(1)

where $\ket{\psi_{\rho}}$ and $\ket{\psi_{\sigma}}$ are the canonical
purifications of $\rho$ and $\sigma$, respectively.

Next we state the result required on quantum relative entropy.

######  Lemma 2.8 (Eq. (35)[29]).

For any $n\geq 1$, and $\epsilon\in(0,1)$, we have

$\displaystyle D_{\max}^{\epsilon}(\rho^{\otimes n}\|\sigma^{\otimes
n})=nD(\rho\|\sigma)-\sqrt{nV(\rho\|\sigma)}\Phi^{-1}(\epsilon^{2})+O(\log
n),$ (2)

where $\Phi(\delta)$ denotes the cumulative distribution function of the
standard normal distribution.

We need a couple of tools from the min-entropy calculus [24].

######  Lemma 2.9 (Lemma 5 [37], Proposition 5.5 [38]).

For any bipartite state $\rho^{AB}\in\mathcal{D}(A\otimes B)$ and
$\epsilon+\delta<1$,

$H_{\min}^{\epsilon}(A|B)_{\rho}\leq
H_{\max}^{\delta}(A|B)_{\rho}+\log\frac{1}{1-(\epsilon+\delta)^{2}}.$

######  Lemma 2.10 (Dupuis 2013, cf. [39, Lemma 9]).

For any bipartite state $\rho^{AB}\in\mathcal{D}(A\otimes B)$ and
$0<\epsilon<1$,

$H_{\min}^{\epsilon}(A|B)_{\rho}\geq H_{\max}^{\delta}(A|B)_{\rho},$

where $\delta=\sqrt{1-\epsilon^{4}}$.

##  3 Quantum soft covering

We begin by formulating the quantum covering problem as follows.

######  Definition 3.1 (Quantum covering).

A quantum covering setup is characterized by a pair $(\rho^{B},\mathcal{N})$,
where $\rho^{B}\in\mathcal{D}(B)$ is a density operator and $\mathcal{N}$ is a
CPTP map from $A$ to $B$.

A code for quantum covering is defined as follows.

######  Definition 3.2 (Quantum covering code).

For a given pair $(\rho^{B},\mathcal{N})$, an $(n,\Theta,\epsilon)$ code for
quantum covering is a density operator $\hat{\sigma}^{A^{n}}$ on $A^{\otimes
n}$ such that $|\hat{\sigma}^{A^{n}}|=\Theta$, and

$\displaystyle\|\rho^{B^{\otimes n}}-\mathcal{N}^{\otimes
n}(\hat{\sigma}^{A^{n}})\|_{1}\leq\epsilon.$ (3)

As our first main result, we characterize the smallest rank $\Theta$ for a
one-shot $(1,\Theta,\epsilon)$ quantum covering code in terms of smoothed min-
entropy.

######  Theorem 3.3 (One-shot quantum covering).

Given a pair $(\rho^{B},\mathcal{N})$, and a density operator
$\sigma^{A}\in\mathcal{S}(\rho^{B},\mathcal{N})$, for all
$\delta,\eta\in(0,1)$, there exists $(1,\Theta,\epsilon)$ code for quantum
covering such that

$\displaystyle\log\Theta\leq\left[{-H_{\min}^{\delta}(A_{R}|B)_{\omega}-2\log{\eta}}\right]^{+},$
(4)

and $\epsilon\leq 8(\delta+\eta)$, where
$\omega^{BA_{R}}=(\mathcal{N}\otimes{\operatorname{id}})\Phi^{AA_{R}}_{\sigma}$,
$\Phi^{AA_{R}}_{\sigma}$ is a purification of $\sigma^{A}$. Moreover, for all
$\epsilon\in(0,1)$, every $(1,\Theta,\epsilon)$ code satisfies

$\log\Theta\geq\inf_{\sigma^{A}\in\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N})}\left[-H_{\min}(A_{R}|B)_{\omega}\right]^{+}.$
(5)

###### Proof.

We begin with the showing the direct part. We apply the general decoupling
theorem [40, Thm. 3.1] to $\omega^{BA_{R}}$, a family of random unitaries $U$
on $A$ forming at least a $2$-design, and the fixed map
$\mathcal{M}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{H}_{A_{R}}\rightarrow\mathcal{H}_{X}$ defined by

$\mathcal{M}(\alpha)=\sum_{x=1}^{\ell}(\tr\alpha P_{x})|x\rangle\\!\langle
x|,$

where the $\ket{x}$ form an orthonormal basis of $X$ and the $P_{x}$ are
mutually orthogonal subspace projectors of rank $r$ each forming a POVM,
$\sum_{x}P_{x}={\openone}_{A_{R}}$. For this to exist, we need
$r\ell=|A_{R}|$, which we can, without loss of generality, assume by
isometrically enlarging the Hilbert space. The Choi matrix $\mu^{A_{R}X}$ of
this channel has $H_{2}(A_{R}|X)_{\mu}=\log r$ [24, Corollary 5.10, see Eq.
(5.67)], and so [40, Thm. 3.1] (see also [41]) implies

$\mathbb{E}_{U}\frac{1}{2}\left\|({\cal M}\circ{\cal
U}\otimes{\operatorname{id}}_{B})\omega^{A_{R}B}-\frac{{\openone}_{X}}{|X|}\otimes\omega^{B}\right\|_{1}\leq
2\epsilon+2^{-\frac{1}{2}\log
r-\frac{1}{2}H_{\min}^{\delta}(A_{R}|B)_{\omega}},$

where ${\cal U}(\alpha)=U\alpha U^{\dagger}$ is the channel applying the
unitary $U$, and only the second term is smoothed, resulting in a lower
factor. If we fix $\log r=-H_{\min}^{\delta}(A_{R}|B)_{\omega}-2\log\eta$, the
right hand side will be bounded from above by $\eta$, and allowing for
rounding to a smaller integer, we obtain the bound $2\eta$.

In particular, in that case there exists a unitary $U$ such that

$\frac{1}{2}\left\|({\cal M}\circ{\cal
U}\otimes{\operatorname{id}}_{B})\omega^{A_{R}B}-\frac{{\openone}_{X}}{|X|}\otimes\omega^{B}\right\|_{1}\leq
2\delta+2\eta,$

and to progress we expand the two matrices inside the trace norm. Namely,
inserting
$\omega^{A_{R}B}=({\operatorname{id}}_{A_{R}}\otimes\mathcal{N})\Phi_{\sigma}^{A_{R}A}$
and in particular $\omega^{B}=\mathcal{N}(\sigma^{A})$, we get

$\begin{split}\frac{{\openone}_{X}}{|X|}\otimes\omega^{B}&=\sum_{x=1}^{\ell}\frac{1}{|X|}|x\rangle\\!\langle
x|^{X}\otimes\mathcal{N}(\sigma^{A})\text{ and }\\\ ({\cal M}\circ{\cal
U}\otimes{\operatorname{id}}_{B})\omega^{A_{R}B}&=\sum_{x=1}^{\ell}|x\rangle\\!\langle
x|^{X}\otimes\tr_{A_{R}}\left[\omega^{A_{R}B}\left(U^{\dagger}P_{x}U\otimes{\openone}_{B}\right)\right]\\\
&=\sum_{x=1}^{\ell}|x\rangle\\!\langle
x|^{X}\otimes\mathcal{N}\left(\tr_{A_{R}}\left[\Phi_{\sigma}^{A_{R}A}\left(U^{\dagger}P_{x}U\otimes{\openone}_{A}\right)\right]\right)\\\
&=\sum_{x=1}^{\ell}p(x)|x\rangle\\!\langle
x|^{X}\otimes\mathcal{N}\left(\sigma_{x}^{A}\right),\end{split}$

where
$p(x)\sigma_{x}^{A}=\tr_{A_{R}}\left[\Phi_{\sigma}^{A_{R}A}\left(U^{\dagger}P_{x}U\otimes{\openone}_{A}\right)\right]$,
$p(x)$ is the normalising trace (a probability) and $\sigma_{x}^{A}$ is a
state of rank at most $r$ on $A$.

By tracing over $B$ we find that the total variational distance between $p$
and the uniform distribution is less than $2\epsilon+2\eta$, and hence by the
triangle inequality we find

$\sum_{x=1}^{\ell}p(x)\frac{1}{2}\left\|\mathcal{N}(\sigma_{x}^{A})-\mathcal{N}(\sigma^{A})\right\|_{1}\leq
4\delta+4\eta.$

To conclude, there exists at least one $x$ such that
$\frac{1}{2}\left\|\mathcal{N}(\sigma_{x}^{A})-\mathcal{N}(\sigma^{A})\right\|_{1}\leq
4\delta+4\eta$, making the statement of the theorem true letting
$\hat{\sigma}^{A}=\sigma_{x}^{A}$.

As for the converse, we have the following. Consider a purification
$\Phi^{AA_{R}}_{\sigma}$ of $\sigma^{A}$. Then we have

$\begin{split}\log\rank\rho^{A}&\geq H_{\max}(A_{R})_{\Phi}\\\
&=-H_{\min}(A_{R}|A)_{\Phi}\\\ &\geq-H_{\min}(A_{R}|B)_{\omega},\end{split}$

where the first line follows from the fact that $H_{\max}(\sigma^{A})$ is the
Rényi-$\frac{1}{2}$ entropy, which is upper bounded by the Rényi-$0$ entropy;
the second line is by the duality of min- and max-entropies ([24, Proposition
5.7]), and the third comes from data processing. Since the rank of a density
matrix is a natural number, we also have $\log\rank\sigma^{A}\geq 0$.
$\sqcap$$\sqcup$

Considering the asymptotic setting, we define achievable rate for a quantum
covering code as follows.

######  Definition 3.4 (Achievability).

For a given pair $(\rho^{B},\mathcal{N})$, a rate $R$ is said to be achievable
for quantum covering, if for all $\epsilon>0$ and all sufficiently large $n$,
there exists an $(n,\Theta,\epsilon)$ quantum code such that
$\frac{1}{n}\log{\Theta}\leq R+\epsilon$.

Building on Theorem 3.3, we now characterize the set of all achievable rates
using single-letter coherent information.

######  Theorem 3.5 (Asymptotic quantum covering).

For a given pair $(\rho^{B},\mathcal{N})$, a rate $R$ is achievable for
quantum covering if and only if $S(\rho^{B},\mathcal{N})$ is non-empty, and

$R\geq\min_{\sigma^{A}\in\mathcal{S}(\rho^{B},\mathcal{N})}\left[I_{c}(\sigma^{A},\mathcal{N})\right]^{+}.$

###### Proof.

Invoking the asymptotic equipartition property for the min-entropy [24], we
immediately get the following consequence which provides the achievability.
Given a pair $(\rho^{B},\mathcal{N})$ and an input state
$\sigma^{A}\in\mathcal{S}(\rho^{B},\mathcal{N})$, we consider the i.i.d.
extension $\mathcal{N}^{\otimes n}\mathrel{\mathop{\mathchar
58\relax}}A^{n}\rightarrow B^{n}$. Then, using Theorem 3.3, we see that there
exists a sequence of states $\hat{\sigma}^{A^{n}}$ on $A^{n}$ of rank $r_{n}$
such that

$\frac{1}{2}\left\|\mathcal{N}^{\otimes
n}(\hat{\sigma}^{A^{n}})-\left({\rho^{B}}\right)^{\otimes
n}\right\|_{1}\rightarrow 0\quad\text{and}\quad\frac{1}{n}\log
r_{n}\rightarrow\left[-S(A_{R}|B)_{\omega}\right]^{+},$ (6)

as $n\rightarrow\infty$, where
$\omega^{A_{R}B}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\operatorname{id}}\otimes\mathcal{N})\Phi^{A_{R}A}_{\sigma}$,
and $\Phi_{\sigma}^{A_{R}A}$ is a purification of $\sigma^{A}$.
$\sqcap$$\sqcup$

For the converse, we proceed as follows. Let $R$ be achievable. Using the
result from Theorem 3.3, for any $\epsilon>0$, we get

$\displaystyle nR$
$\displaystyle\geq\inf_{\sigma^{A^{n}}\in\mathcal{S}_{\epsilon}((\rho^{B})^{\otimes
n},\mathcal{N}^{\otimes
n})}-H_{\min}(A^{n}_{R}|B^{n})_{\upsilon^{n}(\sigma^{A^{n}})},$

where
$\upsilon^{n}(\sigma^{A^{n}})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\operatorname{id}}\otimes\mathcal{N}^{\otimes
n})\Phi_{\sigma}^{A^{n}_{R}A^{n}}$ with $\Phi_{\sigma}^{A^{n}_{R}A^{n}}$
denoting a purification of $\sigma^{A^{n}}$. Using the fact that
$H_{\min}(A^{n}_{R}|B^{n})_{\upsilon^{n}(\sigma^{A^{n}})}\leq
H(A^{n}_{R}|B^{n})_{\upsilon^{n}(\sigma^{A^{n}})}$ [42, Lemma 2], we get

$\displaystyle nR$
$\displaystyle{\geq}\inf_{\sigma^{A^{n}}\in\mathcal{D}(A^{\otimes
n})\mathrel{\mathop{\mathchar 58\relax}}\|(\rho^{B})^{\otimes
n}-\mathcal{N}^{\otimes
n}(\sigma^{A^{n}})\|_{1}\leq\epsilon}-H(A^{n}_{R}|B^{n})_{\upsilon^{n}(\sigma^{A^{n}})}$
(7) $\displaystyle\overset{}{=}\inf_{\sigma^{A^{n}}\in\mathcal{D}(A^{\otimes
n})\mathrel{\mathop{\mathchar 58\relax}}\|(\rho^{B})^{\otimes
n}-\mathcal{N}^{\otimes
n}(\sigma^{A^{n}})\|_{1}\leq\epsilon}H(B^{n})_{\upsilon^{n}(\sigma^{A^{n}})}-H(A^{n}_{R},B^{n})_{\upsilon^{n}(\sigma^{A^{n}})}$
(8)
$\displaystyle\overset{a}{\geq}\inf_{\sigma^{A^{n}}\in\mathcal{D}(A^{\otimes
n})\mathrel{\mathop{\mathchar 58\relax}}\|(\rho^{B})^{\otimes
n}-\mathcal{N}^{\otimes
n}(\sigma^{A^{n}})\|_{1}\leq\epsilon}H(B^{n})_{(\rho^{B})^{\otimes
n}}-H(A^{n}_{R},B^{n})_{\upsilon^{n}(\sigma^{A^{n}})}-n\tilde{\epsilon}_{1}$
(9)
$\displaystyle\overset{b}{\geq}n\min_{\sigma^{A}\in\mathcal{D}(A)\mathrel{\mathop{\mathchar
58\relax}}\|\rho^{B}-\mathcal{N}(\sigma^{A})\|_{1}\leq\epsilon}I_{c}(\sigma^{{A}},\mathcal{N})-2n\tilde{\epsilon}_{1},$
(10)

where $(a)$ follows from the Fannes-Audenart inequality, the constraint on
$\sigma^{A^{n}}$ and defining
$\tilde{\epsilon}_{1}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\epsilon\log|\mathcal{H}_{B}|+h_{b}(\epsilon)$,
and $(b)$ follows from employing the same reasoning as that used in [33, Eqs.
(68)-(72)]. The converse proof is completed by using the continuity arguments
provided in [33].  $\sqcap$$\sqcup$

As our next main result, we obtain a second order achievability bound. The
asymptotic result in Theorem 3.5 states that the rank of the smallest quantum
covering code scales exponentially with the exponent $nI_{c}(\cdot)$. The
objective of the second order analysis is to obtain a more precise estimate of
the exponent by deriving the coefficient of $\sqrt{n}$ present in the
exponent. The exploration of this field was initially introduced by Strassen
in 1962, specifically addressing the classical communication problem. This was
later refined by authors in [26, 27]. In the quantum domain, Tomamichel and
Hayashi [29], and Li [30] were the first to obtain tight results concerning
second order asymptotics. See also [31, 32], where new proofs toward studying
the second order behaviour, inspired from [28], are given utilizing the
collision relative entropy.

######  Theorem 3.6 (Second order achievability bound).

For a given $(\rho^{B},\mathcal{N})$ quantum covering setup, and a density
operator $\sigma^{A}\in\mathcal{S}(\rho^{B},\mathcal{N})$, there exists an
$(n,\Theta,\epsilon)$ covering code such that the rate scales as

$\displaystyle\frac{1}{n}\log{\Theta}=\left[{I_{c}(\sigma^{A},\mathcal{N})-\frac{1}{\sqrt{n}}\sqrt{V(\sigma^{A},\mathcal{N})}\Phi^{-1}\bigg{(}\frac{\epsilon^{2}}{100}\bigg{)}+O\left(\frac{\log
n}{n}\right)}\right]^{+},$ (11)

where

$V(\sigma^{A},\mathcal{N})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}V(\rho^{BA_{R}}\|\rho^{B}\otimes{\openone}_{A_{R}}),$

$\rho^{BA_{R}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mathcal{N}\otimes{\operatorname{id}})\Phi_{\sigma}^{A{A_{R}}}$,
and $\Phi_{\sigma}^{A{A_{R}}}$ is a purification of $\sigma^{A}$.

###### Proof.

Given the pair $(\rho^{B},\mathcal{N})$ and
$\sigma^{A}\in\mathcal{S}(\rho^{B},\mathcal{N})$, consider the $n$-letter pair
$((\rho^{B})^{\otimes n},\mathcal{N}^{\otimes n})$, and let
$\sigma^{A^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\sigma^{A})^{\otimes
n}$. From Theorem 3.3, it follows that for all $\delta,\eta\in(0,1)$ there
exists a $(n,\Theta,8(\delta+\eta))$ quantum covering code such that
$\log\Theta\leq\left[{-H_{\min}^{\delta}(A_{R}^{n}|B^{n})_{\rho^{B^{n}A_{R}^{n}}}-2\log\eta}\right]^{+}$,
where
$\rho^{B^{n}A_{R}^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mathcal{N}^{\otimes
n}\otimes{\operatorname{id}})\Phi_{\sigma}^{A^{n}A_{R}^{n}}$, and
$\Phi_{\sigma}^{A^{n}A_{R}^{n}}$ is a purification of $\sigma^{A^{n}}$. We now
bound $\log\Theta$ as

$\displaystyle\log\Theta$
$\displaystyle\leq\left[{-H_{\min}^{\delta}(A_{R}^{n}|B^{n})_{(\rho^{B{A_{R}}})^{\otimes
n}}-2\log\eta}\right]^{+},$
$\displaystyle\overset{a}{=}\left[{\inf_{\tau^{B^{n}}\in\mathcal{D}(\mathcal{H}_{B}^{\otimes
n})}D_{\max}^{\delta}({(\rho^{B{A_{R}}})^{\otimes
n}}||{\openone}_{A_{R}^{n}}\otimes\tau^{B^{n}})-2\log\eta}\right]^{+}$
$\displaystyle\leq\left[{D_{\max}^{\delta}({(\rho^{B{A_{R}}})^{\otimes
n}}||{\openone}_{A_{R}^{n}}\otimes(\rho^{B})^{\otimes
n})-2\log\eta}\right]^{+}$ (12)

where $(a)$ follows from the definition of $H_{\min}^{\delta}$ [29, Definition
3]. Choosing $\eta=\delta/4$ and using Lemma 2.8 gives the desired result.
$\sqcap$$\sqcup$

We now move on to considering the three applications of the quantum covering
problem.

##  4 Lossy quantum source coding

The history of this problem dates back to the work of Barnum [43], who
introduced the idea of a local distortion criterion using entanglement
fidelity and formulated a quantum rate distortion problem. Barnum conjectured
the minimal coherent information of the quantization (forward) channel to
characterize the asymptotic performance limit of this problem However, in [44]
a regularised expression using the concept of entanglement of purification was
obtained. Further notable investigations for related scenarios involving
additional resources have been performed in studies such as [45, 46, 47, 48,
49, 50, 51, 52, 53, 54, 55, 23]. Recent progress was made in [33] where the
use of a posterior (reverse) channel distortion criterion to quantify
distortion was proposed, together with a global error criterion instead of the
conventional average distortion measure. This formulation, which was inspired
by certain approximation results in classical source and channel coding
problems [56, 57], provided a more optimistic viewpoint on the rate-distortion
problem, as the formulation yielded the single-letter minimal coherent
information of the posterior reference channel as the asymptotic performance
limit. In this work, we aim to characterize the performance limit of a one-
shot formulation for the aforementioned rate distortion problem. To begin, we
establish the following notation.

For a given Hilbert space $A$, its reference $A_{R}$, and two orthonormal
basis $\\{\ket{i}\\}^{A}$ and $\\{\ket{i}\\}^{A_{R}}$ corresponding to the
Hilbert spaces $A$ and $A_{R}$, respectively, we define the unnormalized
maximally entangled state $\Gamma_{A_{R}A}$ as
$\sum_{i}\ket{i}^{A_{R}}\otimes\ket{i}^{A}$. The transpose of a state
$\tau\in\mathcal{L}(A)$ is defined as
$\tau^{T}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{i,i^{\prime}}\ket{i}\bra{i^{\prime}}^{A_{R}}\bra{i^{\prime}}\tau\ket{i}^{A}$.
Here, we focus exclusively on references obtained from canonical purifications
of quantum states [10, Lemma 14 (Pretty good purifications)], and for a given
density operator $\sigma^{A}\in\mathcal{D}(A)$, define the canonical
purification $\ket{\psi_{\sigma}}^{{A_{R}}A}$ of $\sigma^{A}$ as
$\ket{\psi_{\sigma}}^{{A_{R}}A}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\openone}_{{A_{R}}}\otimes\sqrt{\sigma^{A}})\Gamma_{{A_{R}}A}$.
We use $\Psi_{\sigma}^{{A_{R}}A}$ to denote the density operator corresponding
to $\ket{\psi_{\sigma}}^{{A_{R}}A}$. Note that
$\sigma^{A_{R}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\Tr_{A}\left({{\Psi_{\sigma}}^{{A_{R}}A}}\right)=\left({\sigma^{A}}\right)^{T}$.
As is the convention, for two states acting on the same Hilbert space, we use
the same $\Gamma$ when defining their canonical purifications. Recalling the
notion of a posterior reference map, we have the following.

Figure 1: Figure demonstrating the construction of the posterior reference map
$W$ from the isometry $V$ (the Stinespring’s dilation of $\mathcal{N}_{V}$)
and the source state $\rho^{B}$.

######  Lemma 4.1 (Posterior reference map [33]).

Given a source $\rho^{B}\in\mathcal{D}(B)$ and a channel
$\mathcal{N}_{V}\mathrel{\mathop{\mathchar 58\relax}}{B}\rightarrow A$, let
$\rho^{A}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathcal{N}_{V}(\rho^{B})$.
Let $V\mathrel{\mathop{\mathchar 58\relax}}{B}\rightarrow{A}\otimes E$ be a
Stinespring’s isometry corresponding to the CPTP map $\mathcal{N}_{V}$ with
$\dim(E)\geq\dim(A)$, such that
$\mathcal{N}_{V}(\cdot)=\Tr_{E}\\{V(\cdot)V^{\dagger}\\}$. Then there exists a
unique CPTP map $\mathcal{N}_{W}\mathrel{\mathop{\mathchar
58\relax}}{{A_{R}}}\rightarrow{{B_{R}}}$, with an associated isometry
$W\mathrel{\mathop{\mathchar 58\relax}}{{A_{R}}}\rightarrow{{B_{R}}}\otimes
E$, which we refer to as the “posterior reference map” of $V$ with respect to
$\rho^{A}$, satisfying

$\displaystyle(W\otimes{\openone}_{A})\ket{\psi_{\rho}}^{{A_{R}}A}=({\openone}_{{B_{R}}}\otimes
V)\ket{\psi_{\rho}}^{{B_{R}}B},$ (13)

where $\ket{\psi_{\rho}}^{{A_{R}}A}$ and $\ket{\psi_{\rho}}^{{B_{R}}B}$ are
the canonical purifications of $\rho^{A}$ and $\rho^{B}$, respectively, as
shown in Figure 1.

The posterior reference map exhibits a interesting connection with the well-
known Petz recovery map [58]. In particular, the posterior reference map with
respect to a state is equal to a transposed Petz recovery channel acting on
the reference Hilbert space of the given state as stated below.

######  Proposition 4.2 (Posterior reference map as a Petz recovery map).

Given an input state $\rho^{B}$ and a channel $\mathcal{N}_{V}$, for an
arbitrary state $\sigma^{A_{R}}$, we have

$\mathcal{N}_{W}(\sigma^{A_{R}})=(\rho^{{B_{R}}})^{1/2}\left({\mathcal{N}_{V}^{\dagger}\left({(\rho^{A})^{-1/2}\sigma^{A}(\rho^{A})^{-1/2}}\right)}\right)^{T}(\rho^{{B_{R}}})^{1/2},$

where $\rho^{A}=\mathcal{N}_{V}(\rho^{B})$,
$\sigma^{A}=\Tr_{{A_{R}}}{\Psi_{\sigma}^{A{A_{R}}}}=\left({\sigma^{A_{R}}}\right)^{T}$,
$\rho^{B_{R}}=\Tr_{B}{\Psi_{\rho}^{B{B_{R}}}}$.

###### Proof.

A proof of this statement is provided in Section 7.1.  $\sqcap$$\sqcup$

Continuing with the source coding setup, we proceed by recalling the
formulation of the problem [33].

######  Definition 4.3 (Quantum source coding setup).

A quantum source coding setup is characterized by a pair
$(\rho^{B},\mathcal{N}_{W})$, where $\rho^{B}\in\mathcal{D}(B)$ is a density
operator, $A$ is a reconstruction Hilbert space, and $\mathcal{N}_{W}$ is a
CPTP map from ${{A_{R}}}$ to ${{B_{R}}}$, where ${{A_{R}}}$ and ${{B_{R}}}$
are reference spaces corresponding to $A$ and $B$, respectively.

######  Definition 4.4 (Lossy quantum compression protocol).

For a given input and reconstruction Hilbert spaces $(B,A)$, an
$(n,\Theta,\epsilon)$ lossy quantum compression protocol (as shown in Figure
2) consists of an encoding CPTP map
$\mathcal{E}^{(n)}\mathrel{\mathop{\mathchar 58\relax}}{B^{\otimes
n}}\rightarrow{M}$ and a decoding CPTP map
$\mathcal{D}^{(n)}\mathrel{\mathop{\mathchar 58\relax}}M\rightarrow{A^{\otimes
n}}$, such that $\dim(M)=\Theta$, and

$\displaystyle\left\|{\omega^{B_{R}^{n}A^{n}}-(\mathcal{N}_{W}^{\otimes
n}\otimes{\operatorname{id}}_{A^{n}})\Psi_{\omega}^{A_{R}^{n}A^{n}}}\right\|_{1}\leq\epsilon,$
(14)

where
$\omega^{B_{R}^{n}A^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\operatorname{id}}\otimes\mathcal{D}^{(n)})({\operatorname{id}}\otimes\mathcal{E}^{(n)})(\Psi_{\rho}^{B_{R}^{n}B^{n}})$,
and $\Psi_{\rho}^{B_{R}^{n}B^{n}}$ and $\Psi_{\omega}^{A_{R}^{n}A^{n}}$ are
the canonical purifications of ${\rho^{B}}^{\otimes n}$ and $\omega^{A^{n}}$,
respectively.

Figure 2: Illustration of Lossy Quantum Compression protocol

######  Definition 4.5 (Achievability).

For a quantum source coding setup $(\rho^{B},\mathcal{N}_{W})$, a rate $R$ is
said to be achievable for lossy quantum source coding, if for all $\epsilon>0$
and all sufficiently large $n$, there exists an $(n,\Theta,\epsilon)$ lossy
quantum compression protocol satisfying $\frac{1}{n}\log{\Theta}\leq
R+\epsilon$.

As a first result of this section, we aim to provide a characterization to the
one-shot lossy source coding problem. To achieve this, we rely on the
properties of posterior reference maps [33], which enable us to establish the
following equivalence between between the quantum covering problem and the
lossy quantum source coding problem.

######  Lemma 4.6 (Equivalence of quantum lossy source coding and quantum
covering).

Consider an arbitrary state $\rho^{B}\in\mathcal{D}(B)$ and a CPTP map
$\mathcal{N}_{W}\mathrel{\mathop{\mathchar 58\relax}}A_{R}\rightarrow B_{R}$.
The existence of an $(n,\Theta,\epsilon)$ lossy quantum compression protocol
for the $(\rho^{B},\mathcal{N}_{W})$ setup, with the restriction that the
decoding map ${\mathcal{D}}^{(n)}$ is an isometry, implies that there exists
an $(n,\Theta,\epsilon)$ quantum covering code for the
$(\rho^{{B_{R}}},\mathcal{N}_{W})$ setup, where
$\rho^{{B_{R}}}=\left({\rho^{B}}\right)^{T}$. Conversely, the existence of an
$(n,\Theta,\epsilon)$ quantum covering code for
$(\rho^{B_{R}},\mathcal{N}_{W})$ setup implies that there exists an
$(n,\Theta,4\sqrt{\epsilon})$ lossy quantum compression protocol for the
$(\rho^{B},\mathcal{N}_{W})$ setup.

###### Proof.

A detailed proof is provided in Section 7.2. The proof involves utilizing a
quantum soft-covering code to construct an encoder for the source coding
problem. This encoder enables efficient compression of a quantum source while
maintaining the quantified level of loss. As for the other direction, we find
that an encoder for the source coding problem possesses the ability to
generate a state that satisfies the soft-covering constraint.
$\sqcap$$\sqcup$

In [33], the duality between quantum source coding and channel coding problems
was highlighted using the structure of the performance limit: both being
characterized using the coherent information. In the following, we take a step
further, and shed light on the duality relation between the encoder of the
former and the decoder of latter, and vice versa, which is well understood in
the classical settings [59, 60]. Expanding on this line of inquiry, we note
that [32] presents a decoder based on the Petz recovery map for the quantum
channel coding problem. As can be noted from the proof of the above
equivalence (Lemma 4.6), an encoder for the current source coding problem can
be devised using the posterior reference map associated with the quantum soft
covering setup. Further, Proposition 4.2 uncovers the connection between the
posterior reference map and the Petz recovery map, thus establishing a
compelling duality between the encoding and decoding maps of the two problems.

Leveraging the one-shot results pertaining to quantum covering and the above
equivalence, we are able to characterize the achievability results for the
performance of a one-shot lossy source coding problem formulation in the
following. The converse, however, uses a different chain of arguments.

######  Theorem 4.7 (One-shot lossy quantum compression).

For a $(\rho^{B},\mathcal{N}_{W})$ quantum source coding setup, a density
operator $\sigma^{{A_{R}}}\in\mathcal{S}(\rho^{{B_{R}}},\mathcal{N}_{W})$, for
all $\delta,\eta\in(0,1)$, there exists $(1,\Theta,\epsilon)$ lossy quantum
compression protocol such that

$\log\Theta\leq\left[{-H_{\min}^{\delta}(A|B_{R})_{\rho^{B_{R}A}}-2\log{\eta}}\right]^{+},$

and $\epsilon\leq 4\delta+4\eta$, where
$\rho^{B_{R}A}=(\mathcal{N}_{W}\otimes{\operatorname{id}})\Phi^{A_{R}A}_{\sigma}$,
$\Phi^{AA_{R}}_{\sigma}$ is a purification of $\sigma^{A_{R}}$. Moreover, for
all $\epsilon\in(0,1)$, every $(1,\Theta,\epsilon)$ code satisfies

$\log\Theta\geq\inf_{\sigma^{A_{R}}\in\mathcal{S}_{\epsilon}(\rho^{B_{R}},\mathcal{N}_{W})}\left[-H^{\sqrt{\epsilon}}_{\min}(A|B_{R})_{\rho^{B_{R}A}}\right]^{+}.$
(15)

###### Proof.

The proof of achievability follows from using the equivalence with soft-
covering, according to Lemma 4.6 and the achievability part of Theorem 3.3. A
proof of the converse is provided in Section 7.3.  $\sqcap$$\sqcup$

This gives us the following characterization to the set of all achievable
rates for the asymptotic lossy quantum source coding problem, recovering the
characterization obtained in [33, Theorem 1].

######  Theorem 4.8 (Asymptotic lossy quantum compression).

For a $(\rho^{B},\mathcal{N}_{W})$ quantum source coding setup, a rate $R$ is
achievable if and only if $S(\rho^{B_{R}},\mathcal{N}_{W})$ is non empty, and

$R\geq\min_{\sigma^{{A_{R}}}\in\mathcal{S}(\rho^{B_{R}},\mathcal{N}_{W})}I^{+}_{c}(\sigma^{{A_{R}}},\mathcal{N}_{W}).$

###### Proof.

The proof of achievability follows by using the above one-shot achievability
result of Theorem 4.7 and the asymptotic equipartition property (similar to
the proof of Theorem 3.5). The proof of the converse is provided in Section
7.4.  $\sqcap$$\sqcup$

##  5 Quantum channel resolvability

As a next application, we consider the channel resolvability problem.
Initially introduced in the classical setting by Han and Verdú [61], and
generalised to classical-quantum channels with a given output measurement by
Löber [62], and in [8] for the plain output density matrices, this problem
addresses the task of asymptotically approximating a target output
distribution through a given channel using an essentially uniform input
distribution with a smaller support. The capacity of this problem is defined
as the smallest rate of input randomness with which any arbitrary output
distribution can be effectively approximated. Analogously, for the quantum
setting, we define its capacity as the rate of the smallest rank of input
state needed to approximate any arbitrary output state of a given channel. The
objective now is to characterize this smallest rank. To formally define the
problem, we first define channel resolvability for a given input state
$\sigma^{A^{n}}\in\mathcal{D}(A^{\otimes n})$.

######  Definition 5.1 (Channel resolvability for a given input state).

For a given CPTP map $\mathcal{N}\mathrel{\mathop{\mathchar
58\relax}}A\rightarrow B$, a rate $R$ is said to be $(n,\epsilon)$-achievable
for an input state $\sigma^{A^{n}}\in\mathcal{D}(A^{\otimes n})$ if there
exists a density operator $\hat{\sigma}^{A^{n}}$ on $A^{\otimes n}$ with
$|\hat{\sigma}^{A^{n}}|=2^{nR}$ which satisfies

$\displaystyle\frac{1}{2}\left\|{\cal N}^{\otimes
n}(\hat{\sigma}^{A^{n}})-{\cal N}^{\otimes
n}(\sigma^{A^{n}})\right\|_{1}\leq\epsilon.$ (16)

We define

$\mathcal{R}^{0}_{\epsilon}({\cal N}^{\otimes
n},\sigma^{A^{n}})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\inf\\{R\mathrel{\mathop{\mathchar
58\relax}}R\mbox{ is }(n,\epsilon)\mbox{-achievable for }\sigma^{A^{n}}\\}.$

The asymptotic resolvability rate is defined accordingly as

$\mathcal{R}({\cal
N})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sup_{\epsilon>0}\limsup_{n\rightarrow\infty}\left[\sup_{\sigma^{A^{n}}}\mathcal{R}^{0}_{\epsilon}\left({\cal
N}^{\otimes n},\sigma^{A^{n}}\right)\right].$

######  Definition 5.2 (Quantum transmission code).

For a given CPTP map $\mathcal{N}\mathrel{\mathop{\mathchar
58\relax}}A\rightarrow B$, a $(n,\Theta,\epsilon)$ quantum transmission code
consists of a pair of encoding and decoding maps,
$\mathcal{E}\mathrel{\mathop{\mathchar 58\relax}}C\rightarrow A^{\otimes n}$
and $\mathcal{D}\mathrel{\mathop{\mathchar 58\relax}}B^{\otimes n}\rightarrow
C$, respectively, such that $|C|=\Theta$, and

$\sup_{\ket{\Phi}\in
C\otimes{C_{R}}}P(\outerproduct{\Phi}{\Phi},({\operatorname{id}}_{C_{R}}\otimes\mathcal{D}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{E})\outerproduct{\Phi}{\Phi})\leq\epsilon.$

######  Definition 5.3 (Weak converse quantum capacity).

For a given channel $\mathcal{N}$, we define $N_{E}(n,\epsilon|{\cal N})$ as
the maximum dimension $\Theta$ such that there exists a $(n,\Theta,\epsilon)$
quantum transmission code. The quantum capacity is now defined as

$Q(\mathcal{N})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\inf_{\epsilon>0}\liminf_{n\rightarrow\infty}\frac{1}{n}\log
N_{E}(n,\epsilon|\mathcal{N}).$

######  Definition 5.4 (Strong converse quantum capacity).

For a given channel $\mathcal{N}$, we define $R$ to be admissible if all
sequences of $(n,\Theta_{n},\epsilon_{n})$ quantum transmission codes with

$\liminf_{n\rightarrow\infty}\frac{1}{n}\log\Theta_{n}>R,$

satisfy

$\lim_{n\rightarrow\infty}\epsilon_{n}=1.$

The strong converse capacity is defined as

$\widehat{Q}(\mathcal{N})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\inf\\{R\mathrel{\mathop{\mathchar
58\relax}}R\mbox{ is admissible}\\}.$

The above direct part and converse for quantum soft covering yield the
following bounds on the asymptotic resolvability rates of a channel.

######  Theorem 5.5.

For any channel ${\cal N}$, any $\epsilon>0$, and any input state
$\sigma^{A^{n}}\in\mathcal{D}(A^{\otimes n})$, we have

$\inf_{\omega^{A^{n}}\in\mathcal{D}(A^{\otimes n})\mathrel{\mathop{\mathchar
58\relax}}\|\mathcal{N}^{\otimes n}(\sigma^{A^{n}})-\mathcal{N}^{\otimes
n}(\omega^{A^{n}})\|_{1}\leq\epsilon}\left[{-H_{\min}(A_{R}^{n}|B^{n})_{\rho^{B^{n}A_{R}^{n}}}}\right]^{+}\leq\mathcal{R}^{0}_{\epsilon}\left({\cal
N}^{\otimes n},\sigma^{A^{n}}\right)\leq\widehat{Q}({\cal N}),$

where
$\rho^{B^{n}A_{R}^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mathcal{N}^{\otimes
n}\otimes{\operatorname{id}}_{A^{n}_{R}})(\Phi_{\omega}^{A^{n}A_{R}^{n}})$,
$\Phi_{\omega}^{A^{n}A_{R}^{n}}$ is a purification of $\omega^{A^{n}}$, and
$\widehat{Q}({\cal N})$ is the strong converse quantum capacity of ${\cal N}$.

###### Proof.

We begin with the direct part (upper bound). Consider a
$\sigma^{A}\in\mathcal{D}(A^{\otimes n})$. From Theorem 3.3, and with
$\omega^{A_{R}B}=({\operatorname{id}}\otimes\mathcal{N})\Phi_{\sigma}^{A_{R}A}$
in the following optimisation, we have

$\begin{split}\mathcal{R}^{0}_{\epsilon}({\cal N},\sigma^{A})&\leq-
H_{\min}^{\epsilon/5}(A_{R}|B)_{\omega}+2\log\frac{20}{\epsilon}\\\
&\overset{(a)}{\leq}-H_{\max}^{\sqrt{1-\epsilon^{4}/625}}(A_{R}|B)_{\omega}+2\log\frac{20}{\epsilon}\\\
&{\leq}-H_{\max}^{1-\epsilon^{4}/1250}(A_{R}|B)_{\omega}+2\log\frac{20}{\epsilon},\end{split}$

where $(a)$ follows from Lemma 2.10. (Notice in particular that the right hand
side in the first line is always non-negative.) Now we know from [39, Prop.
20] (cf. [63] and [64]) that the number of qubits transmittable via ${\cal N}$
is upper- and lower-bounded tightly in terms of max-entropies:

$\sup_{\Phi^{A_{R}A}}-H_{\max}^{\lambda}(A_{R}|B)_{\omega}-4\log\frac{1}{\mu}\leq\log
N_{E}(\lambda+\mu|{\cal
N})\leq\sup_{\Phi^{A_{R}A}}-H_{\max}^{\lambda+\mu}(A_{R}|B)_{\omega},$ (17)

with $\omega^{A_{R}B}=({\operatorname{id}}\otimes\mathcal{N})\Phi^{A_{R}A}$ as
before. Letting here $\lambda=1-\epsilon^{4}/1250$ and
$\mu=\epsilon^{4}/2500$, we thus obtain

$\mathcal{R}^{0}_{\epsilon}({\cal N},\sigma^{A})\leq\log
N_{E}(1-\epsilon^{4}/2500|{\cal
N})+2\log\frac{20}{\epsilon}+4\log\frac{2500}{\epsilon^{4}}.$

Applying this to ${\cal N}^{\otimes n}$ and letting $n\rightarrow\infty$ in
the regime of small $\epsilon$ shows the upper bound.

The converse (lower bound) follows from the one-shot soft-covering result
obtained in Theorem 3.3.  $\sqcap$$\sqcup$

######  Corollary 5.6.

For any channel ${\cal N}$, we have

$\mathcal{R}({\cal N})\leq\widehat{Q}({\cal N}),$

where $\widehat{Q}({\cal N})$ is the strong converse quantum capacity of
${\cal N}$.

######  Conjecture 5.7.

For any channel ${\cal N}$,

$Q(\mathcal{N})\leq\mathcal{R}({\cal N}),$

where ${Q}({\cal N})$ is the weak converse quantum capacity of ${\cal N}$.

######  Remark 5.8.

Note that finding an exact characterization of the asymptotic resolvability of
a classical channel is still an open problem (see [65, Chapter 6.3]).

######  Remark 5.9.

The strong converse property for the quantum capacity, i.e. $Q({\cal
N})=\widehat{Q}({\cal N})$, is known to hold for PPT entanglement-binding
channels and for generalised dephasing channels [66]. For general degradable
channels it is conjectured, but only a “pretty strong” converse is known,
meaning that the asymptotic rate of quantum codes is bounded by $Q({\cal N})$
for sufficiently small error [39].

For all other channels, the issue of the strong converse is wide open, and no
Shannon-style single-letter or regularised formula is known for
$\widehat{Q}({\cal N})$. However, [66, Thm. 8 and Cor. 7] establishes the so-
called Rains information of the channel as an upper bound to
$\widehat{Q}({\cal N})$.

##  6 Identification via quantum channels

The problem of identification has a rich history, going back to the
groundbreaking work of Ahlswede and Dueck [67]. They observed that Shannon’s
celebrated theory of transmission imposes a very stringent constraint on the
communication task, in that the receiver has to decode the correct message
among all possible ones, whose relaxation to mere “identification” of the
correct message leads to doubly exponentiallay large codes in the block length
$n$. Specifically, given a transmitted message $m$ and an arbitrary message
$m^{\prime}$, the receiver’s sole interest lies in determining whether
“$m=m^{\prime}$” or “$m\neq m^{\prime}$”. Han and Verdú [68, 69] uncovered a
fundamental between the channel resolvability and the classical identification
problem, where the channel resolvability rate forms an upper bound on the
identification rate of the channel (cf. [65, Lemma 6.4.1]).

In the quantum realm, Löber [62] began the study of identification through
quantum channels, uncovering a fundamental distinction inherent to the quantum
setting. Unlike the classical scenario, quantum measurements face inherent
incompatibility, thereby necessitating a choice regarding the receiver’s
capability to answer all “if $m$ equals $m^{\prime}$” questions or only one of
them. This leads to the introduction of simultaneous identification capacity,
wherein a single measurement enables the identification of all messages
simultaneously. Another notable generalization is the concept of quantum
identification capacity of a quantum channel [70, 71, 72]. The survey article
[73] reviews the different notions of identification codes for quantum
channels and the state of the art at the time of writing, which is still
largely up to date.

######  Definition 6.1 ([62]).

A classical identification code for the channel ${\cal
N}\mathrel{\mathop{\mathchar 58\relax}}A\rightarrow B$ with error probability
$\lambda_{1}$ of first, and $\lambda_{2}$ of second kind is a set
$\\{(\rho_{i},D_{i})\mathrel{\mathop{\mathchar 58\relax}}i=1,\ldots,N\\}$ of
states $\rho_{i}$ on $A$ and operators $D_{i}$ on $B$ with $0\leq
D_{i}\leq{\openone}_{B}$, i.e. the pair $(D_{i},{\openone}_{B}-D_{i})$ forms a
measurement, such that

$\displaystyle\forall i$ $\displaystyle\quad\tr\bigl({\cal
N}(\rho_{i})D_{i}\bigr{missing})\geq 1-\lambda_{1},$ $\displaystyle\forall
i\neq j$ $\displaystyle\quad\tr\bigl({\cal
N}(\rho_{i})D_{j}\bigr{missing})\leq\lambda_{2}.$

For the special case of memoryless channels ${\cal N}^{\otimes n}$, we speak
of an _$(n,\lambda_{1},\lambda_{2})$ -ID code_, and denote the largest size
$N$ of such a code $N(n,\lambda_{1},\lambda_{2})$.

An identification code as above is called _simultaneous_ if all the $D_{i}$
are coexistent: this means that there exists a positive operator valued
measure (POVM) $(E_{t})_{t=1}^{T}$ and pairwise disjoint sets ${\cal
D}_{i}\subset\\{1,\ldots,T\\}$ such that $D_{i}=\sum_{t\in{\cal D}_{i}}E_{t}$.
The largest size of a simultaneous $(n,\lambda_{1},\lambda_{2})$-ID code is
denoted $N_{\rm sim}(n,\lambda_{1},\lambda_{2})$.

Note that $N_{\rm
sim}(n,\lambda_{1},\lambda_{2})=N(n,\lambda_{1},\lambda_{2})=\infty$ if
$\lambda_{1}+\lambda_{2}\geq 1$, hence to avoid this triviality one has to
assume $\lambda_{1}+\lambda_{2}<1$.

######  Definition 6.2.

The _(simultaneous) classical ID-capacity_ of a quantum channel ${\cal N}$ is
given by

$\displaystyle C_{\rm ID}({\cal N})$
$\displaystyle=\inf_{\lambda>0}\liminf_{n\rightarrow\infty}\frac{1}{n}\log\log
N(n,\lambda,\lambda),$ $\displaystyle C_{\rm ID}^{\rm sim}({\cal N})$
$\displaystyle=\inf_{\lambda>0}\liminf_{n\rightarrow\infty}\frac{1}{n}\log\log
N_{\rm sim}(n,\lambda,\lambda),$

respectively. We say that the _strong converse_ holds for the identification
capacity if for all $\lambda_{1}+\lambda_{2}<1$,

$\lim_{n\rightarrow\infty}\frac{1}{n}\log\log
N(n,\lambda_{1},\lambda_{2})=C_{\rm ID}({\cal N}),$

and similarly for $C_{\rm ID}^{\rm sim}$.

The next theorem resolves one of the main open questions around identification
capacities of quantum channels, dating back to [8], and explicitly conjectured
in [70], by separating the simultaneous from the unrestricted version.

######  Theorem 6.3.

The simultaneous identification capacity of the noiseless qubit channel is
$C_{\text{ID}}^{\text{sim}}({\operatorname{id}}_{2})=1$, whereas the
unrestricted identification capacity is
$C_{\text{ID}}({\operatorname{id}}_{2})=2$.

More generally, for a quantum channel ${\cal N}\mathrel{\mathop{\mathchar
58\relax}}A\rightarrow B$, $C_{\text{ID}}^{\text{sim}}({\cal
N})\leq\log\min\\{|A|,|B|\\}$, and this is a strong converse bound: for all
$\lambda_{1},\lambda_{2}>0$ with $\lambda_{1}+\lambda_{2}<1$,

$\limsup_{n\rightarrow\infty}\frac{1}{n}\log\log
N_{{sim}}(n,\lambda_{1},\lambda_{2})\leq\log\min\\{|A|,|B|\\}.$

###### Proof.

The statements about the unrestricted identification capacity are from [70],
so only the simultaneous identification capacity has to be addressed. The
lower bound $C_{\text{ID}}^{\text{sim}}({\operatorname{id}}_{2})\geq 1$
follows from Ahlswede and Dueck’s construction [67] showing that every
transmission capacity can be converted into the same amount of double-
exponential identification capacity (cf. [62]).

As a channel ${\cal N}\mathrel{\mathop{\mathchar 58\relax}}A\rightarrow B$ can
be simulated by ${\operatorname{id}}_{A}$ followed by post-processing at the
receiver, and also by pre-processing at the sender followed by
${\operatorname{id}}_{B}$, every simultaneous identification code for ${\cal
N}$ gives rise to a simultaneous identification code for an ideal channel.
Thus, we have to prove the upper bound only for ${\operatorname{id}}_{A}$. For
that, consider a simultaneous identification code for
${\operatorname{id}}_{A}^{\otimes n}={\operatorname{id}}_{A^{n}}$ with $N$
messages and error probabilities $\lambda_{1},\lambda_{2}>0$ such that
$\lambda_{1}+\lambda_{2}<1$. To message $m$ is associated the state $\rho_{m}$
on $A^{n}$, and the binary decision POVM $(D_{m},{\openone}-D_{m})$ on
$A^{n}$. The simultaneity condition requires that all these POVMs are
compatible, i.e. there is a single measurement $(M_{y})_{y\in{\cal Y}}$ with
an arbitrary number of outcomes such that each $(D_{m},{\openone}-D_{m})$ is
obtained as a coarse-graining of it. Define the qc-channel ${\cal
M}\mathrel{\mathop{\mathchar 58\relax}}A^{n}\rightarrow Y$ corresponding to
the measurement, ${\cal M}(\rho)=\sum_{y}(\Tr\rho M_{y})|y\rangle\\!\langle
y|$. Since the given code is ipso facto an identification code for ${\cal M}$,
we are motivated to apply Theorem 3.3 to this channel, with
$\delta=\eta=\frac{1}{24}(1-\lambda_{1}-\lambda_{2})$. This gives us for each
$m$ a state $\sigma_{m}$ of rank $r$ on $A^{n}$ with

$\frac{1}{2}\left\|{\cal M}(\sigma_{m})-{\cal
M}(\rho_{m})\right\|_{1}\leq\frac{1}{3}(1-\lambda_{1}-\lambda_{2})=\mathrel{\mathop{\mathchar
58\relax}}\Delta,$

and $\log
r\leq\left[-H_{\min}^{\epsilon}(A^{n}_{R}|Y)_{\omega}-2\log\eta\right]^{+}$,
where $\omega^{A^{n}_{R}Y}=\sum_{y}\Tr_{A^{n}}\left({({\openone}\otimes
M_{y})\Phi_{m}^{A_{R}^{n}A^{n}}}\right)\otimes|y\rangle\\!\langle y|^{Y}$, and
$\Phi_{m}^{A_{R}^{n}A^{n}}$ is a purification of $\rho_{m}$. The crucial
insight now is that

$H_{\min}^{\epsilon}(A^{n}_{R}|Y)_{\omega}\geq
H_{\min}(A^{n}_{R}|Y)_{\omega}\geq 0,$

since $\omega^{A^{n}_{R}Y}$ is a cq-state, in particular separable. Thus,
$r\leq\frac{2}{\eta^{2}}$, and we can choose purifications $\ket{\zeta_{m}}\in
A^{n}\otimes R$ of $\sigma_{m}$ with $|R|=\frac{2}{\eta^{2}}$. At the same
time, the collection of states $\sigma_{m}$, with the same measurements
$(D_{m},{\openone}-D_{m})$, is an identification code with error probabilities
$\lambda_{i}^{\prime}=\lambda_{i}+\Delta$.

Next, we choose an $\delta$-net ${\cal Z}$ of pure states on $A^{n}\otimes R$,
which is known to exist with cardinality $|{\cal
Z}|\leq\left(\frac{5}{\delta}\right)^{2|A^{n}||R|}$ [74, Lemma III.6]. For
each $m$, we can find an element $\xi_{m}\in{\cal Z}$ with
$\frac{1}{2}\|\zeta_{m}-\xi_{m}\|_{1}\leq\delta$, and hence the collection of
states $\tau_{m}^{A^{n}}=\Tr_{R}\xi_{m}$ is an identification code with error
probabilities $\lambda_{i}^{\prime\prime}=\lambda_{i}+\Delta+\delta$. As
$\lambda_{1}^{\prime\prime}+\lambda_{2}^{\prime\prime}=\lambda_{1}+\lambda_{2}+2\Delta+2\delta=1-\frac{1}{4}(1-\lambda_{1}-\lambda_{2})<1$,
the states $\xi_{m}$ must be pairwise distinct, and that gives us

$N\leq|{\cal Z}|\leq\left(\frac{5}{\delta}\right)^{2|A^{n}||R|},$

i.e.

$\log\log N\leq
n\log|A|+\log\frac{2304}{(1-\lambda_{1}-\lambda_{2})^{2}}+\log\log\frac{120}{1-\lambda_{1}-\lambda_{2}},$

which is the desired bound.  $\sqcap$$\sqcup$

######  Corollary 6.4.

If the channel ${\cal N}\mathrel{\mathop{\mathchar 58\relax}}A\rightarrow B$
is entanglement-breaking, or more generally PPT-entanglement-binding, then
$C_{\text{ID}}({\cal N})\leq\log|A|$, and this is a strong converse bound for
all $\lambda_{1},\lambda_{2}>0$ with $\lambda_{1}+\lambda_{2}<1$.

###### Proof.

For entanglement-breaking channels, this follows from Theorem 6.3 because the
channel is a composition of a destructive measurement ${\cal M}$ with a cq-
channel ${\cal N}^{\prime}$, i.e. ${\cal N}={\cal N}^{\prime}\circ{\cal M}$.
Thus,

$C_{\text{ID}}({\cal N})\leq C_{\text{ID}}({\cal
M})=C_{\text{ID}}^{\text{sim}}({\cal M})\leq\log|A|,$

the middle equality because ${\cal M}$ already outputs the result of a
measurement, and the same for the maximum code size as a function of error
probabilities and block length.

The more general PPT-entanglement-binding case is even simpler: the states
$\omega^{A_{R}^{n}B^{n}}=({\operatorname{id}}_{A_{R}^{n}}\otimes{\cal
N}^{\otimes n})\Phi_{\sigma}^{A_{R}^{n}A^{n}}$ from the proof of Theorem 3.3
(cf. also Theorem 6.3) are all PPT, in particular undistillable. Thus, the
reduction criterion applies,
$\omega^{A^{n}_{R}B^{n}}\leq{\openone}_{A^{n}_{R}}\otimes\omega^{B^{n}}$ [75],
hence

$H_{\min}^{\epsilon}(A_{R}^{n}|B^{n})_{\omega}\geq
H_{\min}(A_{R}^{n}|B^{n})_{\omega}\geq 0,$

and the rest of the argument is as in the proof of Theorem 6.3.
$\sqcap$$\sqcup$

######  Theorem 6.5.

The classical identification capacity of a general quantum channel ${\cal
N}\mathrel{\mathop{\mathchar 58\relax}}A\rightarrow B$ is bounded from above
as $C_{\text{ID}}({\cal N})\leq\log|A|+\widehat{Q}({\cal N})$, where
$\widehat{Q}({\cal N})$ is the strong converse quantum capacity of ${\cal N}$.

###### Proof.

This comes from the fact that the resolvability capacity of a quantum channel
is upper bounded by the strong converse quantum capacity, $R({\cal
N})\leq\widehat{Q}({\cal N})$. Then we use the net argument on the input as
before in the proof of Theorem 6.3, but with an auxiliary space of dimension
$|R|=2^{n\widehat{Q}({\cal N})+o(n)}$. This gives us the desired result.
$\sqcap$$\sqcup$

##  7 Proofs of quantum source coding results

### 7.1 Proof of Proposition 4.2

Consider a state $\rho^{B}\in\mathcal{D}(B)$ and a channel
$\mathcal{N}_{V}\mathrel{\mathop{\mathchar 58\relax}}B\rightarrow A$. Let
$V\mathrel{\mathop{\mathchar 58\relax}}B\rightarrow A\otimes E$ be an
isometric extension of $\mathcal{N}_{V}$ with $\dim(E)>\dim(B)$. Let the
spectral decomposition of
$\rho^{A}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathcal{N}_{V}(\rho^{B})$
and $\rho^{B}$ be given by
$\rho^{A}=\sum_{a\in\mathcal{A}}\lambda_{a}\outerproduct{a}{a}$, and
$\rho^{B}=\sum_{b\in\mathcal{B}}\mu_{b}\outerproduct{b}{b}$, for some finite
sets $\mathcal{A}$ and $\mathcal{B}$. From (13), we have

$\displaystyle
W\ket{a}^{{A_{R}}}=\sum_{b}\sqrt{\frac{\mu_{b}}{\lambda_{a}}}\ket{b}^{{B_{R}}}\otimes\langle
a|V|b\rangle,$ (18)

where
$\ket{a}^{{A_{R}}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\openone}_{{A_{R}}}\otimes\bra{a}^{A})\ket{\Gamma}_{{A_{R}}A}$
and
$\ket{b}^{{B_{R}}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\openone}_{{B_{R}}}\otimes\bra{b}^{B})\ket{\Gamma}_{{B_{R}}B}$
for fixed maximally entangled states $\ket{\Gamma}_{{A_{R}}A}$ and
$\ket{\Gamma}_{{B_{R}}B}$ on the Hilbert spaces ${A_{R}}\otimes A$ and
${B_{R}}\otimes B$, respectively.

Consider an arbitrary density operator
$\sigma^{{A_{R}}}\in\mathcal{D}({{A_{R}}}),$ and let
$\sigma^{{A_{R}}}=\sum_{a,a^{\prime}}\theta_{aa^{\prime}}\ket{a}\bra{a^{\prime}}^{{A_{R}}}$
be its matrix representation, and then
$\sigma^{A}=(\sigma^{{A_{R}}})^{T}=\sum_{a,a^{\prime}}\theta_{aa^{\prime}}\ket{a^{\prime}}\bra{a}^{A}.$
Then

$\displaystyle\mathcal{N}_{W}(\sigma^{{A_{R}}})$
$\displaystyle=\sum_{b,b^{\prime}}\sum_{a,a^{\prime}}\sqrt{\frac{\mu_{b}\mu_{b^{\prime}}}{\lambda_{a}\lambda_{a^{\prime}}}}\theta_{aa^{\prime}}\ket{b}\bra{b^{\prime}}^{{B_{R}}}\left[{{}_{B}\langle
b^{\prime}|V^{\dagger}(|a^{\prime}\rangle\langle
a|\otimes{\openone}_{E})V|b\rangle_{B}}\right]$
$\displaystyle=\sum_{b,b^{\prime}}\sum_{a,a^{\prime}}\sqrt{{\mu_{b}\mu_{b^{\prime}}}}\ket{b}\bra{b^{\prime}}^{{B_{R}}}\left[{{}_{B}\langle
b^{\prime}|V^{\dagger}\left({(\rho^{A})^{-1/2}\sigma^{A}(\rho^{A})^{-1/2}\otimes{\openone}_{E}}\right)V|b\rangle_{B}}\right]$
$\displaystyle=\sum_{b,b^{\prime}}\sum_{a,a^{\prime}}\sqrt{{\mu_{b}\mu_{b^{\prime}}}}\ket{b}\bra{b^{\prime}}^{{B_{R}}}\left[{{}_{B}\langle
b^{\prime}|\mathcal{N}_{V}^{\dagger}\left({(\rho^{A})^{-1/2}\sigma^{A}(\rho^{A})^{-1/2}}\right)|b\rangle_{B}}\right]$
$\displaystyle\stackrel{{\scriptstyle
a}}{{=}}\sum_{b,b^{\prime}}\sum_{a,a^{\prime}}\sqrt{{\mu_{b}\mu_{b^{\prime}}}}\ket{b}\bra{b^{\prime}}^{{B_{R}}}\left[{{}_{{B_{R}}}\langle
b|\left({\mathcal{N}_{V}^{\dagger}\left({(\rho^{A})^{-1/2}\sigma^{A}(\rho^{A})^{-1/2}}\right)}\right)^{T}|b^{\prime}\rangle_{{B_{R}}}}\right]$
$\displaystyle=(\rho^{{B_{R}}})^{1/2}\left({\mathcal{N}_{V}^{\dagger}\left({(\rho^{A})^{-1/2}\sigma^{A}(\rho^{A})^{-1/2}}\right)}\right)^{T}(\rho^{{B_{R}}})^{1/2},$
(19)

where $(a)$ follows from the definition of transpose. Therefore the action of
a posterior reference map is equal to suitably defined Petz recovery channel
acting on the reference Hilbert space.

### 7.2 Proof of Lemma 4.6

The first part of the lemma follows using the monotonicity of trace norm by
partial tracing the states in (14) over the subsystem ${A}^{\otimes n},$
observing that
$\Tr_{A^{n}}{\omega^{B_{R}^{n}A^{n}}}=\left({\rho^{B_{R}}}\right)^{\otimes
n}$, and noting that the restriction of decoding being an isometry maintains
the rank of $\omega^{A_{R}^{n}}$ to be at most $\Theta$.

For the converse direction, we perform the following analysis. Given a pair
$(\rho^{{B_{R}}},\mathcal{N}_{W})$, and an $(n,\Theta,\epsilon)$ covering code
$\sigma^{A_{R}^{n}}$, let $\Psi^{A_{R}^{n}A^{n}}_{\sigma}$ be the canonical
purification of the $\sigma^{A_{R}^{n}}$. We know from (3) that

$\displaystyle\|\left({\rho^{B_{R}}}\right)^{\otimes
n}-\mathcal{N}_{W}^{\otimes n}(\sigma^{A_{R}^{n}})\|_{1}\leq\epsilon.$ (20)

Note that $|\sigma^{A_{R}^{n}}|=\Theta$. Define
$\mathcal{H}_{\sigma}\subset{A^{n}}$ as the support of
$\Tr_{A_{R}^{n}}[\Psi^{A_{R}^{n}A^{n}}_{\sigma}]$, while noting that
$\dim(\mathcal{H}_{\sigma})=\Theta$. Let $W\mathrel{\mathop{\mathchar
58\relax}}{A_{R}}\rightarrow{B_{R}}\otimes E$ be a Stinespring extension of
$\mathcal{N}_{W}$ with $\mbox{dim}(E)\geq\mbox{dim}({B_{R}})$. Consider the
quantum state

$\omega^{B_{R}^{n}E^{n}A^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(W^{\otimes
n}\otimes{\openone}_{A^{n}})\Psi^{A_{R}^{n}A^{n}}_{\sigma}(W^{\otimes
n}\otimes{\openone}_{A^{n}})^{\dagger},$

defined on ${B_{R}^{n}}\otimes{E^{n}}\otimes\mathcal{H}_{\sigma}$. Let
$\tilde{V}\mathrel{\mathop{\mathchar
58\relax}}{B^{n}}\rightarrow\mathcal{H}_{\sigma}\otimes{E^{n}}$ be the
posterior reference isometry of $W^{\otimes n}$ with respect to
$\omega^{B_{R}^{n}}$. Note that $\tilde{V}$ is a non-product $n$-letter
isometry. Using the property of the reference map, we have

$\omega^{B_{R}^{n}E^{n}A^{n}}=(W^{\otimes
n}\otimes{\openone}_{A^{n}})\Psi^{A_{R}^{n}A^{n}}_{\sigma}(W^{\otimes
n}\otimes{\openone}_{A^{n}})^{\dagger}=({\openone}_{B_{R}^{n}}\otimes\tilde{V})\Psi^{B_{R}^{n}B^{n}}_{\omega}({\openone}_{B_{R}^{n}}\otimes\tilde{V})^{\dagger},$

where $\Psi^{B_{R}^{n}B^{n}}_{\omega}$ is the canonical purification of
$\omega^{B_{R}^{n}}=\mathcal{N}_{W}^{\otimes n}(\sigma^{A_{R}^{n}})$. We use
the CPTP map $\mathcal{N}_{\tilde{V}}^{(n)}$ given by
$\Tr_{E^{n}}[\tilde{V}\cdot\tilde{V}^{\dagger}]$ as the encoder-decoder pair
${\mathcal{D}}^{(n)}\circ{\mathcal{E}}^{(n)}$ for the lossy source coding
protocol resulting in the quantum state

$\tau^{B_{R}^{n}A^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\operatorname{id}}_{B_{R}^{n}}\otimes\mathcal{N}_{\tilde{V}}^{(n)})(\Psi_{\rho}^{B_{R}B})^{\otimes
n},$

where $\Psi^{B_{R}B}_{\rho}$ is the canonical purification of $\rho^{B_{R}}$.
Furthermore, define the quantum state

$\lambda^{B_{R}^{n}A^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mathcal{N}_{W}^{\otimes
n}\otimes{\operatorname{id}}_{A^{n}})\Psi^{A_{R}^{n}A^{n}}_{\tau},$

where $\Psi^{A_{R}^{n}A^{n}}_{\tau}$ is the canonical purification of
$\tau^{A^{n}}=\Tr_{B_{R}^{n}}[\tau^{B_{R}^{n}A^{n}}]$. Consider the trace
distance between the states $\tau$ and $\lambda$ as follows:

$\displaystyle\|\tau^{B_{R}^{n}A^{n}}$
$\displaystyle-\lambda^{B_{R}^{n}A^{n}}\|_{1}\leq\|\omega^{B_{R}^{n}A^{n}}-\tau^{B_{R}^{n}A^{n}}\|_{1}+\|\omega^{B_{R}^{n}A^{n}}-\lambda^{B_{R}^{n}A^{n}}\|_{1}$
$\displaystyle=\left\|({\operatorname{id}}_{B_{R}^{n}}\otimes\mathcal{N}_{\tilde{V}}^{(n)})\left({\Psi_{\omega}^{B_{R}^{n}B^{n}}-(\Psi^{B_{R}B}_{\rho})^{\otimes
n}}\right)\right\|+\|(\mathcal{N}_{W}^{\otimes
n}\otimes{\operatorname{id}}_{A^{n}})\left({\Psi_{\sigma}^{A_{R}^{n}A^{n}}-\Psi_{\tau}^{A_{R}^{n}A^{n}}}\right)\|_{1}$
$\displaystyle\overset{(a)}{\leq}\|\Psi_{\omega}^{B_{R}^{n}B^{n}}-(\Psi_{\rho}^{B_{R}B})^{\otimes
n}\|_{1}+\|\Psi_{\sigma}^{A_{R}^{n}A^{n}}-\Psi_{\tau}^{A_{R}^{n}A^{n}}\|_{1}$
$\displaystyle\overset{(b)}{\leq}2\sqrt{\|\omega^{B_{R}^{n}}-\rho^{B_{R}^{\otimes
n}}\|_{1}}+2\sqrt{\|\sigma^{A^{n}}-\tau^{A^{n}}\|_{1}}$
$\displaystyle\overset{(c)}{\leq}2\sqrt{\epsilon}+2\sqrt{\|\mathcal{N}_{\tilde{V}}^{(n)}(\omega^{B^{n}})-\mathcal{N}_{\tilde{V}}^{(n)}(\rho^{B^{\otimes
n}})\|_{1}}$
$\displaystyle\overset{(d)}{\leq}2\sqrt{\epsilon}+2\sqrt{\|\omega^{B^{n}}-\rho^{B^{\otimes
n}}\|_{1}}$
$\displaystyle\overset{(e)}{=}2\sqrt{\epsilon}+2\sqrt{\|\mathcal{N}_{W}^{\otimes
n}(\sigma^{A_{R}^{n}})-\rho^{B_{R}^{\otimes n}}\|_{1}}$
$\displaystyle\overset{(f)}{\leq}4\sqrt{\epsilon},$

where (a) follows from the monotonicity of trace distance, (b) follows from
the Lemmas 2.6 and 2.7, and appropriate identification of canonical
purifications, (c) uses the result of covering (20) and defines
$\omega^{B^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\Tr_{B_{R}^{n}}{\Psi^{B_{R}^{n}B^{n}}_{\omega}}$,
and (d) again uses monotonicity of trace distance, (e) follows from invariance
of trace norm under transposition, and (f) again uses the covering result
(20). Since $\mathcal{N}_{\tilde{V}}^{(n)}$ is a CPTP map from ${B_{R}^{n}}$
to $\mathcal{H}_{\sigma}$, and $|\mathcal{H}_{\sigma}|=\Theta$, the lossy
source code also satisfies the rate constraint. This completes the proof.

### 7.3 Proof of converse for Theorem 4.7

Given a pair ($\rho^{B},\mathcal{N}_{W}$), and any $\epsilon\in(0,1)$,
consider an $(1,\Theta,\epsilon)$ lossy compression protocol with an encoding
CPTP map $\mathcal{E}$ and a decoding CPTP map $\mathcal{D}$ that satisfies
the following constraint:

$\displaystyle c_{1}\mathrel{\mathop{\mathchar
58\relax}}\|\omega^{{B_{R}}A}-\upsilon^{{B_{R}}A}\|_{1}\leq\epsilon,$ (21)

where
$\omega^{{B_{R}}A}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(I\otimes\mathcal{D}\circ\mathcal{E})(\Psi_{\rho}^{{B_{R}}B})$,

$\upsilon^{{B_{R}}A}=\Tr_{E}\left\\{\upsilon^{{B}_{R}AE}\right\\}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\Tr_{E}\left\\{(W\otimes{\openone})\Psi_{\omega}^{{A_{R}}A}(W\otimes{\openone})^{\dagger}\right\\},$

and $\Psi_{\rho}^{{B_{R}}B}$ and $\Psi_{\omega}^{A{A_{R}}}$ are the canonical
purifications of $\rho^{B}$ and $\omega^{A}$, respectively, and $W$ is the
Stinespring’s dilation of the CPTP map $\mathcal{N}_{W}$. Let
$\omega^{A_{R}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\Tr_{A}(\Psi_{\omega}^{AA_{R}})$.

Let $M$ denote the quantum state at the output of the encoder. Let
$V_{\mathcal{E}}\mathrel{\mathop{\mathchar 58\relax}}{B}\rightarrow
M\otimes{\tilde{E}_{1}}$ and $V_{\mathcal{D}}\mathrel{\mathop{\mathchar
58\relax}}{M}\rightarrow{A}\otimes{\tilde{E}_{2}}$ be Stinesping dilations of
encoding and decoding maps ${\mathcal{E}}$ and ${\mathcal{D}}$, respectively,
such that $\dim({\tilde{E}_{1}})\geq\dim(M)$ and
$\dim({\tilde{E}_{2}})\geq\dim({A})$, as shown in Figure 3(a). Let

$\displaystyle{\omega_{1}}^{{B_{R}}M\tilde{E}_{1}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\openone}_{{B_{R}}}\otimes
V_{\mathcal{E}})(\Psi_{\rho}^{{B_{R}}B})({\openone}_{{B_{R}}}\otimes
V_{\mathcal{E}})^{\dagger},$
$\displaystyle\quad{\omega}^{{B_{R}}\tilde{E}_{1}\tilde{E}_{2}A}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\openone}_{{B_{R}}\tilde{E}_{1}}\otimes
V_{\mathcal{D}})({\omega_{1}}^{{B_{R}}\tilde{E}_{1}M})({\openone}_{{B_{R}}\tilde{E}_{1}}\otimes
V_{\mathcal{D}})^{\dagger}.$ (22)

Figure 3: A One-shot lossy quantum source coding protocol and the associated
CPTP maps and their Stinespring dilations.

Let $\Psi_{\omega_{1}}^{M_{R}M}$ denote the canonical purification of the
quantum state $\omega_{1}^{M}$. Let
$W_{\mathcal{E}}^{(n)}\mathrel{\mathop{\mathchar
58\relax}}{M_{R}}\rightarrow{{B_{R}}}\otimes{\tilde{E}_{1}}$ denote the
posterior reference isometry (see Definition 4.1) of $V_{\mathcal{E}}$ with
respect to $\omega_{1}^{M}$, as shown in Figure 3(b). Moreover, let
$W_{\mathcal{D}}\mathrel{\mathop{\mathchar
58\relax}}{{A_{R}}}\rightarrow{M_{R}}\otimes{\tilde{E}_{2}}$ denote the
posterior reference isometry of $V_{\mathcal{D}}$ with respect to $w^{A}$, as
shown in Figure 3(c). Let
$\mathcal{N}_{W_{\mathcal{E}}}(\cdot)=\Tr_{\tilde{E_{1}}}(W_{\mathcal{E}}\cdot(W_{\mathcal{E}})^{\dagger})$
and
$\mathcal{N}_{W_{\mathcal{D}}}(\cdot)=\Tr_{\tilde{E_{2}}}(W_{\mathcal{D}}\cdot(W_{\mathcal{D}})^{\dagger})$
be the induced CPTP maps. Let

$\tilde{\omega}_{1}^{M_{R}\tilde{E}_{2}A}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(W_{\mathcal{D}}\otimes{\openone}_{A})(\Psi_{\omega}^{A_{R}^{n}A})(W_{\mathcal{D}}\otimes{\openone}_{A})^{\dagger}.$

By the definition of the posterior maps, we have

$\displaystyle{\omega}^{B_{R}\tilde{E}_{1}\tilde{E}_{2}A}=(W_{\mathcal{E}}\otimes{\openone}_{\tilde{E}_{2}A})\tilde{\omega}_{1}^{M_{R}\tilde{E}_{2}A}(W_{\mathcal{E}}\otimes{\openone}_{\tilde{E}_{2}A})^{\dagger}.$

We have the following sequence of inequalities:

$\displaystyle\log\Theta$
$\displaystyle{\geq}\log\min\\{\mbox{rank}\left({\tilde{\omega}_{1}^{A}}\right),\mbox{rank}\left({\tilde{\omega}_{1}^{M_{R}}}\right)\\}$
$\displaystyle\overset{(a)}{\geq}-H_{\min}(A|M_{R})_{\tilde{\omega}_{1}}$
$\displaystyle\overset{(b)}{\geq}-H_{\min}(A|B_{R})_{\omega}$
$\displaystyle\overset{(c)}{\geq}-H_{\min}^{\sqrt{\epsilon}}(A|B_{R})_{\upsilon}$
$\displaystyle\overset{(d)}{=}-H_{\min}^{\sqrt{\epsilon}}(A|B_{R})_{\upsilon(\omega^{A_{R}})}$
$\displaystyle\overset{(e)}{\geq}-\sup_{\sigma^{A_{R}}\mathrel{\mathop{\mathchar
58\relax}}\|\rho^{B_{R}}-\mathcal{N}_{W}(\sigma^{A_{R}})\|_{1}\leq\epsilon}H_{\min}^{\sqrt{\epsilon}}(A|B_{R})_{\upsilon(\sigma^{A_{R}})},$
(23)

where (a) follows from [24, Lemma 5.11], (b) follows from the quantum data
processing inequality for min-entropy [24, Corollary 3.5], (c) follows from
the $(c_{1})$ condition which implies that the corresponding purified distance
is no greater than $\sqrt{\epsilon}$, (d) follows by defining
$\upsilon(\omega^{A_{R}})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mathcal{N}_{W}\otimes{\openone}_{A})\Psi_{\omega}^{A_{R}A}$,
and (e) again follows from the condition $(c_{1})$, the monotonicity of the
trace distance, and by noting that
$\|\Tr_{A}\left({\upsilon(\omega^{A_{R}})}\right)-\rho^{{B_{R}}}\|_{1}\leq\epsilon$.

### 7.4 Proof of converse for Theorem 4.8

For the converse, we proceed as follows. Let $R$ be achievable. Using the
result from Theorem 4.7, for any $\epsilon>0$, we get

$\displaystyle nR$
$\displaystyle\geq\log\Theta-n\epsilon\geq\inf_{\sigma^{A^{n}_{R}}\mathrel{\mathop{\mathchar
58\relax}}\|(\rho^{B_{R}})^{\otimes n}-\mathcal{N}_{W}^{\otimes
n}(\sigma^{A^{n}_{R}})\|_{1}\leq\epsilon}-H_{\min}^{\sqrt{\epsilon}}(A^{n}|B^{n}_{R})_{\rho^{B_{R}^{n}A^{n}}}-n\epsilon,$

where
$\rho^{B_{R}^{n}A^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}({\operatorname{id}}\otimes\mathcal{N}_{W}^{\otimes
n})\Phi_{\sigma}^{A^{n}_{R}A^{n}}$ with $\Phi_{\sigma}^{A^{n}_{R}A^{n}}$
denoting a purification of $\sigma^{A^{n}}$.

Using [24, Lemma 6.12], we note that there exists an embedding from $A^{n}$ to
$A^{\prime}$ and a normalized state $\tau^{A^{\prime}B^{n}}$ in
$\mathscr{B}^{\sqrt{\epsilon}}(A^{\prime}B_{R}^{n};\rho^{B_{R}^{n}A^{\prime}}))$
such that
$H_{\min}^{\sqrt{\epsilon}}(A^{n}_{R}|B^{n})_{\rho^{B_{R}^{n},A^{\prime}}}=H_{\min}(A^{\prime}_{R}|B^{n})_{\tau}$,
where $\rho^{B_{R}^{n}A^{\prime}}$ is the corresponding embedding of
$\rho^{B_{R}^{n}A^{n}}$, with $\dim(A^{\prime})=2(\dim(A))^{n}$.

We next use the fact that $H_{\min}(\cdot|\cdot)\leq S(\cdot|\cdot)$, and
Lemma 2.6 and AFW inequality regarding the continuity of conditional entropy
[35, Theorem 11.10.3] to infer that

$-H_{\min}^{\sqrt{\epsilon}}(A^{n}|B^{n}_{R})_{\rho^{B_{R}^{n}A^{n}}}=H_{\min}(A^{\prime}_{R}|B^{n})_{\tau}\geq-S(A^{\prime}|B^{n}_{R})_{\tau}\geq-S(A^{n}|B^{n}_{R})_{\rho}-n\tilde{\epsilon_{1}},$

where
$\tilde{\epsilon_{1}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}2\sqrt{\epsilon}\log(2|A|)+\frac{(1+\sqrt{\epsilon})}{n}h_{2}\left(\frac{\sqrt{\epsilon}}{1+\sqrt{\epsilon}}\right)$,
and we use the invariance of conditional entropy under embeddings. Thus we
have

$nR\geq\inf_{\sigma^{A^{n}_{R}}\mathrel{\mathop{\mathchar
58\relax}}\|(\rho^{B_{R}})^{\otimes n}-\mathcal{N}_{W}^{\otimes
n}(\sigma^{A^{n}_{R}})\|_{1}\leq\epsilon}-S(A^{n}|B^{n}_{R})_{\rho}-n\tilde{\epsilon_{1}}-n\epsilon.$

Observe that the above equation is now similar to (7) obtained in the converse
of Theorem 3.5. Using similar arguments as in the converse of Theorem 3.5 we
obtain the desired result.

##  8 Conclusions and future work

This work formulates the problem of quantum soft-covering in its most natural
setting, and presents a one-shot characterization of the problem in terms of
smoothed one-shot quantum entropic quantities. By leveraging the one-shot
result, we provide a single-letter characterization of the optimal rate of the
quantum soft-covering problem in terms of the minimal coherent information. We
also contribute to the study of second-order asymptotics and provide
achievability bounds for the same. As a part of future work, we aim to study
optimal second order performance limits for the formulated quantum soft-
covering problem. Furthermore, then we explore three applications of the
quantum soft-covering lemma, including the characterization of a one-shot
lossy quantum source coding problem, the formulation of a quantum channel
resolvability problem, and separations between simultaneous and unrestricted
capacities for identification via quantum channels. For the channel
resolvability, we provide a lower bound, and conjecture that it is equal to
the quantum transmission capacity of the given quantum channel.

## Acknowledgements

The authors thank David Neuhoff and Mohammad Aamir Sohail for their
contributions and discussions on the subject matter of the present paper. AW
furthermore acknowledges earlier conversations with Paul Cuff and Zahra
Khanian regarding a different approach to quantum soft covering.

TAA and SSP are supported in part by National Science Foundation grant
CCF-2007878. AW is supported by the European Commission QuantERA grant ExTRaQT
(Spanish MICINN project PCI2022-132965), by the Spanish MICINN (project
PID2019-107609GB-I00) with the support of FEDER funds, by the Spanish MICINN
with funding from European Union NextGenerationEU (PRTR-C17.I1) and the
Generalitat de Catalunya, by the Alexander von Humboldt Foundation, and the
Institute for Advanced Study of the Technical University Munich.

## References

  * [1] Alexander S. Holevo.  The capacity of the quantum channel with general signal states.  IEEE Transactions on Information Theory, 44(1):269–273, 1998.
  * [2] Benjamin Schumacher and Michael D. Westmoreland.  Sending classical information via noisy quantum channels.  Physical Review A, 56(1):131–138, 1997.
  * [3] Daniel Gottesman.  An introduction to quantum error correction.  In Proceedings of Symposia in Applied Mathematics, volume 58, pages 221–236, 2002.
  * [4] Daniel A. Lidar and Todd A. Brun.  Quantum Error Correction.  Cambridge University Press, 2013.
  * [5] Ning Cai, Andreas Winter, and Raymond W. Yeung.  Quantum privacy and quantum wiretap channels.  Problems of Information Transmissions, 40:318–336, 2004.  doi:10.1007/s11122-005-0002-x.
  * [6] Igor Devetak.  The private classical capacity and quantum capacity of a quantum channel.  IEEE Transactions on Information Theory, 51(1):44–55, 2005.
  * [7] Igor Devetak and Andreas Winter.  Relating quantum privacy and quantum coherence: an operational approach.  Physical Review Letters, 93(8):080501, 2004.
  * [8] Rudolf Ahlswede and Andreas Winter.  Strong converse for identification via quantum channels.  IEEE Transactions on Information Theory, 48(3):569–579, 2002.
  * [9] Jaikumar Radhakrishnan, Pranab Sen, and Naqueeb Ahmad Warsi.  One-shot private classical capacity of quantum wiretap channelb based on one-shot quantum covering lemma.  arXiv preprint arXiv:1703.01932, 2017.
  * [10] Andreas Winter.  ‘Extrinsic’ and ‘intrinsic’ data in quantum measurements: asymptotic convex decomposition of positive operator valued measures.  Communication in Mathematical Physics, 244(1):157–185, 2004.
  * [11] Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, and Andreas Winter.  The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels.  IEEE Transactions on Information Theory, 60(5):2926–2959, 2014\.
  * [12] Jianxin Chen and Andreas Winter.  Non-additivity of the entanglement of purification (beyond reasonable doubt).  arXiv:1206.1307, 2012.
  * [13] Yu-Chen Shen, Li Gao, and Hao-Chung Cheng.  Optimal second-order rates for quantum soft covering and privacy amplification.  arXiv:2202.11590, 2022.
  * [14] Aaron D. Wyner.  The Wire-Tap Channel.  Bell Systems Technical Journal, 54(8):1355–1387, 1975.  doi:10.1002/j.1538-7305.1975.tb02040.x.
  * [15] Aaron D. Wyner.  The common information of two dependent random variables.  IEEE Transactions on Information Theory, 21(2):163–179, 1975.  doi:10.1109/TIT.1975.1055346.
  * [16] Charles H. Bennett, Peter W. Shor, John A. Smolin, and Asish V. Thapliyal.  Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem.  IEEE Transactions on Information Theory, 48(10):2637–2655, 2002\.  doi:10.1109/TIT.2002.802612.
  * [17] Paul W. Cuff, Haim H. Permuter, and Thomas M. Cover.  Coordination capacity.  IEEE Transactions on Information Theory, 56(9):4181–4206, 2010\.
  * [18] Paul Cuff.  Distributed channel synthesis.  IEEE Transactions on Information Theory, 59(11):7071–7096, 2013\.
  * [19] Serge Massar and Sandu Popescu.  Amount of information obtained by a quantum measurement.  Physical Review A, 61(6):062303, 2000.
  * [20] Andreas Winter and Serge Massar.  Compression of quantum-measurement operations.  Physical Review A, 64(1):012311, 2001.
  * [21] Hao-Chung Cheng and Li Gao.  Error exponent and strong converse for quantum soft covering.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 1318–1323. IEEE, 2022.
  * [22] Touheed Anwar Atif and S Sandeep Pradhan.  Distributed quantum faithful simulation and function computation using algebraic structured measurements.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 124–129. IEEE, 2021.
  * [23] Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi.  Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction.  IEEE Transactions on Information Theory, 65(9):5905–5924, 2019\.
  * [24] Marco Tomamichel.  Quantum Information Processing with Finite Resources: Mathematical Foundations, volume 5 of Springer Briefs in Mathematical Physics.  Springer, 2021.
  * [25] Volker Strassen.  Asymptotische Abschätzungen in Shannon’s Informationstheorie.  In Transactions of the Third Prague Conference on Information Theory etc, 1962. Czechoslovak Academy of Sciences, Prague, pages 689–723, 1962\.
  * [26] Masahito Hayashi.  Information spectrum approach to second-order coding rate in channel coding.  IEEE Transactions on Information Theory, 55(11):4947–4966, 2009\.
  * [27] Yury Polyanskiy, H. Vincent Poor, and Sergio Verdú.  Channel coding rate in the finite blocklength regime.  IEEE Transactions on Information Theory, 56(5):2307–2359, 2010\.
  * [28] Mohammad Hossein Yassaee, Mohammad Reza Aref, and Amin Gohari.  A technique for deriving one-shot achievability results in network information theory.  In 2013 IEEE International Symposium on Information Theory, pages 1287–1291. IEEE, 2013.
  * [29] Marco Tomamichel and Masahito Hayashi.  A hierarchy of information quantities for finite block length analysis of quantum tasks.  IEEE Transactions on Information Theory, 59(11):7693–7710, 2013\.
  * [30] Ke Li.  Second-order asymptotics for quantum hypothesis testing.  The Annals of Statistics, 42(1):171–189, 2014.  doi:10.1214/13-AOS1185.
  * [31] Salman Beigi and Amin Gohari.  Quantum achievability proof via collision relative entropy.  IEEE Transactions on Information Theory, 60(12):7980–7986, 2014\.
  * [32] Salman Beigi, Nilanjana Datta, and Felix Leditzky.  Decoding quantum information via the petz recovery map.  Journal of Mathematical Physics, 57(8):082203, 2016.
  * [33] Touheed Anwar Atif, Mohammad Aamir Sohail, and S. Sandeep Pradhan.  Lossy Quantum Source Coding with a Global Error Criterion based on a Posterior Reference Map.  arXiv[quant-ph]:2302.00625, 2023.
  * [34] Masahito Hayashi.  General nonasymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to the wiretap channel.  IEEE Transactions on Information Theory, 52(4):1562–1575, 2006\.
  * [35] Mark M. Wilde.  From classical to quantum shannon theory.  arXiv preprint arXiv:1106.1445, 2011.
  * [36] Christopher A. Fuchs and Jeroen van de Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, 1999\.
  * [37] Alexander Vitanov, Frederic Dupuis, Marco Tomamichel, and Renato Renner.  Chain rules for smooth min- and max-entropies.  IEEE Transactions on Information Theory, 59(5):2603–2612, 2013\.
  * [38] Marco Tomamichel.  A Framework for Non-asymptotic Quantum Information Theory.  PhD thesis, ETH Zürich, 2012.  arXiv:1203.2142.
  * [39] Ciara Morgan and Andreas Winter.  ‘Pretty strong’ converse for the quantum capacity of degradable channels.  IEEE Transactions on Information Theory, 60(1):317–333, 2013.
  * [40] Frédéric Dupuis, Mario Berta, Jürg Wullschleger, and Renato Renner.  One-shot decoupling.  Communications in Mathematical Physics, 328:251–284, 2014.
  * [41] Mario Berta.  Single-shot quantum state merging.  Master’s thesis, ETH Zurich, 2009.  arXiv[quant-ph]:0912.4495.
  * [42] Marco Tomamichel, Roger Colbeck, and Renato Renner.  A fully quantum asymptotic equipartition property.  IEEE Transactions on information theory, 55(12):5840–5847, 2009\.
  * [43] Howard Barnum.  Quantum rate-distortion coding.  Physical Review A, 62(4):042309, 2000.
  * [44] Nilanjana Datta, Min-Hsiu Hsieh, and Mark M. Wilde.  Quantum rate distortion, reverse shannon theorems, and source-channel separation.  IEEE Transactions on Information Theory, 59(1):615–630, 2012.
  * [45] Mark M. Wilde, Nilanjana Datta, Min-Hsiu Hsieh, and Andreas Winter.  Quantum rate-distortion coding with auxiliary resources.  IEEE Transactions on Information Theory, 59(10):6755–6773, 2013\.
  * [46] Nilanjana Datta, Min-Hsiu Hsieh, Mark M. Wilde, and Andreas Winter.  Quantum-to-classical rate distortion coding.  Journal of Mathematical Physics, 54(4):042201, 2013.
  * [47] Nilanjana Datta, Joseph M. Renes, Renato Renner, and Mark M. Wilde.  One-shot lossy quantum data compression.  IEEE Transactions on Information Theory, 59(12):8057–8076, 2013\.
  * [48] Zahra Baghali Khanian and Andreas Winter.  A Rate-Distortion Perspective on Quantum State Redistribution.  arXiv[quant-ph]:2112.11952, 2021.
  * [49] Zahra Baghali Khanian and Andreas Winter.  General Mixed-State Quantum Data Compression With and Without Entanglement Assistance.  IEEE Transactions on Information Theory, 68(5):3130–3138, 2022\.
  * [50] Zahra Baghali Khanian, Kohdai Kuroiwa, and Debbie Leung.  Rate-Distortion Theory for Mixed States.  arXiv[quant-ph]:2208.11698, 2022.
  * [51] Masato Koashi and Nobuyuki Imoto.  Compressibility of quantum mixed-state signals.  Physical Review Letters, 87(1):017902, 2001.
  * [52] Igor Devetak and Toby Berger.  Quantum rate-distortion theory for memoryless sources.  IEEE Transactions on Information Theory, 48(6):1580–1589, 2002\.
  * [53] Andreas Winter.  Compression of sources of probability distributions and density operators.  arXiv:quant-ph/0208131, 2002.
  * [54] Min-Hsiu Hsieh and Shun Watanabe.  Channel simulation and coded source compression.  IEEE Transactions on Information Theory, 62(11):6609–6619, 2016\.
  * [55] Sina Salek, Daniela Cadamuro, Philipp Kammerlander, and Karoline Wiesner.  Quantum rate-distortion coding of relevant information.  IEEE Transactions on Information Theory, 65(4):2603–2613, 2018\.
  * [56] Shlomo Shamai and Sergio Verdú.  The empirical distribution of good codes.  IEEE Transactions on Information Theory, 43(3):836–846, 1997.
  * [57] S. Sandeep Pradhan.  Approximation of test channels in source coding.  In Proc. 2004 Conference on Information Sciences and Systems (CISS), 2004.
  * [58] Dénes Petz.  Sufficient subalgebras and the relative entropy of states of a von neumann algebra.  Communications in Mathematical Physics, 105(1):123–131, 1986.
  * [59] Imre Csiszár and János Körner.  Information theory: coding theorems for discrete memoryless systems.  Cambridge University Press, 2nd edition, 2011.
  * [60] S Sandeep Pradhan, Jim Chou, and Kannan Ramchandran.  Duality between source coding and channel coding and its extension to the side information case.  IEEE Transactions on Information Theory, 49(5):1181–1203, 2003\.
  * [61] Te Sun Han and Sergio Verdú.  New results in the theory of identification via channels.  IEEE Transactions on Information Theory, 38(1):14–25, 1992.
  * [62] Peter Löber.  Quantum channels and simultaneous ID coding.  PhD thesis, Department of Mathematics, Universität Bielefeld, July 1999\.  URL: http://nbn-resolving.de/urn:nbn:de:hbz:361-1473.
  * [63] Francesco Buscemi and Nilanjana Datta.  One-shot quantum capacities of quantum channels.  arXiv[quant-ph]:0902.0158, 2009.
  * [64] Nilanjana Datta and Min-Hsiu Hsieh.  One-shot entanglement-assisted quantum and classical communication.  IEEE Transactions on Information Theory, 59(3):1929–1939, 2012\.
  * [65] Te Sun Han.  Information-spectrum methods in information theory, volume 50.  Springer Science & Business Media, 2002.
  * [66] Marco Tomamichel, Mark M. Wilde, and Andreas Winter.  Strong converse rates for quantum communication.  IEEE Transactions on Information Theory, 63(1):715–727, 2016.
  * [67] Rudolf Ahlswede and Gunter Dueck.  Identification via channels.  IEEE Transactions on Information Theory, 35(1):15–29, 1989.  doi:10.1109/18.42172.
  * [68] Te Sun Han and Sergio Verdú.  New results in the theory of identification via channels.  IEEE transactions on information theory, 38(1):14–25, 1992.
  * [69] Te Sun Han and Sergio Verdú.  Approximation theory of output statistics.  IEEE Transactions on Information Theory, 39(3):752–772, 1993.
  * [70] Andreas Winter.  Quantum and classical message identification via quantum channels.  In Osamu Hirota, editor, Festschrift for the 60th birthday of Alexander S. Holevo, pages 171–188. Rinton Press, NJ, 2004.  Reprinted in _Quantum Information & Computation_, 4(6&7):563-578, 2004.
  * [71] Andreas Winter.  Identification via quantum channels in the presence of prior correlation and feedback.  In General Theory of Information Transfer and Combinatorics, volume 4123 of Lecture Notes in Computer Science, pages 486–504. Springer Verlag, Berlin Heidelberg, 2006.
  * [72] Patrick Hayden and Andreas Winter.  Weak decoupling duality and quantum identification.  IEEE Transactions on Information Theory, 58(7):4914–4929, 2012\.
  * [73] Andreas Winter.  Identification via quantum channels.  In Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede, volume 7777 of Lecture Notes in Computer Science, pages 217–233. Springer Verlag, Berlin Heidelberg, 2013.
  * [74] Patrick Hayden, Debbie W. Leung, and Andreas Winter.  Aspects of generic entanglement.  Communications in Mathematical Physics, 265:95–117, 2006.
  * [75] Michał Horodecki and Paweł Horodecki.  Reduction criterion of separability and limits for a class of distillation protocols.  Physical Review A, 59(6):4206–4212, 1999.