# Incompressibility of classical distributions

Anurag Anshu Debbie Leung Dave Touchette IQC and C&O, University of Waterloo,
Perimeter InstituteIQC and C&O, University of Waterloo, Perimeter InstituteIQ
and CS, Universite de Sherbrooke, IQC and C&O, University of Waterloo,
Perimeter Institute

###### Abstract

In _blind_ compression of quantum states, a sender Alice is given a specimen
of a quantum state $\rho$ drawn from a known ensemble (but without knowing
what $\rho$ is), and she transmits sufficient quantum data to a receiver Bob
so that he can decode a near perfect specimen of $\rho$. For many such states
drawn iid from the ensemble, the asymptotically achievable rate is the number
of qubits required to be transmitted per state. The Holevo information is a
lower bound for the achievable rate, and is attained for pure state ensembles,
or in the related scenario of entanglement-assisted _visible_ compression of
mixed states wherein Alice knows what state is drawn.

In this paper, we prove a general, robust, lower bound on the achievable rate
for ensembles of classical states, which holds even in the least demanding
setting when Alice and Bob share free entanglement and a constant per-copy
error is allowed. We apply the bound to a specific ensemble of only two states
and prove a near-maximal separation between the best achievable rate and the
Holevo information for constant error. Since the states are _classical_ , the
observed incompressibility is not fundamentally quantum mechanical. We lower
bound the difference between the achievable rate and the Holevo information in
terms of quantitative limitations to clone the specimen or to distinguish the
two classical states.

##  1 Introduction

###  1.1 Blind quantum data compression and related scenarios

A central goal of information theory is to capture the ultimate rate of
transformation of resources. For example, we may want to minimize the
communication cost of a task, which is an optimization problem over a
potentially unbounded number of possible communication protocols. In some
special cases, the best communication cost is given by a simple enough
information theoretic quantity that can be computed. For example, this has
been achieved in Shannon’s source coding theorem (data compression) and noisy
channel coding [1] and some network analogues [2]. Quantum information theory
shares the same goal, and similar understanding has been achieved in quantum
noisy coding theorem, albeit with regularization issues in many scenarios.

This paper focuses on the problem of quantum data compression, which can be
stated as follows. Fix an ensemble $\\{p(x),\rho^{x}_{C}\\}$ of quantum states
$\rho^{x}_{C}$ on a register $C$, and define the associated state

$\rho_{XC}=\sum_{x}p(x)|x\rangle\langle x|_{X}\otimes\rho^{x}_{C}\,.$ (1)

In the aforementioned ensemble, each state $\rho^{x}_{C}$ is labeled by a
classical index $x$ recorded in the register $X$ and occurring with
probability $p(x)$. Suppose a Referee prepares $n$ copies of the above state:

$\sum_{x_{1}x_{2}\cdots x_{n}}p(x_{1})p(x_{2})\cdots
p(x_{n})\;|x_{1}\rangle\langle x_{1}|_{X_{1}}\\!\otimes|x_{2}\rangle\langle
x_{2}|_{X_{2}}\\!\otimes\cdots\otimes|x_{n}\rangle\langle
x_{n}|_{X_{n}}\otimes\rho^{x_{1}}_{C_{1}}\otimes\rho^{x_{2}}_{C_{2}}\otimes\cdots\otimes\rho^{x_{n}}_{C_{n}},$
(2)

where each $C_{i}\equiv C$. The Referee transmits $C_{1}\cdots C_{n}$ to
Alice. Alice is allowed to send some quantum data to Bob. Bob decodes and his
final output registers are $C_{1}^{\prime}\cdots C_{n}^{\prime}$. The goal is
that the final state of the Referee and Bob should be _close_ to the state in
(2), while minimizing the amount of data sent. A rate $r$ is achievable for
the compression if there is a family of protocols labeled by $n$ in which
Alice sends $nr$ qubits. There are many related but inequivalent scenarios for
quantum data compression.

  * •

In the _blind_ scenario (as described above), Alice does not have access to
the registers $X_{1}\cdots X_{n}$. She has a specimen of the states
$\rho^{x_{1}}\otimes\cdots\otimes\rho^{x_{n}}$ in $C_{1}\cdots C_{n}$, but she
does not known what they are in general. In contrast, in the _visible_
scenario, the Referee gives a copy of $X_{1}\cdots X_{n}$ to Alice so she
knows $x_{1}\cdots x_{n}$ (and in this case it is unnecessary to give her
$C_{1}\cdots C_{n}$).

  * •

In the unassisted model, Alice and Bob do not share any correlations. In other
scenarios, they may share classical randomness. In the entanglement-assisted
scenario, they may share any entangled state of their choice. Note that with
entanglement assistance, sending quantum or classical data are equivalent due
to teleportation [3] and superdense coding [4]. The rate in qubits is equal to
half of the rate in bits.

  * •

One has to specify the measure of proximity between the initial state (2) and
the final state held by the Referee and Bob. A more stringent definition of
error requires that the final state in $X_{1}\cdots X_{n}C_{1}^{\prime}\cdots
C_{n}^{\prime}$ be close to the original state in (2), in trace distance or in
fidelity. The error in this case is called “global.” A more relaxed definition
of error requires that for each $i$, the $i$-th output state in
$X_{i}C_{i}^{\prime}$ is close to the initial state in $X_{i}C_{i}$. The error
in this case is called “local.” For the asymptotic case, the error is
typically required to vanish as $n$ increases. Alternatively, one can consider
the one-shot scenario when $n=1$, but this scenario is out of the scope for
our paper. We will mention some one-shot results which have asymptotic
implications.

  * •

There is no limitation on the states $\rho^{x}_{C}$ in the ensemble in the
problem. There are several special cases of interest. One well-studied special
case is the “pure state case” in which all $\rho^{x}_{C}$ are pure. Another
case concerns ensembles of states that are commuting, in which case they can
be simultaneously diagonalized, and the $\rho^{x}_{C}$ correspond to classical
distributions.

We can summarize prior results as follows. The unassisted blind scenario for
pure state case was formulated in [5, 6, 7]. These pioneering works
established the quantum analogue of Shannon’s source coding theorem when the
ensemble $\\{p(x),|\rho^{x}\rangle\langle\rho^{x}|_{C}\\}$ consists only of
pure states, with the best achievable rate shown to be $\mathrm{S}(\rho_{C})$
qubits, where $\mathrm{S}(.)$ is the von-Neumann entropy [8] and
$\rho_{C}=\sum_{x}p(x)|\rho^{x}\rangle\langle\rho^{x}|_{C}$ is the average
state of the ensemble. If the states $|\rho^{x}\rangle_{C}$ are mutually
orthogonal, the problem reduces to Shannon’s source coding problem and
Schumacher’s protocol recovers Shannon’s result with rate being
$\mathrm{S}(\rho_{C})$ bits.

For a general ensemble $\\{p(x),\rho^{x}_{C}\\}$, the Holevo information is
defined as
$S\\!\left(\sum_{x}\\!p(x)\rho^{x}_{C}\right)-\sum_{x}\\!p(x)S\left(\rho^{x}_{C}\right)$,
and it is also the quantum mutual information
$\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$ between $X$ and $C$
evaluated on $\rho_{XC}$. It was independently shown by [9] and [10] that the
Holevo information is a lower bound for the achievable rate in the unassisted
scenarios for both visible and blind compression.

For unassisted compression of pure states, the above lower bound on the rate
is already attained by the protocol in the blind setting [5, 6, 7]. Thus the
visible scenario, with Alice’s knowledge of the state to be compressed,
surprisingly does not improve the rate. Furthermore, shared randomness does
not reduce the best achievable rate.

The situation is more complex for the compression of mixed quantum states. The
problem was considered as early as in [11] and formulated and studied in
detail in a large body of work [12, 13, 14, 15, 16, 17, 18, 19]. The rate
depends on whether the protocol is visible or blind, what kind of assistance
is available, under local or global error, and whether the ensemble is
classical or quantum, to be discussed as follows.

Visible compression of classical ensemble is relatively well understood, given
the assistance of shared randomness. The problem is equivalent to the
simulation of classical channels (associated to the classical Reverse Shannon
theorem). Authors in [20] and [13] independently showed that the Holevo
information is the achievable rate in bits under _global_ error criteria.
Winter [18] further showed that under the local error criteria, shared
randomness is not needed to achieve the Holevo information. It was also shown
in [18, Theorem 3] that the Holevo information is a lower bound even for
asymptotically non-vanishing global error. This is a robust feature of visible
compression: even a constant global error (for example $\frac{1}{3}$) requires
a rate at least equal to the Holevo information. Using rejection sampling, the
Holevo information was shown to be achievable in the asymptotic setting [21]
and one-shot with expected communication [22].

For the visible compression of quantum ensembles without any assistance,
Horodecki [12] showed that the qubit rate is given by a quantity defined via
extensions of the ensemble. Later, Hayashi [23] gave a simpler
characterization of the qubit rate in terms of the entanglement of
purification [24]. With entanglement assistance, protocols for the visible
compression have several guises. The first guise is remote state preparation
of entangled states between Alice and Bob, first formalized in [25] and solved
in [26] with qubit rate
$\frac{1}{2}\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$ (subsequently
reproduced from a one-shot approach in [27]). The second is via the rejection
sampling method and quantum substate theorem [28, 29] which gives a one-shot
protocol with asymptotic rate of
$\frac{1}{2}\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$ qubits. The
third guise is via the general scenario of the quantum Reverse Shannon theorem
[30] which also attains the optimal qubit rate of
$\frac{1}{2}\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$. The first
and third methods are entanglement optimal as well.

Finally, for blind compression of a mixed ensemble, the difference between the
rate of quantum communication and the Holevo information was termed
“information defect” by Horodecki [9]. Both [9] and [10] provided bounds on
the information defect without resolving whether it could be positive. In
[13], a classical ensemble was presented with an argument sketching the
positivity of its information defect. But the error criteria in their argument
was not made precise. Kramer and Savari [14] also showed a similar result with
an error criteria based on empirical distribution of the outputs. But this
error criteria does not match either the global or local criteria discussed
above. In a powerful series of results [15, 16, 17], Koashi and Imoto
characterized the optimal rates of quantum and classical communication, the
amount of entanglement required, and their tradeoffs in blind compression.
This was done by a decomposition of the ensemble of states, now colloquially
called the Koashi-Imoto decomposition. Their result requires that the local
error goes to zero in the asymptotic setting and leads to a large information
defect. An ensemble witnessing this separation consists of two equiprobable
commuting states [16], and its blind compression requires classical
communication at the rate of the entropy of the average state.

We motivate this study by asking if the above rate characterization holds for
non-vanishing error; mimicking the robust feature of visible compression
mentioned earlier. This is a first step towards chalking out the
“communication versus error” profile for blind compression and understanding
its strong converse rate. We observe that the Koashi-Imoto rate
characterization is sensitive to the amount of error. We highlight this using
an example in Appendix A, where we show that blind compression of any ensemble
of two commuting states $\\{\rho^{0}_{C},\rho^{1}_{C}\\}$ with local error
$\varepsilon$ can be achieved with unassisted rate of
$2\log\log\frac{d}{\varepsilon}+2\log\frac{1}{\varepsilon}+5$ bits ($d$ is the
dimension of register $C$ which is a constant independent of $n$). For
$\varepsilon\geq\frac{1}{\sqrt{d}}$, the achievable rate is substantially less
than the lower bound of $\log d$ given by the Koashi-Imoto rate
characterization for many pairs of commuting states. The general compression
rate, as a function of $\varepsilon$, therefore, remains unresolved.

Is there a coding scheme that can even further reduce the rate exhibited in
the aforementioned example for finite $\varepsilon$? For instance, could the
rate depend on the error as
$\mathcal{O}\left(\log\log\frac{1}{\varepsilon}\right)$, as in [25, 29, 22]
using rejection sampling? Much of this paper is devoted to showing the
contrary. We provide an example where the rate of
$\mathcal{O}\left(\log\frac{1}{\varepsilon}\right)$ is optimal for a suitable
finite choice of local error. For this ensemble, we show a large and robust
lower bound $(\log d)-7$ for the rate, while the Holevo information is less
than $1$. Thus compression of this ensemble does not reduce communication rate
in a significant manner relative to sending the whole register $C$. Note that
since our lower bound holds for local error, it also implies the same lower
bound for the global error. Furthermore, our lower bound applies to
entanglement-assisted protocols.

###  1.2 Main result, techniques and consequences

In this work, we show a near-maximal (for the dimension of the states)
separation between the achievable rate of _classical communication_ for
entanglement-assisted blind mixed state compression and the Holevo
information. As mentioned earlier, our separation holds for finite (non-
vanishing) local error. We establish this separation in two steps.

In the first step, we consider entanglement-assisted blind mixed state
compression of the $n$-copy state in (2), for ensembles of _classical_ states
$\rho^{x}_{C}$ that are diagonal. We obtain a _single-letter_ lower bound on
the _asymptotic_ achievable rate $R$:

$R\geq\min_{\mathcal{F}:C\rightarrow
CC^{\prime}}\left(\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}\right)+\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}-\varepsilon\log|X|-1,$
(3)

