Finally, using Propositions 4, 5, and 6, we bound
$\mathbb{E}\left[{\Xi(\Gamma^{(n)}}\right]$, for all $\epsilon\in(0,1)$,

$\displaystyle\mathbb{E}_{\mathcal{C}}\left[{\Xi(\Gamma^{(n)})}\right]$
$\displaystyle\overset{}{\leq}\mathbb{E}_{\mathcal{C}}\left[{\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}\Xi(\Gamma^{(n)})+2\left({1-\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}}\right)}\right]\overset{}{\leq}\mathbb{E}_{\mathcal{C}}\left[{\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}\Xi(\Gamma^{(n)})}\right]+2\epsilon\overset{}{\leq}6\epsilon.$

Since $\mathbb{E}_{\mathcal{C}}\left[{\Xi(\Gamma^{(n)})}\right]\leq
6\epsilon$, there exists a codebook $\mathcal{C}$ and the associated POVM
$\Gamma^{(n)}$ such that $\Xi(\Gamma^{(n)})\leq 6\epsilon$. This completes the
achievability proof.

###  VI-B Proof of Converse

Let $R$ be an achievable rate. Then from Definition 7, given a triple
$({\rho^{B}},{\mathsf{X}},\mathcal{W})$, for all $\epsilon>0$, and all
sufficiently large $n$, there exists $(n,\Theta)$ QC lossy compression
protocol with a POVM $\Gamma^{(n)}=\left\\{{A_{m}}\right\\}_{m\in[\Theta]}$
and a decoding map $f$ that satisfies the following constraint:

$\sum_{x^{n}}\norm{\sqrt{{\rho^{B}}^{\otimes
n}}A_{f^{-1}(x^{n})}\sqrt{{\rho^{B}}^{\otimes
n}}-\Tr(A_{f^{-1}(x^{n})}{\rho^{B}}^{\otimes
n})\bigotimes_{i=1}^{n}\mathcal{W}_{x_{i}}}_{1}\leq\epsilon,\mbox{ and
}\frac{1}{n}\log\Theta\leq R+\epsilon.$

Let $M$ denote the transmitted message, and define the following classical-
quantum state:

$\displaystyle\omega^{X^{n}B_{{R}}^{n}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x^{n}}\outerproduct{x^{n}}{x^{n}}\otimes{\sqrt{{\rho^{B}}^{\otimes
n}}A_{f^{-1}(x^{n})}\sqrt{{\rho^{B}}^{\otimes n}}}\mbox{ and }$
$\displaystyle\tau^{X^{n}B_{{R}}^{n}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x^{n}}\Tr(A_{f^{-1}(x^{n})}{\rho^{B}}^{\otimes
n})\outerproduct{x^{n}}{x^{n}}\otimes\mathcal{W}_{x^{n}},$ (87)

where $\omega^{X^{n}B_{{R}}^{n}}$ and $\tau^{X^{n}B_{{R}}^{n}}$ are the
resulting CQ-states of the QC lossy compression protocol and the ideal QC
lossy compression protocol according to Definition 7, respectively. By
triangle equality, we have
$\norm{\omega^{X^{n}B_{{R}}^{n}}-\tau^{X^{n}B_{{R}}^{n}}}_{1}\leq\epsilon$. We
now provide a lower bound on the rate $R$. We have the following inequalities:

$\displaystyle nR$ $\displaystyle=\log\Theta-n\epsilon\geq
H(M)-n\epsilon\overset{}{\geq}I(M;B_{{R}}^{n})_{\omega}-n\epsilon$
$\displaystyle\overset{a}{\geq}I(X^{n};B_{{R}}^{n})_{\omega}-n\epsilon,$
$\displaystyle\overset{b}{\geq}nS(B_{{R}})_{\omega}-\sum_{i=1}^{n}S((B_{{R}})_{i}|X_{i})_{\omega}-n\epsilon$
$\displaystyle\overset{c}{\geq}nS(B_{{R}})_{\omega_{Q}}-nS(B_{{R}}|X)_{\omega_{Q}}-n\epsilon=nI(X;B_{{R}})_{\omega_{Q}}-n\epsilon,$
$\displaystyle\overset{d}{\geq}nI(X;B_{{R}})_{\tau_{Q}}-n\tilde{\epsilon}(\epsilon)-n\epsilon,$
(88)

where inequalities are argued as follows: $(a)$ follows from the quantum data
processing inequality [50, Section 11.9.2], $(b)$ follows from the fact that
conditioning does not increase quantum entropy, $(c)$ follows from the
concavity of conditional quantum entropy [50, Ex. 11.7.5] and by defining

$\omega^{X_{Q}(B_{{R}})_{Q}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{n}\sum_{i=1}^{n}\Tr_{X^{n\backslash
i}(B_{{R}})^{n\backslash i}}\left\\{{\omega^{X^{n}B_{{R}}^{n}}}\right\\}\mbox{
and }\text{ noting that }\omega^{(B_{{R}})_{Q}}={\rho^{B}},$

and $(d)$ follows from the continuity of quantum mutual information (AFW
inequality) [50, Ex. 11.10.2], by defining

$\tau^{X_{Q}(B_{{R}})_{Q}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{n}\sum_{i=1}^{n}\Tr_{X^{n\backslash
i}(B_{{R}})^{n\backslash
i}}\left\\{{\tau^{X^{n}B_{{R}}^{n}}}\right\\}=\sum_{x}\left({\frac{1}{n}\sum_{i=1}^{n}\sum_{x^{n\backslash
i}}\Tr{A_{f^{-1}(x^{n})}{\rho^{B}}^{\otimes
n}}}\right)\outerproduct{x}{x}\otimes\mathcal{W}_{x},$

and
$\tilde{\epsilon}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{3}{2}\epsilon\log(\dim\mathcal{H}_{B})+(2+\epsilon)h_{b}\Big{(}\frac{\epsilon}{2+\epsilon}\Big{)}$,
and noting

$\norm{{\rho^{B}}-\Tr_{X_{Q}}\\{\tau^{X_{Q}(B_{{R}})_{Q}}\\}}_{1}\leq\norm{\omega^{X_{Q}(B_{{R}})_{Q}}-\tau^{X_{Q}(B_{{R}})_{Q}}}_{1}\leq\norm{\omega^{X^{n}B_{{R}}^{n}}-\tau^{X^{n}B_{{R}}^{n}}}_{1}\leq\epsilon,$
(89)

where
$\Tr_{X_{Q}}\\{\tau^{X_{Q}(B_{{R}})_{Q}}\\}=\sum_{x}P_{X_{Q}}(x)\mathcal{W}_{x}$,
and

$P_{X_{Q}}(x)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\left({\frac{1}{n}\sum_{i=1}^{n}\sum_{x^{n\backslash
i}}\Tr{A_{f^{-1}(x^{n})}{\rho^{B}}^{\otimes n}}}\right).$

We note that $\sum_{x}P_{X_{Q}}(x)=1$. So far, we have shown that

$R\in\bigcap_{\epsilon>0}\mathcal{I}_{\epsilon},$

where we have defined for all $\epsilon\geq 0$,

$\mathcal{I}_{\epsilon}({\rho^{B}},\mathcal{W})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{R:\exists\;{P}_{X}\in\mathcal{A}_{\epsilon}\mbox{
such that }R\geq I(X,B_{{R}})_{\sigma}-g(\epsilon)\\},$
$\mathcal{A}_{\epsilon}({\rho^{B}},\mathcal{W})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{{P}_{X}\in\mathcal{P}(\mathsf{X}):\|\sum_{x}{P}_{X}(x)\mathcal{W}_{x}-{\rho^{B}}\|_{1}\leq\epsilon\\},\mbox{
and
}\sigma^{XB_{{R}}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x}P_{X}(x)\outerproduct{x}{x}^{X}\otimes\mathcal{W}_{x},$

$g(\epsilon)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\tilde{\epsilon}+\epsilon$.
Equation (89) ensures that the set $\mathcal{A}_{\epsilon}$ is non-empty for
$\epsilon>0$. Using the continuity of rate regions similar to Lemma 5, we
obtain $\bigcap_{\epsilon>0}\mathcal{I}_{\epsilon}=\mathcal{I}_{0},$ and
$\mathcal{A}_{0}$ is non-empty, and hence $R\in\mathcal{I}_{0}$. This
concludes the converse proof.

##  VII Proof of Theorem 3

We begin the section with the achievability part, i.e., any rate $R$ that
satisfies (5) is achievable. We then prove the converse, i.e., any achievable
lossy source compression protocol must satisfy (5).

###  VII-A Proof of Achievability

For a given source distribution ${P}_{X}$, reconstruction alphabet
$\hat{\mathsf{X}}$, and a posterior channel ${W}_{X|\hat{X}}$, we choose a
reconstruction distribution
${P}_{\hat{X}}\in\mathcal{A}({P}_{X},{W}_{X|\hat{X}})$. Toward specifying the
encoder $\mathcal{E}^{(n)}:\mathsf{X}^{n}\longrightarrow[\Theta]$ and the
decoder $\mathcal{D}^{(n)}:[\Theta]\longrightarrow\hat{\mathsf{X}}^{n}$, we
construct a codebook $\mathcal{C}$. From now on, we let $\Theta=2^{nR}+1$.

####  VII-A1 Codebook Construction

We construct a codebook
$\mathcal{C}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{\hat{X}^{n}(1),\hat{X}^{n}(2),\cdots,\hat{X}^{n}(2^{nR})\\}$,
by choosing each codewords randomly and independently according to the
following “pruned” distribution:

$\mathbb{P}(\hat{X}^{n}(m)=\hat{x}^{n})=\begin{cases}\dfrac{{P}_{\hat{X}}^{n}(\hat{x}^{n})}{1-\varepsilon}&\text{if}\
\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X}),\\\
0&\text{otherwise.}\end{cases}$

where
${P}_{\hat{X}}^{n}(\hat{x}^{n})=\Pi_{i=1}^{n}{P}_{\hat{X}}(\hat{x}_{i})$,
$\mathcal{T}_{\delta}^{(n)}(\hat{X})$ is the $\delta$-typical set
corresponding to the distribution ${P}_{\hat{X}}$ on the set
$\hat{\mathsf{X}}$, and
$\varepsilon(\delta,n)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\hat{x}^{n}\not\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}{P}_{\hat{X}}^{n}(\hat{x}^{n})$.
The codebook $\mathcal{C}$ is revealed to both the encoder and the decoder
before the lossy source compression protocol begins.

