Optimal Simulation of Quantum Measurements via the Likelihood POVMs

Arun Padakandla

We provide a new and simplified proof of Winter's measurement compression [1] via likelihood POVMs. Secondly, we provide an alternate proof of the central tool at the heart of this theorem - the Quantum covering lemma. Our proof does not rely on the Ahlswede Winter's operator Chernoff bound [2] and is applicable even when the random operators are pairwise independent. We leverage these results to design structured POVMs and prove their optimality in regards to communication rates.

§ INTRODUCTION

Exploiting the unique behaviour of sub-atomic particles can enable us transform information processing. Measurements play a central role in extracting information and reading out the result of computations performed on a quantum computing device. The design and analysis of quantum measurements thus plays a central role in quantum information processing. In this article, we address the question of how much information is contained in the outcome of a Positive Operator Valued Measurement (POVM).

The outcome of a quantum measurement is random and one of the challenges in addressing the above question is to precisely characterize and quantify that component of the randomness that is intrinsic to the quantum state. This question, being of fundamental importance, has been addressed in a long series of works [3, 4, 5, 6]. In 2004, Winter adopted an information theoretic viewpoint and derived an elegant formulation. His definitive solution to this problem stands as one among the important findings in quantum information theory.

Our work is aimed at answering analogous questions involving multiple and distributed measurements. One question of interest is to study how much information is contained in successive POVMs that are jointly measurable. A second question of interest is to characterize the information contained in the outcomes of distributed measurements performed on entangled states. In this work, we present some of the foundational tools required to answer these questions. Our first contribution involves a new treatment of Winter's findings. This includes a new proof using likelihood POVMS which are much simpler to describe in comparison to those studied in [1], [7] including more recent studies [8, 9, 10]. While the likelihood POVMs are indeed the most intuitive to design, its performance analysis for the problem at hand has remained elusive. Indeed, even while [7] provides an excellent exposition of [1], the simulation POVM and its study is identical and involved. Through a carefully chosen sequence of steps, highlighted in Sec. <ref>, <ref>, we demonstrate the simplicity of likelihood POVMs also facilitates a simplified proof.

As a next step, we revisit the fundamental tool - quantum covering lemma (QCL) <cit.>. Known proofs of QCL are based on the Ahlswede and Winter's [2] operator Chernoff bound (OCB). The OCB requires that the random operators be mutually independent. Its use for the problem at hand precludes the simulation POVM to have any additional structure. For example, relying on the OCB simulation precludes proving optimality of a simulation POVM with a `algebraic closure structure' (Sec. <ref>). This is because, if one picks a random POVM with an algebraic structure, its operators are not mutually independent. Our second contribution is a new proof (Lem. <ref>, Sec. <ref>) of the QCL that does not rely on the OCB and the underlying concentration only requires pairwise independence. Building on this we design - as an application of all our findings - structured likelihood POVMs (Sec. <ref>) that simulate POVMs with optimal communication costs (Thm. <ref>).

Given the technical nature of our work on a studied problem, this article is heavy on details. Yet, the simplicity of the proofs have enabled us illustrate the key new steps through Sec. <ref>, <ref> and also leverage elegant, useful operator properties such as the Löwner Heinz theorem [12] and the operator monotonicity of the square root function that will hopefully find other applications in quantum information theory.

§ PRELIMINARIES AND PROBLEM DESCRIPTION

§.§ Notation

We supplement standard quantum information theory notation with the following. $\alpha^{*} \in \complex$ denotes complex conjugate of $\alpha\in\complex$. For a positive integer $n$, we let $[n] \define \{1,\cdots,n\}, [\overline{n}]\define\{0\}\cup [n]$. All Hilbert spaces are assumed to be finite dimensional. $\mathcal{L}(\mathcal{H})$, $\mathcal{R}(\mathcal{H})$, $\mathcal{P}(\mathcal{H})$, $\mathcal{D}(\mathcal{H})$ denote the collection of linear, Hermitian, positive and density operators acting on Hilbert space $\mathcal{H}$ respectively. $T^{\dagger} \in \CalL(\CalH)$ denotes the adjoint of $T \in \CalL(\CalH)$.

POVMs will play a central role in this article. $\mathscr{M}(\mathcal{H},\mathcal{Y})$ denotes the set of all POVMs acting on $\mathcal{H}$ with outcomes in $\mathcal{Y}$ and $\mathscr{M}(\mathcal{H}) =\displaystyle \cup_{\mathcal{Y}:|\mathcal{Y}|<\infty}\mathscr{M}(\mathcal{H},\mathcal{Y})$ contain POVMs with finite outcome sets. An element of $\mathscr{M}(\mathcal{H},\mathcal{Y})$ is therefore a collection of $|\CalY|$ positive operators[not necessarily distinct] acting on $\CalH$ that sum to $I_{\CalH}$ - the identity operator on $\CalH$. Often times, we denote a POVM $\lambda = \{ \lambda_{y}\in \posop(\HlbSp): y \in \CalY\} \in \mathscr{M}(\mathcal{H},\mathcal{Y})$ by adding the outcome set as a subscript, as in $\lambda_{\CalY}=\lambda$. For POVM $\lambda = \{\lambda_{y}:y \in \mathcal{Y}\}$, $\lambda^{\otimes n}\define\{\lambda_{y^{n}}\define \lambda_{y_{1}}\otimes \cdots\otimes \lambda_{y_{n}}:y^{n}\in \CalY^{n}\}$. To reduce clutter, we let $\lambda^{n}=\lambda_{\mathcal{Y}^{n}}=\lambda^{\otimes n} \in \ScrM(\CalHA^{\otimes n},\CalY^{n})$ denote the same latter POVM. When $\CommK,\InfM\in \naturals$, $c:[\CommK]\times[\InfM]\rightarrow\mathcal{W}^{n}$ is a map, then $c(k,m) \define (c(k,m)_{1},\cdots,c(k,m)_{n}) \in \mathcal{W}^{n}$. When clear from context, we let $w^{n}(k,m)=c(k,m)=(w_{1}(k,m),\cdots,w_{n}(k,m))$. In such a context with $\mu_{\mathcal{W}} = \{\mu_{w}:w \in \mathcal{W}\}$ being a POVM, we let $\mu_{k,m}\define \mu_{w^{n}(k,m)} \define \mu_{c(k,m)} \define \mu_{c(k,m)_{1}}\otimes \cdots\otimes \mu_{c(k,m)_{n}}$.If $\CommK,\InfM\in \naturals$, we let $[\CommK \InfM]$ denote $[\CommK]\times[\InfM]$.To facilitate unified treatment, classical register values, such as $y \in \CalY$ are modeled as $\ketbra{y}{y} \in \densityop(\HlbSp_{\CalY})$ wherein $\mathcal{H}_{\mathcal{Y}} \define \span\{\ket{y}:y \in \mathcal{Y}\}$ with $\braket{\haty}{y}=\delta_{\haty y}$. To remind the reader that we are only dealing with distinguishable objects in $\HlbSp_{\CalY}$, we often times denote $\HlbSp_{\CalY}^{*}=\HlbSp_{\CalY}$ and $\HlbSp_{\CalY^{n}}^{*}=\HlbSp_{\CalY}^{\otimes n}$.

Associated with a POVM $\lambda =\{\lambda_{y} \in \CalP(\CalH) :y \in \mathcal{Y} \}$ is a Hilbert space $\mathcal{H}_{\mathcal{Y}} \define \span\{\ket{y}:y \in \mathcal{Y}\}$ with $\braket{\haty}{y}=\delta_{\haty y}$ and the CPTP map $\mathscr{E}^{\lambda}:\mathcal{L}(\mathcal{H})\rightarrow \mathcal{L}(\mathcal{H}_{\mathcal{Y}})$, defined as $\mathscr{E}^{\lambda}(s)=\sum_{y \in \mathcal{Y}}\tr(s\lambda_{y})\ketbra{y}{y}$. For POVMs $\lambda_{\CalY} =  \{\lambda_{y} \in \CalP(\CalH) :y \in \mathcal{Y} \}\in \ScrM(\CalH,\CalY)$ and $\theta_{\CalZ} = \{\theta_{z} \in \CalP(\CalH) : z \in \CalZ\}\in \ScrM(\CalH,{\CalZ})$, we let $\theta\circ \lambda= \theta_{\CalZ}\circ \lambda_{\CalY} = \{   \sum_{y \in \CalY}\theta_{z}\} \in \ScrM(\CalH,\CalZ)$ denote the composition POVM. For a stochastic matrix $(p_{Y|W}(y|w):(w,y)\in \mathcal{W}\times \mathcal{Y})$, we let $\mathscr{E}^{{Y|W}}_{p}:\linop(\mathcal{H}_{\mathcal{W}})\rightarrow \linop(\HlbSp_{\mathcal{Y}})$ denote the CPTP map $\mathscr{E}^{{Y|W}}_{p}(a) \define \sum_{(w,y) \in \mathcal{W}\times \mathcal{Y}}p_{Y|W}(y|w)\ketbra{y}{w}a\ketbra{w}{y}$. The composition of CPTP maps $\mathcal{L}(\mathcal{H}_{A})\stackrel{\mathscr{E}_{1}}{\rightarrow} \mathcal{L}(\mathcal{H}_{B})$, $\mathcal{L}(\mathcal{H}_{B})\stackrel{\mathscr{E}_{2}}{\rightarrow} \mathcal{L}(\mathcal{H}_{C})$ is denoted $\mathscr{E}_{2}\circ\mathscr{E}_{1}$.

A quantum ensemble $(\rho_{w},p_{W},\CalW)$ comprises of (i) a finite set $\CalW$, (ii) a collection of density operators $\rho_{w}\in \CalD(\CalH) : w \in \CalW$ and (iii) a probability mass function (PMF) $p_{W}$ on $\CalW$ such that $\sum_{w \in \CalW}p_{W}(w)\rho_{w}=\rho$. We also refer to a quantum ensemble $(\rho_{w},p_{W},\CalW)$ as an ensemble $(\rho_{w},p_{W},\CalW)$ or an ensemble $(\rho_{w},p_{W},\CalW)$ with average $\sum_{w\in \mathcal{W}}p_{W}(w)\rho_{w}$. For an ensemble $(\rho_{w},p_{W},\CalW)$, $\chi(\rho_{w};p_{W}(w):\mathcal{W}) \define S(\sum_{w\in \mathcal{W}}p_{W}(w)\rho_{w})-\sum_{w\in \mathcal{W}}p_{W}(w)S(\rho_{w})$ denotes Holevo information. SCD, WHP abbreviate spectral decomposition and with high probability. For POVMs $\lambda \define \lambda_{\mathcal{Y}} \in \mathscr{M}(\mathcal{H},\mathcal{Y})$ and $\Delta \define \Delta_{\mathcal{Z}} = \{\Delta_{z}:z \in \mathcal{Z}\} \in \mathscr{M}(\mathcal{H}_{\mathcal{Y}},\mathcal{Z})$, we let $\Delta \circ \lambda \define \{ \delta_{z}\}$

We let $\{\ket{b_{1}},\cdots,\ket{b_{d}}\} \subseteq \CalHA$ denote an arbitrary but fixed orthonormal basis and $\CalH_{X} =\CalHA$. For any $\ket{x} =\sum_{i=1}^{d}\alpha_{i}\ket{b_{i}} \in \CalHA$, we let $\ket{\olinex}=\sum_{i=1}^{d}\alpha_{i}^{*}\ket{b_{i}}\in \CalH_{A}$ denote the complex conjugation with respect to orthonormal basis $\{\ket{b_{1}},\cdots,\ket{b_{d}}\}$. For any $\sigma \in \CalD(\CalHA)$, with a spectral decomposition $\sigma = \sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}$, we let $|ϕ_σ⟩ ∑_i=1^d√(γ_i)|_i⟩⊗|u_i⟩ ∈_X⊗$ denote a purification of $σ$, henceforth referred to as the canonical purification \cite[App.~A]{200401CommMathPhy_Win} of $σ$. Analogously, we let $|ϕ_σ^⊗n⟩ = ∑_i_1=1^d ⋯∑_i_n=1^d√(γ_i_1⋯γ_i_n)|_i_1⟩ ⋯⊗⋯|_i_n⟩⊗|u_i_1⟩ ⋯⊗⋯|u_i_n⟩ ∈_X^⊗n ⊗^⊗n$  denote a purification of $σ^⊗n$.

\subsection{Problem Description}
\label{SubSec:ProblemDescription}

Let Hilbert space $ℋ_A$ have dimension $d_A$. Let $ρ∈𝒟(ℋ_A)$ model the behaviour of a given sub-atomic particle and $λλ_𝒴 {λ_y ∈𝒫(ℋ_A) : y ∈𝒴 }$ denote a given POVM. We follow [1], [7] in modelling the following question. Suppose a measurement modeled via POVM $λ_𝒴$ is performed on the particle $ρ∈𝒟(ℋ_A)$, how much `intrinsic' information does the outcome contain? The statistical nature of the outcome leads us to a Shannon-theoretic modeling. If one performs $n$ (independent) measurements $λ_𝒴^⊗n$ on $n$ identically prepared particles $ρ^⊗n$, how many bits are necessary to compress the $n$ random outcomes?

\begin{figure}
\centering
\includegraphics[width=3.35in]{SnglEncSnglDecMsmtSimulation}
\vspace{-0.2in}
\caption{Illustrates original and similated POVMs. The components in the two blue ellipses must be statistically indistinguishable.}
\label{Fig:SnglEncSnglDecMsmtSimulation}
\vspace{-0.2in}
\end{figure}
Since a measurement outcome is random, what fraction of the inherent randomness is `intrinsic' to the particle $ρ$, and what fraction is `extrinsic', or unrelated to $ρ$? To quantify this, we design an `alternate $n-$letter measurement' - a simulated POVM - that is supplemented with an external source of \textit{common randomness} of $C$ bits/letter (Fig.~\ref{Fig:SnglEncSnglDecMsmtSimulation}) available at both terminals. These $C$ bits of common randomness are statistically independent of the particle and are available to (i) design this simulated POVM and (ii) postprocess its outcome to simulate the outcome of the original POVM $λ_𝒴$ on $ρ$. We require the outcome of the simulated POVM - both the post measurement particle and the observed outcome $Y^n ∈𝒴^n$ - to be statistically indistinguishable from that of the original POVM $λ_𝒴$. Enforcing this, we aim to quantify the minimum rate $R$ bits/letter that enables Bob reconstruct the classical outcome. Characterizing all possible $(R,C)$ pairs enables us quantify the trade-off between intrinsic information and extrinsic randomness contained in the outcome of POVM $λ_𝒴$.

Since a POVM obfuscates phase information, the above stated requirement is specified in terms of demanding that the combined operators of the reference and outcome post measurement of both the original measurement $λ_𝒴^⊗n$ and the simulated one are statistically `close'. Adopting trace distance to quantify `closeness' we are led to the following.

\begin{definition}
\label{Defn:AsymptoticMsmtSimulation}
Suppose $\rho \in \densityop(\HlbSp_{A})$, $\HlbSp_{X}=\HlbSp_{A}$ and $\lambda \in \mathscr{M}(\mathcal{H}_{A},\mathcal{Y})$ is a POVM. A sequence $\Xi^{(n)} \in \mathscr{M}(\mathcal{H}_{A}^{\otimes n},\mathcal{Y}^{n}): n \geq 1$ of POVMs simulates $\lambda$ on $\rho$ if for all $\eta > 0$, $\exists$ $N_{\eta} \in \naturals$ such that for all $n \geq N_{\eta}$, we have $||\alphaorig-\alpha_{sp}||_{1}\leq \eta$, where $
\alphaorig\define (i_{X}^{\otimes n}\otimes \mathscr{E}^{\lambda^{\otimes n}})(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}} )$
and $\alpha_{sp}=(i_{X}^{\otimes n}\otimes \mathscr{E}^{\Xi^{(n)}})(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}} )$.
\begin{eqnarray}
\label{Eqn:CloseTraceDistance}
||(i_{X}^{\otimes n}\otimes \mathscr{E}^{\lambda^{\otimes n}})(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}} )    -(i_{X}^{\otimes n}\otimes \mathscr{E}^{\Xi^{(n)}})(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}} )||_{1} \leq \eta. \nonumber
\end{eqnarray}
\end{definition}

\begin{remark}
\label{Rem:TheSpecificPurificationDoesNotMatter}
Though the purification of a quantum state is not unique, we have chosen the canonical purification $\ket{\phi_{\rho}}$ in our definition above. In Appendix \ref{AppSec:ChoiceOfPurificationDoesNotMatter}, we prove the choice of the purification does not matter.
\end{remark}