where $\rho$ is defined in (1), the map $\mathcal{F}$ takes $\rho_{XC}$ to
$\rho_{XCC^{\prime}}$ and satisfies the constraints

  1. 1.

$\mathrm{Tr}_{C}\mathcal{F}(\rho_{XC})\approx\rho_{XC^{\prime}}$,

  2. 2.

$\mathrm{Tr}_{C^{\prime}}\mathcal{F}(\rho_{XC})=\rho_{XC}$,

and the approximation in the first constraint is given by $\varepsilon$. Note
that despite a similarity in form between (3) and Lemma 3.1 in [14], our bound
is obtained under the local error condition (unlike the empirical error
condition of [14]). The expression $\min_{\mathcal{F}:C\rightarrow
CC^{\prime}}\left(\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}\right)$
approximates the difference between $R$ and the Holevo information
$\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$ in (3), with the
following noteworthy features:

  * •

If Alice knows $X$ (visible scenario or distinguishable $\rho^{x}_{C}$’s), the
expression vanishes which matches previous known bounds. Thus this expression
represents Alice’s lack of knowledge of the label $X$ of the given state. Our
strategy is to prove a large lower bound for the expression.

  * •

We can view $C$ as the register containing the state held by Alice, and
$C^{\prime}$ as the register $C^{\prime}$ containing the output state held by
Bob. The first constraint
$\mathrm{Tr}_{C}\mathcal{F}(\rho_{XC})\approx\rho_{XC^{\prime}}$ reflects the
correctness of the protocol: the state $\mathrm{Tr}_{C}\mathcal{F}(\rho_{XC})$
between Bob and the Referee (holding $X$) is close to the desired state
$\rho_{XC^{\prime}}$ (with $C$ replaced by $C^{\prime}$). The second
constraint $\mathrm{Tr}_{C^{\prime}}\mathcal{F}(\rho_{XC})=\rho_{XC}$ comes
from classicality of the ensemble, which allows Alice to retain a copy of the
classical value in register $C$.

  * •

In Section 3, we specialize to equiprobable ensembles of two states, and
convert the expression to two simpler lower bounds given in (10). The first
lower bound, (10)(c), is the expected distance (over $x$) between two joint
states shared by Alice and Bob. The first joint state is the output of the
protocol, and the second state consists of two independent copies of Alice’s
input state, one held by each of Alice and Bob. Thus, the compression rate is
lower bounded by the _inability_ to clone the states in the ensemble. The
second lower bound, (10)(f), is the gain in distinguishability between the
states for $x=0$ and $x=1$, if two copies of the states are available instead
of one copy. We also note that the lower bound on the communication rate,
after subtracting the Holevo information of the ensemble, is translated to
these quantities that hold even without locality constraints on Alice and Bob.

The lower bounds (10)(c) and (f) are not extensive. To obtain a large lower
bound on the expression $\min_{\mathcal{F}:C\rightarrow
CC^{\prime}}\left(\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}\right)$
limited only by the dimension, we choose an equiprobable ensemble of two
states $\rho^{0}_{C}$ and $\rho^{1}_{C}$, where the former represents the
uniform distribution and the latter the ‘staircase’ distribution; see Figure
1. We show that if the error is a small constant $\approx\frac{1}{|C|^{4}}$,
then the only strategy Alice can employ is to send the register $C$ to Bob.
For this, we view $\mathcal{F}$ as a transition matrix for probability
distributions and show that it must be close to the identity matrix. We obtain
the following.

######  Theorem 1.

The following holds for the ensemble of two equiprobable states
$\\{\rho^{0}_{C},\rho^{1}_{C}\\}$, where $|C|=d$, $\rho^{0}_{C}=I/d$,
$\rho^{1}_{C}$ is diagonal, with $(c,c)$-entry being $(d-c+1)/\eta$, and
$\eta=d(d+1)/2$. The achievable rate for entanglement-assisted blind
compression is at least $(\log d)-7$ bits, while the Holevo information
$\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$ is at most $1$. The
lower bound holds for both global and local errors of
$\varepsilon\approx\frac{1}{d^{4}}$, which is independent of the number of
instances $n$. Thus the information defect at non-vanishing local error can be
arbitrarily large, and near maximal for the dimension.

$p(c)$$\frac{1}{d}$$\frac{d}{\eta}$$\frac{1}{\eta}$$c\in[1,2,\ldots d]$ Figure
1: The two distributions in our example. The red line is the uniform
distribution and the blue line is the staircase distribution. Here, $d=|C|$
and $\eta=\frac{d(d+1)}{2}$.

Our proof highlights a ‘strong no-cloning principle’ in the classical setting.
To clarify, observe that Alice and Bob cannot transform (or clone)
$\rho^{x}_{C}\rightarrow\rho^{x}_{C}\otimes\rho^{x}_{C^{\prime}}$ without the
knowledge of $x$. This translates to the statement that
$\min_{\mathcal{F}:C\rightarrow
CC^{\prime}}\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}$
is bounded away from $0$ in (10)(c). Theorem 1 goes further to show that the
only way to produce the register $C^{\prime}$ creates a lot of correlation
between $C$ and $C^{\prime}$. This is akin to the situation in quantum no-
cloning; the operation
$|i\rangle_{C}\rightarrow|i\rangle_{C}|i\rangle_{C^{\prime}}$ leads to a large
correlation when applied to a state $\sum_{i}\alpha_{i}|i\rangle_{C}$ in
superposition.

###  1.3 Conclusion

In this work, we study the problem of blind compression of quantum data, in
the regime of finite error. Our inspiration comes from two sources. First is
the visible scenario, where the trade-off between global error and
communication rate is very well understood (providing a strong converse rate)
and the trade-off between local error and communication rate is relatively
well understood. Second is the Koashi-Imoto characterization, which gives the
optimal rate of communication as the error vanishes in the asymptotic limit
and hence shows a near maximal separation between the communication rate and
the Holevo information in the vanishing error regime. We observe that the
Koashi-Imoto characterization does not apply to the case of non-vanishing
(global or local) error. Our main result resolves this problem, showing a near
maximal separation of the rate from the Holevo information in the non-
vanishing local error regime. For this, we prove a new lower bound that is
based on a variant of the no-cloning theorem for classical distributions. Our
technical proof builds on an approximate version of the Birkoff-von Neumann
theorem.

An immediate question raised by our work is to understand the error vs
communication rate trade-off for the blind compression scenario, for the cases
of global and local errors. Furthermore, we ask if a strong converse rate
exists for the blind compression scenario when the global error is finite,
which is known to hold for the visible case. Finally, we highlight that our
lower bound does not entirely rely on the spatial separation between the
sender and the receiver, which leads to the question of further applicability
of our techniques to other problems.

##  2 Notations and information theoretic quantities used

###  2.1 Basic notions in quantum information theory

Throughout the paper, $\log$ is taken base 2. For a finite set $\mathcal{C}$,
a probability distribution is a function $p:\mathcal{C}\rightarrow[0,1]$
satisfying $\sum_{c\in\mathcal{C}}p(c)=1$. In this paper, we only consider
finite dimensional Hilbert spaces. Consider such a Hilbert space $\mathcal{H}$
endowed with an inner product $\langle\cdot,\cdot\rangle$. For an operator $X$
acting on $\mathcal{H}$, the Schatten-$1$ norm of $X$ is defined as
$\|X\|_{1}:=\mathrm{Tr}\sqrt{X^{\dagger}X}$ and the Schatten-$2$ norm is
defined as $\|X\|_{2}:=\sqrt{\mathrm{Tr}XX^{\dagger}}$. A quantum state is
represented by a density matrix $\rho$, which is a positive semi-definite
operator on $\mathcal{H}$ with trace equal to $1$. The quantum state $\rho$ is
pure if and only if its density matrix is rank $1$, in which case
$\rho=|\psi\rangle\langle\psi|$ for some unit vector
$|\psi\rangle\in\mathcal{H}$. Throughout the paper, we may use $\psi$ to
represent the quantum state and also the density matrix
$|\psi\rangle\langle\psi|$. Given a quantum state $\rho$ on $\mathcal{H}$, the
support of $\rho$, denoted $\text{supp}(\rho)$, is the subspace of
$\mathcal{H}$ spanned by all eigenvectors of $\rho$ with _positive_
eigenvalues.

A quantum register $A$ is associated with some Hilbert space
$\mathcal{H}_{A}$. Define $|A|:=\dim(\mathcal{H}_{A})$. Let $\mathcal{L}(A)$
represent the set of all linear operators on $\mathcal{H}_{A}$. We denote the
set of quantum states on the Hilbert space $\mathcal{H}_{A}$ by
$\mathcal{D}(A)$. The quantum state $\rho$ with subscript $A$ indicates
$\rho_{A}\in\mathcal{D}(A)$. If two registers $A,B$ are associated with
isomorphic Hilbert spaces (that is, of the same dimension), we write $A\equiv
B$. Two disjoint registers $A$ and $B$ combined, denoted as $AB$, is
associated with the tensor product Hilbert space
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. For two operators
$M_{1}\in\mathcal{L}(A)$ and $M_{2}\in\mathcal{L}(B)$, $M_{1}\otimes
M_{2}\in\mathcal{L}(AB)$ represents the tensor product (Kronecker product) of
$M_{1}$ and $M_{2}$. The identity operator on $\mathcal{H}_{A}$ (and its
associated register $A$) is denoted as $\mathrm{I}_{A}$.

For any operator $M_{AB}\in\mathcal{L}(AB)$, the partial trace on $A$ is
defined as:

$\mathrm{Tr}_{A}\,(M_{AB}):=\sum_{i}(\langle
i|\otimes\mathrm{I}_{B})\,M_{AB}\,(|i\rangle\otimes\mathrm{I}_{B}),$

where $\\{|i\rangle\\}_{i}$ is an orthonormal basis for the Hilbert space
$\mathcal{H}_{A}$. For a quantum state $\rho_{AB}\in\mathcal{D}(AB)$, we use
the shorthand

$\rho_{B}:=\mathrm{Tr}_{A}\,(\rho_{AB})$

and the quantum state $\rho_{B}\in\mathcal{D}(B)$ is referred to as the
marginal quantum state of $\rho_{AB}$. Unless otherwise stated, a missing
register from the subscript of a quantum state represents a partial trace over
that register.

A quantum state $\rho_{AB}$ is classical-quantum with $A$ being the classical
register, if it is of the form $\rho_{AB}=\sum_{a}p_{A}(a)|a\rangle\langle
a|\otimes\rho^{a}_{B}$, where $\\{|a\rangle\\}_{a}$ forms an orthonormal
basis, $\\{p_{A}(a)\\}_{a}$ is a probability distribution and
$\rho^{a}_{B}\in\mathcal{D}(B)$. The value $a$ stored in register $A$
identifies a corresponding quantum state $\rho^{a}_{B}$ on register $B$. This
convention allows a clear distinction between having a specimen of the state
$\rho^{a}_{B}$ (having system $B$) and knowing what it is (having system $A$).
If all $\rho^{a}_{B}$ are diagonal in the same basis, $\rho_{AB}$ is called
classical-classical or simply classical.

A quantum channel $\mathcal{E}:\mathcal{L}(A)\rightarrow\mathcal{L}(B)$ is a
completely positive and trace preserving (CPTP) linear map. (We sometimes just
call it a “map” in this paper.) In particular, it takes quantum states in
$\mathcal{D}(A)$ to the quantum states in $\mathcal{D}(B)$. A quantum
measurement (or instrument)
$\mathcal{N}:\mathcal{L}(A)\rightarrow\mathcal{L}(A^{\prime}C)$ is
characterized by a collection of operators
$\\{N_{c}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A^{\prime}}\\}$ that satisfy
$\sum_{c}N_{c}^{\dagger}N_{c}=\mathrm{I}_{A}$ and is given by

$\mathcal{N}(\rho_{A})=\sum_{c}|c\rangle\langle c|_{C}\otimes
N_{c}\rho_{A}N^{\dagger}_{c}.$

A unitary operator $U_{A}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A}$ is such
that $U_{A}^{\dagger}U_{A}=U_{A}U_{A}^{\dagger}=\mathrm{I}_{A}$.

###  2.2 List of quantum information theoretic quantities

We consider the following information theoretic quantities. All logarithms are
base $2$ and only normalized quantum states are considered in the definitions
below. Let $\varepsilon\in(0,1)$.

  1. 1.

Trace distance:. For $\rho_{A},\sigma_{A}\in\mathcal{D}(A)$,

$\Delta(\rho_{A},\sigma_{A}):=\frac{1}{2}\|\rho_{A}-\sigma_{A}\|_{1}.$

  2. 2.

Fidelity: For $\rho_{A},\sigma_{A}\in\mathcal{D}(A)$,

$\mathrm{F}(\rho_{A},\sigma_{A}):=\|\sqrt{\rho_{A}}\sqrt{\sigma_{A}}\|_{1}.$

  3. 3.

$\varepsilon$-ball: For $\rho_{A}\in\mathcal{D}(A)$,

$\mathcal{B}^{\varepsilon}\>\\!\\!\left(\rho_{A}\right):=\\{\rho^{\prime}_{A}\in\mathcal{D}(A)|~{}\Delta(\rho_{A},\rho^{\prime}_{A})\leq\varepsilon\\}.$

  4. 4.