####  VII-A2 Encoder Description

For an observed source sequence $x^{n}$, construct a randomized encoder that
chooses an index $m\in[2^{nR}]$ according to a sub-PMF
$E_{M|X^{n}}(m|x^{n})$444A non-negative function $q_{X}(x)$ over a finite
alphabet $\mathsf{X}$ is said to be a sub-PMF if
$\sum_{x\in\mathsf{X}}q_{X}(x)\leq 1$., which is analogous to the likelihood
encoders used in [51, 52]. We now specify $E_{M|X^{n}}(m|x^{n})$ for
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$ and $m\in[2^{nR}]$, where
$\hat{\delta}=\delta(|\mathsf{X}|+|\hat{\mathsf{X}}|)$. For a $\eta\in(0,1)$
(to be specified later), and $\delta>0$, define

$\displaystyle
E_{M|X^{n}}(m|x^{n})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\hat{x}^{n}}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}\frac{{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})}{{P}_{X}^{n}(x^{n})}\mathbbm{1}_{\\{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\\}}\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}.$
(90)

Similar to the encoder specification in [52], we also have relaxed the
constraint that $E_{M|X^{n}}(\cdot|x^{n})$ is strictly a PMF, i.e,
$\sum_{m=1}^{2^{nR}}E_{M|X^{n}}(m|x^{n})=1$. Let
$\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}$ denotes the indicator random
variable corresponding to the event that
$\\{E_{M|X^{n}}(m|x^{n})\\}_{m\in[\Theta]}$ forms a sub-PMF for all
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$. If
$\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}=1$, then construct the sub-PMF
as follows:

$P_{M|X^{n}}(m|x^{n})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}{E_{M|X^{n}}(m|x^{n}),\text{
for all }x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\mbox{ and
}m\in[\Theta]}.$

We then add an additional PMF element
$P_{M|X^{n}}(0|x^{n})=E_{M|X^{n}}(0|x^{n})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\left({1-\sum_{m=1}^{2^{nR}}E_{M|X^{n}}(m|x^{n})}\right)$
for all $x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$, associated with
$m=0$, to form a valid PMF $P_{M|X^{n}}(m|x^{n})$ for all
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$ and
$m\in\left\\{{0}\right\\}\cup[2^{nR}]$. If
$x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$, then we define
$P_{M|X^{n}}(m|x^{n})=\mathbbm{1}_{\left\\{{m=0}\right\\}}$. We provide a
proposition that will be helpful later in the analysis.

######  Proposition 7.

For all $\epsilon,\eta\in(0,1)$, for all sufficiently small $\delta>0$, and
sufficiently large $n$, we have
$\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}}\right]\geq
1-\epsilon$, i.e.,

$\Pr\left({\bigcap_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}\left({\sum_{m=1}^{2^{nR}}E_{M|X^{n}}(m|x^{n})\leq
1}\right)}\right)\geq 1-\epsilon,$

if $R>I(X;\hat{X})$.

###### Proof.

A proof is provided in Appendix A-H. ∎

We now summarize $P_{M|X^{n}}$ for $m\in\\{0\\}\cup[2^{nR}]$ and under the
condition that $\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}=1$,

$P_{M|X^{n}}(m|x^{n})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\begin{cases}\mathbbm{1}_{\\{m=0\\}}&\text{if
}x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X}),\\\
E_{M|X^{n}}(m|x^{n})&\text{if
}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X}).\end{cases}$ (91)

If $\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}=0,\text{ then
}P_{M|X^{n}}(m|x^{n})=\mathbbm{1}_{\\{m=0\\}}$, for all
$x^{n}\in\mathsf{X}^{n}$. This concludes the encoder description.

####  VII-A3 Decoder Description

We now describe the decoder. For an observed index $m\in\\{0\\}\cup[2^{nR}]$
communicated by the encoder, the decoder outputs $\hat{X}^{n}(m)$ if $m\neq
0$. Otherwise, decoder outputs a fixed
$\hat{x}_{0}^{n}\in\hat{\mathsf{X}}^{n}\backslash\mathcal{T}_{\delta}^{(n)}(\hat{X})$,
i.e.,

$\mathcal{D}^{(n)}(m)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\begin{cases}\hat{X}^{n}(m)&\text{if
}m\neq 0,\\\ \hat{x}^{n}_{0}&\text{otherwise.}\end{cases}$ (92)

####  VII-A4 Error Analysis

We show that for the above-mentioned encoder and decoder,
$P_{X^{n}\hat{X}^{n}}$ is close to the approximating distribution
$P_{\hat{X}^{n}}{W}_{X|\hat{X}}^{n}$ in the total variation, averaged over the
random codebook. We begin by splitting the error
$\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})$ into two terms using the indicator
function $\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}$ as

$\displaystyle\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})$
$\displaystyle=\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})+\left({1-\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}}\right)\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)}),$
$\displaystyle\leq\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})+\left({1-\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}}\right).$
(93)

Step 1: Isolating the error term induced by not covering

Using the triangle inequality, we now expand the
$\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})$ under the condition
$\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}=1$.

$\displaystyle 2\;\Xi($ $\displaystyle\mathcal{E}^{(n)},\mathcal{D}^{(n)})$
$\displaystyle=\sum_{x^{n}\hat{x}^{n}}\Bigg{|}{P}_{X}^{n}(x^{n})\\!\\!\\!\\!\\!\sum_{m\in\left\\{{0}\right\\}\cup[2^{nR}]}\\!\\!\\!\\!\\!P_{M|X^{n}}(m|x^{n})\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}-\\!\\!\\!\\!\\!\\!\\!\\!\sum_{m\in\left\\{{0}\right\\}\cup[2^{nR}]}\\!\\!\\!\\!\\!\\!\\!\\!\\!P_{M}(m)\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\Bigg{|}$
$\displaystyle\overset{a}{\leq}\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\end{subarray}}\Bigg{|}{P}_{X}^{n}(x^{n})\\!\\!\\!\\!\\!\sum_{m\in[2^{nR}]}\\!\\!\\!\\!\\!E_{M|X^{n}}(m|x^{n})\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}-\\!\\!\\!\\!\sum_{m\in[2^{nR}]}\\!\\!\\!\\!P_{M}(m)\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\Bigg{|}$
$\displaystyle\hskip
72.26999pt+\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\end{subarray}}\Bigg{|}{P}_{X}^{n}(x^{n})E_{M|X^{n}}(0|x^{n})-P_{M}(0){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}_{0}^{n})\Bigg{|}$
$\displaystyle\hskip
72.26999pt+\sum_{\begin{subarray}{c}x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\end{subarray}}\Bigg{|}{P}_{X}^{n}(x^{n})\mathbbm{1}_{\\{\hat{x}^{n}=\hat{x}_{0}^{n}\\}}-\\!\\!\\!\\!\\!\\!\\!\\!\sum_{m\in\left\\{{0}\right\\}\cup[2^{nR}]}P_{M}(m){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}\Bigg{|}$
$\displaystyle\overset{b}{\leq}\zeta+\tilde{\zeta}+\\!\\!\\!\\!\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}P_{M}(0){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}_{0}^{n})+\\!\\!\\!\\!\sum_{x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}P_{M}(0){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}_{0}^{n})+\\!\\!\\!\\!\sum_{\begin{subarray}{c}x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\end{subarray}}{P}_{X}^{n}(x^{n})$
$\displaystyle\hskip
72.26999pt+\sum_{m\in[2^{nR}]}\sum_{\begin{subarray}{c}\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\\\
x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\end{subarray}}P_{M}(m){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}$
$\displaystyle\overset{c}{\leq}\zeta+\tilde{\zeta}+\\!\\!\\!\\!\sum_{\begin{subarray}{c}x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\end{subarray}}{P}_{X}^{n}(x^{n})+P_{M}(0)+\epsilon$
$\displaystyle=\zeta+2\tilde{\zeta}+2\\!\\!\\!\\!\sum_{\begin{subarray}{c}x^{n}\not\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\end{subarray}}{P}_{X}^{n}(x^{n})+\epsilon\overset{d}{\leq}\zeta+2\tilde{\zeta}+3\epsilon,$
(94)

for all sufficiently large $n$ and all $\delta>0$, where $(a)$ and $(b)$
follow from the triangle inequality, and by defining

$\displaystyle\zeta$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\end{subarray}}\Bigg{|}{P}_{X}^{n}(x^{n})\\!\\!\\!\sum_{m\in[2^{nR}]}\\!\\!\\!\\!\\!E_{M|X^{n}}(m|x^{n})\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}-\\!\\!\sum_{m\in[2^{nR}]}\\!\\!\\!\\!P_{M}(m)\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\Bigg{|},$
$\displaystyle\mbox{ and }\tilde{\zeta}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}{P}_{X}^{n}(x^{n})E_{M|X^{n}}(0|x^{n})=\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}{P}_{X}^{n}(x^{n})\Bigg{(}1-\sum_{m=1}^{2^{nR}}E_{M|X^{n}}(m|x^{n})\Bigg{)},$
(95)

$(c)$ follows from the conditional typicality argument for all sufficiently
large $n$, and finally, $(d)$ follows from the standard typicality argument
for all sufficiently large $n$. The error term $\tilde{\zeta}$ captures the
error induced by not covering the $n$-product posterior test channel. We
provide the following proposition that bounds this term.

######  Proposition 8.

For all $\epsilon\in(0,1)$, and for all sufficiently small $\eta,\delta>0$,
and sufficiently large $n$, we have
$\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\tilde{\zeta}}\right]\leq\epsilon$
if $R>I(X;\hat{X})$.

###### Proof.

The proof is provided in Appendix A-I. ∎

Step 2: Bounding the error induced by covering

We now bound the term $\zeta$, which captures the error induced by covering.
Using the triangle inequality, we get