Since the simulated POVM can utilize independent randomness at both terminals, we let (i) $ρ_^⊗n 1/∑_k ∈[]ρ^⊗n⊗|k⟩⟨k|$ model its input state, (ii) design the simulated measurement to be of the form $θ{ θ_k,m⊗|k⟩⟨k| : (k,m) ∈[]⊗[]} ∈ℳ(ℋ_A^nK,[]×[])$, where $ℋ_A^nKℋ_A^⊗n ⊗ℋ_$, $ℋ_={|k⟩:k ∈[]}$ and $⟨|k⟩=δ_k$. Essentially, the simulated POVM $θ$ observes the common randomness $k$ and chooses to perform the POVM ${θ_k,m : m ∈[]} ∈ℳ(ℋ_A^⊗n,[])$ and hands over the nature provided common randomness $k$ and the POVM outcome $m$ to the Dec. Denoting $𝒮(ℋ_A^nK,[])⊆ℳ(ℋ_A^nK,[]×[])$ as the set of POVMs of the above form, we define the quantity of interest.
\begin{definition}
\label{Defn:CommnCostofSimulatedMsmt}
The communication cost of a simulation POVM $\theta \in \mathscr{S}(\mathcal{H}_{A^{n}K},[\CommK\InfM])$ is $(\frac{\log \CommK}{n},\frac{\log \InfM}{n})$. POVM $\lambda_{\mathcal{Y}}$ on $\rho$ can be simulated at a cost $(C,R)$ if $\forall\eta>0$, $\exists N_{\eta} \in \naturals$, such that $\forall n \geq N_{\eta}$, there exists a $\theta \in \mathscr{S}(\mathcal{H}_{A^{n}K},[\CommK\InfM])$ and a POVM $\Delta_{\mathcal{Y}^{n}} \in \mathscr{M}(\mathcal{H}_{K}\otimes \mathcal{H}_{M},\mathcal{Y}^{n})$ such that $\frac{\log \CommK}{n} \leq C+\eta$, $\frac{\log \InfM}{n} \leq R+\eta$ and $||\alphaorig-\alphasim||_{1}\leq \eta$, where
\begin{eqnarray}
\label{Eqn:AlphaOrigDefn}
\alphaorig \define (i_{X}^{ n}\!\otimes \mathscr{E}^{\lambda^{n}}\!)(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}} ),  \alphasim \define  \SimulationCPTP(\ketbra{\phi_{\rho_{K}^{\otimes n}}\!\!}{\!\phi_{\rho_{K}^{\otimes n}}\!} ),\!\!\!\\
\label{Eqn:AlphaSimDefn}
\SimulationCPTP\define (i_{X}^{n}\!\otimes\!\tr_{K}\!\otimes i_{\CalY^{n}})\circ(i_{X}^{ n}\!\otimes\! i_{\mathcal{H}_{K}}\!\otimes\! \mathscr{E}^{\Delta}\! )\!\circ\! (i_{X}^{ n}\!\otimes\! i_{\mathcal{H}_{K}}\!\otimes\!  \mathscr{E}^{\theta}),\!\!\!
\end{eqnarray}
$\HlbSp_{X}=\HlbSp_{A}$, $i_{X}^{n}$ abbreviates the identity map $i_{X}^{\otimes n}$ on $\linop(\HlbSp_{X}^{\otimes n})$.
\end{definition}
\begin{remark}
\label{Rem:ExplainRatePairDefn}
In Defn.~\ref{Defn:CommnCostofSimulatedMsmt}, $\alphaorig$ is the outcome of the original POVM and hence takes only $\rho^{\otimes n}$ as input. Note that the purification of $\rho_{K}^{\otimes n}$ contains a component in the reference space corresponding to common randomness $K$. This justifies the presence of $i_{\HlbSp_{K}}$ in $\SimulationCPTP(\cdot)$. Finally, we wish to only guarantee faithful simulation of the particle post measurement. This explains the $tr_{K}(\cdot)$ in the final CPTP map of $\SimulationCPTP(\cdot)$.
\end{remark}

\begin{remark}
\label{Rem:AlternateProblemFormulation}
In the interest of brevity, we have only provided a heuristic explanation for the above formulation. In Appendix \ref{AppSec:EquivalentFormulation}, we argue this formulation involving purification more directly. The interested reader will find the contents therein similar to the discussion provided in [7].
\end{remark}

\subsection{Communication Cost of Simulating $\lambda_{\mathcal{Y}}$ on $\rho$}
\label{SubSec:KnownResults}
Winter [1] derived an elegant computable characterization for the communication cost of simulating $λ_𝒴$ on $ρ$ for the case when both terminals wish to possess outcome of the simulated POVM. We state below Wilde et.~al.'s [7] generalization for the case when only Bob wishes to possess the simulated outcome.
\begin{definition}
\label{Eqn:TestPOVMsConstraintSet}
For $\rho \in \densityop(\HlbSp_{A})$ and $\lambda_{\mathcal{Y}} \in \mathscr{M}(\HlbSp_{A},\mathcal{Y})$, let $\mathcal{C}(\rho,\lambda_{\mathcal{Y}}) $ be a collection of triples $(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W})$ wherein (i) $\mathcal{W}$ is a finite set, (ii) $\mu_{\mathcal{W}} \in \mathscr{M}(\mathcal{H}_{A},\mathcal{W}) $ is a POVM, and (iii) $(p_{Y|W}(y|w):(w,y)\in \mathcal{W}\times \mathcal{Y})$ is a stochastic matrix such that
\begin{eqnarray}
(i_{X}\otimes \mathscr{E}^{p_{Y|W}})\circ(i_{X}\otimes \mathscr{E}^{\mu})(\ketbra{\phi_{\rho}}{\phi_{\rho}})
\label{Eqn:QuantMarkovChainCondition}
=(i_{X}\otimes \mathscr{E}^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}}).
\end{eqnarray}
For $(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W}) \in \mathcal{C}(\rho,\lambda_{\mathcal{Y}})$, let $p_{W}(w)\define \tr(\rho\mu_{w}) $,
\begin{eqnarray}
\label{Eqn:BetaAndPWDefn}
\beta_{w}\define \frac{\sqrt{\rho}\mu_{w}\sqrt{\rho}}{p_{W}(w)},
\gamma_{w} \displaystyle\define \sum_{y \in \mathcal{Y}}p_{Y|W}(y|w)\beta_{w}\otimes\ketbra{y}{y},
\end{eqnarray}
Let $\mathscr{R}\mathscr{C}(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W})\define\chi(\gamma_{w},p_{W}(w):\mathcal{W})$ and $\mathscr{R}(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W})\define\chi(\beta_{w},p_{W}(w):\mathcal{W})$.
\end{definition}
\begin{remark}
\label{Rem:RelationshipBetweenGammaAndBeta}
For $(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W}) \in \mathcal{C}(\rho,\lambda_{\mathcal{Y}})$, we note $\tr_{W}\left\{(i_{X}\otimes \mathscr{E}^{p_{Y|W}})\circ(i_{X}\otimes \mathscr{E}^{\mu})(\ketbra{\phi_{\rho}}{\phi_{\rho}})\right\} = \sum_{w \in \mathcal{W}}p_{W}(w)\gamma_{w}$,
\begin{eqnarray}
\label{Eqn:RevealingGammaAndBeta2}
(i_{X}\otimes \mathscr{E}^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}})=\sum_{y \in \mathcal{Y}}\sqrt{\rho}\lambda_{y}\sqrt{\rho}\otimes \ketbra{y}{y}, \mbox{ and hence} \\
\label{Eqn:RevealingGammaAndBeta3}
\rho=\sum_{w \in \mathcal{W}}p_{W}(w)\beta_{w}, \sum_{y \in \mathcal{Y}}\sqrt{\rho}\lambda_{y}\sqrt{\rho}\otimes \ketbra{y}{y} = \sum_{w \in \mathcal{W}}p_{W}(w)\gamma_{w}.
\end{eqnarray}
\end{remark}\vspace{-0.05in}
\begin{theorem}
\label{Thm:CommnCostCharacterization}
POVM $\lambda_{\mathcal{Y}}$ on $\rho$ can be simulated at a cost $(C,R)$ iff there exists $(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W}) \in \mathcal{C}(\rho,\lambda_{\mathcal{Y}}) $ for which $R > \mathscr{R}(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W})$ and $R+C > \mathscr{R}\mathscr{C}(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W})$.\vspace{-0.05in}
\end{theorem}\vspace{-0.05in}
\section{Proof Via Unstructured Likelihood POVMs}
\label{Sec:ProofViaUnstructuredPOVMs}
\begin{comment}{Our first contribution is a simplified proof of achievability of Thm.~\ref{Thm:CommnCostCharacterization} via unstructured POVMs.\vspace{-0.05in}}\end{comment}
\subsection{Proof Setup : Notations, Definitions and Likelihood POVM}
\label{SubSec:Proofsetup}
Our proof will involve specifying an $(n,C,R,θ,Δ)$ simulation protocol, analyzing $-_1$ where $, $ is as defined in (\ref{Eqn:TheStatementToProve}), (\ref{Eqn:CharacterizeAlphasim}) respectively, and thereby characterizing conditions under which $-_1$ shrinks exponentially in $n$. Towards that end, we begin by introducing notations and conventions used throughout the proof. Let $ωρ^⊗n$. Choose $(𝒲,μ_𝒲,p_Y|W) ∈𝒞(ρ,λ_𝒴)$. Let $c:[]×[] →^n$ be a map and let $w^n(k,m)(w(k,m)_1,⋯,w(k,m)_n) (c(k,m)_1,⋯,c(k,m)_n)$. We let $μ_k,m μ_c(k,m)_1⊗⋯⊗μ_c(k,m)_n ∈𝒫(_A^⊗n)$ and\vspace{-0.05in}
\begin{eqnarray}
\label{Eqn:DefnOfS_k}
S_{k} \define \sum_{m=1}^{\InfM}\frac{\sqrt{\omega}\mu_{k,m}\sqrt{\omega}}{\tr(\omega\mu_{k,m})}, \theta_{k,m} \define \frac{S_{k}^{-\frac{1}{2}}\sqrt{\omega}\mu_{k,m}\sqrt{\omega}S_{k}^{-\frac{1}{2}}}{\tr(\omega\mu_{k,m})},
\end{eqnarray}
where $S_k^-1/2$, as is standard, is the generalized inverse of $S_k^1/2$ that is $0$ on the null space of $S_k$. We let $θ_k,0 I_H_A^⊗n-∑_m=1^θ_k,m$ for all $k ∈[]$. From this and the definition of the generalized inverse, we note that, for each $k ∈[K]$,
\begin{eqnarray}
\label{Eqn:RelationshipOfThetak0}
\sqrt{\theta_{k,0}}S_{k}\sqrt{\theta_{k,0}} = \sqrt{S_{k}}\theta_{k,0}\sqrt{S_{k}} = 0.
\end{eqnarray}
Since $μ_$ is a POVM, we have $0≤μ_c(k,m)_i ≤I_H_A $ for $i∈[n]$, and hence $0 ≤μ_k,m ≤I_H_A^⊗n$ implying $0 ≤θ_k,m ≤I_H_A^⊗n$. Furthermore, $∑_m=1^Mθ_k,m$ is a projection on the support of $S_k$ and hence  $0 ≤∑_m=1^Mθ_k,m≤I_H_A^⊗n$. By definition of $θ_k,0$, we have ensured $∑_m =0^Mθ_k,m = I_H_A^⊗n$ for all $k ∈[]$. We let $θ{ θ_k,mθ_k,m⊗|k⟩⟨k|: (k,m)∈[]×[]}∈(ℋ_A^⊗n⊗_K,[]×[])$ be our chosen POVM.