Von Neumann entropy: ([8]) For $\rho_{A}\in\mathcal{D}(A)$,

$\mathrm{S}(A)_{\rho}:=-\mathrm{Tr}(\rho_{A}\log\rho_{A}).$

  5. 5.

Conditional entropy: For $\rho_{AB}\in\mathcal{D}(AB)$,

$\mathrm{S}\left(A|B\right)_{\rho}:=\mathrm{S}(AB)_{\rho}-\mathrm{S}(B)_{\rho}.$

  6. 6.

Relative entropy: ([31]) For $\rho_{A},\sigma_{A}\in\mathcal{D}(A)$ such that
$\text{supp}(\rho_{A})\subset\text{supp}(\sigma_{A})$,

$\mathrm{D}\>\\!\\!\left(\rho_{A}\middle\|\sigma_{A}\right):=\mathrm{Tr}(\rho_{A}\log\rho_{A})-\mathrm{Tr}(\rho_{A}\log\sigma_{A}).$

  7. 7.

Mutual information: For $\rho_{AB}\in\mathcal{D}(AB)$,

$\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!B\right)_{\rho}:=\mathrm{S}(A)_{\rho}+\mathrm{S}(B)_{\rho}-\mathrm{S}(AB)_{\rho}=\mathrm{D}\>\\!\\!\left(\rho_{AB}\middle\|\rho_{A}\otimes\rho_{B}\right).$

  8. 8.

Conditional mutual information: For $\rho_{ABC}\in\mathcal{D}(ABC)$,

$\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!B\>\\!\middle|\>\\!C\right)_{\rho}:=\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!BC\right)_{\rho}-\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!C\right)_{\rho}.$

###  2.3 Basic facts used in our proofs

######  Fact 1 (Triangle inequality for trace distance, [32], Chapter 9).

For quantum states $\rho,\sigma,\tau\in\mathcal{D}(A)$,

$\Delta(\rho,\sigma)\leq\Delta(\rho,\tau)+\Delta(\tau,\sigma).$

######  Fact 2 (Data-processing inequality, [33, 34]).

For the quantum states $\rho$, $\sigma\in\mathcal{D}(A)$,
$\theta\in\mathcal{D}(AC)$ and the quantum channel
$\mathcal{E}:\mathcal{L}(A)\rightarrow\mathcal{L}(B)$, it holds that

$\displaystyle\Delta(\mathcal{E}(\rho),\mathcal{E}(\sigma))$
$\displaystyle\leq\Delta(\rho,\sigma),$
$\displaystyle\mathrm{D}\>\\!\\!\left(\rho\middle\|\sigma\right)$
$\displaystyle\geq\mathrm{D}\>\\!\\!\left(\mathcal{E}(\rho)\middle\|\mathcal{E}(\sigma)\right),$
$\displaystyle\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!C\right)_{\theta}$
$\displaystyle\geq\mathrm{I}\>\\!\\!\left(B\>\\!:\>\\!C\right)_{\mathcal{E}(\theta)}.$

######  Fact 3 (Pinsker’s inequality, [35]).

For the quantum states $\rho,\sigma\in\mathcal{D}(A)$,

$\Delta(\rho,\sigma)^{2}\leq\frac{1}{2}\mathrm{D}\>\\!\\!\left(\rho\middle\|\sigma\right).$

######  Fact 4 (Dimension bound).

For the quantum state $\rho_{XAB}$, with classical register $X$, it holds that

$\displaystyle\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!X\>\\!\middle|\>\\!B\right)_{\rho}$
$\displaystyle\leq\log|X|.$

######  Fact 5 (Alicki-Fannes-Winter inequality, [36, 37]).

For quantum-classical states $\rho_{AB}$ and $\sigma_{AB}$ satisfying
$\rho_{B}=\sigma_{B}$,

$|\mathrm{S}\left(A|B\right)_{\rho}-\mathrm{S}\left(A|B\right)_{\sigma}|\leq\Delta\left(\rho_{AB},\sigma_{AB}\right)\cdot\log|A|+1,$
$|\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!B\right)_{\rho}-\mathrm{I}\>\\!\\!\left(A\>\\!:\>\\!B\right)_{\sigma}|\leq\Delta\left(\rho_{AB},\sigma_{AB}\right)\cdot\log|B|+1.$

######  Fact 6 (Fano’s inequality, [38]).

For any classical state
$\rho_{AA^{\prime}}=\sum_{a,a^{\prime}}p_{AA^{\prime}}(a,a^{\prime})|a,a^{\prime}\rangle\langle
a,a^{\prime}|$, with $p_{AA^{\prime}}$ a probability distribution, it holds
that

$\mathrm{S}\left(A|A^{\prime}\right)_{\rho}\leq 1+\Pr[A\neq
A^{\prime}]\log|A|.$

Note that we have stated weaker versions of Alicki-Fannes-Winter inequality
and Fano’s inequality that simplify the expressions in our results.

##  3 Lower bound on entanglement-assisted blind distribution compression

For our lower bound on the compression rate, we focus on ensembles of
_classical_ states (these can be simultaneously diagonalized). We will
henceforth refer to them as distributions. We begin with a formal definition
of our task.

######  Definition 1 (Entanglement-assisted blind distribution compression).

Consider an ensemble $\\{p(x),\rho^{x}_{C}\\}$ where all $\rho^{x}_{C}$’s are
diagonal. Let $\rho_{XC}$ be as defined in (1). Let $\varepsilon\in(0,1)$ be
an error parameter and $n\in\mathbb{N}$. Let the initial joint state between
the Referee and Alice be
$\rho_{X_{1}C_{1}}\otimes\rho_{X_{2}C_{2}}\otimes\ldots\otimes\rho_{X_{n}C_{n}}$,
with the Referee holding registers $X_{1},X_{2},\ldots,X_{n}$ (each
$X_{i}\equiv X$) and Alice holding registers $C_{1},C_{2},\ldots,C_{n}$ (each
$C_{i}\equiv C$). Alice and Bob share entanglement
$|\theta\rangle_{E_{A}E_{B}}$, where $E_{A}$ is with Alice and $E_{B}$ is with
Bob. An $(n,R,\varepsilon)$\- entanglement-assisted blind distribution
compression protocol is as follows. Alice applies an encoding map
$\mathcal{E}:C_{1}C_{2}\ldots C_{n}E_{A}\rightarrow C_{1}C_{2}\ldots C_{n}M$,
where $M$ is a classical register of size $2^{nR}$. She communicates $M$ to
Bob (so the number of bits communicated in the protocol is $nR=\log|M|$).
After receiving $M$, Bob applies a decoding map $\mathcal{D}:ME_{B}\rightarrow
C^{\prime}_{1}C^{\prime}_{2}\ldots C^{\prime}_{n}$. Here, each
$C^{\prime}_{i}\equiv C$. It is required that

$\Delta\left(\mathrm{Tr}_{C_{1}\ldots
C_{n}}\circ\mathcal{D}\circ\mathcal{E}\left(\rho_{X_{1}C_{1}}\otimes\ldots\otimes\rho_{X_{n}C_{n}}\otimes\theta_{E_{A}E_{B}}\right),\rho_{X_{1}C^{\prime}_{1}}\otimes\ldots\otimes\rho_{X_{n}C^{\prime}_{n}}\right)\leq\varepsilon.$
(4)

The above definition involves a global error for the compression. Our lower
bounds apply also to the more relaxed setting of the local error model:

$\forall_{i}\;\Delta\left(\mathrm{Tr}_{C^{\prime}_{1}\ldots
C^{\prime}_{i-1}C^{\prime}_{i+1}\ldots C^{\prime}_{n}C_{1}\ldots
C_{n}}\circ\mathcal{D}\circ\mathcal{E}\left(\rho_{X_{1}C_{1}}\otimes\ldots\otimes\rho_{X_{n}C_{n}}\otimes\theta_{E_{A}E_{B}}\right),\rho_{X_{i}C^{\prime}_{i}}\right)\leq\varepsilon.$
(5)

Note that the definition uses classical communication, which is equivalent to
quantum communication up to a factor of $2$ when entanglement is free.

Since the ensemble is classical, Alice can always retain the information in
the registers $C_{1},C_{2},\ldots,C_{n}$, so, without loss of generality, we
assume the following equality throughout the discussion.

$\mathrm{Tr}_{M}\left(\mathcal{E}\left(\rho_{X_{1}C_{1}}\otimes\rho_{X_{2}C_{2}}\otimes\ldots\otimes\rho_{X_{n}C_{n}}\otimes\theta_{E_{A}}\right)\right)=\rho_{X_{1}C_{1}}\otimes\rho_{X_{2}C_{2}}\otimes\ldots\otimes\rho_{X_{n}C_{n}}.$
(6)

The following theorem shows a lower bound on the rate of communication $R$
required for the task.

######  Theorem 2.

Let $\rho_{XC}$ be as defined in Definition 1, $n$ a natural number, and
$\varepsilon\in(0,1)$. For any $(n,R,\varepsilon)$\- entanglement-assisted
blind distribution compression, it holds that

$R\;\geq\min_{\mathcal{F}:C\rightarrow
CC^{\prime}}\left(\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}+\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}\right)-\varepsilon\log|X|-1,$

where the map $\mathcal{F}$ must satisfy
$\Delta\left(\mathrm{Tr}_{C}\left(\mathcal{F}(\rho_{XC})\right),\rho_{XC^{\prime}}\right)\leq\varepsilon$
and $\mathrm{Tr}_{C^{\prime}}\mathcal{F}(\rho_{XC})=\rho_{XC}$.

###### Proof.

For brevity, set $\textbf{X}^{n}=X_{1}X_{2}\ldots X_{n}$,
$\textbf{C}^{n}=C_{1}C_{2}\ldots C_{n}$ and $\textbf{C}^{\prime
n}=C^{\prime}_{1}C^{\prime}_{2}\ldots C^{\prime}_{n}$. Let
$\sigma_{\textbf{X}^{n}\textbf{C}^{n}ME_{B}}$ be the state after Alice’s
encoding, and $\tau_{\textbf{X}^{n}\textbf{C}^{n}\textbf{C}^{\prime n}}$ be
the final quantum state at the end of the protocol. Observe that

$nR\;=\;\log|M|\;\geq\;\mathrm{I}\>\\!\\!\left(\textbf{X}^{n}\textbf{C}^{n}\>\\!:\>\\!M\>\\!\middle|\>\\!E_{B}\right)_{\sigma}\;\overset{(a)}{=}\;\mathrm{I}\>\\!\\!\left(\textbf{X}^{n}\textbf{C}^{n}\>\\!:\>\\!ME_{B}\right)_{\sigma}\;\overset{(b)}{\geq}\;\mathrm{I}\>\\!\\!\left(\textbf{X}^{n}\textbf{C}^{n}\>\\!:\>\\!\textbf{C}^{\prime
n}\right)_{\tau}.$ (7)

The equality $(a)$ in (7) follows from the fact that
$\mathrm{I}\>\\!\\!\left(\textbf{X}^{n}\textbf{C}^{n}\>\\!:\>\\!E_{B}\right)_{\sigma}=0$.
We apply the data processing inequality to obtain $(b)$. Note also from this
step onwards, entanglement no longer plays a role in the proof. Now, consider

$\displaystyle\mathrm{I}\>\\!\\!\left(\textbf{X}^{n}\textbf{C}^{n}\>\\!:\>\\!\textbf{C}^{\prime
n}\right)_{\tau}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\mathrm{I}\>\\!\\!\left(X_{i}C_{i}\>\\!:\>\\!\textbf{C}^{\prime
n}\>\\!\middle|\>\\!X_{1}\dots X_{i-1}C_{1}\ldots C_{i-1}\right)_{\tau}$ (8)
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\left(\mathrm{I}\>\\!\\!\left(X_{i}C_{i}\>\\!:\>\\!\textbf{C}^{\prime
n}X_{1}\dots X_{i-1}C_{1}\ldots
C_{i-1}\right)_{\tau}-\mathrm{I}\>\\!\\!\left(X_{i}C_{i}\>\\!:\>\\!X_{1}\dots
X_{i-1}C_{1}\ldots C_{i-1}\right)_{\tau}\right)$
$\displaystyle\overset{(c)}{=}$
$\displaystyle\sum_{i=1}^{n}\mathrm{I}\>\\!\\!\left(X_{i}C_{i}\>\\!:\>\\!\textbf{C}^{\prime
n}X_{1}\dots X_{i-1}C_{1}\ldots C_{i-1}\right)_{\tau}$ $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{n}\mathrm{I}\>\\!\\!\left(X_{i}C_{i}\>\\!:\>\\!C^{\prime}_{i}\right)_{\tau}.$

In (8), the equality $(c)$ holds since (6) ensures that

$\tau_{X_{i}C_{i}X_{1}\dots X_{i-1}C_{1}\ldots
C_{i-1}}=\rho_{X_{i}C_{i}X_{1}\dots X_{i-1}C_{1}\ldots
C_{i-1}}=\rho_{X_{i}C_{i}}\otimes\rho_{X_{1}\dots X_{i-1}C_{1}\ldots
C_{i-1}},$