$\displaystyle\zeta$
$\displaystyle=\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\end{subarray}}\Bigg{|}\;{\sum_{m\in[2^{nR}]}\left({{P}_{X}^{n}(x^{n})E_{M|X^{n}}(m|x^{n})-P_{M}(m){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})}\right)\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}}\Bigg{|},$
$\displaystyle\overset{}{\leq}\\!\\!\sum_{m\in[2^{nR}]}\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\end{subarray}}\left|{{P}_{X}^{n}(x^{n})E_{M|X^{n}}(m|x^{n})-P_{M}(m){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})}\right|\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}.$

We now provide the following proposition that bounds the error term $\zeta$.

######  Proposition 9.

For all $\epsilon,\eta\in(0,1)$, for all sufficiently small $\delta>0$, and
sufficiently large $n$, we have
$\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}{\zeta}}\right]\leq\epsilon$.

###### Proof.

A proof is provided in Appendix A-J. ∎

Finally, using Propositions 7, 8, and 9, we bound
$\mathbb{E}\left[{\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})}\right]$, for all
$\epsilon\in(0,1)$,

$\displaystyle\mathbb{E}_{\mathcal{C}}\left[{\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})}\right]$
$\displaystyle\overset{}{\leq}\mathbb{E}_{\mathcal{C}}\left[{\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})+\left({1-\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}}\right)}\right]\overset{}{\leq}9\epsilon/2.$

Since
$\mathbb{E}_{\mathcal{C}}\left[{\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})}\right]\leq
9\epsilon/2$, there exists a code $\mathcal{C}$ such that the associated
$\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})\leq 9\epsilon/2$. This completes the
achievability proof.

###  VII-B Proof of Converse

Let $R$ be an achievable rate. Then from Definition 4, given a triple
$({P}_{X},\hat{\mathsf{X}},{W}_{X|\hat{X}})$, for all $\epsilon>0$, and for
all sufficiently large $n$, there exists $(n,\Theta)$ lossy compression
protocol with an encoding map $\mathcal{E}^{(n)}$ and a decoding map
$\mathcal{D}^{(n)}$ that satisfy the following constraints:

$\Xi(\mathcal{E}^{(n)},\mathcal{D}^{(n)})=\norm{P_{X^{n}\hat{X}^{n}}-P_{\hat{X}^{n}}{W}_{X|\hat{X}}^{n}}_{\text{TV}}\leq\epsilon,\mbox{
and }\frac{1}{n}\log\Theta\leq R+\epsilon.$

Let $M$ denote the transmitted message. We now provide a lower bound on the
rate $R$. We have the following inequalities:

$\displaystyle nR$ $\displaystyle=\log\Theta-n\epsilon\geq H(M)-n\epsilon\geq
I(X^{n},M)-n\epsilon$
$\displaystyle\overset{a}{\geq}I(X^{n},\hat{X}^{n})-n\epsilon$
$\displaystyle\overset{}{\geq}\sum_{i}H(X_{i})-\sum_{i}H(X_{i}|\hat{X}_{i})-n\epsilon$
$\displaystyle=\sum_{i}I(X_{i};\hat{X}_{i})-n\epsilon$
$\displaystyle\overset{b}{\geq}nI(X_{Q};\hat{X}_{Q})-n\epsilon$
$\displaystyle\overset{c}{=}nI(P_{\hat{X}_{Q}},P_{X_{Q}|\hat{X}_{Q}})-n\epsilon$
$\displaystyle\overset{d}{\geq}nI(P_{\hat{X}_{Q}},{W}_{X|\hat{X}})-n\tilde{\epsilon}(\epsilon)-n\epsilon,$

where the inequalities are argued as follows: $(a)$ follows from the data
processing inequality, $(b)$ follows from the convexity of mutual information
as the function of varying channel for a fixed source, and by defining

$P_{X_{Q}\hat{X}_{Q}}=\sum_{i}\frac{1}{n}P_{X_{i}\hat{X}_{i}}\quad\text{ and
noting that }\quad P_{X_{Q}}={P}_{X},$

$(c)$ follows from the change of notation of mutual information [24], and
$(d)$ follows from the continuity of mutual information [57, Theorem 17.3.3]
and from Lemma 6 (see below) and by defining
$\tilde{\epsilon}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}-2\epsilon\log\frac{4\epsilon^{2}}{|\mathsf{X}|^{2}|\hat{\mathsf{X}}|}$.

######  Lemma 6.

The distributions $P_{X^{n}\hat{X}^{n}}$ and
$P_{\hat{X}^{n}}{W}_{X|\hat{X}}^{n}$ satisfy

$\|P_{X}-\sum_{\hat{x}}P_{\hat{X}_{Q}}(\hat{x}){W}_{X|\hat{X}}(\cdot|\hat{x})\|_{\text{TV}}\leq\|P_{X_{Q}\hat{X}_{Q}}-P_{\hat{X}_{Q}}{W}_{X|\hat{X}}\|_{\text{TV}}\leq\|P_{X^{n}\hat{X}^{n}}-P_{\hat{X}^{n}}{W}_{X|\hat{X}}^{n}\|_{\text{TV}}.$

###### Proof.

The proof is provided in Appendix A-K. ∎

So far, we have shown that

$R\in\bigcap_{\epsilon>0}\mathcal{I}_{\epsilon},$

where we have defined for all $\epsilon\geq 0$,

$\mathcal{I}_{\epsilon}({P}_{X},{W}_{X|\hat{X}})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{R:\exists{P}_{\hat{X}}\in\mathcal{A}_{\epsilon}(P_{X},W_{X|\hat{X}})\mbox{
such that }R\geq I({P}_{\hat{X}},W_{X|\hat{X}})-g(\epsilon)\\},$
$\mathcal{A}_{\epsilon}({P}_{X},{W}_{X|\hat{X}})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{{P}_{\hat{X}}\in\mathcal{P}(\hat{\mathsf{X}}):\|\sum_{\hat{x}}{P}_{\hat{X}}(\hat{x}){W}_{X|\hat{X}}(\cdot|\hat{x})-{P}_{X}\|_{\text{TV}}\leq\epsilon\\},$

$g(\epsilon)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\tilde{\epsilon}+\epsilon$.
Lemma 6 ensures that the set $\mathcal{A}_{\epsilon}$ is non-empty for
$\epsilon>0$. Using the continuity of rate regions similar to Lemma 5, we
obtain $\bigcap_{\epsilon>0}\mathcal{I}_{\epsilon}=\mathcal{I}_{0}$ and
$\mathcal{A}_{0}$ is non-empty, and hence $R\in\mathcal{I}_{0}$. This
concludes the converse proof.

##  VIII Conclusion

In this work, we explored a new formulation of the lossy quantum source coding
problem. The two ingredients that make our formulation different from the
standard rate-distortion problem are (i) the usage of a global error criterion
to measure the quality of reconstruction, and (ii) the notion of a posterior
reference channel defined as a CPTP map acting on the reference of the
reconstruction to produce the reference of the source. Instead of a single-
letter distortion function, a global error criterion measures the error
incurred by using the given single-letter posterior channel. The given channel
characterizes the nature of the loss incurred in the encoding and decoding
operations.

As a first main result, we provide a single-letter characterization of the
asymptotic performance limit of this source coding problem using the minimal
coherent information of the posterior reference map, where the minimization is
over all reconstructions. Even though the formulation uses a global error
criterion, it sheds light on an “optimistic” perspective of the lossy source
coding theory. In this regard, our results provide the missing duality pair of
the quantum channel coding problem, and also broadens the framework of
performing lossy quantum source compression. Investigation of this formulation
to other variants of lossy source coding problem can be an interesting
research avenue to pursue. Similarly, it would be interesting to explore other
techniques of establishing the achievability and converse of this limit.

Subsequently, we considered the quantum-classical (QC) setting and formulated
a corresponding lossy QC source coding problem. We provided a single-letter
characterization of the asymptotic performance limit of this problem using the
minimal Holevo information (or the corresponding quantum mutual information)
of the posterior classical-quantum (CQ) channel, where the minimization is
over all reconstruction distributions (see Theorem 2). Finally, we performed a
correspondingly new formulation for the classical setup, and established the
minimal mutual information of the posterior channel as the single-letter
characterization of the asymptotic performance limit of the classical source
coding problem.

##  Appendix A Proof of Lemmas

###  A-A Proof of Lemma 2

Note that