We choose
\begin{eqnarray}
\label{Eqn:DecoderPOVM}
\Delta\define \Delta_{\CalY^{n}}\define \{ \Delta_{y^{n}} \define \sum_{(k,m) \in [\CommK]\times[\InfM]}\ketbra{k~ m}{k~ m}p_{Y|W}^{n}(y^{n}|c(k,m)):y^{n}\in \mathcal{Y}^{n}\} \in \ScrM(\CalH_{K}\otimes \CalH_{M},\CalY^{n})
\end{eqnarray}
as the post-processing POVM employed by the decoder. It is straight forward to verify $Δ∈ℳ(_⊗_,𝒴^n)$ is a POVM.\vspace{-0.05in}
\subsection{Key Steps Outlining the Proof}
\label{SubSec:KeyStepsOutliningProof}
While it is easy to conjecture the above simulation POVMs, the non-commutativity of quantum operations has obfuscated its analysis for the task at hand, leading studies [7, 1] including the more recent ones [8, 9, 10] to adopt an alternate simulation POVM leading to much complexity. We therefore illustrate the key steps below, which is also revealing. For $a ∈[]$, let\vspace{-0.05in}
\begin{eqnarray}
\label{Eqn:TheAuxillaryState1}
T_{a}\define \frac{S_{a}}{M} \mbox{ have SCD }T_{a} = \sum_{t=1}^{d_{A}^{n}}\nu_{ta}\ketbra{x_{ta}}{x_{ta}},\mbox{ i.e., }
\braket{x_{ta}}{x_{\hatt a}} = \delta_{\hatt t}\mbox{ for } a \in [K]\mbox{ and }\sigma_{A^{n}K} \define \frac{1}{\CommK}\sum_{a \in [\CommK]}T_{a}\otimes\ketbra{a}{a}.
\end{eqnarray}
In order to bound $||α_-α_||_1$ we define\vspace{-0.05in}
\begin{eqnarray}
\label{Eqn:DefnOfAlpha}
\alpha \define \SimulationCPTP(\ketbra{\phi_{\sigma_{A^{n}K}}}{\phi_{\sigma_{A^{n}K}}} ),\mbox{ where } \ket{\phi_{\sigma_{A^{n}K}}}\define \sum_{t =1}^{d_{A}^{n}}\sum_{a\in [\CommK]}\frac{1}{K}\sqrt{\nu_{ta}}\ket{\olinex_{ta}~a}\otimes \ket {x_{ta}~a}
\end{eqnarray}
is the canonical purification of $σ_A^nK$ Recognizing that $α$ above and $$ in (\ref{Eqn:CharacterizeAlphasim}) are the result of applying the same CPTP map - $$ - on two different states provides us with the right clue. Indeed, we have\vspace{-0.05in}
\begin{eqnarray}
\label{Eqn:KeyTriangleIneq}
\lefteqn{\!\!\!\!\!\!||\alpha_{\mbox{\tiny O}}-\alpha_{\mbox{\tiny S}}||_{1}\leq ||\alpha_{\mbox{\tiny O}}-\alpha||_{1}+||\alpha-\alpha_{\mbox{\tiny S}}||_{1}}\nonumber\\
\label{Eqn:KeyIneqCPTPShrinksDist}
&&\!\!\!\!\!\!\!\!\leq ||\alpha_{\mbox{\tiny O}}-\alpha||_{1}+||\ketbra{\phi_{\sigma_{A^{n}K}}}{\phi_{\sigma_{A^{n}K}}} -\ketbra{\phi_{\rho_{K}^{\otimes n}}}{\phi_{\rho_{K}^{\otimes n}}}||_{1}.~
\end{eqnarray}
from the Triangular inequality and the fact that CPTP maps shrink the trace distance \cite[Eq.~9.69]{BkWilde_2017}. Through the rest of the proof, we analyze each of the terms in the RHS of (\ref{Eqn:KeyIneqCPTPShrinksDist}). In Sec.~\ref{SubSec:SecondTermAnalysis}, we analyze the second term where we leverage an elegant bound that relates the distance between states and their canonical purifications. In Sec.~\ref{SubSec:FirstTermAnalysis}, we evaluate the RHS of (\ref{Eqn:DefnOfAlpha}) and thereby knock off the inconvenient outer normalizing factors $S_k^-1/2$ in $θ_k,m$ defined in (\ref{Eqn:DefnOfS_k})!
\subsection{Relating distance between states and their canonical purifications}
\label{SubSec:SecondTermAnalysis}
Our approach to deriving an upper bound on the second term in (\ref{Eqn:KeyIneqCPTPShrinksDist}) is by relating the latter to $σ_A^nK -ρ_K^⊗n_1$. However, note that tracing over components decreases the trace distance, and hence $σ_A^nK -ρ_K^⊗n_1 ≤|ϕ_σ_A^nK ⟩⟨ϕ_σ_A^nK  |  -    |   ϕ_ρ_K^⊗n     ⟩⟨   ϕ_ρ_K^⊗n      |   _1$. However, we need an inequality in the reverse. The choice of the canonical purification [1], \cite[Pg.~166]{BkWilde_2017} enables us to suitably reverse the above inequality. Specifically, by leveraging the relationship between fidelity and trace distance \cite[Thm.~9.3.1]{BkWilde_2017} and the specific form of the canonical purification, we have\vspace{-0.05in}
\begin{eqnarray}
\label{Eqn:WinterCanonicalPuresClose}
\norm{\ketbra{\phi_{\sigma_{A^{n}K}}\!}{\phi_{\sigma_{A^{n}K}}\!} -\ketbra{\phi_{\!\rho_{K}^{\otimes n}}\!}{\!\phi_{\!\rho_{K}^{\otimes n}}}}_{1} \leq 4\sqrt[4]{\norm{\sigma_{A^{n}K} -{\rho_{K}^{\otimes n}}_{1}}}.
\end{eqnarray}
A proof of (\ref{Eqn:WinterCanonicalPuresClose}) can be found in \cite[App.~A, Lem.~14]{200401CommMathPhy_Win} and the same is elaborated in Lemma \ref{Lem:WinterCanoniPuresCannotBeTooFar} of Appendix \ref{AppSec:PurificationAndSimulation}. In Sec.~\ref{SubSec:NewProofQuantCoveringLemma}, we derive an upper bound on the RHS of  (\ref{Eqn:WinterCanonicalPuresClose}).
\subsection{Characterizing $\alpha=\SimulationCPTP(\ketbra{\phi_{\sigma_{A^{n}K}}}{\phi_{\sigma_{A^{n}K}}} )$ and $\alpha_{\mbox{\tiny O}}$}
\label{SubSec:FirstTermAnalysis}
In this section, we focus on the first term in (\ref{Eqn:KeyIneqCPTPShrinksDist}) and evaluate $, α$.
In characterizing $α$, we ought to evolve $|ϕ_σ_A^nK⟩⟨ϕ_σ_A^nK|$ through three CPTP maps that define $$ in (\ref{Eqn:CharacterizeAlphasim}). From definition of $ℰ^θ$, we have $(i_X^ n⊗i__K⊗ℰ^θ)(|ϕ_σ_A^nK⟩⟨ϕ_σ_A^nK| )=$
\begin{eqnarray}
\label{Eqn:CPTPMapOnAuxStatePurification1}
\lefteqn{\sum_{t =1}^{d_{A}^{n}}\sum_{v=1}^{d_{A}^{n}}\sum_{a\in [\CommK]}\sum_{b\in[\CommK]}\sum_{k \in [\CommK]}\sum_{m \in [\overline{\InfM}]}K^{-1}\sqrt{{\nu_{ta}\nu_{vb}}}\ketbra{\olinex_{ta}~a}{\olinex_{vb}~b}\otimes\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification2}
\label{Eqn:CPTPMapOnAuxStatePurification3}
&&\!\!\!\!\!\!\!\!\!\!=\sum_{t =1}^{d_{A}^{n}}\sum_{v=1}^{d_{A}^{n}}\sum_{k \in [\CommK]}\sum_{m \in [\overline{\InfM}]}K^{-1}\sqrt{{\nu_{tk}\nu_{vk}}}\ketbra{\olinex_{tk}~k}{\olinex_{vk}~k}\otimes\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification4}
\label{Eqn:CPTPMapOnAuxStatePurification5}
&&\!\!\!\!\!\!\!\!\!\!=\sum_{t =1}^{d_{A}^{n}}\sum_{v=1}^{d_{A}^{n}}\sum_{k \in [\CommK]}\sum_{m \in [\overline{\InfM}]}K^{-1}\ketbra{\olinex_{tk}~k}{\olinex_{vk}~k}\otimes\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification6}
\label{Eqn:CPTPMapOnAuxStatePurification7}
&&\!\!\!\!\!\!\!\!\!\!=\sum_{t =1}^{d_{A}^{n}}\sum_{v=1}^{d_{A}^{n}}\sum_{k \in [\CommK]}\sum_{m \in [\overline{\InfM}]}K^{-1}\ketbra{\olinex_{tk}~k}{\olinex_{vk}~k}\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification8}
\label{Eqn:CPTPMapOnAuxStatePurification7Again}
&&\!\!\!\!\!\!\!\!\!\!=\sum_{k \in [\CommK]}\sum_{m \in [\overline{\InfM}]}\sum_{t =1}^{d_{A}^{n}}\sum_{v=1}^{d_{A}^{n}}\frac{\! \ketbra{\olinex_{tk}}{\olinex_{vk}}\mel{x_{vk}\sqrt{T_{k}}}{\theta_{k,m}}{\sqrt{T_{k}}x_{tk}}\!}{K}\!\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification8Again}
&&\!\!\!\!\!\!\!\!\!\!\otimes\ketbra{k}{k}\otimes \ketbra{k~m}{k~m}\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification9}
&&\!\!\!\!\!\!\!\!\!\!=\sum_{k \in [\CommK]}\sum_{m \in [\overline{\InfM}]}
\frac{\left(\sqrt{T_{k}}\theta_{k,m}\sqrt{T_{k}}\right)^{*}}{K}\otimes \ketbra{k}{k}\otimes \ketbra{k~m}{k~m}\\
\label{Eqn:CPTPMapOnAuxStatePurification9Again}
&&\!\!\!\!\!\!\!\!\!\!=\sum_{k \in [\CommK]}\sum_{m \in [{\InfM}]}
\frac{\left(\sqrt{S_{k}}\theta_{k,m}\sqrt{S_{k}}\right)^{*}}{KM}\otimes \ketbra{k}{k}\otimes \ketbra{k~m}{k~m}\nonumber\\
\label{Eqn:CPTPMapOnAuxStatePurification9AgainAgain}
&&\!\!\!\!\!\!\!\!\!\!+\sum_{k \in [\CommK]}
\frac{\left(\sqrt{S_{k}}\theta_{k,0}\sqrt{S_{k}}\right)^{*}}{KM}\otimes \ketbra{k}{k}\otimes \ketbra{k~0}{k~0}\\
\label{Eqn:CPTPMapOnAuxStatePurification10}
&&\!\!\!\!\!\!\!\!\!\!=\frac{1}{KM}\!\!\sum_{k \in [\CommK]}\sum_{m \in [{\InfM]}}\!\!
\frac{\left(\sqrt{\omega}\mu_{k,m}\sqrt{\omega}\right)^{t}}{\tr(\omega\mu_{k,m})}\otimes \ketbra{k}{k}\otimes \ketbra{k~m}{k~m}
\end{eqnarray}
where (\ref{Eqn:CPTPMapOnAuxStatePurification6}) follows from shifting scalars $√(ν_vk),√(ν_tk)$, (\ref{Eqn:CPTPMapOnAuxStatePurification8}) follows from spectral decomposition in (\ref{Eqn:TheAuxillaryState1}), (\ref{Eqn:CPTPMapOnAuxStatePurification9}) follows from Part 4 of Lemma \ref{Lem:CanonicalBasisSimpleFacts}, (\ref{Eqn:CPTPMapOnAuxStatePurification9AgainAgain}) follows from the relationship between $T_k, S_k$ in (\ref{Eqn:TheAuxillaryState1}) and $[] = [M]∪{0}$, (\ref{Eqn:CPTPMapOnAuxStatePurification10}) follows from definition of $θ_m,k$ and $T_k$ in (\ref{Eqn:DefnOfS_k}) and the fact stated in (\ref{Eqn:RelationshipOfThetak0}). Next, we evolve the state in RHS of (\ref{Eqn:CPTPMapOnAuxStatePurification10}) through the CPTP map $(i_X^ n⊗i__K⊗ℰ^Δ)(·)$ to yield the state
\begin{eqnarray}
\label{Eqn:AlphaSimplifiedOld}
\frac{1}{KM}\!\!\!\!\sum_{ \substack{k \in  [\CommK] \\m \in [\InfM] }}\sum_{\substack{y^{n}\in \\\mathcal{Y}^{n}}}\!p^{n}_{Y|W}\!(y^{n}|c(k,m))
\frac{\left(\sqrt{\omega}\mu_{k,m}\sqrt{\omega}\right)^{t}}{\tr(\omega\mu_{k,m})} \!\!\otimes\ketbra{k~y^{n}}{k~y^{n}}\!,\nonumber
\end{eqnarray}
where the above follows from defn. (\ref{Eqn:DecoderPOVM}). Finally, evolving above state through CPTP map $(i_X^ n⊗_K⊗ℰ^Δ)(·)$ yields
\begin{eqnarray}
\alpha = \!\frac{1}{KM}\!\!\!\!\!\!\!\!\sum_{ \substack{(k,m,y^{n}) \in  \\ [\CommK] \times [\InfM] \times \CalY^{n}}}\!\!\!\!\!\!\!\!\!\!\!p^{n}_{Y|W}(y^{n}|c(k,m))
\frac{\left(\sqrt{\omega}\mu_{k,m}\sqrt{\omega}\right)^{t}}{\tr(\omega\mu_{k,m})}\label{Eqn:AlphaSimplified}
\!\otimes\! \ketbra{y^{n}}{y^{n}}\!.\!\!
\end{eqnarray}
An identical sequence of steps yields\footnote{This is a standard computation and can be verified in \cite[Proof of Lem.~4]{2012MMJPhyA_WilHayBusHsi}}
\begin{eqnarray}
\label{Eqn:AlphaOSimplified}
\alpha_{\mbox{\tiny O}} =\sum_{y^{n}\in \mathcal{Y}^{n}}
\left(\sqrt{\omega}\lambda_{y^{n}}\sqrt{\omega}\right)^{t} \otimes \ketbra{y^{n}}{y^{n}}.
\end{eqnarray}

\subsection{A new proof of the quantum covering lemma}
\label{SubSec:NewProofQuantCoveringLemma}
Substituting (\ref{Eqn:AlphaSimplified}), (\ref{Eqn:AlphaOSimplified}) and (\ref{Eqn:WinterCanonicalPuresClose}) in the RHS of (\ref{Eqn:KeyIneqCPTPShrinksDist}), we have
\begin{eqnarray}
\label{Eqn:CollatingBounds}
||\alphaorig-\alphasim||_{1} \leq ||\alphaorig-\alpha||_{1}+4\sqrt[4]{||\sigma_{A^{n}K} -{\rho_{K}^{\otimes n}||_{1}}}.
\end{eqnarray}
Collating definitions of $S_k$ from (\ref{Eqn:DefnOfS_k}), Substituting $T_k$ into $σ_A^nK$ in (\ref{Eqn:TheAuxillaryState1}), recalling definition of $ρ_K^⊗n$ from Lemma \ref{Lem:CharacterizeAlphasim}, recognizing the block diagonal structure of $ρ_K^⊗n$ and $σ_A^nK$, we have
\begin{eqnarray}
\label{Eqn:FinalStep1OnTerm2}
||\sigma_{A^{n}K} -\rho_{K}^{\otimes n}||_{1} \!=\! \frac{1}{K}\!\sum_{k=1}^{\CommK}\!|| \rho^{\otimes n}- \frac{1}{\InfM}\sum_{m=1}^{\InfM}\!\!\frac{\sqrt{\omega}\mu_{k,m}\sqrt{\omega}}{\tr(\omega\mu_{k,m})}||_{1}\nonumber\\
\label{Eqn:FinalStep2OnTerm2}
= \frac{1}{K}\!\sum_{k=1}^{\CommK}\!|| \rho^{\otimes n}- \frac{1}{\InfM}\sum_{m=1}^{\InfM}\beta_{c(k,m)}||_{1}
\end{eqnarray}
from the definition of $β_w$ in (\ref{Eqn:BetaAndPWDefn}) and $β_c(k,m)β_c(k,m)_1⊗⋯⊗β_c(k,m)_n$. Analogously defining $γ_c(k,m)γ_c(k,m)_1⊗⋯⊗ γ_c(k,m)_n$, recognizing $α= 1/∑_k=1^∑_m=1^γ_c(k,m)$ from (\ref{Eqn:AlphaSimplified}) and $=( ∑_w ∈𝒲p_W(w)γ_w)^⊗n$ from (\ref{Eqn:RevealingGammaAndBeta3}), (\ref{Eqn:AlphaOSimplified}), we have
\begin{eqnarray}
\label{Eqn:FinalStep1OnTerm1}
||\alphaorig-\alpha||_{1} = ||\gamma^{\otimes n}- \frac{1}{\CommK\InfM}\sum_{k,m}\gamma_{c(k,m)}||_{1}.
\end{eqnarray}
where we have let $γ=∑_w ∈𝒲p_W(w)γ_w$. Noting $ρ=∑_wp_W(w)β_w$, one recognizes similarity in the RHSs (\ref{Eqn:FinalStep2OnTerm2}) and (\ref{Eqn:FinalStep1OnTerm1}). Indeed, they are instances of the following QCL \cite[Sec.~17.4]{BkWilde_2017}, for which we provide a new proof. The reader is also referred to [10] for another proof of QCL.

\begin{lemma}
\label{Lem:QuantSoftCoveringLemma}
Suppose $p_{X}(\cdot)$ is a PMF on a finite set $\mathcal{X}$, $s_{x} \in \mathcal{D}(\HlbSp): x \in \CalX$ and $s=\sum_{x}p_{X}(x)s_{x} \in \mathcal{D}(\HlbSp)$. Suppose the $2^{nR}$ elements of $A=(X^{n}(1),\cdots,X^{n}(2^{nR}))$ are identically distributed according to $\CalP(X^{n}(i)=x^{n})=p_{X}^{n}(x^{n})$ $\forall x^{n} \in \CalX^{n}, \forall i \in [2^{nR}]$, and \textbf{pairwise independent}, then
\begin{eqnarray}
\label{Eqn:QuantCoverExpBound}
\mathbb{E}_{\mathcal{P}}\left\{||s^{\otimes n}-s(A)||_{1} \right\} \leq \exp\left\{\! -\frac{n}{2}\!\left( R-\chi(s_{x};p_{X}:\mathcal{X})\!\right) \!\right\}
\end{eqnarray}
where $s(A)\define \frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}s_{X^{n}(m)}$. In particular, there exists a map $c:[2^{nR_{0}}]\times [2^{nR_{1}}] \rightarrow \mathcal{X}^{n}$ such that
\begin{eqnarray}
\label{Eqn:CorollaryOfQuantSftCover}
\frac{1}{2^{nR_{0}}}\sum_{k=1}^{2^{nR_{0}}}||s^{\otimes n}-\frac{1}{2^{nR_{1}}}\sum_{m=1}^{2^{nR_{1}}}s_{c(k,m)}||_{1}\leq 2^{-\frac{n\eta}{8}}
\end{eqnarray}
if $R_{1}> \chi(s_{x};p_{X}:\mathcal{X})+2\eta$.
\end{lemma}
\begin{remark}
\label{Rem:LemmaProvesThm}
Lem.~\ref{Lem:QuantSoftCoveringLemma} yields an achievability of Thm.~\ref{Thm:CommnCostCharacterization} if one chooses (i) $R_{0}=\frac{\log \CommK}{n}, R_{1}=\frac{\log \InfM}{n}$ to bound (\ref{Eqn:FinalStep1OnTerm2}) and (ii) $R_{0}=0$ and $R_{1}=\frac{\log \CommK\InfM}{n}$ to bound (\ref{Eqn:FinalStep1OnTerm1}).
\end{remark}
\med
\textit{Proof of Lem.~\ref{Lem:QuantSoftCoveringLemma}}: In the interest of brevity, we only elaborate on the key new steps and how it differs from earlier proofs \cite[Sec.~17.4]{BkWilde_2017}. Let