and the last step follows from the data processing inequality. From (4), we
have
$\Delta\left(\tau_{X_{i}C^{\prime}_{i}},\rho_{X_{i}C^{\prime}_{i}}\right)\leq\varepsilon$.
Thus, using Fact 5, we obtain

$\mathrm{I}\>\\!\\!\left(X_{i}C_{i}\>\\!:\>\\!C^{\prime}_{i}\right)_{\tau}=\mathrm{I}\>\\!\\!\left(C_{i}\>\\!:\>\\!C^{\prime}_{i}\>\\!\middle|\>\\!X_{i}\right)_{\tau}+\mathrm{I}\>\\!\\!\left(X_{i}\>\\!:\>\\!C^{\prime}_{i}\right)_{\tau}\geq\mathrm{I}\>\\!\\!\left(C_{i}\>\\!:\>\\!C^{\prime}_{i}\>\\!\middle|\>\\!X_{i}\right)_{\tau}+\mathrm{I}\>\\!\\!\left(X_{i}\>\\!:\>\\!C_{i}\right)_{\rho}-\varepsilon\log|X|-1.$
(9)

Combining (7)-(9), we obtain

$nR\geq
n\min_{i}\left(\mathrm{I}\>\\!\\!\left(C_{i}\>\\!:\>\\!C^{\prime}_{i}\>\\!\middle|\>\\!X_{i}\right)_{\tau}+\mathrm{I}\>\\!\\!\left(X_{i}\>\\!:\>\\!C_{i}\right)_{\rho}-\varepsilon\log|X|-1\right).$

We can now convert the above asymptotic inequality to a single-letter bound.
For an $i$ that achieves the minimum, define $\mathcal{F}_{i}$ to be the map
that acts on register $C_{i}$ as follows. It first creates the state
$\rho_{X_{1}C_{1}}\otimes\ldots\otimes\rho_{X_{i-1}C_{i-1}}\otimes\rho_{X_{i+1}C_{i+1}}\otimes\ldots\otimes\rho_{X_{n}C_{n}}\otimes\theta_{E_{A}E_{B}}$.
Then it applies $\mathcal{D}\circ\mathcal{E}$ and traces out registers
$X_{1},\ldots,X_{i-1},X_{i+1},\ldots,X_{n}$,
$C_{1},\ldots,C_{i-1},C_{i+1},\ldots,C_{n}$,
$C^{\prime}_{1},\ldots,C^{\prime}_{i-1},C^{\prime}_{i+1},\ldots,C^{\prime}_{n}$.
From (4), we conclude that

$\Delta\left(\mathrm{Tr}_{C_{i}}\mathcal{F}_{i}(\rho_{XC_{i}}),\rho_{XC^{\prime}_{i}}\right)\leq\varepsilon.$

Moreover,
$\mathrm{Tr}_{C^{\prime}_{i}}\mathcal{F}(\rho_{XC_{i}})=\rho_{XC_{i}}$, as the
maps $\mathcal{E}$ and $\mathcal{D}$ do not change the state in registers
$XC_{i}$. Since $C_{i}\equiv C$, $C^{\prime}_{i}\equiv C^{\prime}$ and
$\rho_{XC_{i}}=\rho_{XC}$, the proof concludes. ∎

Theorem 2 shows that the communication cost for entanglement-assisted blind
mixed distribution compression can exceed the Holevo information of the
distribution $\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}$. We now
show that this additional cost can be quantitatively bounded by some measure
of indistinguishability of the states in the ensemble, and also by some
measure of the inability to clone the states. To proceed with this, consider a
simple example of compressing two equiprobable distributions, with
$\rho_{XC}=\frac{1}{2}(|0\rangle\langle
0|_{X}\otimes\rho_{C}^{0}+|1\rangle\langle 1|_{X}\otimes\rho_{C}^{1})$. For a
map $\mathcal{F}$ satisfying
$\Delta(\mathrm{Tr}_{C}\left(\mathcal{F}(\rho_{XC})\right),\rho_{XC^{\prime}})\leq\varepsilon$
and $\mathrm{Tr}_{C^{\prime}}\mathcal{F}(\rho_{XC})=\rho_{XC}$, let
$\tau_{XCC^{\prime}}=\mathcal{F}(\rho_{XC})$. We will prove the following:

$\displaystyle\sqrt{\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho_{XC})}}$
$\displaystyle\overset{(a)}{=}$
$\displaystyle\sqrt{\frac{1}{2}\left(D(\tau^{0}_{CC^{\prime}}||\tau^{0}_{C}\otimes\tau^{0}_{C^{\prime}})+D(\tau^{1}_{CC^{\prime}}||\tau^{1}_{C}\otimes\tau^{1}_{C^{\prime}})\right)}$
(10) $\displaystyle\overset{(b)}{\geq}$
$\displaystyle\sqrt{\Delta(\tau^{0}_{CC^{\prime}},\tau^{0}_{C}\otimes\tau^{0}_{C^{\prime}})^{2}+\Delta(\tau^{1}_{CC^{\prime}},\tau^{1}_{C}\otimes\tau^{1}_{C^{\prime}})^{2}}$
$\displaystyle\overset{(c)}{\geq}$
$\displaystyle\frac{1}{\sqrt{2}}\left(\Delta(\tau^{0}_{CC^{\prime}},\tau^{0}_{C}\otimes\tau^{0}_{C^{\prime}})+\Delta(\tau^{1}_{CC^{\prime}},\tau^{1}_{C}\otimes\tau^{1}_{C^{\prime}})\right)$
$\displaystyle\overset{(d)}{\geq}$
$\displaystyle\frac{1}{\sqrt{2}}\left(\Delta(\tau^{0}_{C}\otimes\tau^{0}_{C^{\prime}},\tau^{1}_{C}\otimes\tau^{1}_{C^{\prime}})-\Delta(\tau^{0}_{CC^{\prime}},\tau^{1}_{CC^{\prime}})\right)$
$\displaystyle\overset{(e)}{\geq}$
$\displaystyle\frac{1}{\sqrt{2}}\left(\Delta(\rho^{0}_{C}\otimes\rho^{0}_{C^{\prime}},\rho^{1}_{C}\otimes\rho^{1}_{C^{\prime}})-\Delta(\tau^{0}_{CC^{\prime}},\tau^{1}_{CC^{\prime}})-2\varepsilon\right)$
$\displaystyle\overset{(f)}{\geq}$
$\displaystyle\frac{1}{\sqrt{2}}\left(\Delta(\rho^{0}_{C}\otimes\rho^{0}_{C^{\prime}},\rho^{1}_{C}\otimes\rho^{1}_{C^{\prime}})-\Delta(\rho^{0}_{C},\rho^{1}_{C})-2\varepsilon\right).$

Here, $(a)$ uses the expansion

$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}=\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}=\sum_{x}\,p(x)\,\mathrm{D}\>\\!\\!\left(\tau^{x}_{CC^{\prime}}\middle\|\tau^{x}_{C}\otimes\tau^{x}_{C^{\prime}}\right),$

and $(b)$ uses Pinsker’s inequality (Fact 3), $(c)$ follows from the
inequality $a^{2}+b^{2}\geq\frac{(a+b)^{2}}{2}$, $(d)$ uses the triangle
inequality for trace distance, $(e)$ uses the identity
$\tau^{x}_{C}=\rho^{x}_{C}$ and the inequality
$\Delta(\tau_{XC^{\prime}},\rho_{XC^{\prime}})=\frac{1}{2}\Delta(\tau^{0}_{C^{\prime}},\rho^{0}_{C^{\prime}})+\frac{1}{2}\Delta(\tau^{1}_{C^{\prime}},\rho^{1}_{C^{\prime}})\leq\varepsilon$
and $(f)$ uses the data-processing inequality (Fact 2) to conclude that
$\Delta(\tau^{0}_{CC^{\prime}},\tau^{1}_{CC^{\prime}})=\Delta\left(\mathcal{F}\left(\rho^{0}_{C}\right),\mathcal{F}\left(\rho^{1}_{C}\right))\leq\Delta(\rho^{0}_{C},\rho^{1}_{C}\right)$.

Furthermore, the above chain of inequalities quantitatively relate the gap
between the communication cost and the Holevo information to other
quantitative properties of the ensemble. Recall that
$\tau^{x}_{C}=\rho^{x}_{C}$, so the RHS of the inequality (c) lower-bounds the
gap by a “classical no-cloning bound”, which is the average distance between
two copies of $\rho^{x}_{C}$ and the actual Alice-Bob joint-output.
Furthermore, the RHS of the inequality (f) says that the gap is lower-bounded
by the _increase_ in distinguishability of $\rho_{C}^{0}$ and $\rho_{C}^{1}$
if a second copy is available, which is a measure of the indistinguisability
between $\rho_{C}^{0,1}$.

This gap can be strictly positive for some ensemble. For example, consider:

$\rho^{0}_{C}=\begin{pmatrix}\frac{1}{2}&0\\\
0&\frac{1}{2}\end{pmatrix},\quad\rho^{1}_{C}=\begin{pmatrix}\frac{1}{3}&0\\\
0&\frac{2}{3}\end{pmatrix}.$

We evaluate

$\Delta(\rho^{0}_{C},\rho^{1}_{C})=\frac{1}{2}\left(\bigg{|}\frac{1}{2}-\frac{1}{3}\bigg{|}+\bigg{|}\frac{1}{2}-\frac{2}{3}\bigg{|}\right)=\frac{1}{6}$

and

$\Delta(\rho^{0}_{C}\otimes\rho^{0}_{C},\rho^{1}_{C}\otimes\rho^{1}_{C})=\frac{1}{2}\left(\bigg{|}\frac{1}{4}-\frac{1}{9}\bigg{|}+2\bigg{|}\frac{1}{4}-\frac{2}{9}\bigg{|}+\bigg{|}\frac{1}{4}-\frac{4}{9}\bigg{|}\right)=\frac{7}{36}.$

We conclude that
$\Delta(\rho^{0}_{C}\otimes\rho^{0}_{C},\rho^{1}_{C}\otimes\rho^{1}_{C})-\Delta(\rho^{0}_{C},\rho^{1}_{C})=\frac{1}{36}$.
Thus,

$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}\geq\frac{(1-72\varepsilon)^{2}}{2\cdot
6^{4}}.$

This example demonstrates a constant lower bound on the information defect. In
the next section, we develop a large lower bound that is nearly maximal given
the dimension of $C$.

##  4 Near maximal separation between information cost and the communication
cost

We start with the observation that, despite the fact that the map
$\mathcal{F}$ involves entanglement, the state
$\tau_{XCC^{\prime}}=\mathcal{F}\left(\rho_{XC}\right)$ can be considered to
be completely classical, without loss of generality. To see this, consider the
constraints

$\Delta(\mathrm{Tr}_{C}\left(\mathcal{F}(\rho_{XC})\right),\rho_{XC^{\prime}})\leq\varepsilon$

and $\mathrm{Tr}_{C^{\prime}}\mathcal{F}(\rho_{XC})=\rho_{XC}$. Let
$\mathcal{F}^{\prime}$ be the map resulting from measuring register
$C^{\prime}$ after applying $\mathcal{F}$ to $\rho_{XC}$. Then it still holds
that

$\Delta(\mathrm{Tr}_{C}\left(\mathcal{F}^{\prime}(\rho_{XC})\right),\rho_{XC^{\prime}})\leq\Delta(\mathrm{Tr}_{C}\left(\mathcal{F}(\rho_{XC})\right),\rho_{XC^{\prime}})\leq\varepsilon$

and $\mathrm{Tr}_{C^{\prime}}\mathcal{F}^{\prime}(\rho_{XC})=\rho_{XC}$, so
the constraints are still satisfied, and moreover

$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}^{\prime}(\rho)}\leq\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\mathcal{F}(\rho)}$

by the data processing inequality. Therefore, it suffices to look at maps
$\mathcal{F}$ with completely classical $\tau_{XCC^{\prime}}$, which has the
form

$\tau_{XCC^{\prime}}=\sum_{x,c,c^{\prime}}p_{XCC^{\prime}}(x,c,c^{\prime})|x,c,c^{\prime}\rangle\langle
x,c,c^{\prime}|.$

Note that $p_{XCC^{\prime}}(x,c,c^{\prime})$ satisfies the Markov chain
condition
$p_{XC^{\prime}|C=c}(x,c^{\prime})=p_{X|C=c}(x)\,p_{C^{\prime}|C=c}(c^{\prime})$,
as the map $\mathcal{F}$ produces $C^{\prime}$ from $C$. Define a matrix $M$
with $M_{c,c^{\prime}}=p_{C^{\prime}|C=c}(c^{\prime})$. Clearly, $M$ is a
stochastic matrix: $\forall_{c}\,\sum_{c^{\prime}}M_{c,c^{\prime}}=1$, so,
distributions on $C$ is mapped to distributions on $C^{\prime}$. So we view
$M$ as a ‘channel’ between Alice and Bob that inputs $C$ and outputs
$C^{\prime}$, and appeal to Fano’s inequality (Fact 6) to bound the
information between $C$ and $C^{\prime}$ in terms of the probability of $C$
being equal to $C^{\prime}$. This is shown in the following claim.

######  Claim 1.

It holds that