$\displaystyle\ket{\psi_{\rho}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(I_{R}\otimes\sqrt{\rho^{B}})\ket{\Gamma}^{RB},\quad\ket{\psi_{\sigma}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(I_{R}\otimes\sqrt{\sigma^{B}})\ket{\Gamma}^{RB},$

where $\ket{\Gamma}_{RB}$ is the unnormalized maximally entangled pure state:
$\ket{\Gamma}_{RB}=\sum_{i}\ket{i}_{R}\ket{i}_{B}$. Consider the fidelity
between the canonical purification states $\ket{\psi_{\rho}}$ and
$\ket{\psi_{\sigma}}$:

$\displaystyle
F(\ket{\psi_{\rho}},\ket{\psi_{\sigma}})\overset{a}{=}|\bra{\psi_{\rho}}\ket{\psi_{\sigma}}|^{2}$
$\displaystyle\overset{}{=}|\bra{\Gamma}^{RB}(I_{R}\otimes\sqrt{\rho^{B}}\sqrt{\sigma^{B}})\ket{\Gamma}^{RB}|^{2},$
$\displaystyle\overset{b}{=}|\Tr(\sqrt{\rho^{B}}\sqrt{\sigma^{B}})|^{2}\overset{c}{\geq}\left(1-\frac{1}{2}\norm{{\rho^{B}}-{\sigma^{B}}}_{1}\right)^{2}\geq
1-\norm{{\rho^{B}}-{\sigma^{B}}}_{1},$

where $(a)$ follows from the definition of fidelity for a pure state, $(b)$
follows from the definition of trace, $(c)$ follows from the Power-Størmer
inequality [63, Lemma 4.1], i.e., for any positive semi-definite matrices $A$
and $B$, we have

$\Tr(A)+\Tr(B)-\norm{A-B}_{1}\leq 2\Tr(\sqrt{A}\sqrt{B}).$

###  A-B Proof of Lemma 4

We first provide the following lemma.

######  Lemma 7 (Covering superposition states).

Consider a finite set $\mathcal{U}$, and a pair of collections
$\\{\rho_{u}\\}_{u\in\mathcal{U}}$ and $\\{\sigma_{u}\\}_{u\in\mathcal{U}}$
where $\rho_{u},\sigma_{u}\in\mathcal{D}(\mathcal{H}_{A})$ for all
$u\in\mathcal{U}$. Let $\\{\Psi_{u}^{\rho}\\}_{u\in\mathcal{U}}$ and
$\\{\Psi_{u}^{\sigma}\\}_{u\in\mathcal{U}}$ acting on
$\mathcal{D}(\mathcal{H}_{R_{1}}\otimes\mathcal{H}_{A})$ and
$\mathcal{D}(\mathcal{H}_{R_{2}}\otimes\mathcal{H}_{A})$ be some purifications
of $\\{\rho_{u}\\}_{u\in\mathcal{U}}$ and
$\\{\sigma_{u}\\}_{u\in\mathcal{U}}$, respectively, with
$\dim(\mathcal{H}_{R_{1}})\leq\dim(\mathcal{H}_{R_{2}})$. Then there exists a
collection of isometric operators $\\{U_{r}(u)\\}_{u\in\mathcal{U}}$ acting on
$\mathcal{H}_{R_{1}}\rightarrow\mathcal{H}_{R_{2}}$ and phases
$\\{\delta_{u}\\}$ such that

$\displaystyle F((U_{R}\otimes
I_{A})\ket{\tau_{\rho}},\ket{\tau_{\sigma}})=F(\ket{\tau_{\rho}},(U_{R}\otimes
I_{A})^{\dagger}\ket{\tau_{\sigma}})\geq
1-\sum_{u\in\mathcal{U}}\frac{1}{|\mathcal{U}|}\|\rho_{u}-\sigma_{u}\|_{1},$
(96)

where

$\displaystyle
U_{R}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{u\in\mathcal{U}}e^{-i\delta_{u}}U_{r}(u)\otimes\outerproduct{u}{u},\quad\ket{\tau_{\rho}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{u\in\mathcal{U}}\frac{1}{\sqrt{|\mathcal{U}|}}\ket{\psi_{u}^{\rho}}\otimes\ket{u},\quad\ket{\tau_{\sigma}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{u\in\mathcal{U}}\frac{1}{\sqrt{|\mathcal{U}|}}\ket{\psi^{\sigma}_{u}}\otimes\ket{u}.$

###### Proof.

We provide a proof in Appendix A-C. ∎

Now, with the intention of employing the above lemma we perform the following
identification. Identify $\mathcal{U}$ with $\mathcal{M}\times\mathcal{K}$,
$\rho_{u}$ with $\hat{\rho}_{m,k}^{{B_{R}}}$, $\sigma_{u}$ with
$\tilde{\rho}_{m,k}^{{B_{R}}}$, $\ket{\psi_{u}^{\rho}}$ with $\frac{(I\otimes
M_{m,k})}{\sqrt{\lambda_{m,k}}}|{\psi_{\rho}^{\otimes
n}}\rangle^{B_{R}^{n}B^{n}}$, and $\ket{\psi_{u}^{\sigma}}$ with
$\frac{(I\otimes\sqrt{A_{m,k}})}{\sqrt{\delta_{m,k}}}|{\psi_{\rho}^{\otimes
n}}\rangle^{B_{R}^{n}B^{n}}$. Note that the last two identifications are, in
fact, the purifications of $\hat{\rho}_{m,k}^{{B_{R}}}$ and
$\tilde{\rho}_{m,k}^{{B_{R}}}/\Tr(\tilde{\rho}_{m,k}^{{B_{R}}})$, respectively
as

$\displaystyle\Tr_{E}\left(\frac{(I\otimes
M_{m,k})}{\sqrt{\lambda_{m,k}}}{\Psi_{\rho_{B}}^{\otimes n}}\frac{(I\otimes
M^{\dagger}_{m,k})}{\sqrt{\lambda_{m,k}}}\right)=\hat{\rho}_{m,k}^{{B_{R}}},\;\;\Tr_{B}\left(\frac{(I\otimes\sqrt{A_{m,k}})}{\sqrt{\delta_{m,k}}}{\Psi_{\rho_{B}}^{\otimes
n}}\frac{(I\otimes\sqrt{A_{m,k}})}{\sqrt{\delta_{m,k}}}\right)=\frac{\tilde{\rho}_{m,k}^{{B_{R}}}}{\Tr(\tilde{\rho}_{m,k}^{{B_{R}}})}.$

Using Lemma 7, we obtain

$\displaystyle F$
$\displaystyle(|{\hat{\sigma}}\rangle^{{{B_{R}}}EMK},(I_{{B_{R}}}\otimes
U_{\mathcal{R}})|{\tilde{\sigma}}\rangle^{{B_{R}}BMK})$ $\displaystyle\geq
1-\frac{1}{(1-\sqrt{\epsilon})|\mathcal{M}||\mathcal{K}|}\sum_{m,k}\bigg{\|}\hat{\rho}_{m,k}^{{B_{R}}}-\frac{\tilde{\rho}_{m,k}^{{B_{R}}}}{\Tr(\tilde{\rho}_{m,k}^{{B_{R}}})}\bigg{\|}_{1}$
$\displaystyle\geq\frac{1}{(1-\sqrt{\epsilon})|\mathcal{M}||\mathcal{K}|}\sum_{m,k}{\Tr{\tilde{\rho}_{m,k}^{{B_{R}}}}}-\frac{1}{(1-\sqrt{\epsilon})|\mathcal{M}||\mathcal{K}|}\sum_{m,k}\bigg{\|}\hat{\rho}_{m,k}^{{B_{R}}}-{\tilde{\rho}_{m,k}^{{B_{R}}}}\bigg{\|}_{1}\geq
1-4\sqrt{\epsilon},$ (97)

where the last inequality follows from using the bounds in (38) and (39).

###  A-C Proof of Lemma 7

Consider the following:

$\displaystyle F(\ket{\tau_{\rho}},(U_{R}\otimes
I)^{\dagger}\ket{\tau_{\sigma}})$
$\displaystyle{=}\left|\sum_{u\in\mathcal{U}}\frac{1}{|\mathcal{U}|}e^{-i\delta_{u}}\bra{\psi_{u}^{\rho}}U_{r}^{\dagger}(u)\ket{\psi_{u}^{\sigma}}\right|^{2}$
$\displaystyle\overset{a}{=}\left(\sum_{u\in\mathcal{U}}\frac{1}{|\mathcal{U}|}\left|\bra{\psi_{u}^{\rho}}U_{r}^{\dagger}(u)\ket{\psi_{u}^{\sigma}}\right|\right)^{2}$
$\displaystyle\overset{b}{=}\left(\sum_{u\in\mathcal{U}}\frac{1}{|\mathcal{U}|}\sqrt{F(\rho_{u},\sigma_{u})}\right)^{2}$
$\displaystyle\overset{c}{\geq}\left(1-\frac{1}{2}\sum_{u\in\mathcal{U}}\frac{1}{|\mathcal{U}|}\norm{\rho_{u}-\sigma_{u}}_{1}\right)^{2}\geq
1-\sum_{u\in\mathcal{U}}\frac{1}{|\mathcal{U}|}\norm{\rho_{u}-\sigma_{u}}_{1},$

where $(a)$ follows by choosing $\delta_{u}$ such that
$e^{-i\delta_{u}}\bra{\psi_{u}^{\rho}}U_{r}^{\dagger}(u)\ket{\psi_{u}^{\sigma}}=|\bra{\psi_{u}^{\rho}}U_{r}^{\dagger}(u)\ket{\psi_{u}^{\sigma}}|$,
$(b)$ follows from Uhlmann’s theorem [50, Theorem 9.2.1], i.e., there exists
some isometry $U_{r}(u)$ such that
$F(\rho_{u},\sigma_{u})=F(U_{r}(u)\ket{\psi^{\rho}},\ket{\psi^{\sigma}})$, and
$(c)$ follows from Lemma 1.

###  A-D Proof of Proposition 3

We begin by defining indexing functions
$f^{(m)}:[0,K^{\prime}_{m}-1]\rightarrow\mathcal{I}_{\mathcal{E}}^{(m)}$, for
each $m\in\mathcal{M}^{\prime}$, that uniquely map each element of the
$[0,K^{\prime}_{m}-1]$ to the set $\mathcal{I}_{\mathcal{E}}^{(m)}$ in a
monotonic fashion. Let
$g^{(m)}:\mathcal{I}_{\mathcal{E}}^{(m)}\rightarrow[0,K^{\prime}_{m}-1]$ be
the inverse of $f^{(m)}$, for each $m\in\mathcal{M}^{\prime}$. Define the
transformed vectors corresponding to the collections $\\{{\chi_{k}^{(m)}}\\}$
and $\\{{\phi_{k}^{(m)}}\\}$ as

$\displaystyle|{\hat{\chi}_{s}^{(m)}}\rangle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}c\sum_{j=0}^{K_{m}^{\prime}-1}e^{\frac{2\pi
ijs}{K^{\prime}_{m}}}|\chi_{f^{(m)}(j)}^{(m)}\rangle\mbox{\quad
and\quad}|{\hat{\phi}_{s}^{(m)}}\rangle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}c\sum_{j=0}^{K_{m}^{\prime}-1}e^{\frac{2\pi
ijs}{K^{\prime}_{m}}}|\phi_{f^{(m)}(j)}^{(m)}\rangle,$

for $s\in[0,K_{m}^{\prime}-1]$. It follows from basic algebra that, for all
$m\in\mathcal{M}^{\prime}$,

$\displaystyle\frac{1}{K^{\prime}_{m}}\sum_{s=0}^{K_{m}^{\prime}-1}\langle{\hat{\phi}_{s}^{(m)}}|{\hat{\chi}_{s}^{(m)}}\rangle=c^{2}\sum_{j=0}^{K_{m}^{\prime}-1}\langle\phi_{f^{(m)}(j)}^{(m)}|\chi_{f^{(m)}(j)}^{(m)}\rangle=c^{2}\sum_{k\in\mathcal{I}_{\mathcal{E}}^{(m)}}\langle{{\phi}_{k}^{(m)}}|{{\chi}_{k}^{(m)}}\rangle.$
(98)

This implies, for all $m\in\mathcal{M}^{\prime}$, there exists at least one
value of $s_{m}\in[0,K_{m}^{\prime}-1]$ that follows the inequality:

$e^{i\hat{\theta}_{m}}\langle{\hat{\phi}_{s_{m}}^{(m)}}|{\hat{\chi}_{s_{m}}^{(m)}}\rangle\geq
c^{2}\sum_{k\in\mathcal{I}_{\mathcal{E}}^{(m)}}\langle{{\phi}_{k}^{(m)}}|{{\chi}_{k}^{(m)}}\rangle,\quad\mbox{for
some phase }\hat{\theta}_{m}.$

Observe that,

$\displaystyle\langle{\hat{\phi}_{s_{m}}^{(m)}}|{\hat{\chi}_{s_{m}}^{(m)}}\rangle=c^{2}\sum_{k\in\mathcal{I}_{\mathcal{E}}^{(m)}}\sum_{k^{\prime}\in\mathcal{I}_{\mathcal{E}}^{(m)}}e^{\frac{2\pi
i(g^{(m)}(k)-g^{(m)}(k^{\prime}))s_{m}}{K_{m}^{\prime}}}\langle{\phi}_{k^{\prime}}^{(m)}|{\chi}_{k}^{(m)}\rangle,$

for all $m\in\mathcal{M}^{\prime}$. Choosing $\alpha_{k}^{(m)}=\frac{2\pi
g^{(m)}(k)s_{m}}{K_{m}^{\prime}}$ and $\beta_{k}^{(m)}=\frac{2\pi
g^{(m)}(k)s_{m}}{K_{m}^{\prime}}+\hat{\theta}_{m}$, we obtain

$\displaystyle\frac{1}{M^{\prime}}\sum_{m\in\mathcal{M}^{\prime}}\langle\phi_{m}|\chi_{m}\rangle\geq\frac{c^{2}}{M^{\prime}}\sum_{m\in\mathcal{M}^{\prime}}\sum_{k\in\mathcal{I}_{\mathcal{E}}^{(m)}}\langle{{\phi}_{k}^{(m)}}|{{\chi}_{k}^{(m)}}\rangle=\frac{c^{2}}{M^{\prime}}\sum_{m\in\mathcal{M}^{\prime}}\sum_{k\in\mathcal{I}_{\mathcal{E}}^{(m)}}\Tr{\Xi^{(m)}_{k}\tau_{k}^{(m)}}\geq
1-2\sqrt{\epsilon},$

where the equality uses (56), and the last inequality uses (40) and
substitutes the value of $c$. This means

$\frac{1}{M^{\prime}}\mbox{Re}\left({\sum_{m\in\mathcal{M}^{\prime}}\langle\phi_{m}|\chi_{m}\rangle}\right)\geq
1-2\sqrt{\epsilon},$

and consequently,

$\displaystyle\bigg{|}\frac{1}{M^{\prime}}\sum_{m\in\mathcal{M}^{\prime}}\langle\phi_{m}|\chi_{m}\rangle\bigg{|}$
$\displaystyle\geq\bigg{[}\frac{1}{M^{\prime}}\mbox{Re}\left(\sum_{m\in\mathcal{M}^{\prime}}\langle\phi_{m}|\chi_{m}\rangle\right)\bigg{]}\geq
1-2\sqrt{\epsilon}.$ (99)

This completes the proof.

###  A-E Proof of Lemma 5

Here we follow arguments similar to the proof of [51, Lemma VI.5]. We begin by
defining $\mathcal{I}^{\prime}_{\epsilon}$ (removing the relaxation in the
rate) as, for all $\epsilon\geq 0$,

$\displaystyle\mathcal{I}^{\prime}_{\epsilon}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\left\\{{R:\exists\;\rho^{{A}_{R}}\in\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N}_{W})\mbox{
such that }R\geq I_{c}(\mathcal{N}_{W},\rho^{{A}_{R}})}\right\\},$ (100)