\begin{eqnarray}s_{x}\!=\!\!\sum_{y}\!\gamma_{y|x}\ketbra{e_{y|x}}{e_{y|x}} : x \in \CalX, s\!=\!\sum_{y}p_{Y}(y)\ketbra{f_{y}}{f_{y}}\nonumber
\end{eqnarray}
be SCDs, $π_x^n^ηπ_x^n,p_Xγ_Y|X^η1_x^n∈T_δ(p_X)$\begin{comment}{\define\sum_{y^{n}}\mathds{1}_{\{y^{n}:(x^{n},y^{n}) \in T_{\eta}(p_{X}\gamma_{Y|X})\}}\displaystyle \otimes_{i=1}^{n}\ketbra{e_{y_{i}|x_{i}}}{e_{y_{i}|x_{i}}}}\end{comment} be a conditional typical projector of $s_x^n$ and\footnote{Note that $\pi_{x^{n}}^{\eta}=0$ if $x^{n}$ is \textit{not} typical} $π^ηπ_p_Y^η$ the (unconditional) typical projector of $s$. For $a=(x^n(m):m ∈[2^nR])$, let
\begin{eqnarray}
s(a)\define \!\!\sum_{m=1}^{2^{nR}}\!\!\frac{s_{x^{n}(m)}}{2^{nR}},~w(a)\define\!\!\sum_{m=1}^{2^{nR}}\!\!\frac{\pi^{\eta}\pi^{\eta}_{x^{n}(m)}s_{x^{n}(m)}\pi^{\eta}_{x^{n}(m)}\pi^{\eta}}{2^{nR}}
\nonumber\\
\label{Eqn:DefnOfwAndNote}
w\!\define\! \sum_{x^{n}}\!p_{X}^{n}(x^{n}\!)\pi^{\eta}\pi_{x^{n}}^{\eta}s_{x^{n}}\pi_{x^{n}}^{\eta}\pi^{\eta}\mbox{ and note }w\!=\!\mathbb{E}_{\mathcal{P}}\{w(A)\}.\!
\end{eqnarray}
Let $s(A),w(A)$ be corresponding random quantities. The quantity of interest
\begin{eqnarray}
\label{Eqn:TriangularIneq}
\Expectation_{\CalP}\{ ||s(A)-s^{\otimes n}||_{1} \}\leq T_{1}+T_{2}+T_{3}\mbox{ where }
\end{eqnarray}
$T_1=_{ ||s(A)-w(A)||_1},T_2=_{ ||w(A)-w||_1},T_3=_{||w-s^⊗n||_1 }$. $T_1,T_3$ are handled in a straight forward sequence of arguments leveraging (i) properties of conditional and unconditional typicality projectors, (ii) gentle operator lemma, (iii) and the bound $||AB||_1≤||A||_1||B||_∞$. These steps can be verified at \cite[Sec.~17.4.3]{BkWilde_2017}. We address the crucial term $T_2$ that yields the rate bound and this is where we differ from earlier proofs. While the proof in \cite[Sec.~17.4]{BkWilde_2017} relies on the Ahlswede-Winter operator Chernoff bound [2], our proof takes a clue from Cuff's \cite[Lem.~19]{CuffPhDThesis} `root-variance' technique. Letting $v(A)w(A)-_{w(A)}$, we have
\begin{eqnarray}
\label{Eqn:CrucialSteps1}
T_{2}= \Expectation_{\CalP}[ ||v(A)||_{1}]= \Expectation_{\CalP}[ \tr\{\sqrt{(v(A)^{\dagger}v(A)}\}]
\\
\label{Eqn:CrucialSteps2}
=\tr\{\Expectation_{\CalP}[\sqrt{(v(A)^{\dagger}v(A)}]\} \leq \tr\{\sqrt{\Expectation_{\CalP}[(v(A)^{\dagger}v(A)]}\}
\end{eqnarray}
where (\ref{Eqn:CrucialSteps1}) follows from definition of trace, (\ref{Eqn:CrucialSteps2}) from linearity of trace and the operator concavity \cite[Thm.~2.6]{201001CM_Car} of the square root function (a consequence of the Lowner-Heinz theorem \cite[Thm.~2.6]{201001CM_Car}). Substituting $w(A), _{w(A)}$, suppressing $η$, expanding out the expectation and following a sequence of standard steps, yields
\begin{eqnarray}
\label{Eqn:CrucialSteps3}
\lefteqn{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\Expectation_{\CalP}\![(v(A)^{\dagger}v(A)]\leq  \sum_{x^{n}}\frac{p_{X}(x^{n})\pi\pi_{x^{n}}s_{x^{n}}\pi_{x^{n}}\pi\pi\pi_{x^{n}}s_{x^{n}}\pi_{x^{n}}\pi}{2^{nR}} + 2^{nR}(2^{nR}-1)\!\!\!\sum_{ x^{n},\hatx^{n}}\!\frac{p_{X}(x^{n})p_{X}(\hatx^{n})\pi\pi_{x^{n}}s_{x^{n}}\pi_{x^{n}}\pi\pi\pi_{\hatx^{n}}s_{\hatx^{n}}\pi_{\hatx^{n}}\pi}{2^{2nR}}
\label{Eqn:CrucialSteps13New}
- 2^{2nR}\sum_{ \substack{x^{n},\hatx^{n}\\\hatx^{n}\neq x^{n} }}\frac{p_{X}(x^{n})p_{X}(\hatx^{n})\pi\pi_{x^{n}}s_{x^{n}}\pi_{x^{n}}\pi\pi\pi_{\hatx^{n}}s_{\hatx^{n}}\pi_{\hatx^{n}}\pi}{2^{2nR}}
\nonumber\\
\label{Eqn:CrucialSteps3New}
\nonumber\\
\label{Eqn:CrucialSteps4}
&&\!\!\!\!\!\!\!\!\!\!\!\!\leq \sum_{x^{n}}\frac{p_{X}(x^{n})\pi\pi_{x^{n}}s_{x^{n}}^{\frac{1}{2}}\pi_{x^{n}}s_{x^{n}}\pi_{x^{n}}s_{x^{n}}^{\frac{1}{2}}\pi_{x^{n}}\pi}{2^{nR}}
\\
\label{Eqn:CrucialStep5}
&&\!\!\!\!\!\!\!\!\!\!\!\!= \sum_{x^{n} \in T_{\delta}(p_{X})}\frac{p_{X}(x^{n})\pi\pi_{x^{n}}s_{x^{n}}^{\frac{1}{2}}\pi_{x^{n}}s_{x^{n}}\pi_{x^{n}}s_{x^{n}}^{\frac{1}{2}}\pi_{x^{n}}\pi}{2^{nR}}
\\
\label{Eqn:CrucialSteps6}
&&\!\!\!\!\!\!\!\!\!\!\!\!\leq \!\!\!\!\!\!\!\sum_{x^{n} \in T_{\delta}(p_{X})}\!\!\!\!\!\!\!\!\!\frac{p_{X}(x^{n})\pi\pi_{x^{n}}s_{x^{n}}^{\frac{1}{2}}\pi_{x^{n}}s_{x^{n}}^{\frac{1}{2}}\pi_{x^{n}}\pi}{2^{n(R+\sum_{a}p_{X}(a)S(s_{a}))}}
\\
\label{Eqn:CrucialSteps7}
&&\!\!\!\!\!\!\!\!\!\!\!\leq \!\!\!\!\!\!\!\!\!\sum_{x^{n} \in T_{\delta}(p_{X})}\!\!\!\!\!\!\frac{p_{X}(x^{n})\pi s_{x^{n}}\pi}{2^{n(R+\sum_{a}p_{X}(a)S(s_{a}))}}
\leq\!\frac{\pi s^{\otimes n}\pi}{2^{n(R+\sum_{a}p_{X}(a)S(s_{a}))}}
\end{eqnarray}\begin{eqnarray}
\label{Eqn:CrucialSteps8}
&&\!\!\!\!\!\!\!\!\!\!\!\!\leq \pi {2^{-n(R+\sum_{a}p_{X}(a)S(s_{a}) +S(\sum_{a}p_{X}(a)s_{a}) )}}
\end{eqnarray}
where (\ref{Eqn:CrucialSteps4}) follows from commutativity of $s_x^n$ and its conditional typicality projector $π_x^n$ and $π≤I^⊗n$, (\ref{Eqn:CrucialStep5}) from earlier definition of conditional typicality projector being $0$ on non-typical elements, (\ref{Eqn:CrucialSteps6}) from \cite[Prop.~15.2.6]{BkWilde_2017}, (\ref{Eqn:CrucialSteps7}) follows from commutativity of $s_x^n$ and its conditional frequency projector $π_x^n$ and $π_x^n≤I^⊗n$, expanding the sum to the entire set and (\ref{Eqn:CrucialSteps8}) from \cite[Prop.~15.1.3]{BkWilde_2017}. From operator monotonicity of square root function \cite[Thm.~2.6]{201001CM_Car}, we can substitute RHS of (\ref{Eqn:CrucialSteps8}) under the square root in (\ref{Eqn:CrucialSteps2}) as an upper bound. Following through (\ref{Eqn:CrucialSteps1}) - (\ref{Eqn:CrucialSteps8}), we have
\begin{eqnarray}
\label{Eqn:CrucialSteps9}
T_{2} \leq \tr\{\sqrt{\pi {2^{-n(R+\sum_{a}p_{X}(a)S(s_{a}) +S(\sum_{a}p_{X}(a)s_{a}) )}}}\}\nonumber\\
\label{Eqn:CrucialSteps10}
= {2^{-\frac{n}{2}(R+\sum_{a}p_{X}(a)S(s_{a}) +S(\sum_{a}p_{X}(a)s_{a}) )}}\tr(\sqrt{\pi})\nonumber\\
\label{Eqn:CrucialSteps11}
\leq {2^{-\frac{n}{2}(R-\chi(p_{X};s_{x}:\CalX)  )}}
\end{eqnarray}
where (\ref{Eqn:CrucialSteps11}) follows from the bound $(√(π))=(π) ≤2^nS(∑_ap_X(a)s_a)$ on the trace of the unconditional projector \cite[Prop.~15.1.2]{BkWilde_2017}, thus completing the proof.

\section{Simulation Via Algebraically Closed POVMs}
\label{Sec:CosetPOVMs}
We briefly revisit the simulated POVM in Sec.~\ref{Sec:ProofViaUnstructuredPOVMs}. Alice possesses POVM operators ${θ_k,m:1≤K,0≤m ≤M}$ and Bob has a corresponding table ${w^n(k,m):1≤K,0≤m ≤M}$. On observing (common) random bits $k^*$, Alice performs POVM ${θ_k^*,m:0≤m ≤M}$. Bob chooses $w^n(k^*,m^*)$, where $m^*$ is the POVM outcome, and evolves this through the stochastic matrix $p_Y|W^n(·|w^n(k^*,m^*))$. The question we ask in this section is whether the table $$, and the corresponding POVMs $$ be endowed with certain \textit{algebraic} structure? Specifically, suppose $𝒲$ is a finite field or a group, can the table $$ be chosen to be a coset of a linear code?

Optimal compression requires that each outcome $w^n(k,m)$ is an equally likely POVM outcome, forcing the entries of the table to be $p_W-$typical, where, we recall $p_W(w)=(ρμ_w)$. Requiring table entries to be algebraically closed forces us to choose entries $w^n(k,m)$ that are \textit{not} $p_W-$typical. Non-$p_w-$typical outcomes are extremely rare lending the simulation protocol sub-optimal (in terms of communication rates).

Does this imply that the table cannot have algebraic properties? There is one way to get around this obstacle. Can we add redundant operators and corresponding table entries in a controlled manner to guarantee algebraic closure, yet not suffer on the communication and common randomness rate? The idea is to enlarge the table into a third dimension. Let $ĉ:[K]×[M]×[B] →𝒲^n$ be a map,
\begin{eqnarray}
\label{Eqn:DefnOfNewS_k}
\hat{S}_{k}\! \define \!\!\!\!\!\sum_{\substack{(b,m)\in\\ [B]\times[M] }}\!\!\!\!\!\!\frac{\sqrt{\omega}\mu_{k,m,b}\sqrt{\omega}}{\tr(\omega\mu_{k,m,b})}, \hat{\theta}_{k,m,b} \define \frac{\hat{S}_{k}^{-\frac{1}{2}}\sqrt{\omega}\mu_{k,m,b}\sqrt{\omega}\hat{S}_{k}^{-\frac{1}{2}}}{\tr(\omega\mu_{k,m,b})},\end{eqnarray}
and $θ̂ { θ̂_k,m,b⊗|k⟩⟨k|:1≤k≤K,1≤m ≤M,1≤b≤B}$ be a POVM. On observing random bits $k^*$, Alice performs POVM $θ̂_k^* { θ_k^*,m,b:1≤m ≤M,1≤b≤B}$. Only the component $m^*$ of the outcome $(m^*,b^*)$ is communicated to Bob. If the table has the desired property that for each $(k,m) ∈[K]×[M]$, there is a \textit{unique} index $b^*(k,m) ∈[B]$ such that $w^n(k,m,b^*(k,m))$ is $p_W-$typical, then Bob can evolve $w^n(k^*,m^*,b^*(k^*,m^*))$ through the stochastic matrix $p^n_Y|W(·|w^n(k^*,m^*,b^*(k^*,m^*)))$ and simulate the POVM outcome. Since the POVM outcome is $p_W-$typical WHP, Bob's choice would indeed be the correct POVM outcome WHP.

This provides us with the clue. For simplicity, let us assume $𝒲=$ to be the binary field. In order to prove achievability in Lem.~\ref{Lem:QuantSoftCoveringLemma}, we picked entries of table $$ independently and randomly with distribution $p_W^n$. Instead, suppose we let table $Ĉ$ to be range of a generator matrix $G ∈^(c+r+β)×n$ whose entries are picked uniformly independently from $={0,1}$, then its range is a random linear code with uniform \textit{pairwise independent} codewords. Common randomness specifies $c$ bits. For each choice of these $c$ bits, we build a POVM with $2^r+β$ operators. Only $r$ of the $(r+β)$ outcome bits is communicated to Bob. Having been provided $c+r$ bits, Bob looks for a unique collection of $β$ bits for which the corresponding entry in $Ĉ$ that is $p_W-$typical. Since the entries of $Ĉ$ are uniformly distributed, the expected number of $p_W-$typical codewords in any collection of $2^β$ entries is $2^β|T_η(p_W)|/2^n=2^-n(1-H(p_W)-β)$. Therefore, so long as $β< 1-H(p_W)$, it is natural to expect that Bob will find just one $p_W-$typical entry whose index agrees with the $c+r$ bits he has been provided. This suggests that, if we can enlarge our table by a factor not greater than $2^n(1-H(p_W))$ and prove a QCL analogous to Lem.~\ref{Lem:QuantSoftCoveringLemma}, but with entries of the table $A$ uniformly chosen from $^n$, instead of $p_W^n$, then we can perform POVM simulation with an `\textit{algebraically closed POVM}'. This is indeed true. A proof of Lem.~\ref{Lem:SoftCoverWithUnifCodewords} is similar to proof of Lem.~\ref{Lem:QuantSoftCoveringLemma} and is provided in an enlarged version of this preprint. We follow this up with a final statement on the existence of structured POVMs for simulation. A proof is provided in an enlarged version of this preprint.

\begin{lemma}
\label{Lem:SoftCoverWithUnifCodewords}
Suppose $p_{X}(\cdot)$ is a PMF on a finite field $\mathcal{X}=\fieldq$ of size $q$, $s_{x} \in \mathcal{D}(\HlbSp): x \in \CalX$ and $s=\sum_{x}p_{X}(x)s_{x} \in \mathcal{D}(\HlbSp)$. Suppose the $q^{nR}$ elements of $A=(X^{n}(1),\cdots,X^{n}(q^{nR}))$ are uniformly distributed and pairwise independent, then\vspace{-0.1in}
\begin{eqnarray}
\label{Eqn:QuantCoverExpBoundCosetCode}
\mathbb{E}_{\!\mathcal{U}}\!\left\{\!||s^{\otimes n}-s(A)||_{1} \!\right\} \leq \exp\left\{\! -\frac{n[\substack{ R-\chi(s_{x};p_{X}:\mathcal{X})-\log q+H(p_{X})}]}{2} \!\right\}\mbox{ where } s(A)\define \frac{1}{q^{nR}}\sum_{m=1}^{q^{nR}}q^{n}p_{X}(X^{n}(m))s_{X^{n}(m)}.\nonumber
\end{eqnarray}
In particular, $\exists$ a map $c:[q^{nR_{0}}]\times [q^{nR_{1}}] \rightarrow \mathcal{X}^{n}$ whose \textbf{range is a coset} such that\vspace{-0.1in}
\begin{eqnarray}
\label{Eqn:CorollaryOfQuantSftCoverCosetCode}
\frac{1}{q^{nR_{0}}}\sum_{k=1}^{q^{nR_{0}}}||s^{\otimes n}-\frac{1}{q^{nR_{1}}}\sum_{m=1}^{q^{nR_{1}}}q^{n}p_{X}^{n}(c(k,m))s_{c(k,m)}||_{1}\leq 2^{-\frac{n\eta}{8}}
\end{eqnarray}
if $R_{1}> \chi(s_{x};p_{X}:\mathcal{X})+\log q-H(p_{X})+2\eta$.
\end{lemma}
\begin{theorem}
\label{Thm:CosetPOVMIsAnoptimalSimulation}
Let $\rho \in \mathcal{D}(\HlbSp_{A}), \lambda_{\CalY} \in \mathscr{M}(\HlbSp_{A},\CalY)$ and $(\mathcal{W}=\fieldq,\mu_{\mathcal{W}},p_{Y|W}) \in \mathcal{C}(\rho,\lambda_{\mathcal{Y}})$, where $\mathcal{W}=\fieldq$ is a finite field with $q$ elements. Suppose $c+r+\beta > \mathscr{R}\mathscr{C}(\mathcal{W}=\fieldq,\mu_{\mathcal{W}},p_{Y|W})+\log q-H(p_{W})$ and $r+\beta > \mathscr{R}(\mathcal{W}=\fieldq,\mu_{\mathcal{W}},p_{Y|W})+\log q-H(p_{W})$, where $p_{W}(w)=\tr(\rho\mu_{w}):w \in \CalW$, then there exists a $\hat{c}:[q^{nc}]\times[q^{nr}]\times[q^{n\beta}]\rightarrow \mathcal{W}^{n}$ whose range is a coset for which the POVM $\hat{\theta} \define \{ \hat{\theta}_{k,m,b}\otimes \ketbra{k}{k}:1\leq k\leq q^{nc},1\leq m \leq q^{nr},1\leq b\leq q^{n\beta}\}$ defined through (\ref{Eqn:DefnOfNewS_k}) simulates POVM $\lambda_{\CalY}$ on $\rho$ with communication cost $(\mathscr{R}\mathscr{C}(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W}),\mathscr{R}(\mathcal{W},\mu_{\mathcal{W}},p_{Y|W}))$.
\end{theorem}
\begin{remark}
\label{Rem:FinalRemark}
To prove achievability of Thm.~\ref{Thm:CosetPOVMIsAnoptimalSimulation} using Lem.~\ref{Lem:SoftCoverWithUnifCodewords}, one needs to pick a random linear code with uniform and IID generator matrix indices for $\beta$ is just smaller than but within $\eta$ of $\log q-H(p_{W})$. The rest of the steps are identical to Proof of Thm.~\ref{Thm:CommnCostCharacterization} and leverages an analogous substition for the two terms as in Rem.~\ref{Rem:LemmaProvesThm}.
\end{remark}

\begin{comment}{

In the sequel, we recognize that $||\alphaorig-\alpha||_{1}$ and $||\sigma_{A^{n}K} -\rho_{K}^{\otimes n}||_{1}$ are specific instances of the quantum covering lemma \cite[Lem.~?]{2013Bk_Wil}. Towards that end, recall $p_{W}(\cdot),\beta_{w},\gamma_{w}$ from (\ref{Eqn:BetaAndPWDefn}), (\ref{Eqn:GammaDefn}). If we let $\gamma \define \sum_{y \in \mathcal{Y}}\sqrt{\rho}\lambda_{y}\sqrt{\rho}\otimes \ketbra{y}{y}$, then it is easily verified that LHS and RHS of (\ref{Eqn:QuantMarkovChainCondition}) are $\gamma$ and $\sum_{w\in \mathcal{W}}p_{W}(w)\gamma_{w}$ respectively. Moreover $\alphaorig=\gamma^{\otimes n}$ in ((\ref{Eqn:AlphaOSimplified})) and $\alpha = \frac{1}{KM}\sum_{k,m}\beta_{c(k,m)}$. Requiring $||\alphaorig-\alpha||_{1}$ to be exponentially small is therefore asking the question how many samples of the collection $(\gamma_{w^{n}}:w^{n}\in \mathcal{W}^{n})$ such that the corresponding uniform density operator is close to $\gamma^{\otimes n}$.

observe that, in studying $||\alphaorig-\alpha||_{1}$, the block diagonal structure of $\alpha,\alphaorig$ and the $\frac{1}{K}$ factor in (\ref{Eqn:AlphaSimplified}), (\ref{Eqn:AlphaOSimplified}) imply that it suffices to prove
\begin{eqnarray}
\label{Eqn:Connect1stBoundToQuantCover}
||\!\!\sum_{m=1}^{M}\!\!\frac{\beta_{w^{n}(k,m)}}{M}-\!\beta||_{1} \leq \frac{\eta}{2},\! \mbox{ where } \beta\define\! \!\!\!\sum_{y^{n}\in \mathcal{Y}^{n}}\!\!\!\!\!
\sqrt{\omega}\lambda_{y^{n}}\!\sqrt{\omega}\!\otimes \!\ketbra{y^{n}}{y^{n}} \nonumber\\\beta_{w^{n}} \define \sum_{y^{n} \in \mathcal{Y}^{n}}p_{Y|W}(y^{n}|w^{n})\frac{\sqrt{\omega}\mu_{w^{n}}\sqrt{\omega}}{\tr(\omega\mu_{w^{n}})} \nonumber\otimes \ketbra{y^{n}}{y^{n}}.
\end{eqnarray}
Similarly, collating $\sigma_{A^{n}K}$ from (\ref{Eqn:TheAuxillaryState2}), $T_{k}$ from (\ref{Eqn:TheAuxillaryState1}), $S_{k}$ from (\ref{Eqn:DefnOfS_k}) and recalling $\rho^{\otimes n}_{K}=\frac{1}{K}\sum_{k=1}^{K}\rho^{\otimes n}\otimes\ketbra{k}{k}$, it suffices to prove
\begin{eqnarray}
||\!\!\sum_{m=1}^{M}\!\!\frac{\gamma_{w^{n}(k,m)}}{M}-\!\gamma||_{1} \leq \frac{\eta}{2},\! \mbox{ where } \gamma\define\! \!\!\!\sum_{y^{n}\in \mathcal{Y}^{n}}\!\!\!\!\!
\sqrt{\omega}\lambda_{y^{n}}\!\sqrt{\omega}\!\otimes \!\ketbra{y^{n}}{y^{n}} \nonumber\\\beta_{w^{n}} \define \sum_{y^{n} \in \mathcal{Y}^{n}}p_{Y|W}(y^{n}|w^{n})\frac{\sqrt{\omega}\mu_{w^{n}}\sqrt{\omega}}{\tr(\omega\mu_{w^{n}})} \nonumber\otimes \ketbra{y^{n}}{y^{n}}.
\end{eqnarray}
\begin{comment}{
We consider a classical-quantum multiple access channel (CQ-MAC) with two senders and a receiver. The receiver's objective is to reconstruct a specific bivariate function of the two classical information streams observed by the senders. In this work, we undertake a Shannon-theoretic study and address the problem of characterizing sufficient conditions under which the receiver can reconstruct the desired function losslessly. We characterize a new set of sufficient conditions that are strictly weaker than the current known best for identified examples.
% \error{
% \begin{enumerate}
%         \item Proof techniques for CQ-MAC. Specifically write a) Coding , Decoding, Characterize Eroor events, b) State how the event is analyzed - key elements without equations and write the obtained rate bounds. Refer for complete proof.
%     \item
% \end{enumerate}
% }

\appendices
\section{POVM Simulation with respect to Purifications}
\label{AppSec:PurificationAndSimulation}
We recall notation that is adopted throughout the article. We let ${|b_1⟩,⋯,|b_d⟩} ⊆$ denote an arbitrary but fixed orthonormal basis and $_X =$. For any $|x⟩ =∑_i=1^dα_i|b_i⟩ ∈$, we let $|⟩=∑_i=1^dα_i^*|b_i⟩∈_A$ denote the complex conjugation with respect to orthonormal basis ${|b_1⟩,⋯,|b_d⟩}$. Similarly, for $A ∈()$ with a spectral decomposition $A=∑_i=1^dα_i|a_i⟩⟨a_i|$, we let $A^* A^t ∑_i=1^dα_i|_i⟩⟨_i|$.\footnote{This notation can be justified by the fact that the matrices of $A$ and and $A^{*}$ in the orthonormal basis $\{ \ket{b_{1}},\cdots,\ket{b_{d}}\} \subseteq \CalHA$ are complex conjugates or transposes of each other.} We collate simple facts regarding these in the following.

\begin{lemma}
\label{Lem:CanonicalBasisSimpleFacts}
\begin{enumerate}
\item If $\{\ket{u_{1}},\cdots,\ket{u_{d}}\} \subseteq \CalHA$ is an orthonormal basis, then $\{\ket{\olineu_{1}},\cdots,\ket{\olineu_{d}}\} \subseteq \CalHA$ is an orthonormal basis.
\item For any $\ket{x},\ket{y} \in \CalHA$, we have $\braket{\olinex}{\oliney}=\braket{y}{x}$.
\item Suppose $\sigma \in \CalD(\CalHA)$ has a spectral decomposition $\sigma = \sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}$, then $\ket{\phi_{\sigma}} \define \sum_{i=1}^{d}\sqrt{\gamma_{i}}\ket{\olineu_{i}}\otimes \ket{u_{i}} \in \CalH_{X}\otimes\CalHA$ is a purification of $\sigma$. Analogously, $\ket{\phi_{\sigma^{\otimes n}}} = \sum_{i_{1}=1}^{d} \cdots \sum_{i_{n}=1}^{d}\sqrt{\gamma_{i_{1}}\cdots \gamma_{i_{n}}}\ket{\olineu_{i_{1}}} \cdots \otimes  \cdots\ket{\olineu_{i_{n}}} \otimes \ket{u_{i_{1}}} \cdots \otimes  \cdots\ket{u_{i_{n}}}$ is a purification of $\sigma^{\otimes n}$, and
\item Suppose $A,C \in \CalR(\CalHA)$ and $\{\ket{u_{1}},\cdots,\ket{u_{d}}\} \subseteq \CalHA$ is an orthonormal basis, then $\mel{u_{j}}{ACA}{u_{i}} = \mel{\olineu_{i}}{(ACA)^{*}}{\olineu_{j}}$ for all $i,j \in [d]$ and hence
\begin{eqnarray}
\label{Eqn:ACATranspose}
\sum_{i=1}^{d}\sum_{j=1}^{d}\mel{u_{j}}{ACA}{u_{i}}\ketbra{\olineu_{i}}{\olineu_{j}}= (ACA)^{*}=(ACA)^{t}\begin{comment}{\mbox{ and }(ACA)^{*}=(ACA)^{t} = A^{*}C^{*}A^{*}=A^{t}C^{t}A^{t}}\end{comment}.\nonumber
\end{eqnarray}
\item For any $A,C \in \CalR(\CalH)$, we have $(A-C)^{*}=A^{*}-C^{*}$ and $\norm{A}_{1}=\norm{A^{*}}_{1}=\norm{A^{t}}_{1}$.
\begin{comment}{
$\sigma \in \CalD(\CalHA)$ has a spectral decomposition $\sigma = \sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}$, then $\sigma^{*}\ket{\olineu_{i}} = \sigma^{t}\ket{\olineu_{i}}= \gamma_{i}\ket{\olineu_{i}}$ and $\bra{\olineu_{i}}\sigma^{*} = \bra{\olineu_{i}}\sigma^{t}= \bra{\olineu_{i}}\gamma_{i}$ and $\sqrt{\sigma}^{*}\ket{\olineu_{i}} = \sqrt{\sigma}^{t}\ket{\olineu_{i}}= \sqrt{\gamma_{i}}\ket{\olineu_{i}}$ and $\bra{\olineu_{i}}\sqrt{\sigma}^{*} = \bra{\olineu_{i}}\sqrt{\sigma}^{t}= \bra{\olineu_{i}}\sqrt{\gamma_{i}}$.}\end{comment}
\end{enumerate}
\end{lemma}
\begin{proof}
For $i \in [d]$, let $\ket{u_{i}} = \sum_{k=1}^{d}\alpha_{ki}\ket{b_{k}}$ and $\ket{\olineu_{i}} = \sum_{k=1}^{d}\alpha_{ki}^{*}\ket{b_{k}}$. Since $\{\ket{u_{1}},\cdots,\ket{u_{d}}\} \subseteq \CalHA$ is an orthonormal basis, we have $\delta_{ji}= \braket{u_{j}}{u_{i}} = \sum_{k=1}^{d}\alpha_{kj}^{*}\alpha_{ki}$. We therefore have $\braket{\olineu_{j}}{\olineu_{i}} = \sum_{k=1}^{d}\alpha_{kj}\alpha_{ki}^{*} = \left(\sum_{k=1}^{d}\alpha_{kj}^{*}\alpha_{ki}\right)^{*}= \delta_{ji}^{*}=\delta_{ji}$.

Suppose $\ket{x}=\sum_{i=1}^{d}\alpha_{i}\ket{b_{i}}$ and $\ket{y}=\sum_{i=1}^{d}\beta_{i}\ket{b_{i}}$, then $\ket{\olinex}=\sum_{i=1}^{d}\alpha_{i}^{*}\ket{b_{i}}$ and $\ket{\oliney}=\sum_{i=1}^{d}\beta_{i}^{*}\ket{b_{i}}$. Therefore, $\braket{\olinex}{\oliney} = \sum_{i=1}^{d}\alpha_{i}\beta_{i}^{*} = \left(\sum_{i=1}^{d}\alpha_{i}^{*}\beta_{i}\right)^{*} = \left(\braket{x}{y}\right)^{*} =\braket{y}{x}$.

From 1), we have $\braket{\phi_{\sigma}}{\phi_{\sigma}} = \sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\braket{\olineu_{j}}{\olineu_{i}}\braket{u_{j}}{u_{i}} = \sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\delta_{ji}\delta_{ji} = \sum_{j=1}^{d}\gamma_{j}=1$ and $\tr_{\CalH_{X}}( \ketbra{\phi_{\sigma}}{\phi_{\sigma}}) = \sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\braket{\olineu_{j}}{\olineu_{i}}\ketbra{u_{j}}{u_{i}} = \sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\delta_{ji}\ketbra{u_{j}}{u_{i}} =  \sum_{j=1}^{d}\gamma_{j}\ketbra{u_{j}}{u_{j}} =\sigma$. The next statement in regards to $\sigma^{\otimes n}$ can be verified analogously.

With regard to the fourth assertion, clearly $A,C \in \CalR(\CalHA)$ implies $ACA \in \CalR(\CalH)$. Let $ACA=\sum_{i=1}^{d}\sum_{j=1}^{d}\nu_{ij}\ketbra{u_{i}}{u_{j}}$, where $\{\ket{u_{1}},\cdots,\ket{u_{d}}\} \subseteq \CalHA$ is some orthonormal basis, have a spectral decomposition $ACA = \sum_{l=1}^{d}\chi_{l}\ketbra{x_{l}}{x_{l}}$ with $\chi_{l} \in \reals$ for $l \in [d]$. We have $(ACA)^{*}=(ACA)^{t}=\sum_{l=1}^{d}\chi_{l}\ketbra{\olinex_{l}}{\olinex_{l}}$ and $\nu_{st} = \mel{u_{s}}{ACA}{u_{t}}$. Substituting spectral decomposition of $ACA$ and using the third assertion, we have
\begin{eqnarray}
\label{Eqn:SimpleFactsLemma11}
\nu_{st} &=& \mel{u_{s}}{ACA}{u_{t}}= \sum_{l=1}^{d}\chi_{l}\braket{u_{s}}{x_{l}}\braket{x_{l}}{u_{t}} = \sum_{l=1}^{d}\chi_{l}\braket{\olinex_{l}}{\olineu_{s}}\braket{\olineu_{t}}{\olinex_{l}} = \sum_{l=1}^{d}\chi_{l}\braket{\olineu_{t}}{\olinex_{l}}\braket{\olinex_{l}}{\olineu_{s}} \nonumber\\
\label{Eqn:SimpleFactsLemma12}
&=& \mel{\olineu_{t}}{\sum_{l=1}^{d}\chi_{l}\ketbra{\olinex_{l}}{\olinex_{l}}}{\olineu_{s}}=\mel{\olineu_{t}}{(ACA)^{*}}{\olineu_{s}}= \mel{\olineu_{t}}{(ACA)^{t}}{\olineu_{s}}.
\end{eqnarray}
From the first assertion, equality of the second and the last terms in (\ref{Eqn:SimpleFactsLemma12}), we have
\begin{eqnarray}
\label{Eqn:SimpleFactsLemma13}
(ACA)^{*}=(ACA)^{t} = \sum_{i=1}^{d}\sum_{j=1}^{d}\mel{\olineu_{i}}{(ACA)^{*}}{\olineu_{j}}\ketbra{\olineu_{i}}{\olineu_{j}}= \sum_{i=1}^{d}\sum_{j=1}^{d}\mel{\olineu_{i}}{(ACA)^{t}}{\olineu_{j}}\ketbra{\olineu_{i}}{\olineu_{j}}= \sum_{i=1}^{d}\sum_{j=1}^{d}\mel{u_{j}}{ACA}{u_{i}}\ketbra{\olineu_{i}}{\olineu_{j}}
\nonumber
\end{eqnarray}
which proves our claimed assertion.

Suppose $A,C\in \CalR(\CalH)$, $A = \sum_{l=1}^{d}\chi_{l}\ketbra{x_{l}}{x_{l}}$ and $C=\sum_{l=1}^{d}\epsilon_{l}\ketbra{y^{l}}{y^{l}}$ with $\chi_{l},\epsilon_{l} \in \reals$ for $l \in [d]$. Let $A-C \in \CalR(\CalH)$ have spectral decomposition $A-C = \sum_{l=1}^{d}\mu_{l}\ketbra{w_{l}}{w_{l}}$ with $\mu_{l} \in \reals$ for $l \in [d]$. We also observe
\begin{eqnarray}
\lefteqn{\mu_{i} = \mel{w_{i}}{A-C}{w_{i}} = \mel{w_{i}}{A}{w_{i}}-\mel{w_{i}}{C}{w_{i}} = \sum_{l=1}^{d}\chi_{l}\braket{w_{i}}{x_{l}}\braket{x_{l}}{w_{i}} - \sum_{l=1}^{d}\epsilon_{l}\braket{w_{i}}{y_{l}}\braket{y_{l}}{w_{i}}} \nonumber\\
&&\!\!\!\!\!\!\!\!\!\!\!\!\!\!= \sum_{l=1}^{d}\chi_{l}\braket{\olinex_{l}}{\olinew_{i}}\braket{\olinew_{i}}{\olinex_{l}} - \sum_{l=1}^{d}\epsilon_{l}\braket{\oliney_{l}}{\olinew_{i}}\braket{\olinew_{i}}{\oliney_{l}} = \sum_{l=1}^{d}\chi_{l}\braket{\olinew_{i}}{\olinex_{l}}\braket{\olinex_{l}}{\olinew_{i}} - \sum_{l=1}^{d}\epsilon_{l}\braket{\olinew_{i}}{\oliney_{l}}\braket{\oliney_{l}}{\olinew_{i}} = \mel{\olinew_{i}}{A^{*}}{\olinew_{i}}-\mel{\olinew_{i}}{C^{*}}{\olinew_{i}}.
\nonumber
\end{eqnarray}
We now have $(A-C)^{*} = \sum_{i=1}^{d}\mu_{i}\ketbra{\olinew_{i}}{\olinew_{i}} = \sum_{i=1}^{d} \mel{\olinew_{i}}{A^{*}}{\olinew_{i}}\ketbra{\olinew_{i}}{\olinew_{i}}-\mel{\olinew_{i}}{C^{*}}{\olinew_{i}}\ketbra{\olinew_{i}}{\olinew_{i}} = A^{*}-C^{*} $. In regards to the assertion relating norms, we have $A^{*}=A^{t} = \sum_{l=1}^{d}\chi_{l}\ketbra{\olinex_{l}}{\olinex_{l}}$ from the spectral decomposition of $A$, and $U_{X}\define \sum_{i=1}^{d}\ketbra{\olinex_{i}}{x_{i}}$ is unitary. Since trace norm is invariant under multiplication by isometries \cite[Prop.~9.1.4]{BkWilde_2017}, we have
\begin{eqnarray}
\label{Eqn:SimplePropNormEqualivalence}
\norm{A^{*}}_{1}=\norm{U_{X}^{\dagger}A^{*}U_{X}}_{1}=\norm{\sum_{i=1}^{d}\sum_{j=1}^{l}\sum_{l=1}^{d} \ketbra{x_{j}}{\olinex_{j}}\chi_{l}\ketbra{\olinex_{l}}{\olinex_{l}} \ketbra{\olinex_{i}}{x_{i}}}_{1} =
\norm{\sum_{l=1}^{d} \chi_{i}\ketbra{x_{i}}{x_{i}} }_{1}=\norm{A}_{1}.
\nonumber
\end{eqnarray}
\begin{comment}{Let $\ket{u_{i}}=\sum_{k=1}^{d}\alpha_{ki}\ket{b_{k}}$, we then have
\begin{eqnarray}
\label{Eqn:SimplePropsPurification1}
\sum_{k=1}^{d}\alpha_{ki}\sigma\ket{b_{k}} = \sigma \ket{u_{i}} = \gamma_{i}\sum_{k=1}^{d}\alpha_{ki}\ket{b_{k}}\mbox{ implying } \left(\sum_{k=1}^{d}\alpha_{ki}\sigma\ket{b_{k}}\right)^{*} = \sigma^{*} \ket{\olineu_{i}} = \left(\gamma_{i}\sum_{k=1}^{d}\alpha_{ki}\ket{b_{k}}\right)^{*}\mbox{which in turn implies}\!\!\!\!\!\!\!\nonumber\\
\label{Eqn:SimplePropsPurification2}
\sum_{k=1}^{d}\alpha_{ki}^{*}\sigma^{*}\ket{b_{k}} = \sigma^{*} \ket{\olineu_{i}} = \gamma_{i}\sum_{k=1}^{d}\alpha_{ki}^{*}\ket{b_{k}} = \gamma_{i}\ket{\olineu_{i}} \mbox{ and since }\sigma^{*}=\sigma^{t}\mbox{ we have }\sigma^{*}\ket{\olineu_{i}}=\sigma^{t}\ket{\olineu_{i}} = \gamma_{i}\ket{\olineu_{i}}.\mbox{ Similarly}\nonumber\\
\sum_{k=1}^{d}\!\!\alpha_{ki}\sqrt{\sigma}\ket{b_{k}} = \!\sqrt{\sigma} \ket{u_{i}} = \sqrt{\gamma_{i}}\sum_{k=1}^{d}\!\!\alpha_{ki}\ket{b_{k}}\!\!\mbox{ implying } \!\left(\!\sum_{k=1}^{d}\!\!\alpha_{ki}\sqrt{\sigma}\ket{b_{k}}\!\!\right)^{\!*}\!\!\! = \sqrt{\sigma}^{*} \ket{\olineu_{i}} \!\!= \left(\!\!\sqrt{\gamma_{i}}\sum_{k=1}^{d}\!\!\alpha_{ki}\ket{b_{k}}\!\!\right)^{\!*}\!\!\mbox{which in turn implies}\!\!\!\!\!\!\!\nonumber\\
\label{Eqn:SimplePropsPurification2}
\sum_{k=1}^{d}\alpha_{ki}^{*}\sqrt{\sigma}^{*}\ket{b_{k}} = \sqrt{\sigma}^{*} \ket{\olineu_{i}} = \gamma_{i}\sum_{k=1}^{d}\alpha_{ki}^{*}\ket{b_{k}} = \gamma_{i}\ket{\olineu_{i}} \mbox{ and since }\sqrt{\sigma}^{*}=\sqrt{\sigma}^{t}\mbox{ we have }\sqrt{\sigma}^{*}\ket{\olineu_{i}}=\sqrt{\sigma}^{t}\ket{\olineu_{i}} = \gamma_{i}\ket{\olineu_{i}}.
\nonumber
\end{eqnarray}
where we have used the fact that $\gamma_{i}=\gamma_{i}^{*}$, $A \in \CalP(\CalH)$ implies $A^{*}=A^{t}$.}\end{comment}
\end{proof}

The following lemma enables us relate simulation of POVMs as stated in Defn.~\ref{Defn:EpsilonSimulationOn} to simulation of POVMs with respect to purifications. To begin with, we recall our notation. Associated with any POVM $\lambda =\{\lambda_{y} \in \CalP(\CalH) :y \in \mathcal{Y} \}$ is a Hilbert space $\mathcal{H}_{\mathcal{Y}} \define \span\{\ket{y}:y \in \mathcal{Y}\}$ with $\braket{\haty}{y}=\delta_{\haty y}$ and the CPTP map $\mathscr{E}^{\lambda}:\mathcal{L}(\mathcal{H})\rightarrow \mathcal{L}(\mathcal{H}_{\mathcal{Y}})$, defined as $\mathscr{E}^{\lambda}(s)=\sum_{y \in \mathcal{Y}}\tr(s\lambda_{y})\ketbra{y}{y}$.

\begin{lemma}
\label{Lem:PurificationSimulation}
Suppose $\rho \in \CalD(\CalHA)$, $\lambda_{\CalY},\theta_{\CalY} \in \ScrM(\CalHA,\CalY)$ are POVMs and $\eta > 0$. $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on $\rho$ if
\begin{eqnarray}
\label{Eqn:POVMSimOnPurificationsSuffice}
\norm{(i_{X}\otimes \ScrE^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}}) - (i_{X}\otimes \ScrE^{\theta})(\ketbra{\phi_{\rho}}{\phi_{\rho}})}_{1} \leq \eta.
\end{eqnarray}
\end{lemma}
\begin{proof}
Our proof is identical to that in [7] and is provided here only for completeness. Let $(\sigma_{k},p_{K}:\CalK)$ be an ensemble with average $\rho$. Let $\rho=\sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}$ be a spectral decomposition and we have $\ket{\phi_{\rho}}= \sum_{i=1}^{d}\sqrt{\gamma_{i}}\ket{\olineu_{i}}\otimes \ket{u_{i}} \in \CalH_{X}\otimes\CalHA$. We let $S_{k} \define \rho^{-\frac{1}{2}}p_{K}(k)\sigma_{k}\rho^{-\frac{1}{2}} $ and we note $S_{k} \in \CalP(\CalHA)$ and $\sum_{k\in\CalK}S_{k}=I_{\CalHA}$. Let $A_{y} \define \rho^{\frac{1}{2}}(\lambda_{y}-\theta_{y})\rho^{\frac{1}{2}} \in \CalR(\CalH)$ and $A_{y}=A_{y}^{+}-A_{y}^{-}$ with $A_{y}^{+},A_{y}^{-} \in \CalP(\CalH)$. We are led to
\begin{eqnarray}
\label{Eqn:PurificationSimulationIsGood11}
\lefteqn{\!\!\!\!\sum_{k \in \CalK}\sum_{y \in \CalY}|\tr(\lambda_{y}p_{K}(k)\sigma_{k})- \tr(\theta_{y}p_{K}(k)\sigma_{k})| =  \sum_{k \in \CalK}\sum_{y \in \CalY}\left|\tr(\rho^{\frac{1}{2}}\lambda_{y}\rho^{\frac{1}{2}}\rho^{-\frac{1}{2}}p_{K}(k)\sigma_{k}\rho^{-\frac{1}{2}})- \tr(\rho^{\frac{1}{2}}\theta_{y}\rho^{\frac{1}{2}}\rho^{-\frac{1}{2}}p_{K}(k)\sigma_{k}\rho^{-\frac{1}{2}})\right| }
\\
\label{Eqn:PurificationSimulationIsGood12}
&&\!\!\!\!\!\!\!\!\!\!=  \sum_{k \in \CalK}\sum_{y \in \CalY}\left|\tr(\rho^{\frac{1}{2}}\lambda_{y}\rho^{\frac{1}{2}}S_{k})- \tr(\rho^{\frac{1}{2}}\theta_{y}\rho^{\frac{1}{2}}S_{k})\right|  = \sum_{k \in \CalK}\sum_{y \in \CalY}\left|\tr(\rho^{\frac{1}{2}}(\lambda_{y}-\theta_{y})\rho^{\frac{1}{2}}S_{k})\right| = \sum_{k \in \CalK}\sum_{y \in \CalY}\left|\tr(A_{y}S_{k})\right|\\
\label{Eqn:PurificationSimulationIsGood13}
&&\!\!\!\!\!\!\!\!\!\!= \sum_{k \in \CalK}\sum_{y \in \CalY}\left|\tr(A_{y}^{+}S_{k}) - \tr(A_{y}^{-}S_{k}) \right| \leq \sum_{k \in \CalK}\sum_{y \in \CalY}\left|\tr(A_{y}^{+}S_{k})\right| +\left| \tr(A_{y}^{-}S_{k}) \right| = \sum_{k \in \CalK}\sum_{y \in \CalY}\tr(A_{y}^{+}S_{k}) + \tr(A_{y}^{-}S_{k})
\\
\label{Eqn:PurificationSimulationIsGood14}
&&\!\!\!\!\!\!\!\!\!\!= \sum_{y \in \CalY}\tr(A_{y}^{+}) + \tr(A_{y}^{-}) = \sum_{y \in \CalY}\|A_{y}\|_{1} = \sum_{y \in \CalY}\|\rho^{\frac{1}{2}}\lambda_{y}\rho^{\frac{1}{2}}-\rho^{\frac{1}{2}}\theta_{y}\rho^{\frac{1}{2}}\|_{1}  = \|\sum_{y \in \CalY}\!\!\left[\rho^{\frac{1}{2}}\lambda_{y}\rho^{\frac{1}{2}}\otimes\ketbra{y}-\rho^{\frac{1}{2}}\theta_{y}\rho^{\frac{1}{2}}\otimes\ketbra{y}\right]\!\!\|_{1},
\end{eqnarray}
where the equalities in (\ref{Eqn:PurificationSimulationIsGood11}), (\ref{Eqn:PurificationSimulationIsGood12}) follows from cyclicity, linearity of trace operator, the inequality in (\ref{Eqn:PurificationSimulationIsGood13}) follows from the triangular inequality, the last equality in (\ref{Eqn:PurificationSimulationIsGood13}) follows from the fact that $A,B\in \CalP(\CalH)$ implies $\tr(AB) \geq 0$, \ref{Eqn:PurificationSimulationIsGood14} follows from $\sum_{k \in \CalK}S_{k}=I_{\CalHA}$, the second equality in (\ref{Eqn:PurificationSimulationIsGood14}) follows from \cite[Eqn. 1.8 and 1.15]{BkHolevo_2019}, and finally the last equality in (\ref{Eqn:PurificationSimulationIsGood14}) follows from the fact that the trace norm of a block diagonal matrix is the sum of the trace norm of each of the blocks. We shall now evaluate the LHS in (\ref{Eqn:POVMSimOnPurificationsSuffice}) and prove that the same is equal to the RHS of (\ref{Eqn:PurificationSimulationIsGood14}). Towards the end, we have
\begin{eqnarray}
\label{Eqn:PurificationSimulationIsGood21}
\lefteqn{(i_{X}\otimes \ScrE^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}}) = (i_{X}\otimes \ScrE^{\lambda})\left(\sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\ketbra{\olineu_{i}}{\olineu_{j}}\otimes \ketbra{u_{i}}{u_{j}}\right) = \sum_{i=1}^{d}\sum_{j=1}^{d}\sum_{y \in \CalY}\sqrt{\gamma_{i}\gamma_{j}}\ketbra{\olineu_{i}}{\olineu_{j}}\otimes \tr(\lambda_{y}\ketbra{u_{i}}{u_{j}})\ketbra{y}}
\nonumber\\
&=& \sum_{y \in \CalY}\sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\braket{u_{j}}{\lambda_{y}u_{i}}\ketbra{\olineu_{i}}{\olineu_{j}}\otimes \ketbra{y} =  \sum_{y \in \CalY}\sum_{i=1}^{d}\sum_{j=1}^{d}\mel{u_{j}}{\sqrt{\rho}\lambda_{y}\sqrt{\rho}}{u_{i}}\ketbra{\olineu_{i}}{\olineu_{j}}\otimes \ketbra{y} = \sum_{y \in \CalY}\left({\sqrt{\rho}\lambda_{y}\sqrt{\rho}}\right)^{*}\otimes \ketbra{y}
\nonumber
\end{eqnarray}
where the last equality follows the fourth assertion in Lemma \ref{Lem:PurificationSimulation}. Substituting this, (\ref{Eqn:POVMSimOnPurificationsSuffice}) implies
\begin{eqnarray}
\label{Eqn:PurificationSimulationIsGood15}
\eta &\geq& \norm{(i_{X}\otimes \ScrE^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}}) - (i_{X}\otimes \ScrE^{\theta})(\ketbra{\phi_{\rho}}{\phi_{\rho}})}_{1} = \norm{\sum_{y \in \CalY}\left({\sqrt{\rho}\lambda_{y}\sqrt{\rho}}\right)^{*}\otimes \ketbra{y} - \sum_{y \in \CalY}\left({\sqrt{\rho}\theta_{y}\sqrt{\rho}}\right)^{*}\otimes \ketbra{y} }_{1}
\\
\label{Eqn:PurificationSimulationIsGood16}
&=&\sum_{y \in \CalY}\norm{\left({\sqrt{\rho}\lambda_{y}\sqrt{\rho}}\right)^{*}-\left({\sqrt{\rho}\theta_{y}\sqrt{\rho}}\right)^{*} }_{1} = \sum_{y \in \CalY}\norm{\left({\sqrt{\rho}\lambda_{y}\sqrt{\rho}}-{\sqrt{\rho}\theta_{y}\sqrt{\rho}}\right)^{*} }_{1} = \sum_{y \in \CalY}\norm{{\sqrt{\rho}\lambda_{y}\sqrt{\rho}}-{\sqrt{\rho}\theta_{y}\sqrt{\rho}} }_{1} \\
\label{Eqn:PurificationSimulationIsGood17}
&\geq& \sum_{k \in \CalK}\sum_{y \in \CalY}|\tr(\lambda_{y}p_{K}(k)\sigma_{k})- \tr(\theta_{y}p_{K}(k)\sigma_{k})|,
\end{eqnarray}
where we have leveraged the fifth assertion in Lemma \ref{Lem:CanonicalBasisSimpleFacts} and (\ref{Eqn:PurificationSimulationIsGood11}) - (\ref{Eqn:PurificationSimulationIsGood14}) in asserting the last inequality.
\end{proof}

For any $\sigma \in \CalD(\CalHA)$, with a spectral decomposition $\sigma = \sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}$, we let $\ket{\phi_{\sigma}} \define \sum_{i=1}^{d}\sqrt{\gamma_{i}}\ket{u_{i}}\otimes \ket{\olineu_{i}}$ denote a purification of $\sigma$. Analogously, we let $\ket{\phi_{\sigma^{\otimes n}}} = \sum_{i_{1}=1}^{d} \cdots \sum_{i_{n}=1}^{d}\sqrt{\gamma_{i_{1}}\cdots \gamma_{i_{n}}}\ket{u_{i_{1}}} \cdots \otimes  \cdots\ket{u_{i_{n}}}\otimes \ket{\olineu_{i_{1}}} \cdots \otimes  \cdots\ket{\olineu_{i_{n}}}$.

Finally, we prove that that if two quantum states $\rho,\sigma \in \CalD(\CalH)$ are close, then their canonical purifications are not too far apart. Our proof mimics the proof steps of \cite[App.~14]{200401CommMathPhy_Win} and is provided only for self-containment.
\begin{lemma}
\label{Lem:WinterCanoniPuresCannotBeTooFar}
For any two states $\rho,\sigma \in \CalD(\CalH)$, we have
\begin{eqnarray}
\label{Eqn:CanPuresAreNotTooFar1}
\norm{\ketbra{\phi_{\rho}}{\phi_{\rho}} - \ketbra{\phi_{\sigma}}{\phi_{\sigma}}}_{1} \leq 2\sqrt{2}\sqrt[4]{\norm{\rho-\sigma}_{1}}.
\end{eqnarray}
\end{lemma}
\begin{proof}
We note that $\norm{\ketbra{\phi_{\rho}}{\phi_{\rho}} - \ketbra{\phi_{\sigma}}{\phi_{\sigma}}}_{1} = 2 \sqrt{1-|\braket{\phi_{\rho}}{\phi_{\sigma}}|^{2}}$ \cite[Eqn.~\(9.173\)]{BkWilde_2017}. We therefore compute $\braket{\phi_{\rho}}{\phi_{\sigma}}$. Let $\rho=\sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}{u_{i}}$ and $\sigma = \sum_{j=1}^{d}\mu_{j}\ketbra{w_{j}}{w_{j}}$ be spectral decompositions and $\ket{\phi_{\rho}} = \sum_{i=1}^{d}\sqrt{\gamma_{i}}\ket{\olineu_{i}}\otimes\ket{u_{i}} \in \CalH_{X}\otimes\CalHA$ and $\ket{\phi_{\sigma}} = \sum_{j=1}^{d}\sqrt{\mu_{j}}\ket{\olinew_{j}}\otimes\ket{w_{j}} \in \CalH_{X}\otimes\CalHA$ be canonical purifications. We have
\begin{eqnarray}
\label{Eqn:CanPuresAreNotTooFar2}
\lefteqn{\!\!\!\!\!\!\!\!\!\!\braket{\phi_{\rho}}{\phi_{\sigma}} = \sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\mu_{j}}\braket{\olineu_{i}}{\olinew_{j}}\braket{u_{i}}{w_{j}} = \sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\mu_{j}}\braket{w_{j}}{u_{i}}\braket{u_{i}}{w_{j}} = \sum_{j=1}^{d}\sqrt{\mu_{j}}\bra{w_{j}}\sum_{i=1}^{d}\sqrt{\gamma_{i}}\ketbra{u_{i}}{u_{i}}\ket{w_{j}}}
\\
\label{Eqn:CanPuresAreNotTooFar3}
&&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!= \sum_{j=1}^{d}\sqrt{\mu_{j}}\bra{w_{j}}\sqrt{\rho}\ket{w_{j}} =\sum_{j=1}^{d}\tr(\sqrt{\rho}\sqrt{\mu_{j}}\ketbra{w_{j}}{w_{j}}) =\tr(\sqrt{\rho}\sum_{j=1}^{d}\sqrt{\mu_{j}}\ketbra{w_{j}}{w_{j}})= \tr(\sqrt{\rho}\sqrt{\sigma}) = 1-\tr(\rho-\sqrt{\rho}\sqrt{\sigma})
\\
\label{Eqn:CanPuresAreNotTooFar4}
&&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!=1-\tr(\sqrt{\rho}\left(\sqrt{\rho}-\sqrt{\sigma}\right)) \geq 1- \norm{\sqrt{\rho}\left(\sqrt{\rho}-\sqrt{\sigma}\right)}_{1}\geq 1-\norm{\sqrt{\rho}}_{2}\norm{\sqrt{\rho}-\sqrt{\sigma}}_{2}\geq 1-\norm{\sqrt{|\rho-\sigma|}}_{2}= 1-\sqrt{\norm{\rho-\sigma}_{1}}
\\
\label{Eqn:CanPuresAreNotTooFar5}
&&= 1-\sqrt{\norm{\rho-\sigma}_{1}} \nonumber\\
\label{Eqn:CanPuresAreNotTooFar6}
\nonumber
\end{eqnarray}
where (i) the second equality in (\ref{Eqn:CanPuresAreNotTooFar2}) follows from Part 4 of Lemma \ref{Lem:CanonicalBasisSimpleFacts} by choosing $A=C=I_{A}$, the identity operator in $\CalH_{A}$, (ii) the last equality in (\ref{Eqn:CanPuresAreNotTooFar3}) follows from $\rho \in \CalD(\CalH)$, (iii) the first inequality in (\ref{Eqn:CanPuresAreNotTooFar4}) follows from the definition of $\norm{\cdot}_{1}$, (iv) the second inequality in (\ref{Eqn:CanPuresAreNotTooFar4}) follows from \cite[Corollary IV.2.6]{BkBhatia_1997} - a form of H\"older's inequality, (v) the third inequality in (\ref{Eqn:CanPuresAreNotTooFar4}) follows from \cite[Theorem X.1.3]{BkBhatia_1997} and (vi) the last equality in (\ref{Eqn:CanPuresAreNotTooFar4}) follows from the definition of $|\cdot|$ for an operator and the definition of $\norm{\cdot}_{1}$.
\end{proof}

\section{Invariance in the choice of the purification}
\label{AppSec:ChoiceOfPurificationDoesNotMatter}
It is natural to question whether we can replace the canonical purification $\phi_{\rho}$ in \ref{Eqn:POVMSimOnPurificationsSuffice} with any purification of $\rho$. This is indeed true and we provide a proof of this statement in the following.
\begin{lemma}
\label{Lem:AllPurificationsWork}
Suppose $\ket{\omega_{\rho}} \in \CalH_{X}\otimes \CalHA$ and $\ket{\alpha_{\rho}} \in \CalH_{Z}\otimes \CalHA$ are two purifications of $\rho \in \CalD(\CalHA)$ with $\dim(\CalH_{Z}) \geq \dim(\CalH_{X})$, $\lambda=\{\lambda_{y} : y \in \CalY\}, \theta = \{ \theta_{y} : y \in \CalY\} \in \ScrM(\CalHA,\CalY)$ are POVMs, then
\begin{eqnarray}
\label{Eqn:AllPurificationsWork1}
\norm{(i_{X}\otimes \ScrE^{\lambda})(\ketbra{\omega_{\rho}}{\omega_{\rho}}) - (i_{X}\otimes \ScrE^{\theta})(\ketbra{\omega_{\rho}}{\omega_{\rho}})}_{1} = \norm{(i_{Z}\otimes \ScrE^{\lambda})(\ketbra{\alpha_{\rho}}{\alpha_{\rho}}) - (i_{Z}\otimes \ScrE^{\theta})(\ketbra{\alpha_{\rho}}{\alpha_{\rho}})}_{1}.
\end{eqnarray}
\end{lemma}
\begin{proof}
Suppose $\rho \in \CalD(\CalHA)$ has a spectral decomposition $\rho = \sum_{i=1}^{d}\gamma_{i}\ketbra{u_{i}}$ and $\phi_{\rho} = \sum_{i=1}^{d}\sqrt{\gamma_{i}}\ket{\olineu_{i}}\otimes\ket{u_{i}}$ be the canonical purification. We shall prove (\ref{Eqn:AllPurificationsWork1}) the stated asssertion by proving equality (\ref{Eqn:AllPurificationsWork1}) with $\ket{\omega_{\rho}} = \ket{\phi_{\rho}}$ and a  a generic purification $\ket{\alpha_{\rho}}$. Since any two purifications of $\rho$ are related via an isometry acting on the reference Hilbert space \cite[Thm.~5.1.1]{BkWilde_2017}, there exists an isomery $V:\mathcal{H}_{X}\rightarrow \mathcal{H}_{Z}$ such that $\ket{\alpha_{\rho}} = (V\otimes I_{A})\ket{\phi_{\rho}} = \sum_{i=1}^{d}\sqrt{\gamma_{i}}V\ket{\olineu_{i}}\otimes \ket{u_{i}}$. we therefore have
\begin{eqnarray}
\label{Eqn:AllPurificationsWork2}
\lefteqn{(i_{Z}\otimes \ScrE^{\lambda})(\ketbra{\alpha_{\rho}}{\alpha_{\rho}})  = (i_{Z}\otimes \ScrE^{\lambda})\left(\sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}V\ketbra{\olineu_{i}}{\olineu_{j}}V^{\dagger}\otimes \ketbra{u_{i}}{u_{j}}\right) = \sum_{i=1}^{d}\sum_{j=1}^{d}\sum_{y \in \CalY}\sqrt{\gamma_{i}\gamma_{j}}V\ketbra{\olineu_{i}}{\olineu_{j}}V^{+}\otimes \tr(\lambda_{y}\ketbra{u_{i}}{u_{j}})\ketbra{y}}
\nonumber\\
\label{Eqn:AllPurificationsWork3}
&=& \sum_{y \in \CalY}\sum_{i=1}^{d}\sum_{j=1}^{d}\sqrt{\gamma_{i}\gamma_{j}}\braket{u_{j}}{\lambda_{y}u_{i}}V\ketbra{\olineu_{i}}{\olineu_{j}}V^{\dagger}\otimes \ketbra{y} =  \sum_{y \in \CalY}\sum_{i=1}^{d}\sum_{j=1}^{d}\mel{u_{j}}{\sqrt{\rho}\lambda_{y}\sqrt{\rho}}{u_{i}}V\ketbra{\olineu_{i}}{\olineu_{j}}V^{\dagger}\otimes \ketbra{y}
\nonumber\\
\label{Eqn:AllPurificationsWork4}
&=& \sum_{y \in \CalY}\sum_{i=1}^{d}\sum_{j=1}^{d}\mel{\olineu_{i}}{\left(\sqrt{\rho}\lambda_{y}\sqrt{\rho}\right)^{*}}{\olineu_{j}}V\ketbra{\olineu_{i}}{\olineu_{j}}V^{\dagger}\otimes \ketbra{y} = \sum_{y \in \CalY}\sum_{i=1}^{d}\sum_{j=1}^{d}V\ket{\olineu_{i}}\mel{\olineu_{i}}{\left(\sqrt{\rho}\lambda_{y}\sqrt{\rho}\right)^{*}}{\olineu_{j}}\bra{\olineu_{j}}V^{\dagger}\otimes \ketbra{y}  \nonumber\\
\label{Eqn:AllPurificationsWork5}
&=& \sum_{y \in \CalY}{V\left(\sqrt{\rho}\lambda_{y}\sqrt{\rho}\right)^{*}}V^{\dagger}\otimes \ketbra{y}
\nonumber
\end{eqnarray}
which follows from a standard sequence of equalities. The RHS of (\ref{Eqn:AllPurificationsWork1}) is therefore
\begin{eqnarray}
\label{Eqn:AllPurificationsWork6}
\lefteqn{\norm{(i_{Z}\otimes \ScrE^{\lambda})(\ketbra{\alpha_{\rho}}{\alpha_{\rho}}) - (i_{Z}\otimes \ScrE^{\theta})(\ketbra{\alpha_{\rho}}{\alpha_{\rho}})}_{1} = \norm{ \sum_{y \in \CalY}{V\left(\sqrt{\rho}\lambda_{y}\sqrt{\rho}\right)^{*}}V^{\dagger}\otimes \ketbra{y} - \sum_{y \in \CalY}{V\left(\sqrt{\rho}\theta_{y}\sqrt{\rho}\right)^{*}}V^{\dagger}\otimes \ketbra{y}}_{1}}\nonumber\\
\label{Eqn:AllPurificationsWork7}
&&= \sum_{y \in \CalY} \norm{ {V\left(\sqrt{\rho}\lambda_{y}\sqrt{\rho}\right)^{*}}V^{\dagger} - {V\left(\sqrt{\rho}\theta_{y}\sqrt{\rho}\right)^{*}}V^{\dagger}}_{1} = \sum_{y \in \CalY} \norm{ {\left(\sqrt{\rho}\lambda_{y}\sqrt{\rho}\right)^{*}} - {\left(\sqrt{\rho}\theta_{y}\sqrt{\rho}\right)^{*}}}_{1}= \sum_{y \in \CalY} \norm{ {\sqrt{\rho}\lambda_{y}\sqrt{\rho}} - {\sqrt{\rho}\theta_{y}\sqrt{\rho}}}_{1}\\
\label{Eqn:AllPurificationsWork8}
&&=\norm{(i_{X}\otimes \ScrE^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}}) - (i_{X}\otimes \ScrE^{\theta})(\ketbra{\phi_{\rho}}{\phi_{\rho}})}_{1},
\end{eqnarray}
where (\ref{Eqn:AllPurificationsWork7}) follows from trace norm being invariant under multiplication by isometries \cite[Prop.~9.1.4]{BkWilde_2017} and the fifth assertion of Lemma \ref{Lem:CanonicalBasisSimpleFacts}, while the last equality follows from the equalities in (\ref{Eqn:PurificationSimulationIsGood15}), (\ref{Eqn:PurificationSimulationIsGood16}).
\end{proof}
\section{Characterization of $\alphasim$ via CPTP Map $\SimulationCPTP$ : Proof of Lemma \ref{Lem:CharacterizeAlphasim}}
\label{AppSec:ProofCharacterizealphasim}
We shall evaluate $\SimulationCPTP(\ketbra{\phi_{\rho_{K}^{\otimes n}}}{\phi_{\rho_{K}^{\otimes n}}} )$, where $\SimulationCPTP\define (i_{X}^{n}\otimes\tr_{K}\otimes i_{\CalY^{n}})\circ(i_{X}^{ n}\otimes i_{\mathcal{H}_{K}}\otimes \mathscr{E}^{\Delta} )\circ (i_{X}^{ n}\otimes i_{\mathcal{H}_{K}}\otimes  \mathscr{E}^{\theta})$ and prove the desired equivalence. Let $\rho=\sum_{i=1}^{n}\gamma_{i}\ketbra{u_{i}}{u_{i}}$ be a spectral decomposition and
\begin{eqnarray}
\label{Eqn:RhokCanonicaPur}
\ket{\phi_{\rho_{K}^{\otimes n}}} = \sum_{i_{1}=1}^{d_{A}}\cdots \sum_{i_{n}=1}^{d_{A}}\sum_{\hatk=1}^{K}\frac{\sqrt{\gamma_{i_{1}}\cdots\gamma_{i_{n}}}}{\sqrt{K}}\ket{\olineu_{i_{1}}\otimes \cdots\otimes \olineu_{i_{n}}}\otimes\ket{\hatk}\otimes \ket{u_{i_{1}}\otimes \cdots\otimes u_{i_{n}}}\otimes\ket{\hatk}\end{eqnarray}
be the canonical purification of $\rho_{K} = \frac{1}{K}\sum_{k=1}^{K}\rho^{\otimes n}\otimes \ketbra{k}{k}$. Since $\theta \define \{ \overline{\theta}_{k,m}\define \theta_{k,m}\otimes \ketbra{k}{k} : (k,m) \in [K]\times [M]\} \in \ScrM(\CalHA^{\otimes n} \otimes \CalH_{K},[K]\times [M])$, we have
\begin{eqnarray}
\label{Eqn:CharacAlphaSimFirstCPTP1}
\lefteqn{\!\!\!\!\!\!\!\!\alpha_{\mbox{\tiny S}1}\define (i_{X}^{ n}\!\otimes\! i_{\mathcal{H}_{K}}\!\otimes\!  \mathscr{E}^{\theta})(\ketbra{\phi_{\rho_{K}^{\otimes n}}}{\phi_{\rho_{K}^{\otimes n}}} ) = \sum_{i_{1}=1}^{d_{A}}\sum_{j_{1}=1}^{d_{A}}\!\cdots\! \sum_{i_{n}=1}^{d_{A}}\sum_{j_{n}=1}^{d_{A}}\sum_{\hatk=1}^{K} \sum_{\hatl=1}^{K} \frac{\sqrt{\gamma_{i_{1}}\gamma_{j_{1}}\!\cdots\!\gamma_{i_{n}}\gamma_{j_{n}} }}{K}\ketbra{\olineu_{i_{1}} \otimes \!\cdots\!\otimes \olineu_{i_{n}}}{\olineu_{j_{1}}\otimes \cdots\otimes \olineu_{j_{n}}}}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP2}
&&\otimes\ketbra{\hatk}{\hatl}\otimes \sum_{k=1}^{K}\sum_{m=1}^{m}\tr(\theta_{k,m}\ketbra{u_{i_{1}} \otimes \cdots\otimes u_{i_{n}}}{u_{j_{1}}\otimes \cdots\otimes u_{j_{n}}}\otimes\ketbra{k}{k}\ketbra{\hatk}{\hatl})\ketbra{k}{k}\otimes \ketbra{m}{m}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP3}
\lefteqn{\!\!\!\!\!\!\!\!= \sum_{i_{1}=1}^{d_{A}}\sum_{j_{1}=1}^{d_{A}}\cdots \sum_{i_{n}=1}^{d_{A}}\sum_{j_{n}=1}^{d_{A}}\sum_{k=1}^{K}\sum_{m=1}^{m} \!\!\!\frac{\sqrt{\gamma_{i_{1}}\gamma_{j_{1}}\cdots\gamma_{i_{n}}\gamma_{j_{n}} }}{K}\mel{u_{j_{1}} \!\otimes\! \cdots\!\otimes\! u_{j_{n}}}{\theta_{k,m}}{u_{i_{1}}\otimes \cdots\otimes u_{i_{n}}}\ketbra{\olineu_{i_{1}} \otimes \cdots\otimes \olineu_{i_{n}}}{\olineu_{j_{1}}\otimes \cdots\otimes \olineu_{j_{n}}}}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP4}
&&\otimes\ketbra{k}{k}\otimes \ketbra{k}{k}\otimes \ketbra{m}{m}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP5}
\lefteqn{\!\!\!\!\!\!\!\!= \sum_{i_{1}=1}^{d_{A}}\sum_{j_{1}=1}^{d_{A}}\!\cdots\! \sum_{i_{n}=1}^{d_{A}}\sum_{j_{n}=1}^{d_{A}}\sum_{k=1}^{K}\sum_{m=1}^{m} \!\!\frac{\mel{\sqrt{\gamma_{j_{1}}}u_{j_{1}} \!\otimes \!\cdots\!\otimes \!\sqrt{\gamma_{j_{n}}}u_{j_{n}}}{\theta_{k,m}}{\sqrt{\gamma_{i_{1}}}u_{i_{1}}\!\otimes \!\cdots\!\otimes \sqrt{\gamma_{i_{n}}}u_{i_{n}}}}{K}\ketbra{\olineu_{i_{1}} \otimes \!\cdots\!\otimes \olineu_{i_{n}}}{\olineu_{j_{1}}\otimes \cdots\otimes \olineu_{j_{n}}}}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP6}
&&\otimes\ketbra{k}{k}\otimes \ketbra{k}{k}\otimes \ketbra{m}{m}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP7}
&&= \sum_{i_{1}=1}^{d_{A}}\sum_{j_{1}=1}^{d_{A}}\!\!\cdots\!\! \sum_{i_{n}=1}^{d_{A}}\sum_{j_{n}=1}^{d_{A}}\sum_{k=1}^{K}\sum_{m=1}^{m} \!\!\!\frac{\mel{u_{j_{1}} \otimes \!\cdots\!\otimes u_{j_{n}}}{\sqrt{\omega}\theta_{k,m}\sqrt{\omega}}{u_{i_{1}}\otimes \!\cdots\!\otimes u_{i_{n}}\!}}{K}\ketbra{\olineu_{i_{1}} \otimes \!\cdots\!\otimes \olineu_{i_{n}}}{\olineu_{j_{1}}\otimes \cdots\otimes \olineu_{j_{n}}}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP8}
&&\otimes\ketbra{k}{k}\otimes \ketbra{k}{k}\otimes \ketbra{m}{m}\\
\label{Eqn:CharacAlphaSimFirstCPTP9}
&&= \frac{1}{K}\sum_{k=1}^{K}\sum_{m=1}^{m} {\left(\sqrt{\omega}\theta_{k,m}\sqrt{\omega}\right)^{*}}
\otimes\ketbra{k}{k}\otimes \ketbra{k}{k}\otimes \ketbra{m}{m}\mbox{ and hence}\end{eqnarray}\begin{eqnarray}
\label{Eqn:CharacAlphaSimFirstCPTP10}
&&\alpha_{\mbox{\tiny S}2}\define (i_{X}^{ n}\otimes i_{\mathcal{H}_{K}}\otimes \mathscr{E}^{\Delta} )(\alpha_{\mbox{\tiny S}1}) = \frac{1}{K}\sum_{k=1}^{K}\sum_{m=1}^{m}\sum_{y^{n} \in \CalY^{n}} {\left(\sqrt{\omega}\theta_{k,m}\sqrt{\omega}\right)^{*}}
\otimes\ketbra{k}{k}\otimes \Delta_{y^{n}|k,m}\ketbra{y^{n}}{y^{n}} \mbox{ thus leading to }
\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP11}
&&\alphasim = (i_{X}^{n}\otimes\tr_{K}\otimes i_{\CalY^{n}})(\alpha_{\mbox{\tiny S}2}) = \frac{1}{K}\sum_{k=1}^{K}\sum_{m=1}^{m}\sum_{y^{n} \in \CalY^{n}} {\left(\sqrt{\omega}\theta_{k,m}\sqrt{\omega}\right)^{*}} \otimes \Delta_{y^{n}|k,m}\ketbra{y^{n}}{y^{n}}\nonumber\\
\label{Eqn:CharacAlphaSimFirstCPTP12}
&&= \sum_{y^{n} \in \CalY^{n}} {\left(\sqrt{\omega}\left\{\frac{1}{K}\sum_{k=1}^{K}\sum_{m=1}^{m} \Delta_{y^{n}|k,m}\theta_{k,m}\right\}\sqrt{\omega}\right)^{*}} \otimes \ketbra{y^{n}}{y^{n}} = (i_{X} \otimes \ScrE^{\Delta\circ\theta_{e}})(\ketbra{\phi_{\omega}}{\phi_{\omega}})
\end{eqnarray}
where we have used the above stated spectral decomposition for $\rho$ and $\omega$ in (\ref{Eqn:CharacAlphaSimFirstCPTP8}), the fact stated in Part 4 of Lemma ~\ref{Lem:CanonicalBasisSimpleFacts} to arrive at (\ref{Eqn:CharacAlphaSimFirstCPTP9}), and the last equality follows from the fact that $\Delta_{y^{n}|k,m},K$ are real valued scalars and the definition of $\Delta \circ \theta_{e}$ in (\ref{Eqn:EffectiveSimPOVM}) associated with the simulation protocol in question.

\section{Equivalence of Formulations}
\label{AppSec:EquivalentFormulation}
\subsection{Alternate Problem Statement}
\label{SubSec:ProblemStatement}
In this appendix, we shall justify the formulation stated in Sec.~\ref{SubSec:ProblemDescription}. Specifically, we begin with an alternate formulation in Defn.~\ref{Defn:EpsilonSimulationOn} and prove equivalence of the same.
\begin{definition}
\label{Defn:EpsilonSimulationOn}
Let $\rho \in \CalD(\CalHA)$, $\lambda_{\CalY} = \{\lambda_{y}:y \in \CalY\} \in \ScrM(\CalHA,\CalY)$, $\theta_{\CalY} = \{\theta_{y}:y \in \CalY\} \in \ScrM(\CalHA,\CalY)$ be POVMs and $\eta >0$. We say $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on $\rho$ if
\begin{eqnarray}
\sum_{k \in \CalK}\sum_{y \in \CalY}|p_{K}(k)\tr(\lambda_{y}\sigma_{k}) - p_{K}(k)\tr(\theta_{y}\sigma_{k})| \leq \eta
\nonumber
\end{eqnarray}
for every ensemble $(\sigma_{k},p_{K},\CalK)$ with average $\rho$.
\end{definition}
In order to simulate a POVM $\lambda_{\CalY}$ on $\rho$, one can utilize common randomness that is independent of the quantum system and available at both encoder and decoder. A \textit{simulation protocol}, defined in the following, formalizes the components involved that make up a POVM simulation protocol that can exploit $C$ bits/measurement of common randomness to simulate a target POVM.
\begin{definition}
\label{Defn:POVMSmlProtocol}
A simulation protocol $(n,C,R,\theta,\Delta)$ for $\lambda_{\CalY}$ consists of
\begin{enumerate}
\item index sets $[K]$, $[M]$, where $K\define \lceil2^{nC} \rceil$, $M \define \lceil 2^{nR} \rceil$,
\item a collection of $K$ POVMs $\theta_{k} = \{ \theta_{k,m} \in \CalP(\CalHA^{\otimes n}):m \in [M]\} \in \ScrM(\CalHA^{\otimes n},\{k\}\times[M])$ for $k \in [K]$, and the associated POVM $\theta \define \{ \overline{\theta}_{k,m}\define \theta_{k,m}\otimes \ketbra{k}{k} : (k,m) \in [K]\times [M]\} \in \ScrM(\CalHA^{\otimes n} \otimes \CalH_{K},[K]\times [M])$, where $\CalH_{\CalK} = \span\{ \ket{k}: k \in \CalK\}$ satisfies $\braket{\hatk}{k}=\delta_{\hatk k}$,
\item POVM $\Delta_{\CalY^{n}} = \{\Delta_{y^{n}}\in \CalP(\CalH_{\CalK}\otimes \CalH_{\CalM}) : y^{n} \in \CalY^{n}\} \in \ScrM(\CalH_{\CalK} \otimes \CalH_{\CalM},\CalY^{n})$ where $\CalH_{\CalM} = \span\{ \ket{m}: m \in \CalM\}$ satisfies $\braket{\hatm}{m}=\delta_{\hatm m}$ as indicated by our notation, and $\Delta_{y^{n}} = \sum_{(k,m) \in [K]\times [M]}\Delta_{y^{n}|k,m}\ketbra{k}{k}\otimes \ketbra{m}{m}$ for $y^{n} \in \CalY^{n}$, and $(\Delta_{y^{n}|k,m} :(k,m,y^{n}) \in [K] \times [M] \times \CalY^{n})$ is a stochastic matrix, i.e., $\Delta_{y^{n}|k,m} \geq 0$ and $\sum_{y^{n} \in \CalY^{n}}\Delta_{y^{n}|k,m} =1$ for $(k,m)\in [K]\times [M]$.\end{enumerate}
For such a simulation protocol $(n,C,R,\theta,\Delta)$, we let $\theta_{e} = \left\{ \frac{\theta_{k,m}}{K}  \in \CalP(\CalH^{\otimes n}): (k,m) \in [K]\times [M]\right\} \in \ScrM(\CalH^{\otimes n},[K]\times [M])$ and
\begin{eqnarray}
\label{Eqn:EffectiveSimPOVM}
\Delta\circ\theta_{e} \define \left\{ \frac{1}{K}\sum_{k \in [K]}\sum_{m \in [M]}\Delta_{y^{n}|k,m}\theta_{k,m} \in \CalP(\CalHA^{\otimes n}): y^{n}\in\CalY^{n}\right\} \in \ScrM(\CalHA^{\otimes n},\CalY^{n}).
\end{eqnarray}
A sequence $(n,C,R,\theta,\Delta): n\geq 1$ of simulation protocols is said to have a communication cost $(C,R)$.
\end{definition}
The notations $K\define \lceil2^{nC} \rceil$, $M \define \lceil 2^{nR} \rceil$ suppress the dependence of $K,M$ on $n$. This abuse of notation reduces clutter. Morever, since we focus throughout on a generic $n$, this abuse is inconsequential.
\begin{definition}
A sequence of simulation protocols $(n,C,R,\theta,\Delta): n\geq 1$ simulates $\lambda_{\CalY}$ on $\rho \in \CalD(\CalHA)$ if for every $\eta > 0$, there exists $N(\eta) \in \naturals$ such that for all $n\geq N(\eta)$, the POVM $\Delta\circ\theta$ $\eta-$simulates $\lambda_{\CalY^{n}}$ on $\rho^{\otimes n}$. POVM $\lambda_{\mathcal{Y}}$ on $\rho$ can be simulated at a (communication) cost $(C,R)$ if there exists a sequence of simulation protocols $(n,C,R,\theta,\Delta): n\geq 1$ that simulates $\lambda_{\CalY}$ on $\rho \in \CalD(\CalHA)$.

\end{definition}
In this article, our goal is to characterize the set of all communication costs that permit simulation of $\lambda_{\CalY}$ on $\rho$. Specifically, we are interested in characterizing the set
\begin{eqnarray}
\label{Eqn:CommunicationCosts}
\mathscr{I}(\rho,\lambda_{\CalY}) = \cl\left\{\!\!\!\begin{array}{lc} (C,R) \in [0,\infty): &\mbox{there exists a sequence of simulation protocols }(n,C,R,\theta,\Delta): n\geq 1\mbox{ that }\\&\mbox{simulates }\lambda_{\CalY}\mbox{ on }\rho \in \CalD(\CalHA) \end{array}\!\!\!\right\}.
\nonumber
\end{eqnarray}
where $\cl(\cdot)$ denotes the closure of the set. In the following, we recall an equivalent formulation involving purifications.

\subsection{Equivalent Formulation via Purifications}
\label{SubSec:EqFormviaPurifications}
We provide a formulation of the above problem statement in terms of purifications of the quantum state in question. As we shall see in the subsequent lemma, these formulations are equivalent.

\begin{definition}
\label{Defn:POVMSimViaPurfications}
Let $\rho \in \CalD(\CalHA)$, $\lambda_{\CalY} = \{\lambda_{y}:y \in \CalY\} \in \ScrM(\CalHA,\CalY)$, $\theta_{\CalY} = \{\theta_{y}:y \in \CalY\} \in \ScrM(\CalHA,\CalY)$ be POVMs and $\eta >0$. We say $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on purifications of $\rho$ if for any purification $\ket{\phi_{\rho}} \in \CalH_{X}\otimes\CalHA$ of $\rho\in \CalD(\CalHA)$, we have
\begin{eqnarray}
\label{Eqn:DefnPurificationSimulation}
\norm{(i_{X}\otimes \ScrE^{\lambda})(\ketbra{\phi_{\rho}}{\phi_{\rho}}) - (i_{X}\otimes \ScrE^{\theta})(\ketbra{\phi_{\rho}}{\phi_{\rho}})}_{1} \leq \eta.
\end{eqnarray}
\end{definition}

\begin{lemma}
\label{Lem:PurificationSimIsEquivalent}
Let $\rho \in \CalD(\CalHA)$, $\lambda_{\CalY} = \{\lambda_{y}:y \in \CalY\} \in \ScrM(\CalHA,\CalY)$, $\theta_{\CalY} = \{\theta_{y}:y \in \CalY\} \in \ScrM(\CalHA,\CalY)$ be POVMs and $\eta >0$. $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on $\rho$ if and only if $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on purifications of $\rho$.
\end{lemma}
\begin{proof}
We provide a proof in this article only for completeness. Our proof consists of two steps. In the first step, provided in Lemma \ref{Lem:AllPurificationsWork} and its proof, we prove that the trace distance on the LHS of (\ref{Eqn:DefnPurificationSimulation}) is invariant with the choice of purification. Proof of Lemma \ref{Lem:AllPurificationsWork} leverages the fact that any two purifications are related via an isometry acting on the purifying system and the invariance of trace norm under multiplication by isometries. This enables us focus on any chosen purification. We thus focus on a chosen purification $\ket{\phi_{\rho}}$, henceforth referred to as the canonical purification, that plays a central role throughout this article. This purification facilitates simple uncluttered calculations and upper bounding of associated trace distances. In Lemma \ref{Lem:PurificationSimulation} and its proof, we prove that if $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on purification $\ket{\phi_{\rho}}$ of $\rho$, then $\theta_{\CalY}$ $\eta-$simulates $\lambda_{\CalY}$ on $\rho$.
\end{proof}

As stated in the above proof, the canonical purification will play an important role throughout this article. We introduce the same in the context of a generic state $\sigma \in \CalD(\CalHA)$. The following notations and conventions are adopted throughout the rest of this article.

From Lemma \ref{Lem:PurificationSimIsEquivalent}, we conclude that to prove $(C,R) \in \ScrI(\rho,\lambda_{\CalY})$, it suffices to identify for every $\eta > 0$, a sequence $(n,C+\eta,R+\eta,\theta,\Delta): n \geq 1$ of simulation protocols for which
\begin{eqnarray}
\label{Eqn:TheStatementToProve}
\norm{ \alphaorig- \alphasim}_{1} \leq \exp\{-nf(\eta)\}\mbox{ where }\alphaorig \define (i_{X^{n}}\otimes \ScrE^{\lambda_{\CalY^{n}}})(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}}),\mbox{ and } \alphasim \define (i_{X^{n}}\otimes \ScrE^{\Delta\circ\theta_{e}})(\ketbra{\phi_{\rho^{\otimes n}}}{\phi_{\rho^{\otimes n}}}).
\end{eqnarray}
for some positive valued function $f:(0,\infty)\rightarrow (0,\infty)$. In the following, we characterize $\alphasim$ via an alternate evolution and employ the same in our proof.

\begin{lemma}
\label{Lem:CharacterizeAlphasim}
Consider a simulation protocol $(n,C,R,\theta,\Delta)$ for $\lambda_{\CalY} \in \ScrM(\CalHA,\CalY)$ and the associated components as in Defn.~\ref{Defn:POVMSmlProtocol}. Let $\rho_{K} \define \frac{1}{K}\sum_{k=1}^{K}\rho^{\otimes n} \otimes \ketbra{k}{k}$. Then $\alphasim$ defined in (\ref{Eqn:TheStatementToProve}) is also characterized as
\begin{eqnarray}
\label{Eqn:CharacterizeAlphasim}
\alphasim =    \SimulationCPTP(\ketbra{\phi_{\rho_{K}^{\otimes n}}}{\phi_{\rho_{K}^{\otimes n}}} ),\mbox{ where }
\SimulationCPTP\define (i_{X}^{n}\otimes\tr_{K}\otimes i_{\CalY^{n}})\circ(i_{X}^{ n}\otimes i_{\mathcal{H}_{K}}\otimes \mathscr{E}^{\Delta} )\circ (i_{X}^{ n}\otimes i_{\mathcal{H}_{K}}\otimes  \mathscr{E}^{\theta}).
\end{eqnarray}
If there exists, for every $\eta > 0$, a sequence of simulation protocols $(n,C+\eta,R+\eta,\theta,\Delta) : n \geq 1$ and some positive valued function $f:(0,\infty)\rightarrow (0,\infty)$ for which
$\norm{ \alphaorig- \alphasim}_{1} \leq \exp\{-nf(\eta)\}$ where $\alphaorig, \alphasim$ is as defined in (\ref{Eqn:TheStatementToProve}), (\ref{Eqn:CharacterizeAlphasim}) respectively, then $(C,R) \in \ScrI(\rho,\lambda_{\CalY})$.
\end{lemma}
A proof of (\ref{Eqn:CharacterizeAlphasim}) is provided in Appendix \ref{AppSec:ProofCharacterizealphasim}. The proof of the last statement follows from our earlier discussion and (\ref{Eqn:TheStatementToProve}). Our proof will revolve around establishing the above stated sufficient conditions for a specifically designed simulation protocol.

\bibliographystyle{IEEEtran}
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@rmstyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand\BIBentrySTDinterwordspacing{\spaceskip=0pt\relax}
\providecommand\BIBentryALTinterwordstretchfactor{4}
\providecommand\BIBentryALTinterwordspacing{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
\fontdimen4\font\relax}
\providecommand\BIBforeignlanguage[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi

[1]
A.~Winter, ``‘‘{E}xtrinsic’’and ‘‘{I}ntrinsic’’ {D}ata in
{Q}uantum {M}easurements: {A}symptotic {C}onvex {D}ecomposition of {P}ositive
{O}perator {V}alued {M}easures,'' \emph{Communications in mathematical
physics}, vol. 244, no.~1, pp. 157--185, 2004.

[2]
R.~Ahlswede and A.~Winter, ``Strong converse for identification via quantum
channels,'' \emph{IEEE Transactions on Information Theory}, vol.~48, no.~3,
pp. 569--579, 2002.

[3]
H.~J. {Groenewold}, ``{A Problem of Information Gain by Quantal
Measurements},'' \emph{International Journal of Theoretical Physics}, vol.~4,
no.~5, pp. 327--338, Sept. 1971.

[4]
\BIBentryALTinterwordspacing
S.~Massar and S.~Popescu, ``Amount of information obtained by a quantum
measurement,'' \emph{Phys. Rev. A}, vol.~61, p. 062303, May 2000. [Online].
Available: \url{https://link.aps.org/doi/10.1103/PhysRevA.61.062303}
\BIBentrySTDinterwordspacing

[5]
\BIBentryALTinterwordspacing
A.~Winter and S.~Massar, ``Compression of quantum-measurement operations,''
\emph{Phys. Rev. A}, vol.~64, p. 012311, Jun 2001. [Online]. Available:
\url{https://link.aps.org/doi/10.1103/PhysRevA.64.012311}
\BIBentrySTDinterwordspacing

[6]
M.~Berta, J.~Renes, and M.~Wilde, ``Identifying the information gain of a
quantum measurement,'' \emph{Information Theory, IEEE Transactions on},
vol.~60, 01 2013.

[7]
M.~M. Wilde, P.~Hayden, F.~Buscemi, and M.-H. Hsieh, ``The
information-theoretic costs of simulating quantum measurements,''
\emph{Journal of Physics A: Mathematical and Theoretical}, vol.~45, no.~45,
p. 453001, 2012.

[8]
M.~Heidari, T.~A. Atif, and S.~Sandeep~Pradhan, ``Faithful simulation of
distributed quantum measurements with applications in distributed
rate-distortion theory,'' in \emph{2019 IEEE International Symposium on
Information Theory (ISIT)}, 2019, pp. 1162--1166.

[9]
T.~A. Atif, M.~Heidari, and S.~S. Pradhan, ``Faithful simulation of distributed
quantum measurements with applications in distributed rate-distortion
theory,'' 2020.

[10]
T.~A. Atif and S.~S. Pradhan, ``Distributed quantum faithful simulation and
function computation using algebraic structured measurements,'' 2021.

[11]
M.~M. Wilde, \emph{Quantum Information Theory}, 2nd~ed.\hskip 1em plus 0.5em
minus 0.4em\relax Cambridge University Press, 2017.

[12]
E.~Carlen, ``Trace inequalities and quantum entropy: An introductory course,''
vol. 529, 01 2010.

[13]
P.~W. Cuff, ``Communication in networks for coordinating behavior,'' Ph.D.
dissertation, Stanford, CA, USA, 2009.

[14]
A.~S. Holevo, \emph{Quantum Systems, Channels, Information}, 2nd~ed.\hskip 1em
plus 0.5em minus 0.4em\relax De Gruyter, 2019.

[15]
R.~Bhatia, \emph{Matrix Analysis}, 1st~ed.\hskip 1em plus 0.5em minus
0.4em\relax Springer, 1997.

\end{thebibliography}

\end{document}