$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}\geq\mathrm{S}\left(C|X\right)_{\rho}-2-\left(1-\sum_{c}p_{C}(c)M_{c,c}+\varepsilon\right)\log\left(|C|\right).$

###### Proof.

Using the definition for conditional entropy, the Markov chain property
$\mathrm{S}\left(C^{\prime}|CX\right)_{\tau}=\mathrm{S}\left(C^{\prime}|C\right)_{\tau}$
on $\tau$, and applying the Alicki-Fannes-Winter inequality along with the
condition
$\Delta(\mathrm{Tr}_{C}\left(\mathcal{F}(\rho_{XC})\right),\rho_{XC^{\prime}})\leq\varepsilon$
to $\mathrm{S}\left(C^{\prime}|X\right)_{\tau}$, we obtain

$\displaystyle\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}$
$\displaystyle=$
$\displaystyle\mathrm{S}\left(C^{\prime}|X\right)_{\tau}-\mathrm{S}\left(C^{\prime}|CX\right)_{\tau}$
(11) $\displaystyle=$
$\displaystyle\mathrm{S}\left(C^{\prime}|X\right)_{\tau}-\mathrm{S}\left(C^{\prime}|C\right)_{\tau}$
$\displaystyle\geq$
$\displaystyle\mathrm{S}\left(C^{\prime}|X\right)_{\rho}-\mathrm{S}\left(C^{\prime}|C\right)_{\tau}-\Delta(\rho_{XC^{\prime}},\tau_{XC^{\prime}})\log(|C|)-1$
$\displaystyle\geq$
$\displaystyle\mathrm{S}\left(C|X\right)_{\rho}-\mathrm{S}\left(C^{\prime}|C\right)_{\tau}-\varepsilon\log(|C|)-1.$

Using Fano’s inequality (Fact 6)

$\displaystyle\mathrm{S}\left(C^{\prime}|C\right)_{\tau}$ $\displaystyle\leq$
$\displaystyle 1+\Pr[C\neq
C^{\prime}]\log\left(|C|\right)=1+\left(1-\sum_{c}p_{C}(c)M_{c,c}\right)\log\left(|C|\right).$

This concludes the proof. ∎

The ensemble. Using Claim 1, our strategy to obtain a large gap between the
communication cost for compression and the Holevo information is to construct
ensembles for which $\sum_{c}p_{C}(c)M_{c,c}\approx 1$, which implies
$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}\approx\mathrm{S}\left(C|X\right)_{\rho}$.
We now define our ensemble using the following notations. Let $d=|C|$,
$c\in\\{1,2,\ldots d\\}$, $x\in\\{0,1\\}$, and
$p_{X}(0)=p_{X}(1)=\frac{1}{2}$. We choose the states $\rho^{0}_{C}$ and
$\rho^{1}_{C}$ to correspond to the uniform and ‘staircase’ distributions (see
Figure 1), defined as follows.

$p_{C|X=0}(c)=\frac{1}{d}\;{=}{:}\;u_{c}\,,\quad
p_{C|X=1}(c)=\frac{d-c+1}{\eta}\;{=}{:}\;v_{c}\,,$ (12)

where $\eta=\frac{d(d+1)}{2}$. We use $u$ to denote the row vector with the
$c$-th entry being $u_{c}$, and similarly for $v$.

###  4.1 Lower bound in the zero error case

To illustrate the principles in the general case, we first consider the zero-
error case where $\varepsilon=0$. In this case, we have

$uM=u,vM=v\,,$ (13)

so both $u,v$ are fixed points of the transition matrix $M$. We have the
following theorem.

######  Theorem 3.

Using aforementioned definitions, (13) implies that $M_{c,c^{\prime}}=1\text{
iff }c^{\prime}=c$ (i.e., $M=\mathrm{I}$).

###### Proof.

Using the conditions $uM=u$ and $u_{c}=\frac{1}{|C|}$ for all $c$, (13)
implies that

$\forall_{c^{\prime}}\;\sum_{c}M_{c,c^{\prime}}=1.$

Thus the matrix $M$ is doubly stochastic. From the Birkoff-von Neumann theorem
[39, 40, 41], there exist permutation matrices $\Pi_{1},\Pi_{2},\ldots\Pi_{k}$
and a probability distribution $(q_{1},\ldots q_{k})$ such that

$M=\sum_{i}q_{i}\Pi_{i}.$ (14)

Next, we show that $M=\mathrm{I}$. Without loss of generality,
$\Pi_{1}=\mathrm{I}$, $0\leq q_{1}\leq 1$. Suppose, by contradiction,
$q_{1}<1$, so there exists $i\geq 2$ with $q_{i}>0$ and
$\Pi_{i}\neq\mathrm{I}$. Using $vM=v$ and applying (14),

$\sum_{i}q_{i}\left(v\Pi_{i}\right)=v.$

Since $v\Pi_{1}=v$, we obtain

$\frac{1}{1-q_{1}}\sum_{i=2}^{k}q_{i}\left(v\Pi_{i}\right)=v.$ (15)

We will argue that this is a contradiction for the vector $v$. A permutation
$\Pi_{i}$ is said to act “non-trivially” on an index $j\in[d]$ if $j$ is not
invariant under $\Pi_{i}$. Let $j_{0}\in[d]$ be the smallest index such that
at least one of the permutations in the set $\\{\Pi_{i}\\}_{i=2}^{k}$ act non-
trivially on $j_{0}$. Since $\Pi_{i}\neq\mathrm{I}$ for $i=2,3,\cdots,k$, such
an index $j_{0}$ must exist. This implies the following:

  1. 1.

$\left(v\Pi_{i}\right)_{j}=v_{j}$ for all $j<j_{0}$, that is, all the
permutations act trivially on indices smaller than $j_{0}$.

  2. 2.

$\left(v\Pi_{i}\right)_{j_{0}}\leq v_{j_{0}}$, as any permutation $\Pi_{i}$
swaps the element $v_{j_{0}}$ with a potentially smaller element $v_{j}$.

  3. 3.

There is a permutation $\Pi_{i_{0}}$ such that
$\left(v\Pi_{i_{0}}\right)_{j_{0}}<v_{j_{0}}$, by the definition of $j_{0}$.

But items $2,3$ jointly contradict what is implied by the $j_{0}$-th entry of
the vector equality in (15):

$\frac{1}{1-q_{1}}\sum_{i=2}^{k}q_{i}\left(v\Pi_{i}\right)_{j_{0}}=v_{j_{0}}.$

Hence we must have $q_{1}=1$ and $M=\mathrm{I}$. This completes the proof. ∎

We conclude this subsection with a lower bound on the rate in the zero error
case. When $\varepsilon=0$, Theorem 3 implies that
$\sum_{c}p_{C}(c)M_{c,c}=1$. Substituting this into Claim 1,
$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}\geq
S(C|X)_{\rho}-\varepsilon\log(|C|)$. Substituting this into Theorem 2,

$R\geq\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}+S(C|X)_{\rho}-\varepsilon(\log(|C|)+1)-1\approx\mathrm{I}\>\\!\\!\left(X\>\\!:\>\\!C\right)_{\rho}+\alpha\log(|C|)$

for some constant $\alpha$. In the next subsection, we proceed to the case of
small error $\varepsilon$. We will generalize the intuition from the zero-
error case in which $v$ is a vertex of the polytope formed by the convex hull
of $\\{v\Pi_{i}\\}_{i=1}^{k}$.

###  4.2 Lower bound for the case of non-zero error

In this case, we have the guarantee that
$\Delta\left(\tau_{XC^{\prime}},\rho_{XC^{\prime}}\right)\leq\varepsilon$.
This translates to

$\sum_{x}p_{X}(x)\sum_{c^{\prime}}\,\Bigl{|}\,p_{C|X=x}(c^{\prime})-p_{C^{\prime}|X=x}(c^{\prime})\Bigr{|}\leq
2\varepsilon.$

Translating the above tn terms of $M,u,v$ defined earlier, and using the fact
$p_{X}(0)=p_{X}(1)=\frac{1}{2}$,

$\frac{1}{2}\bigl{(}\|u-uM\|_{1}+\|v-vM\|_{1}\bigr{)}\leq 2\varepsilon.$

In particular,

$\|u-uM\|_{1}\leq 4\varepsilon~{}~{}{\rm and}~{}~{}\|v-vM\|_{1}\leq
4\varepsilon.$ (16)

We are ready to obtain our lower bound in spirits similar to the zero-error
case. First, we will use the condition concerning $u$ in (16) to approximate
$M$ by a doubly stochastic matrix $N$ (Lemma 1 part (a)). Then we approximate
$vM$ by $vN$ (Lemma 1 part (b)). With this approximation, and with the
condition on $v$ in (16), we lower bound the identity component of $N$ which
in turns lower bound $N_{c,c}$ and then $M_{c,c}$ and the last bound gives us
the desired lower bound on the communication cost for the compression.

######  Lemma 1.

Let $d\geq 2$. There exists a doubly stochastic matrix $N$ such that

$\displaystyle{\bf{\rm(a)}}$
$\displaystyle\forall_{c,c^{\prime}}\;|N_{c,c^{\prime}}-M_{c,c^{\prime}}|\leq
12d\varepsilon\,,$ $\displaystyle{\bf{\rm(b)}}$ $\displaystyle\|vN-
vM\|_{1}\leq 12d\varepsilon\,.$ (17)

###### Proof.

Rewriting the condition $\|u-uM\|_{1}\leq 4\varepsilon$ from (16) using
$u_{c}=\frac{1}{d}$ for all $c$,

$\sum_{c^{\prime}}\;\biggl{|}\sum_{c}M_{c,c^{\prime}}-1\biggr{|}\leq
4d\varepsilon\,.$ (18)

Thus, the matrix $M$ is a stochastic matrix, but “approximately” a doubly
stochastic matrix. In particular, define
$\alpha_{c^{\prime}}=\sum_{c}M_{c,c^{\prime}}-1$ which measures how far $M$
deviates from being doubly stochastic. Using (18),

$\forall_{c^{\prime}}~{}~{}|\alpha_{c^{\prime}}|\leq 4d\varepsilon\,.$ (19)

We can now follow the idea from [42] to find a doubly stochastic matrix $N$
that approximates $M$. Define

$N_{c,c^{\prime}}=\frac{1}{1+4d\varepsilon}\left(M_{c,c^{\prime}}+\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}\right).$

First, note that the entries of $N_{c,c^{\prime}}$ are non-negative, as
$M_{c,c^{\prime}}\geq 0$ and $4d\varepsilon\geq\alpha_{c^{\prime}}$ for all
$c^{\prime}$ (according to (19)). Second, $N$ is stochastic:

$\displaystyle\sum_{c^{\prime}}N_{c,c^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(\sum_{c^{\prime}}M_{c,c^{\prime}}+\sum_{c^{\prime}}\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(1+4d\varepsilon\right)=1,$

where we have used the stochastic property of $M$ to substitute
$\sum_{c^{\prime}}M_{c,c^{\prime}}=1$, and also
$\sum_{c^{\prime}}\alpha_{c^{\prime}}=\sum_{c,c^{\prime}}M_{c,c^{\prime}}-d=0$.
Next we show that $N$ is doubly stochastic.

$\displaystyle\sum_{c}N_{c,c^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(\sum_{c}M_{c,c^{\prime}}+\sum_{c}\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(1+\alpha_{c^{\prime}}+4d\varepsilon-\alpha_{c^{\prime}}\right)=1.$

Now, we bound the entry-wise difference between $M$ and $N$. Consider

$\displaystyle N_{c,c^{\prime}}-M_{c,c^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(M_{c,c^{\prime}}+\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}\right)-M_{c,c^{\prime}}$
(20) $\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}-4d\varepsilon
M_{c,c^{\prime}}\right)$

Thus,

$\displaystyle|N_{c,c^{\prime}}-M_{c,c^{\prime}}|$ $\displaystyle\leq$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(\bigg{|}\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}\bigg{|}+4d\varepsilon\bigg{|}M_{c,c^{\prime}}\bigg{|}\right)$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle
8\varepsilon+4d\varepsilon\leq 12d\varepsilon,$

where $(a)$ uses $|M_{c,c^{\prime}}|\leq 1$ and
$|4d\varepsilon-\alpha_{c^{\prime}}|\leq 8d\varepsilon$, in turns followed
from (19). This proved claim (a).

For claim (b), define a matrix $W$ as
$W_{c,c^{\prime}}=\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d(1+4d\varepsilon)}$.
Equation (20) states that

$N-M=W-\frac{4d\varepsilon}{1+4d\varepsilon}\,M\,.$

Thus,

$\displaystyle\bigl{\|}vN-vM\bigr{\|}_{1}$ $\displaystyle=$
$\displaystyle\left\|\;vW-\frac{4d\varepsilon}{1+4d\varepsilon}\;vM\;\right\|_{1}$
$\displaystyle\leq$
$\displaystyle\left\|vW\right\|_{1}+\frac{4d\varepsilon}{1+4d\varepsilon}\;\left\|vM\right\|_{1}$
$\displaystyle\overset{(a)}{=}$
$\displaystyle\|vW\|_{1}+\frac{4d\varepsilon}{1+4d\varepsilon}$
$\displaystyle=$
$\displaystyle\frac{1}{1+4d\varepsilon}\left(\sum_{c^{\prime}}\,\bigg{|}\,\frac{4d\varepsilon{-}\alpha_{c^{\prime}}}{d}\,\biggl{(}\sum_{c}v_{c}\biggr{)}\,\bigg{|}\right)+\frac{4d\varepsilon}{1+4d\varepsilon}$
$\displaystyle\leq$
$\displaystyle\sum_{c^{\prime}}\bigg{|}\frac{4d\varepsilon-\alpha_{c^{\prime}}}{d}\bigg{|}+4d\varepsilon$
$\displaystyle\overset{(b)}{\leq}$ $\displaystyle
8d\varepsilon+4d\varepsilon\leq 12d\varepsilon$