and note from [51] that

$\bigcap_{\epsilon>0}\mathcal{I}_{\epsilon}\subseteq\mbox{Closure}\left(\bigcap_{\epsilon>0}\mathcal{I}^{\prime}_{\epsilon}\right).$

Now we prove the following:

$\displaystyle\mathcal{S}_{0}(\rho^{B},\mathcal{N}_{W})=\bigcap_{\epsilon>0}\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N}_{W}).$
(101)

$\mathcal{S}_{0}(\rho^{B},\mathcal{N}_{W})\subseteq\bigcap_{\epsilon>0}\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N}_{W})$
is straightforward. To show the other direction, consider any
$\rho_{1}^{A_{R}}\in\bigcap_{\epsilon>0}\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N}_{W})$.
This means, for all $\epsilon>0$,

$\displaystyle\|\mathcal{N}_{W}(\rho_{1}^{{A_{R}}})-\rho^{{B_{R}}}\|_{1}\leq\epsilon\implies\|\mathcal{N}_{W}(\rho_{1}^{{A_{R}}})-\rho^{{B_{R}}}\|_{1}=0\implies\mathcal{N}_{W}(\rho_{1}^{{A_{R}}})=\rho^{{B_{R}}},$
(102)

where the second implication follows from the definition of a metric, and
hence $\rho_{1}^{{A_{R}}}\in\mathcal{S}_{0}(\rho^{B},\mathcal{N}_{W})$ and
(101) is true. Observe that, since the intersection of decreasing sequence of
non-empty closed and bounded sets of a compact (finite-dimensional) metric
space is non-empty, $\mathcal{S}_{0}(\rho^{B},\mathcal{N}_{W})$ is non-empty.
Therefore, using the continuity of
$f(\rho^{{A_{R}}})=I_{c}(\mathcal{N}_{W},\rho^{{A_{R}}})$, and the fact that
$\mathcal{S}_{\epsilon}$ are decreasing non-empty closed and bounded subsets
of a compact (finite-dimensional) metric space gives

$f(\mathcal{S}_{0}(\rho^{B},\mathcal{N}_{W}))=\bigcap_{\epsilon>0}f(\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N}_{W})).$

Noting that the images $f(\mathcal{S}_{\epsilon}(\rho^{B},\mathcal{N}_{W}))$
and $f(\mathcal{S}_{0}(\rho^{B},\mathcal{N}_{W}))$ characterize the rate
regions $\mathcal{I}^{\prime}_{\epsilon}$ and $\mathcal{I}_{0}$, respectively,
and the fact that $\mathcal{I}_{0}$ is closed completes the proof.

###  A-F Proof of Proposition 5

Consider the following inequalities:

$\displaystyle\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}\tilde{\zeta}}\right]$
$\displaystyle\leq\mathbb{E}\left[{\Tr{\left({I-\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}A_{x^{n}}}\right){\rho^{B}}^{\otimes
n}}}\right]=1-\mathbb{E}\left[{\
\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\Tr{A_{x^{n}}{\rho^{B}}^{\otimes
n}}}\right],$
$\displaystyle=1-\frac{(1-\varepsilon)}{(1+\eta)}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\frac{P_{X}^{n}(x^{n})}{(1-\varepsilon)}\Tr{\tilde{\rho}_{x^{n}}},$
$\displaystyle\overset{a}{=}1-\frac{(1-\varepsilon)}{(1+\eta)}\Tr{\tilde{\rho}}\overset{b}{\leq}1-\frac{(1-\varepsilon)}{(1+\eta)}(1-2\varepsilon-2\sqrt{\varepsilon})<\epsilon,$

for all sufficiently large $n$ and all sufficiently small $\eta,\delta>0$,
where (a) follows from (81) and (b) follows from [58, Eq. 28]. This completes
the proof of Proposition 5.

###  A-G Proof of Proposition 6

We begin the proof by splitting the term $\zeta$ under the condition
$\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}=1$; using triangle inequality, we
get $\zeta\leq\zeta_{1}+\zeta_{2}$, where

$\displaystyle\zeta_{1}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\gamma_{x^{n}}\Tr{\tilde{\rho}_{x^{n}}}\norm{\frac{\tilde{\rho}_{x^{n}}}{\Tr{\tilde{\rho}_{x^{n}}}}-\tilde{\rho}_{x^{n}}}_{1},\;\zeta_{2}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\gamma_{x^{n}}\Tr{\tilde{\rho}_{x^{n}}}\norm{\tilde{\rho}_{x^{n}}-\mathcal{W}_{x^{n}}}_{1}.$
(103)

Consider the following inequalities:

$\displaystyle\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}\zeta_{1}}\right]$
$\displaystyle\leq\sum_{m=1}^{2^{nR}}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}\mathbb{E}\left[{\mathbbm{1}_{\left\\{{X^{n}(m)=x^{n}}\right\\}}}\right]\Tr{\tilde{\rho}_{x^{n}}}\norm{\frac{\tilde{\rho}_{x^{n}}}{\Tr{\tilde{\rho}_{x^{n}}}}-\tilde{\rho}_{x^{n}}}_{1}$
$\displaystyle\leq\sum_{m=1}^{2^{nR}}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}\frac{P_{X}^{n}(x^{n})}{(1-\varepsilon)}\left({1-\Tr{\tilde{\rho}_{x^{n}}}}\right)$
$\displaystyle=\frac{(1-\varepsilon)}{(1+\eta)}\left[{1-\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\frac{P_{X}^{n}(x^{n})}{(1-\varepsilon)}\Tr{\tilde{\rho}_{x^{n}}}}\right]$
$\displaystyle\overset{a}{=}\frac{(1-\varepsilon)}{(1+\eta)}\left[{1-\Tr{\tilde{\rho}}}\right]\overset{b}{\leq}\frac{(1-\varepsilon)}{(1+\eta)}(2\varepsilon+2\sqrt{\varepsilon})\leq\epsilon,$

for all sufficiently large $n$ and all sufficiently small $\eta,\delta>0$,
where $(a)$ follows from definition (81), and $(b)$ follows from [58, Eq. 28].
Similarly, we now compute