In the above, step $(a)$ uses the fact that $vM$ is a probability distribution
so $\|vM\|=1$ and step $(b)$ uses (18) to substitute
$\sum_{c^{\prime}}|\alpha_{c^{\prime}}|\leq 4d\varepsilon$. This completes the
proof. ∎

Now, we are ready to prove our main result, using the condition
$\|v-vM\|_{1}\leq 4\varepsilon$ from (16).

######  Theorem 4.

Let $d\geq 2$. It holds that

$\forall_{c}~{}~{}M_{c,c}\geq 1-24d^{4}\varepsilon.$

###### Proof.

Let $N$ be the doubly stochastic matrix as promised in Lemma 1. We start with

$\displaystyle\|v-vN\|_{1}$ $\displaystyle\leq$
$\displaystyle\|v-vM\|_{1}+\|vM-vN\|$ (21) $\displaystyle\overset{(a)}{\leq}$
$\displaystyle 4\varepsilon+12d\varepsilon\leq 16d\varepsilon.$

Here, $(a)$ uses (16) and Lemma 1.

Now, we apply the Birkoff-von Neumann theorem to write
$N=\sum_{i=1}^{k}q_{i}\Pi_{i}$, where $\Pi_{1}=\mathrm{I}$ and
$\Pi_{2},\cdots,\Pi_{k}$ are permutation matrices not equal to the identity.
If $q_{1}=1$ then we are done so assume $q_{1}<1$, and there exists $i\geq 2$
with $q_{i}>0$. We lower bound $\|v-vN\|_{1}$ as follows.

$\displaystyle\|v-vN\|_{1}$ $\displaystyle=$
$\displaystyle\bigg{\|}v-\sum_{i=1}^{k}q_{i}\left(v\Pi_{i}\right)\bigg{\|}_{1}=\bigg{\|}v-q_{1}v-\sum_{i=2}^{k}q_{i}\left(v\Pi_{i}\right)\bigg{\|}_{1}$
(22) $\displaystyle=$
$\displaystyle\bigg{\|}(1-q_{1})v-\sum_{i=2}^{k}q_{i}\left(v\Pi_{i}\right)\bigg{\|}_{1}=(1-q_{1})\bigg{\|}v-\sum_{i=2}^{k}\frac{q_{i}}{1-q_{1}}\left(v\Pi_{i}\right)\bigg{\|}_{1}.$

The last expression in (22) is lower bounded by the minimum $\ell_{1}$
distance between the vector $v$ and the convex hull of the vectors
$\\{v\Pi_{i}\\}_{i=2}^{k}$. As shown in Claim 2 below, this distance is lower
bounded by

$\bigg{\|}v-\sum_{i=2}^{k}\frac{q_{i}}{1-q_{1}}\left(v\Pi_{i}\right)\bigg{\|}_{1}\geq\frac{1}{v_{1}}\left(\sum_{j}v^{2}_{j}-\max_{i>1}\left(\sum_{j}v_{j}\left(v\Pi_{i}\right)_{j}\right)\right).$

From Claim 3,

$\max_{i>1}\left(\sum_{j}v_{j}\left(v\Pi_{i}\right)_{j}\right)\leq\sum_{i}v_{i}^{2}-\frac{1}{\eta^{2}}.$

This implies

$\bigg{\|}v-\sum_{i=2}^{k}\frac{q_{i}}{1-q_{1}}\left(v\Pi_{i}\right)\bigg{\|}_{1}\geq\frac{1}{v_{1}\eta^{2}}.$

From (22), we conclude

$\|v-vN\|_{1}\geq(1-q_{1})\frac{1}{v_{1}\eta^{2}},$

and combining this with (21), we find

$(1-q_{1})\frac{1}{v_{1}\eta^{2}}\leq 16d\varepsilon\implies 1-q_{1}\leq
16d\varepsilon v_{1}\eta^{2}\leq 16d^{4}\varepsilon.$ (23)

Since $N_{c,c}\geq q_{1}$, we finally conclude from Lemma 1 and (23) that

$M_{c,c}\geq N_{c,c}-12d\varepsilon\geq q_{1}-12d\varepsilon\geq
1-24d^{4}\varepsilon.$

Here we used $d\geq 2$ to substitute $16d^{4}\varepsilon+12d\varepsilon\leq
24d^{4}\varepsilon$. This completes the proof. ∎

The following claims were used in the proof.

######  Claim 2.

Let $v,w_{1},\ldots w_{s}$ be vectors in $\mathbb{R}^{n}$ with non-negative
entries. Suppose $v_{1}$ is the largest entry of $v$, and $v_{1}>0$. It holds
that

$\min_{r_{1},\ldots
r_{s}\in[0,1]:\sum_{i}r_{i}=1}\|v-\sum_{i}r_{i}w_{i}\|_{1}\geq\frac{1}{v_{1}}\left(\sum_{j}v^{2}_{j}-\max_{i}\left(\sum_{j}v_{j}\left(w_{i}\right)_{j}\right)\right)$

###### Proof.

We use the fact that $\|u\|_{1}=\max_{m_{1},\ldots
m_{n}\in[-1,1]}\sum_{j}u_{j}m_{j}$ to write

$\displaystyle\min_{r_{1},\ldots
r_{s}\in[0,1]:\sum_{i}r_{i}=1}\|v-\sum_{i}r_{i}w_{i}\|_{1}$
$\displaystyle=\min_{r_{1},\ldots
r_{s}\in[0,1]:\sum_{i}r_{i}=1}\quad\max_{m_{1},\ldots
m_{n}\in[-1,1]}\left(\sum_{j}m_{j}\left(v_{j}-\sum_{i}r_{i}\left(w_{i}\right)_{j}\right)\right)$
$\displaystyle=\min_{r_{1},\ldots
r_{s}\in[0,1]:\sum_{i}r_{i}=1}\quad\max_{m_{1},\ldots
m_{n}\in[-1,1]}\left(\sum_{j}m_{j}v_{j}-\sum_{i,j}r_{i}m_{j}\left(w_{i}\right)_{j}\right)$
$\displaystyle\overset{(a)}{=}\max_{m_{1},\ldots
m_{n}\in[-1,1]}\quad\min_{r_{1},\ldots
r_{s}\in[0,1]:\sum_{i}r_{i}=1}\left(\sum_{j}m_{j}v_{j}-\sum_{i,j}r_{i}m_{j}\left(w_{i}\right)_{j}\right)$
$\displaystyle\overset{(b)}{=}\max_{m_{1},\ldots
m_{n}\in[-1,1]}\left(\sum_{j}m_{j}v_{j}-\max_{i}\left(\sum_{j}m_{j}\left(w_{i}\right)_{j}\right)\right)$
$\displaystyle\overset{(c)}{\geq}\frac{1}{v_{1}}\left(\sum_{j}v^{2}_{j}-\max_{i}\left(\sum_{j}v_{j}\left(w_{i}\right)_{j}\right)\right).$

Here $(a)$ uses the minimax theorem [43], $(b)$ chooses the optimal
$\\{r_{1},\ldots r_{s}\\}$ to maximize

$\sum_{i,j}r_{i}m_{j}\left(w_{i}\right)_{j}=\sum_{i}r_{i}\left(\sum_{j}m_{j}\left(w_{i}\right)_{j}\right)$

and $(c)$ chooses $m_{i}=\frac{v_{i}}{v_{1}}\in[0,1]$. This completes the
proof. ∎

######  Claim 3.

It holds that

$\max_{\Pi\neq\mathrm{I}}\left(\sum_{j}v_{j}\left(v\Pi\right)_{j}\right)=\sum_{j}v_{j}^{2}-\frac{1}{\eta^{2}},$

where maximization is over all permutations $\Pi$ not equal to identity.

###### Proof.

We recall that $\Pi$ can be decomposed as a product of disjoint cycles
$C_{1},C_{2},\ldots C_{s}$. If $\Pi$ leaves an index unchanged, we will view
the action of $\Pi$ on this index as a ‘trivial cycle’ of size $1$. Let
$L_{k}$ be the set of indices on which the cycle $C_{k}$ acts. Since the
cycles are disjoint,

$\sum_{j}v_{j}\left(v\Pi\right)_{j}=\sum_{k=1}^{s}\sum_{j\in
L_{k}}v_{j}\left(vC_{k}\right)_{j}.$ (24)

Consider the expression $\sum_{j\in L_{k}}v_{j}\left(vC_{k}\right)_{j}$. Let
$|L_{k}|$ be the number of elements in $L_{k}$. Relabel the elements in
$L_{k}$ with integers $\\{0,1,\ldots|L_{k}|-1\\}$ in a manner that
$C_{k}(m)=m+s\mod|L_{k}|$, for some integer $s$. Then

$\displaystyle\sum_{j\in L_{k}}v_{j}\left(vC_{k}\right)_{j}$ $\displaystyle=$
$\displaystyle\sum_{m=0}^{|L_{k}|-1}v_{m}v_{m+s\mod|L_{k}|}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{m=0}^{|L_{k}|-1}\left(v^{2}_{m}+v^{2}_{m+s\mod|L_{k}|}-\left(v_{m}-v_{m+s\mod|L_{k}|}\right)^{2}\right)$
$\displaystyle=$
$\displaystyle\sum_{m=0}^{|L_{k}|-1}v_{m}^{2}-\frac{1}{2}\sum_{m=0}^{|L_{k}|-1}(v_{m}-v_{m+s\mod|L_{k}|})^{2}$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\sum_{m=0}^{|L_{k}|-1}v_{m}^{2}-\lfloor|L_{k}|/2\rfloor=\sum_{j\in
L_{k}}v_{j}^{2}-\frac{1}{\eta^{2}}\cdot\lfloor|L_{k}|/2\rfloor.$

Here $(a)$ follows by noticing that
$(v_{m}-v_{m+s\mod|L_{k}|})^{2}\geq\frac{1}{\eta^{2}}$. Combining with (24),
we find that

$\sum_{j}v_{j}\left(v\Pi\right)_{j}\leq\sum_{k=1}^{s}\left(\sum_{j\in
L_{k}}v_{j}^{2}-\frac{1}{\eta^{2}}\cdot\lfloor|L_{k}|/2\rfloor\right)=\sum_{j}v_{j}^{2}-\frac{1}{\eta^{2}}\cdot\left(\sum_{k=1}^{s}\lfloor|L_{k}|/2\rfloor\right).$

Since $\Pi$ is not the identity permutation, there is a $C_{k}$ of length at
least $2$. Thus, $\sum_{k=1}^{s}\lfloor|L_{k}|/2\rfloor\geq 1$ and

$\max_{\Pi}\left(\sum_{j}v_{j}\left(v\Pi\right)_{j}\right)\leq\sum_{j}v_{j}^{2}-\frac{1}{\eta^{2}}.$

To show that the right hand side is achieved, choose $\Pi$ to be any
permutation that swaps a pair of consecutive indices and leaves every other
index unchanged. This completes the proof. ∎

###  4.3 Final lower bound

Theorem 4 says that $M_{c,c}\geq 1-24d^{4}\varepsilon$ for all $c$. If we
choose $\varepsilon=\frac{1}{24d^{4}\log d}$, we conclude that for all $c$

$M_{c,c}\geq 1-\frac{1}{\log d}.$

Thus, the lower bound in Claim 1 takes the form

$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}\;\geq\;\mathrm{S}\left(C|X\right)_{\rho}-2-\left(1-\sum_{c}p_{C}(c)M_{c,c}+\varepsilon\right)\log\left(d\right)\;\geq\;\mathrm{S}\left(C|X\right)_{\rho}-4.$

The conditional entropy can be evaluated to be

$\displaystyle\mathrm{S}\left(C|X\right)_{\rho}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\mathrm{S}(C)_{\rho^{0}}+\mathrm{S}(C)_{\rho^{1}}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\sum_{c}v_{c}\log\frac{1}{v_{c}}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\sum_{c}v_{c}\log\frac{\eta}{d-c+1}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\log\eta-\sum_{c}v_{c}\log(d-c+1)\right)$
$\displaystyle\overset{(a)}{\geq}$ $\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\log\eta-\log\left(\sum_{c}v_{c}(d-c+1)\right)\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\log\eta-\log\left(\sum_{c}\frac{(d-c+1)^{2}}{\eta}\right)\right)$
$\displaystyle\overset{(b)}{=}$ $\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\log\frac{d(d+1)}{2}-\log\left(\frac{d(d+1)(2d+1)}{3d(d+1)}\right)\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\log
d+\frac{1}{2}\left(\log\frac{3d(d+1)}{4d+2}\right)\geq(\log d)-1.$

Here $(a)$ follows from concavity of log and $(b)$ follows by substituting the
value of $\eta$. This leads to the lower bound

$\mathrm{I}\>\\!\\!\left(C\>\\!:\>\\!C^{\prime}\>\\!\middle|\>\\!X\right)_{\tau}\geq(\log
d)-5.$

Thus, from Theorem 2, we have a state $\rho_{XC}$ such that the asymptotic
rate of communication for local error $\varepsilon=\frac{1}{24d^{4}\log d}$ is
at least $(\log d)-7$ while the Holevo information is at most $1$. Note that
$d$ is independent of the number of copies $n$, and $\varepsilon$ is
independent of $n$ and only depends on $d$.

### Acknowledgements

We thank Masato Koashi and Andreas Winter for helpful discussions. This
research is supported by research grants administered by NSERC and CIFAR.
Perimeter Institute is supported in part by the Government of Canada and the
Province of Ontario.

## References

  * [1] C. E. Shannon, “A mathematical theory of communication,” The Bell System Technical Journal, vol. 27, pp. 379–423, July 1948.
  * [2] A. E. Gamal and Y.-H. Kim, Network Information Theory.  New York, NY, USA: Cambridge University Press, 2012.
  * [3] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels,” Phys. Rev. Lett., vol. 70, pp. 1895–1899, Mar 1993.
  * [4] C. H. Bennett and S. J. Wiesner, “Communication via one- and two-particle operators on einstein-podolsky-rosen states,” Phys. Rev. Lett., vol. 69, no. 20, pp. 2881–2884, 1992.
  * [5] B. Schumacher, “Quantum coding,” Phys. Rev. A., vol. 51, pp. 2738–2747, 1995.
  * [6] R. Jozsa and B. Schumacher, “A new proof of the quantum noiseless coding theorem,” Journal of Modern Optics, vol. 41, no. 12, pp. 2343–2349, 1994\.
  * [7] H. Barnum, C. A. Fuchs, R. Jozsa, and B. Schumacher, “General fidelity limit for quantum channels,” Phys. Rev. A, vol. 54, pp. 4707–4711, Dec 1996\.
  * [8] J. V. Neumann, Mathematische Grundlagen der Quantenmechanik.  Berlin, Germany: Springer, 1932.
  * [9] M. Horodecki, “Limits for compression of quantum information carried by ensembles of mixed states,” Phys. Rev. A, vol. 57, pp. 3364–3369, May 1998\.
  * [10] H. Barnum, C. M. Caves, C. A. Fuchs, R. Jozsa, and B. W. Schumacher, “On quantum coding for ensembles of mixed states,” 2000.  https://arxiv.org/abs/quant-ph/0008024.
  * [11] R. Jozsa, “Fidelity for mixed quantum states,” Journal of Modern Optics, vol. 41, no. 12, pp. 2315–2323, 1994.
  * [12] M. Horodecki, “Optimal compression for mixed signal states,” Phys. Rev. A, vol. 61, p. 052309, Apr 2000.
  * [13] W. Dür, G. Vidal, and J. I. Cirac, “Visible compression of commuting mixed states,” Phys. Rev. A, vol. 64, p. 022308, Jul 2001.
  * [14] G. Kramer and S. A. Savari, “Quantum data compression of ensembles of mixed states with commuting density operators,” 2001.  https://arxiv.org/abs/quant-ph/0101119.
  * [15] M. Koashi and N. Imoto, “Operations that do not disturb partially known quantum states,” Phys. Rev. A, vol. 66, p. 022318, Aug 2002.  https://arxiv.org/abs/quant-ph/0101144.
  * [16] M. Koashi and N. Imoto, “Compressibility of quantum mixed-state signals,” Phys. Rev. Lett., vol. 87, p. 017902, Jun 2001.
  * [17] M. Koashi and N. Imoto, “Teleportation cost and hybrid compression of quantum signals,” 2001.  https://arxiv.org/abs/quant-ph/0104001.
  * [18] A. Winter, “Compression of sources of probability distributions and density operators,” 2002.  https://arxiv.org/abs/quant-ph/0208131.
  * [19] E. Soljanin, “Compressing quantum mixed-state sources by sending classical information,” IEEE Transactions on Information Theory, vol. 48, pp. 2263–2275, Aug 2002.
  * [20] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,” IEEE Transactions on Information Theory, vol. 48, pp. 2637–2655, Oct 2002.
  * [21] R. Jain, J. Radhakrishnan, and P. Sen, “A direct sum theorem in communication complexity via message compression,” in Proceedings of the 30th international conference on Automata, languages and programming, ICALP’03, (Berlin, Heidelberg), pp. 300–315, Springer-Verlag, 2003.
  * [22] P. Harsha, R. Jain, D. Mc.Allester, and J. Radhakrishnan, “The communication complexity of correlation.,” IEEE Transactions on Information Theory, vol. 56, pp. 438–449, 2010.
  * [23] M. Hayashi, “Optimal visible compression rate for mixed states is determined by entanglement of purification,” Phys. Rev. A, vol. 73, p. 060301, Jun 2006.
  * [24] B. M. Terhal, M. Horodecki, D. W. Leung, and D. P. DiVincenzo, “The entanglement of purification,” Journal of Mathematical Physics, vol. 43, p. 4286–4298, Sep 2002.
  * [25] C. H. Bennett, D. P. DiVincenzo, P. W. Shor, J. A. Smolin, B. M. Terhal, and W. K. Wootters, “Remote state preparation,” Phys. Rev. Lett., vol. 87, p. 077902, Jul 2001.
  * [26] C. H. Bennett, P. Hayden, D. W. Leung, P. W. Shor, and A. Winter, “Remote preparation of quantum states,” IEEE Transactions on Information Theory, vol. 51, pp. 56–74, Jan 2005.
  * [27] A. Abeyesinghe, P. Hayden, G. Smith, and A. J. Winter, “Optimal superdense coding of entangled states,” IEEE Transactions on Information Theory, vol. 52, pp. 3635–3641, Aug 2006.
  * [28] R. Jain, J. Radhakrishnan, and P. Sen, “Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states,” in Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS ’02, (Washington, DC, USA), pp. 429–438, IEEE Computer Society, 2002.
  * [29] R. Jain, “Communication complexity of remote state preparation with entanglement,” Quantum Information and Computation, vol. 6, pp. 461–464, July 2006.
  * [30] C. H. Bennett, I. Devetak, A. W. Harrow, P. W. Shor, and A. Winter, “The quantum reverse shannon theorem and resource tradeoffs for simulating quantum channels,” IEEE Transactions on Information Theory, vol. 60, pp. 2926–2959, May 2014.
  * [31] H. Umegaki, “Conditional expectation in an operator algebra, i,” Tohoku Math. J. (2), vol. 6, no. 2-3, pp. 177–181, 1954.
  * [32] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information.  Cambridge, UK: Cambridge University Press, 2000.
  * [33] H. Barnum, C. M. Cave, C. A. Fuch, R. Jozsa, and B. Schmacher, “Noncommuting mixed states cannot be broadcast,” Phys. Rev. Lett., vol. 76, no. 15, pp. 2818–2821, 1996.
  * [34] G. Lindblad, “Completely positive maps and entropy inequalities,” Commun. Math. Phys., vol. 40, pp. 147–151, 1975.
  * [35] M. S. Pinsker, Information and Information Stability of Random Variables and Processes.  Holden-Day, 1964.
  * [36] R. Alicki and M. Fannes, “Continuity of quantum conditional information,” Journal of Physics A: Mathematical and General, vol. 37, no. 5, p. L55, 2004\.
  * [37] A. Winter, “Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints,” Communications in Mathematical Physics, vol. 347, no. 1, pp. 291–313, 2016.
  * [38] R. Fano, Transmission Of Information: A Statistical Theory Of Communication.  Cambridge, Massachusetts: M.I.T. Press, 1961.
  * [39] D. K’́onig, Theorie der endlichen und unendlichen Graphen.  Akademische. Verlags Gesellschaft, 1936.
  * [40] G. Birkhoff, “Three observations on linear algebra,” Univ. Nac. Tucuman. Revista A., vol. 5, p. 147–151, 1946.
  * [41] J. von Neumann, “A certain zero-sum two-person game equivalent to the optimal assignment problem,” Ann. Math. Studies, vol. 28, pp. 5–12, 1953.
  * [42] R. N. Khoury, “Closest matrices in the space of generalized doubly stochastic matrices,” Journal of Mathematical Analysis and Applications, vol. 222, no. 2, pp. 562 – 568, 1998.
  * [43] J. V. Neumann, “Zur theorie der gesellschaftsspiele,” Math. Annalen., vol. 100, pp. 295–320, 1928.

##  Appendix A Koashi-Imoto characterization at non-vanishing error

Koashi and Imoto [15, 16, 17] provide a characterization of the optimal rates
of quantum communication, classical communication, and entanglement for
$(n,R,\varepsilon)$\- blind compression of general quantum states (defined
similarly to the task of blind distribution compression) in the limit where
$n\rightarrow\infty$ and the local error $\varepsilon\rightarrow 0$. These
results apply to both the unassisted and the entanglement-assisted scenarios.

The Koashi-Imoto characterization of $(n,R,\varepsilon)$\- blind compression
is achieved by the following structure theorem for any ensemble
$\\{p_{i},\rho_{i}\\}$. There exists a decomposition of the Hilbert space
$\mathcal{H}$ as
$\mathcal{H}=\bigoplus_{\ell}\mathcal{H}^{(\ell)}_{J}\otimes\mathcal{H}^{(\ell)}_{K}$,
in a manner that
$\rho_{i}=\bigoplus_{\ell}q_{i,\ell}\rho^{(i,\ell)}_{J}\otimes\rho^{\ell}_{K}$.
Here, $\rho^{(i,\ell)}_{J}$ and $\rho^{\ell}_{K}$ are normalized density
matrices acting on $\mathcal{H}^{(\ell)}_{J}$ and $\mathcal{H}^{(\ell)}_{K}$
respectively, and $q_{i,\ell}\geq 0$, $\sum_{i}q_{i,\ell}=1$. Furthermore, for
each $\ell$, $\\{\rho^{(1,\ell)}_{J},\rho^{(2,\ell)}_{J},\cdots\\}$ cannot be
expressed in a simultaneously block-diagonal form. The register $K$ is viewed
as redundant, as it has no dependence on $i$. Without loss of generality, one
can restrict the attention to ensembles which have no redundant register $K$,
as the register $K$ can be removed by Alice and later be generated by Bob
without communication between them. The average state
$\rho=\sum_{i}p_{i}\rho_{i}$ can also be written as
$\rho=\bigoplus_{\ell}p^{(\ell)}\rho^{(\ell)}_{J}$ where
$p^{(\ell)}=\sum_{i}p_{i}q_{i,\ell}$ and $\rho^{(\ell)}_{J}={1\over
p^{(\ell)}}\left(\sum_{i}p_{i}q_{i,\ell}\rho^{(i,\ell)}_{J}\right)$. Let
$I_{C}=-\sum_{\ell}p^{(\ell)}\log p^{(\ell)}$ and
$I_{Q}=\sum_{\ell}p^{(\ell)}S\left(\rho^{(\ell)}_{J}\right)$. The ensemble can
be compressed at optimal rates of $I_{C}$ bits and $I_{Q}$ qubits combined,
whereas $I_{C}+I_{Q}=S(\rho)$. Furthermore, the authors proved that any
channel $\mathcal{E}$ satisfying $\mathcal{E}(\rho_{i})=\rho_{i}$ acts as the
identity map on $J$.

The characterization in the case of zero error ($\varepsilon=0$) is now
immediate. Let $\mathcal{P}$ be the combined encoding and decoding map in the
protocol. Since the protocol makes no error, $\mathcal{P}(\rho_{i})=\rho_{i}$
for all $i$ and hence $\mathcal{P}$ acts as the identity map on the $J$
register, giving rise to the aforementioned optimal rates.

To address the regime $n\rightarrow\infty,\varepsilon\rightarrow 0$, Koashi
and Imoto [16] introduce two error functions

$f(\mathcal{P})=1-\sum_{i}p_{i}\mathrm{F}(\rho_{i},\mathcal{P}(\rho_{i}))$

and

$g(\mathcal{P})=H(\lambda)+\lambda\log(d-1),$

where $\lambda=1-\sum_{a}r(a)\mathrm{Tr}(|a\rangle\langle
a|\,\mathcal{P}(|a\rangle\langle a|))$ and $|a\rangle,r(a)$ are the
eigenvectors and eigenvalues of the average state of the ensemble,
$\rho=\sum_{i}p_{i}\rho_{i}$. The parameter $f(\mathcal{P})$ captures the
error $\varepsilon$ (up to the difference that we are working in trace
distance, whereas they work in fidelity). The parameter $g(\mathcal{P})$
appears in their lower bound $R\geq S(\rho)-g(\mathcal{P})$ on the
communication cost. They give a continuity argument that if
$f(\mathcal{P})\rightarrow 0$, then $g(\mathcal{P})\rightarrow 0$.