$\displaystyle\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sP}}\right\\}}\zeta_{2}}\right]$
$\displaystyle\overset{}{\leq}\sum_{m=1}^{2^{nR}}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\frac{(1-\varepsilon)}{(1+\eta)}\frac{1}{2^{nR}}\frac{P_{X}^{n}(x^{n})}{(1-\varepsilon)}\norm{\tilde{\rho}_{x^{n}}-\mathcal{W}^{\otimes
n}_{x^{n}}}_{1}$
$\displaystyle\overset{}{=}\frac{(1-\varepsilon)}{(1+\eta)}\sum_{x^{n}\in\mathcal{T}_{{\delta}}^{(n)}({X})}\frac{P_{X}^{n}(x^{n})}{(1-\varepsilon)}\norm{\tilde{\rho}_{x^{n}}-\mathcal{W}^{\otimes
n}_{x^{n}}}_{1}\leq\epsilon.$

for all sufficiently large $n$ and all sufficiently small $\eta,\delta>0$,
where the last inequality follows from (82). This completes the proof of
Proposition 6.

###  A-H Proof of Proposition 7

Recall, the definition of $E_{M|X^{n}}(m|x^{n})$, for
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$:

$\displaystyle E_{M|X^{n}}(m|x^{n})=$
$\displaystyle\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}\frac{{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})}{{P}_{X}^{n}(x^{n})}\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}.$

Let $D=2^{n(H(X|\hat{X})-\delta_{1})}$, where $\delta_{1}(\delta)\searrow 0$
as $\delta\searrow 0$, and will be specified in the sequel. Define a sequence
of $2^{nR}$ IID random variables
$\left\\{{Z_{m}(x^{n})}\right\\}_{m=1}^{2^{nR}}$, for all
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$,

$\displaystyle Z_{m}(x^{n})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}(1-\varepsilon){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}.$
(104)

We get the following bound on the expectation of the empirical average of
$\\{Z_{m}(x^{n})\\}_{\in[2^{n{R}}]}$, for all sufficiently large $n$:

$\displaystyle\mathbb{E}\bigg{[}\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}DZ_{m}(x^{n})\bigg{]}$
$\displaystyle=\frac{D}{2^{nR}}\sum_{m=1}^{2^{nR}}\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}(1-\varepsilon){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\mathbb{E}[\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}],$
$\displaystyle\overset{}{=}\frac{D}{2^{nR}}\sum_{m=1}^{2^{nR}}\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}P^{n}_{\hat{X}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}},$
$\displaystyle\overset{a}{=}D\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}P^{n}_{\hat{X}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{(x^{n},\hat{x}^{n})\in\mathcal{T}_{\hat{\delta}}^{(n)}(X,\hat{X})\\}}\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}},$
$\displaystyle\overset{b}{\geq}2^{n(H(X|\hat{X})-\delta_{1})}2^{-n(H(X,\hat{X})+2\delta_{1})}2^{n(H(\hat{X}|X)-\delta_{1})}=2^{-n(I(X;\hat{X})+4\delta_{1})},$
(105)

where in $(a)$ follows from the fact that if
$x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})$ and
$\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})$, then
$(x^{n},\hat{x}^{n})\in\mathcal{T}_{\hat{\delta}}^{(n)}(X,\hat{X})$, where
$\hat{\delta}=\delta(|\mathsf{X}|+|\hat{\mathsf{X}}|)$, and $(b)$ follows from
the properties of joint typical and conditional typical sequences and
$\delta_{1}(\delta)$ is a function that follows from the characterization of
the size of the typical set [57].

Furthermore, observe that, for all sufficiently large $n$, we have

$\displaystyle DZ_{m}(x^{n})$ $\displaystyle\leq
2^{n(H(X|\hat{X})-\delta_{1})}2^{-n(H(X|\hat{X})-\delta_{1})}(1-\varepsilon)\Bigg{(}\;\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}\Bigg{)}\leq
1,$ (106)

where the first inequality follows from the properties of joint typical
sequences, i.e., if
$(x^{n},\hat{x}^{n})\in\mathcal{T}_{\hat{\delta}}^{(n)}(X,\hat{X})$, then
${W}_{X|\hat{X}}(x^{n}|\hat{x}^{n})\leq 2^{-n(H(X|\hat{X})-\delta_{1})}$. From
(105) and (106), observe that $\\{DZ_{m}(x^{n})\\}_{m}$ satisfies the
constraints of Lemma 8 (stated below). Thus, after applying Lemma (8) to
$\\{DZ_{m}(x^{n})\\}_{m}$ for all $\eta\in(0,1)$ and
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$, we get

$\displaystyle\\!\\!\Pr\left(Z(x^{n})\in\Big{[}(1-\eta)\mathbb{E}[Z(x^{n})],(1+\eta)\mathbb{E}[Z(x^{n})]\Big{]}\right)\geq
1\\!\\!-\\!2\exp{\\!\\!-\frac{\eta^{2}2^{n(R-I(X;\hat{X})-4\delta_{1})}}{4}\\!\\!},$
(107)

where
$Z(x^{n})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{2^{nR}}\sum_{m=1}^{2^{n{R}}}Z_{m}(x^{n})$.
Moreover, using the definition of $Z_{m}(x^{n})$ and $E_{M|X^{n}}(m|x^{n})$,
we can simplify the above inequality as follows:

$\displaystyle\Pr\left(\\!\\!(1+\eta)P_{X}^{n}(x^{n})\sum_{m=1}^{2^{nR}}E_{M|X^{n}}(m|x^{n})\\!\leq\\!(1+\eta)\mathbb{E}{[Z(x^{n})]}\right)\\!\\!\geq
1\\!\\!-\\!2\exp{\\!\\!-\frac{\eta^{2}2^{n(R-I(X;\hat{X})-4\delta_{1})}}{4}\\!\\!}.$
(108)

Now, observe the following bound on $\mathbb{E}[Z(x^{n})]$

$\displaystyle\frac{1}{P^{n}_{X}(x^{n})}\mathbb{E}[Z(x^{n})]$
$\displaystyle\leq\frac{1}{P^{n}_{X}(x^{n})}\sum_{\hat{x}^{n}}P^{n}_{\hat{X}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})=1.$

This simplifies the inequality $\eqref{eqn:app:Zchernoof}$ as, for all
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$,

$\displaystyle\mathbb{P}\left(\sum_{m=1}^{2^{nR}}E_{M|X^{n}}(m|x^{n})\leq
1\right)\geq
1-2\exp{\bigg{(}-\frac{\eta^{2}2^{n({R}-I(X,\hat{X})-4\delta_{1})}}{4}\bigg{)}}.$

Eventually, using the union bound, we get

$\displaystyle\Pr\left[\;\bigcap_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}\left({\sum_{m=1}^{2^{n{R}}}E_{M|X^{n}}(m|x^{n})\leq
1}\right)\right]$ $\displaystyle\geq
1-\\!\\!\\!\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}\Pr\left(\sum_{m=1}^{2^{n{R}}}E_{M|X^{n}}(m|x^{n})>1\right),$
$\displaystyle\geq
1-2|\mathcal{T}_{\hat{\delta}}^{(n)}({X})|\exp{\\!\\!-\frac{\eta^{2}2^{n(R-I(X;\hat{X})-4\delta_{1})}}{4}\\!\\!}.$
(109)

Thus, if ${R}>I(X;\hat{X})+4\delta_{1}$, the second term in the right hand
side of (109) decays exponentially to zero, and as a result, the probability
of the above intersections goes to 1. This completes the proof of Proposition
7.

######  Lemma 8.

Let $\\{Z_{n}\\}_{n=1}^{N}$ be a sequence of N IID random variables bounded
between zero and one, i.e., $Z_{n}\in[0,1]\quad\forall n\in[N]$, and suppose
$\mathbb{E}\bigg{[}\frac{1}{N}\sum_{n=1}^{N}Z_{n}\bigg{]}=\mu$ be bounded
below by a positive constant $\theta$ as $\mu\geq\theta$ where
$\theta\in(0,1)$, then for every $\eta\in(0,1/2)$ and $(1+\eta)\theta<1$, we
can bound the probability that the ensemble average of the sequence
$\\{Z_{n}\\}_{n=1}^{N}$ lies in $(1\pm\eta)\mu$ as

$\displaystyle\mathbb{P}\bigg{(}\frac{1}{N}\sum_{n=1}^{N}Z_{n}\in$
$\displaystyle[(1-\eta)\mu,(1+\eta)\mu]\bigg{)}\geq
1-2\exp{\bigg{(}-\frac{N\eta^{2}\theta}{4}\bigg{)}}.$ (110)

###### Proof.

Follows from the Operator Chernoff Bound [64]. ∎

###  A-I Proof of Proposition 8

Fix an $\epsilon>0$. Recall, the definition of $Z_{m}(x^{n})$ for
$x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$ from Appendix A-H,

$\displaystyle Z_{m}(x^{n})$
$\displaystyle=\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}(1-\varepsilon){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}.$

We begin by using the lower bound from (107) given in Appendix A-H. We have
for all sufficiently large $n$:

$\displaystyle\sum_{m=1}^{2^{n{R}}}E_{M|X^{n}}(m|x^{n})$
$\displaystyle=\left(\frac{1}{1+\eta}\right)\frac{1}{P^{n}_{X}(x^{n})}\frac{1}{2^{n{R}}}\sum_{m=1}^{2^{n{R}}}Z_{m}(x^{n})$
$\displaystyle\stackrel{{\scriptstyle
w.h.p}}{{\geq}}\left(\frac{1-\eta}{1+\eta}\right)\frac{1}{P^{n}_{X}(x^{n})}\mathbb{E}[Z(x^{n})]\geq\left(\frac{1-\eta}{1+\eta}\right)(1-\epsilon),$
(111)

where the first inequality uses the lower bound from (107), which holds true
with probability greater than $1-\tau$, where
$\tau\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}2\exp{\bigg{(}-\frac{\eta^{2}2^{n({R}-I(X,W)-4\delta_{1})}}{4}\bigg{)}}$,
and the second inequality uses the following bound on $\mathbb{E}[Z(x^{n})]$,
for all sufficiently large $n$:

$\displaystyle\frac{1}{{P}_{X}^{n}(x^{n})}\mathbb{E}[Z(x^{n})]$
$\displaystyle=\frac{1}{{P}_{X}^{n}(x^{n})}\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}P^{n}_{\hat{X}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\geq(1-\epsilon).$
(112)

Using (112), we get, with probability greater than
$(1-|\mathcal{T}_{\hat{\delta}}^{(n)}({X})|\tau)$ and for all sufficiently
large $n$,

$\displaystyle\widetilde{\zeta}$
$\displaystyle\leq\\!\\!\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}{P}_{X}^{n}(x^{n})\Bigg{(}1-\left({\frac{1-\eta}{1+\eta}}\right)(1-\epsilon)\Bigg{)}\leq\frac{2\eta+{\epsilon}(1-\eta)}{1+\eta}.$

Noting that
$\widetilde{\zeta}\cdot\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\leq 1,$
and using the above result, we have, for all sufficiently large $n$,

$\displaystyle\mathbb{E}\left[\widetilde{\zeta}\cdot\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\right]\leq\frac{2\eta+\epsilon(1-\eta)}{1+\eta}+\tau.$
(113)

Therefore, if $R>I(X;\hat{X})+4\delta_{1}$, then $\tau\rightarrow 0$ for all
sufficiently large $n$. Hence,
$\mathbb{E}\left[\widetilde{\zeta}\cdot\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\right]$
can be made smaller than $\epsilon$ for all sufficiently large $n$ and
sufficiently small $\eta$. This completes the proof of Proposition 8.

###  A-J Proof of Proposition 9

We begin by writing the PMF $P_{M}(m)$ for $m\in[2^{nR}]$ and under the
condition that $\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}=1$.

$\displaystyle P_{M}(m)$
$\displaystyle=\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}{P}_{X}^{n}(x^{n})E_{M|X^{n}}(m|x^{n}),$
$\displaystyle=\sum_{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}\\!\\!\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}.$
(114)

We now argue that the error term $\zeta$, averaged over the random codebook,
can be made arbitrarily small by the following inequalities:

$\displaystyle\mathbb{E}_{\mathcal{C}}\left[{\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\zeta}\right]$
$\displaystyle\overset{}{\leq}\mathbb{E}\left[{\mathbbm{1}_{\left\\{{\mbox{sPMF}}\right\\}}\sum_{m\in[2^{nR}]}\sum_{\begin{subarray}{c}\hat{x}^{n}\\\
x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\end{subarray}}\left|{{P}_{X}^{n}(x^{n})E_{M|X^{n}}(m|x^{n})-P_{M}(m){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})}\right|\mathbbm{1}_{\\{\hat{X}^{n}(m)=\hat{x}^{n}\\}}}\right]$
$\displaystyle\leq\sum_{m\in[2^{nR}]}\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\end{subarray}}\mathbb{P}(\hat{X}^{n}(m)=\hat{x}^{n})\Bigg{|}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\mathbbm{1}_{\\{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\\}}\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}$
$\displaystyle\hskip
50.58878pt-\left({\sum_{\texttt{x}^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}{W}_{X|\hat{X}}^{n}(\texttt{x}^{n}|\hat{x}^{n})\mathbbm{1}_{\\{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\\}}\mathbbm{1}_{\\{\texttt{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}}\right){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\Bigg{|}$
$\displaystyle=\\!\\!\\!\sum_{m\in[2^{nR}]}\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\\
\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\end{subarray}}\\!\\!\\!\frac{1}{2^{nR}}\frac{1}{(1+\eta)}P^{n}_{\hat{X}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\Bigg{|}\mathbbm{1}_{\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}}-\\!\\!\\!\\!\\!\\!\sum_{\texttt{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})}\\!\\!\\!{W}_{X|\hat{X}}^{n}(\texttt{x}^{n}|\hat{x}^{n})\Bigg{|}$
$\displaystyle\overset{a}{\leq}\sum_{m\in[2^{nR}]}\sum_{\begin{subarray}{c}\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\end{subarray}}\\!\\!\\!\frac{1}{2^{nR}}\frac{1}{(1+\eta)}P^{n}_{\hat{X}}(\hat{x}^{n})\;2\\!\\!\\!\\!\sum_{\begin{subarray}{c}x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\\
\texttt{x}^{n}\not\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\end{subarray}}{W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n}){W}_{X|\hat{X}}^{n}(\texttt{x}^{n}|\hat{x}^{n})$
$\displaystyle\overset{}{\leq}\sum_{\begin{subarray}{c}m\in[2^{nR}]\\\
\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})\end{subarray}}\\!\\!\\!\frac{1}{2^{nR}}\frac{1}{(1+\eta)}P^{n}_{\hat{X}}(\hat{x}^{n})\;2\\!\\!\\!\\!\sum_{\begin{subarray}{c}\texttt{x}^{n}\not\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\end{subarray}}{W}_{X|\hat{X}}^{n}(\texttt{x}^{n}|\hat{x}^{n})$
$\displaystyle\overset{b}{\leq}\sum_{m\in[2^{nR}]}\frac{1}{2^{nR}}\frac{(1-\varepsilon)}{(1+\eta)}\left({\;\sum_{\hat{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(\hat{X})}\frac{1}{(1-\varepsilon)}P^{n}_{\hat{X}}(\hat{x}^{n})}\right)2\epsilon\leq
2\epsilon,$

for all sufficiently large $n$ and all $\eta,\delta>0$, where $(a)$ follows by
splitting the summation over $x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})$
as summation over
$\\{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}\cap\\{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\}$
and
$\\{x^{n}\not\in\mathcal{T}_{\delta}^{(n)}(X|\hat{x}^{n})\\}\cap\\{x^{n}\in\mathcal{T}_{\hat{\delta}}^{(n)}({X})\\}$
and $(b)$ follows from the standard conditional typicality argument. This
completes the proof of Proposition 9.

###  A-K Proof of Lemma 6

Consider the following inequalities:

$\displaystyle\|P_{X^{n}\hat{X}^{n}}(x^{n},\hat{x}^{n})$ $\displaystyle-
P_{\hat{X}^{n}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\|_{\text{TV}}$
$\displaystyle=\frac{1}{2}\sum_{x^{n},\hat{x}^{n}}\Big{(}\sum_{i}\frac{1}{n}\Big{)}\Big{|}P_{X^{n}\hat{X}^{n}}(x^{n},\hat{x}^{n})-P_{\hat{X}^{n}}(\hat{x}^{n}){W}_{X|\hat{X}}^{n}(x^{n}|\hat{x}^{n})\Big{|}$
$\displaystyle=\frac{1}{2}\sum_{i,x^{n},\hat{x}^{n}}\frac{1}{n}\Big{|}P_{X_{i}\hat{X}_{i}}(x_{i},\hat{x}_{i})P_{X^{n\backslash
i}\hat{X}^{n\backslash i}|X_{i}\hat{X}_{i}}(x^{n\backslash
i},\hat{x}^{n\backslash i}|x_{i},\hat{x}_{i})$ $\displaystyle\hskip 108.405pt-
P_{\hat{X}_{i}}(\hat{x}_{i}){W}_{X|\hat{X}}(x_{i}|\hat{x}_{i})P_{\hat{X}^{n\backslash
i}|\hat{X}_{i}}(\hat{x}^{n\backslash i}|\hat{x}_{i})\Pi_{j\neq
i}{W}_{X|\hat{X}}(x_{j}|\hat{x}_{j})\Big{|}$
$\displaystyle\overset{}{\geq}\frac{1}{2}\sum_{i,x_{i},\hat{x}_{i}}\frac{1}{n}\Big{|}P_{X_{i}\hat{X}_{i}}(x_{i},\hat{x}_{i})-P_{\hat{X}_{i}}(\hat{x}_{i}){W}_{X|\hat{X}}(x_{i}|\hat{x}_{i})\Big{|}$
$\displaystyle\overset{}{\geq}\frac{1}{2}\sum_{x,\hat{x}}\Big{|}\sum_{i}\frac{1}{n}P_{X_{i}\hat{X}_{i}}(x,\hat{x})-\sum_{i}\frac{1}{n}P_{\hat{X}_{i}}(\hat{x}){W}_{X|\hat{X}}(x|\hat{x})\Big{|}$
$\displaystyle=\|P_{X_{Q}\hat{X}_{Q}}-P_{\hat{X}_{Q}}{W}_{X|\hat{X}}\|_{TV}\geq\|P_{X}-\sum_{\hat{x}}P_{\hat{X}_{Q}}(\hat{x}){W}_{X|\hat{X}}(\cdot|\hat{x})\|_{\text{TV}},$

where the above inequalities are the consequence of triangle inequality and
the fact that $P_{X_{Q}}=P_{X}$.

## References

  * [1] B. Schumacher, “Quantum coding,” _Physical Review A_ , vol. 51, no. 4, p. 2738, 1995.
  * [2] R. Jozsa and B. Schumacher, “A new proof of the quantum noiseless coding theorem,” _Journal of Modern Optics_ , vol. 41, no. 12, pp. 2343–2349, 1994\.
  * [3] A. Winter, “Coding theorems of quantum information theory,” _arXiv preprint quant-ph/9907077_ , 1999.
  * [4] Z. Baghali Khanian, “Strong converse bounds for compression of mixed states,” _arXiv e-prints_ , pp. arXiv–2206, 2022.
  * [5] H. Barnum, “Quantum rate-distortion coding,” _Physical Review A_ , vol. 62, no. 4, p. 042309, 2000.
  * [6] C. E. Shannon _et al._ , “Coding theorems for a discrete source with a fidelity criterion,” _IRE Nat. Conv. Rec_ , vol. 4, no. 142-163, p. 1, 1959\.
  * [7] N. Datta, M.-H. Hsieh, and M. M. Wilde, “Quantum rate distortion, reverse shannon theorems, and source-channel separation,” _IEEE Transactions on Information Theory_ , vol. 59, no. 1, pp. 615–630, 2012.
  * [8] M. M. Wilde, N. Datta, M.-H. Hsieh, and A. Winter, “Quantum rate-distortion coding with auxiliary resources,” _IEEE Transactions on Information Theory_ , vol. 59, no. 10, pp. 6755–6773, 2013.
  * [9] M. Berta, M. Christandl, and R. Renner, “The quantum reverse shannon theorem based on one-shot information theory,” _Communications in Mathematical Physics_ , vol. 306, no. 3, pp. 579–615, 2011.
  * [10] C. H. Bennett, I. Devetak, A. W. Harrow, P. W. Shor, and A. Winter, “The quantum reverse shannon theorem and resource tradeoffs for simulating quantum channels,” _IEEE Transactions on Information Theory_ , vol. 60, no. 5, pp. 2926–2959, 2014.
  * [11] N. Datta, M.-H. Hsieh, M. M. Wilde, and A. Winter, “Quantum-to-classical rate distortion coding,” _Journal of Mathematical Physics_ , vol. 54, no. 4, p. 042201, 2013.
  * [12] I. Devetak and J. Yard, “Exact cost of redistributing multipartite quantum states,” _Physical Review Letters_ , vol. 100, no. 23, p. 230501, 2008.
  * [13] Z. Luo and I. Devetak, “Channel simulation with quantum side information,” _IEEE Transactions on Information Theory_ , vol. 55, no. 3, pp. 1331–1342, 2009.
  * [14] Z. B. Khanian and A. Winter, “A rate-distortion perspective on quantum state redistribution,” _arXiv preprint arXiv:2112.11952_ , 2021.
  * [15] ——, “General mixed-state quantum data compression with and without entanglement assistance,” _IEEE Transactions on Information Theory_ , vol. 68, no. 5, pp. 3130–3138, 2022.
  * [16] Z. Baghali Khanian, K. Kuroiwa, and D. Leung, “Rate-distortion theory for mixed states,” _arXiv e-prints_ , pp. arXiv–2208, 2022.
  * [17] M. Koashi and N. Imoto, “Compressibility of quantum mixed-state signals,” _Physical Review Letters_ , vol. 87, no. 1, p. 017902, 2001.
  * [18] I. Devetak and T. Berger, “Quantum rate-distortion theory for memoryless sources,” _IEEE Transactions on Information Theory_ , vol. 48, no. 6, pp. 1580–1589, 2002.
  * [19] A. Winter, “Compression of sources of probability distributions and density operators,” _arXiv preprint quant-ph/0208131_ , 2002.
  * [20] N. Datta, J. M. Renes, R. Renner, and M. M. Wilde, “One-shot lossy quantum data compression,” _IEEE Transactions on Information Theory_ , vol. 59, no. 12, pp. 8057–8076, 2013.
  * [21] M.-H. Hsieh and S. Watanabe, “Channel simulation and coded source compression,” _IEEE Transactions on Information Theory_ , vol. 62, no. 11, pp. 6609–6619, 2016.
  * [22] S. Salek, D. Cadamuro, P. Kammerlander, and K. Wiesner, “Quantum rate-distortion coding of relevant information,” _IEEE Transactions on Information Theory_ , vol. 65, no. 4, pp. 2603–2613, 2018.
  * [23] A. Anshu, R. Jain, and N. A. Warsi, “Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction,” _IEEE Transactions on Information Theory_ , vol. 65, no. 9, pp. 5905–5924, 2019.
  * [24] I. Csiszár and J. Körner, _Information theory: coding theorems for discrete memoryless systems_. Cambridge University Press, 2011.
  * [25] A. S. Holevo, “The capacity of the quantum channel with general signal states,” _IEEE Transactions on Information Theory_ , vol. 44, no. 1, pp. 269–273, 1998.
  * [26] B. Schumacher and M. D. Westmoreland, “Sending classical information via noisy quantum channels,” _Physical Review A_ , vol. 56, no. 1, p. 131, 1997.
  * [27] A. Winter, “”Extrinsic” and ”intrinsic” data in quantum measurements: asymptotic convex decomposition of positive operator valued measures,” _Communication in Mathematical Physics_ , vol. 244, no. 1, pp. 157–185, 2004\.
  * [28] A. S. Holevo, “Quantum systems, channels, information,” in _Quantum Systems, Channels, Information_. de Gruyter, 2019.
  * [29] H.-C. Cheng, E. P. Hanson, N. Datta, and M.-H. Hsieh, “Duality between source coding with quantum side information and cq channel coding,” in _2019 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2019, pp. 1142–1146.
  * [30] S. Lloyd, “Capacity of the noisy quantum channel,” _Physical Review A_ , vol. 55, no. 3, p. 1613, 1997.
  * [31] P. W. Shor, “The quantum channel capacity and coherent information,” in _lecture notes, MSRI Workshop on Quantum Computation_ , 2002.
  * [32] I. Devetak, “The private classical capacity and quantum capacity of a quantum channel,” _IEEE Transactions on Information Theory_ , vol. 51, no. 1, pp. 44–55, 2005.
  * [33] P. Hayden, M. Horodecki, A. Winter, and J. Yard, “A decoupling approach to the quantum capacity,” _Open Systems & Information Dynamics_, vol. 15, no. 01, pp. 7–19, 2008.
  * [34] M. A. Nielsen and I. Chuang, “Quantum computation and quantum information,” 2002\.
  * [35] T. Berger, “Rate distortion theory and data compression,” in _Advances in Source Coding_. Springer, 1975, pp. 1–39.
  * [36] R. G. Gallager, _Information theory and reliable communication_. Springer, 1968, vol. 588.
  * [37] T. Berger, _Rate Distortion Theory: A Mathematical Basis for Data Compression_ , ser. Prentice-Hall electrical engineering series. Prentice-Hall, 1971.
  * [38] A. M. Gerrish, “Estimation of information rates,” Ph.D. dissertation, Yale University, 1963.
  * [39] S. Shamai and S. Verdú, “The empirical distribution of good codes,” _IEEE Transactions on Information Theory_ , vol. 43, no. 3, pp. 836–846, 1997\.
  * [40] S. S. Pradhan, “Approximation of test channels in source coding,” in _Proc. Conf. Inform. Syst. Sci.(CISS)_ , 2004.
  * [41] T. Weissman and E. Ordentlich, “The empirical distribution of rate-constrained source codes,” _IEEE transactions on information theory_ , vol. 51, no. 11, pp. 3718–3733, 2005.
  * [42] P. W. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,” _IEEE Transactions on Information Theory_ , vol. 56, no. 9, pp. 4181–4206, 2010.
  * [43] C. Schieler and P. Cuff, “A connection between good rate-distortion codes and backward dmcs,” in _2013 IEEE Information Theory Workshop (ITW)_. IEEE, 2013, pp. 1–5.
  * [44] V. Kostina and S. Verdú, “The output distribution of good lossy source codes,” in _2015 Information Theory and Applications Workshop (ITA)_. IEEE, 2015, pp. 308–312.
  * [45] H. V. Poor, _An introduction to signal detection and estimation_. Springer Science & Business Media, 1998.
  * [46] D. Petz, “Sufficient subalgebras and the relative entropy of states of a von neumann algebra,” _Communications in mathematical physics_ , vol. 105, no. 1, pp. 123–131, 1986.
  * [47] H. Barnum and E. Knill, “Reversing quantum dynamics with near-optimal quantum and classical fidelity,” _Journal of Mathematical Physics_ , vol. 43, no. 5, pp. 2097–2106, 2002.
  * [48] P. Hayden, R. Jozsa, D. Petz, and A. Winter, “Structure of states which satisfy strong subadditivity of quantum entropy with equality,” _Communications in mathematical physics_ , vol. 246, no. 2, pp. 359–374, 2004\.
  * [49] A. Uhlmann, “The “transition probability” in the state space of a*-algebra,” _Reports on Mathematical Physics_ , vol. 9, no. 2, pp. 273–279, 1976.
  * [50] M. M. Wilde, “From classical to quantum shannon theory,” _arXiv preprint arXiv:1106.1445_ , 2011.
  * [51] P. Cuff, “Distributed channel synthesis,” _IEEE Transactions on Information Theory_ , vol. 59, no. 11, pp. 7071–7096, 2013.
  * [52] T. A. Atif, A. Padakandla, and S. S. Pradhan, “Source coding for synthesizing correlated randomness,” _IEEE Transactions on Information Theory_ , 2022\.
  * [53] C. A. Fuchs and J. Van De Graaf, “Cryptographic distinguishability measures for quantum-mechanical states,” _IEEE Transactions on Information Theory_ , vol. 45, no. 4, pp. 1216–1227, 1999.
  * [54] M. Naimark, “Spectral functions of a symmetric operator,” _Bull. Acad. Sci. URSS. Sér. Math.[Izvestia Akad. Nauk SSSR]_ , vol. 4, pp. 277–318, 1940\.
  * [55] M. M. Wilde, “Sequential decoding of a general classical-quantum channel,” _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , vol. 469, no. 2157, p. 20130259, 2013.
  * [56] H. Mattson Jr, “An upper bound on covering radius,” in _Combinatorial Mathematics Proceedings of the International Colloquium on Graph Theory and Combinatorics_ , vol. 75, 2012, pp. 453–458.
  * [57] T. M. Cover and J. A. Thomas, “Elements of information theory 2nd edition (wiley series in telecommunications and signal processing),” _Acessado em_ , 2006.
  * [58] M. M. Wilde, P. Hayden, F. Buscemi, and M.-H. Hsieh, “The information-theoretic costs of simulating quantum measurements,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 45, no. 45, p. 453001, 2012.
  * [59] A. Anshu, R. Jain, and N. Warsi, “Measurement compression with quantum side information using shared randomness,” _arXiv preprint arXiv:1703.02342_ , 2017.
  * [60] G. M. Ziegler, _Lectures on polytopes_. Springer Science & Business Media, 2012, vol. 152.
  * [61] G. Dueck, “The strong converse to the coding theorem for the multiple–access channel,” _J. Comb. Inform. Syst. Sci_ , vol. 6, no. 3, pp. 187–196, 1981\.
  * [62] R. Ahlswede and N. Cai, “A strong converse theorem for quantum multiple access channels,” in _General Theory of Information Transfer and Combinatorics_. Springer, 2006, pp. 460–485.
  * [63] R. T. Powers and E. Størmer, “Free states of the canonical anticommutation relations,” _Communications in Mathematical Physics_ , vol. 16, no. 1, pp. 1–33, 1970.
  * [64] R. Ahlswede and A. Winter, “Strong converse for identification via quantum channels,” _IEEE Transactions on Information Theory_ , vol. 48, no. 3, pp. 569–579, 2002.