For non-vanishing error, the dependence of $\lambda$ on $f(\mathcal{P})$ and
in turn, the dependence of $g(\mathcal{P})$ on $f(\mathcal{P})$ (via
$\lambda$) is important. While $\lambda\rightarrow 0$ as
$f(\mathcal{P})\rightarrow 0$, it is unclear how quickly $\lambda$ vanishes as
$f(\mathcal{P})\rightarrow 0$. Consequently, $g(\mathcal{P})$ need not vanish
quickly enough to provide a strong lower bound. In our context, we construct a
protocol in Theorem 5 exhibiting this sensitivity. We show an example where
$g(\mathcal{P})$ becomes close to $\log d$, even if
$f(\mathcal{P})\approx\frac{1}{\sqrt{d}}$. Thus we know from the example that
for two distributions, the lower bound proved by Koashi and Imoto only works
for error substantially smaller than ${1\over\sqrt{d}}$.

Another reason to expect that the Koashi-Imoto characterization is sensitive
to errors, is as follows. Consider an equiprobable ensemble of two states
$\rho$ and $\sigma$. When the error $\varepsilon$ (defined in (5)) is finite,
we have the conditions $\Delta(\mathcal{P}(\rho),\rho)\leq
2\varepsilon,\Delta(\mathcal{P}(\sigma),\sigma)\leq 2\varepsilon$. Does this
guarantee that $\rho$ and $\sigma$ are respectively close to states
$\tilde{\rho}$ and $\tilde{\sigma}$ that are fixed points of $\mathcal{P}$? If
this were the case, we could apply the Koashi-Imoto decomposition to
$\tilde{\rho},\tilde{\sigma}$ to obtain a large lower bound for the rate for
finite $\varepsilon$. Unfortunately this is not true, as witnessed by the
channel
$\mathcal{E}(\tau)=(1-\varepsilon)\tau+\varepsilon\frac{\mathrm{I}}{d}$. This
channel satisfies $\Delta(\mathcal{E}(\tau),\tau)\leq\varepsilon$ for all
$\tau$, but its only fixed point is $\frac{\mathrm{I}}{d}$.

Our arguments are made precise in the following protocol for the blind
compression of any pair of commuting states $\rho,\sigma$, with rate
significantly less than $\log(d)$ for non vanishing local error.

######  Theorem 5.

Let $n$ be a positive integer and $\delta\in(0,\frac{1}{2}),\gamma\in(0,1)$.
Consider the local error model. Given two commuting states $\rho,\sigma$,
there exists an $(n,R,\delta+\gamma)$ blind distribution compression protocol
$\mathcal{P}$ with $R=2\log\log(\frac{d}{\gamma})+2\log\frac{1}{\delta}+3$.

###### Proof.

Without loss of generality, $\rho,\sigma$ are both diagonal in the
computational basis, so, they can be written as
$\rho=\sum_{a}p(a)|a\rangle\langle a|$ and
$\sigma=\sum_{a}q(a)|a\rangle\langle a|$ where $p(a),q(a)\geq 0$,
$\sum_{a}p(a)=\sum_{a}q(a)=1$. Let
$u=\Bigl{\lceil}\frac{\log\frac{d}{\gamma}}{\log\frac{1}{1-\delta}}\Bigr{\rceil}$,
so that $(1-\delta)^{u}\leq\frac{\gamma}{d}$. For $i,j\in\\{1,2,\cdots,u\\}$,
define the sets

$\displaystyle T_{i,j}$
$\displaystyle:=\\{\,a\,:\,p(a)\\!\in\\!((1{-}\delta)^{i},(1{-}\delta)^{i-1}]\,,\;q(a)\\!\in\\!((1{-}\delta)^{j},(1{-}\delta)^{j-1}]\,\\}\,,$
$\displaystyle T_{i,u+1}$
$\displaystyle:=\\{\,a\,:\,p(a)\\!\in\\!((1{-}\delta)^{i},(1{-}\delta)^{i-1}]\,,\;q(a)\leq(1{-}\delta)^{u}\,\\}\,,$
$\displaystyle T_{u+1,j}$
$\displaystyle:=\\{\,a:\,p(a)\leq(1{-}\delta)^{u}\,,\;q(a)\\!\in\\!((1{-}\delta)^{j},(1{-}\delta)^{j-1}]\\}$
$\displaystyle T_{u+1,u+1}$
$\displaystyle:=\\{\,a:\,p(a)\leq(1{-}\delta)^{u}\,,\;q(a)\leq(1{-}\delta)^{u}\\}\,.$

The protocol $\mathcal{P}$ is as follows.

  * •

Alice receives a sample $a$. She finds the unique $(i,j)$ such that $a\in
T_{i,j}$ and communicates $(i,j)$ to Bob.

  * •

Receiving $(i,j)$, Bob outputs an $a^{\prime}$ drawn uniformly from $T_{i,j}$.

If the input given to Alice is drawn from $\rho$ ($\sigma$), let the output
produced by Bob be drawn from $\rho^{\prime}$ ($\sigma^{\prime}$). The
analysis of the protocol is as follows.

  * •

Communication cost: Since there are at most $(u+1)^{2}$ $(i,j)$’s, it suffices
for Alice to communicate $2\log(u+1)\leq 2((\log u)+1)\leq
2\log\log\frac{d}{\gamma}+2\log\frac{1}{\log\frac{1}{1{-}\delta}}+3\leq
2\log\log\frac{d}{\gamma}+2\log\frac{1}{\delta}+3$ bits to Bob. Note that we
have used the inequality $\frac{1}{-\log(1-\delta)}\leq\frac{1}{\delta}$
derived from the Taylor series expansion of $\log(1-\delta)$.

  * •

Error analysis: Let $p(T_{i,j}):=\sum_{a\in T_{i,j}}p(a)$ and
$q(T_{i,j}):=\sum_{a\in T_{i,j}}q(a)$. We can rewrite $\rho$ and $\sigma$ as

$\rho=\sum_{i,j=1}^{u+1}p(T_{i,j})\sum_{a\in
T_{i,j}}\frac{p(a)}{p(T_{i,j})}|a\rangle\langle
a|,\quad\sigma=\sum_{i,j=1}^{u+1}q(T_{i,j})\sum_{a\in
T_{i,j}}\frac{q(a)}{q(T_{i,j})}|a\rangle\langle a|.$

Observe from the protocol that

$\rho^{\prime}=\sum_{i,j=1}^{u+1}p(T_{i,j})\sum_{a\in
T_{i,j}}\frac{1}{|T_{i,j}|}|a\rangle\langle
a|,\quad\sigma^{\prime}=\sum_{i,j=1}^{u+1}q(T_{i,j})\sum_{a\in
T_{i,j}}\frac{1}{|T_{i,j}|}|a\rangle\langle a|.$

So,

$\displaystyle\Delta(\rho,\rho^{\prime})$ $\displaystyle=$
$\displaystyle\Delta\bigg{(}\sum_{i,j=1}^{u+1}p(T_{i,j})\sum_{a\in
T_{i,j}}\frac{p(a)}{p(T_{i,j})}|a\rangle\langle
a|\,,\;\sum_{i,j=1}^{u+1}p(T_{i,j})\sum_{a\in
T_{i,j}}\frac{1}{|T_{i,j}|}|a\rangle\langle a|\bigg{)}$ (25) $\displaystyle=$
$\displaystyle\sum_{i,j=1}^{u+1}p(T_{i,j})\;\Delta\bigg{(}\sum_{a\in
T_{i,j}}\frac{p(a)}{p(T_{i,j})}|a\rangle\langle a|\,,\;\sum_{a\in
T_{i,j}}\frac{1}{|T_{i,j}|}|a\rangle\langle a|\bigg{)}$

By definition of the set $T_{i,j}$ with $i\leq u$, it holds that
$1-\delta\leq\frac{p(a_{1})}{p(a_{2})}\leq\frac{1}{1-\delta}$ for all
$a_{1},a_{2}\in T_{i,j}$. Thus, for all $a\in T_{i,j}$ with $i\leq u$,

$(1-\delta)\frac{1}{|T_{i,j}|}\leq\frac{p(a)}{p(T_{i,j})}\leq\frac{1}{1-\delta}\frac{1}{|T_{i,j}|}\implies\bigg{|}\frac{p(a)}{p(T_{i,j})}-\frac{1}{|T_{i,j}|}\bigg{|}\leq\frac{\delta}{1-\delta}\frac{1}{|T_{i,j}|}\,.$

So,

$\Delta\bigg{(}\sum_{a\in T_{i,j}}\frac{p(a)}{p(T_{i,j})}|a\rangle\langle
a|\,,\,\sum_{a\in T_{i,j}}\frac{1}{|T_{i,j}|}|a\rangle\langle
a|\bigg{)}\leq{1\over 2}\sum_{a\in
T_{i,j}}\frac{\delta}{1-\delta}\frac{1}{|T_{i,j}|}\leq\frac{\delta}{2(1-\delta)}\,.$
(26)

Furthermore,

$\sum_{j=1}^{u+1}p(T_{u+1,j})=\sum_{a:p(a)\leq(1-\delta)^{u}}p(a)\leq(1-\delta)^{u}\cdot
d\leq\gamma\,.$ (27)

Applying (26), (27), and $\delta\leq{1\over 2}$ to (25),

$\displaystyle\Delta(\rho,\rho^{\prime})\;\leq\;\sum_{i=1}^{u}\sum_{j=1}^{u+1}\,p(T_{i,j})\,\frac{\delta}{2(1-\delta)}+\sum_{j=1}^{u+1}p(T_{u+1,j})\;\leq\;\frac{\delta}{2(1-\delta)}+\gamma\;\leq\;\delta+\gamma\,.$

A similar argument shows that
$\Delta(\sigma,\sigma^{\prime})\leq\delta+\gamma.$ This completes the error
analysis.

The correctness of the protocol concludes by running the above protocol
independently for each copy to obtain an $(n,R,\delta+\gamma)$ protocol. ∎

Theorem 5 immediately implies that $g(\mathcal{P})$ is close to $S(\rho)$ for
constant $\delta,\gamma$, else the lower bound $R\geq S(\rho)-g(\mathcal{P})$
would contradict the statement of the theorem. We can see this explicitly by
evaluating the functions $f(\mathcal{P})$ and $g(\mathcal{P})$. Let us
continue using the notation in Theorem 5. Since
$\Delta(\rho,\mathcal{P}(\rho))\leq\delta+\gamma$, the Fuchs-van de graaf
inequality implies that $\mathrm{F}(\rho,\mathcal{P}(\rho))\geq
1-2\delta-2\gamma$. Similarly, $\mathrm{F}(\sigma,\mathcal{P}(\sigma))\geq
1-2\delta-2\gamma$. Hence $f(\mathcal{P})\leq 2\delta+2\gamma$. Now, for the
given ensemble, $r(a)=\frac{1}{2}p(a)+\frac{1}{2}q(a)$. Then,

$\displaystyle 1-\lambda$ $\displaystyle=$
$\displaystyle\sum_{a}r(a)\,\mathrm{Tr}(|a\rangle\langle
a|\cdot\mathcal{P}(|a\rangle\langle a|))$ $\displaystyle=$
$\displaystyle\sum_{i,j=1}^{u+1}\sum_{a\in
T_{i,j}}r(a)\,\mathrm{Tr}\left(|a\rangle\langle
a|\cdot\left(\sum_{a^{\prime}\in T_{i,j}}\frac{|a^{\prime}\rangle\langle
a^{\prime}|}{|T_{i,j}|}\right)\right)$ $\displaystyle=$
$\displaystyle\sum_{i,j=1}^{u+1}\sum_{a\in
T_{i,j}}r(a)\cdot\frac{1}{|T_{i,j}|}\leq\max_{a^{\prime}}\,r(a^{\prime})\cdot\sum_{i,j=1}^{u+1}\sum_{a\in
T_{i,j}}\frac{1}{|T_{i,j}|}$ $\displaystyle=$
$\displaystyle\max_{a^{\prime}}\,r(a^{\prime})\cdot(u+1)^{2}\leq\frac{4\log^{2}\frac{d}{\gamma}}{\delta^{2}}\cdot\max_{a^{\prime}}\,r(a^{\prime}).$

Suppose $p$ and $q$ are the uniform and the staircase distributions (Figure
1). That is, $p(a)=\frac{1}{d}$ for all $a$ and
$q(a)=\frac{2(d-a+1)}{d(d+1)}=\frac{2}{d}-\frac{2a}{d(d+1)}$ (note that these
distributions have no redundant part). Then $\max_{a}r(a)\leq\frac{3}{2d}$,
which leads to $1-\lambda\leq\frac{6\log^{2}\frac{d}{\gamma}}{d\delta^{2}}$.
This gives us
$g(\mathcal{P})\geq\lambda\log(d{-}1)\geq\log(d{-}1)-\frac{6\log^{3}\frac{d}{\gamma}}{d\delta^{2}}$.
If $\delta=\gamma=\frac{\log^{2}d}{\sqrt{d}},$ then
$g(\mathcal{P})\geq\log(d{-}1)-\frac{20}{\log(d)}$ and
$f(\mathcal{P})\leq\frac{4\log^{2}d}{\sqrt{d}}$. So, $g(\mathcal{P})$ is close
to $\log d$, even when $f(\mathcal{P})\approx\frac{1}{\sqrt{d}}$.