A limit relation for entropy and channel capacity per unit cost
A limit relation for entropy
and channel capacity per unit cost
Imre Csiszár1,4, Fumio Hiai2,5 and Dénes Petz3,4
4 Alfréd Rényi Institute of Mathematics,
H-1364 Budapest, POB 127, Hungary
5 Graduate School of Information Sciences, Tohoku University
Aoba-ku, Sendai 980-8579, Japan
Abstract: In a quantum mechanical model, Diósi, Feldmann and Kosloff
arrived at a conjecture stating that the limit of the entropy of certain mixtures
is the relative entropy as system size goes to infinity. The conjecture is
proven in this paper for density matrices. The first proof is analytic and uses
the quantum law of large numbers. The second one clarifies the relation to
channel capacity per unit cost for classical-quantum channels. Both proofs
lead to generalizations of the conjecture.
Key words: Shannon entropy, von Neumann entropy, relative entropy, ca-
pacity per unit cost, Holevo bound.
1E-mail: csiszar@renyi.hu. Partially supported by the Hungarian Research Grant OTKA T068258.
2E-mail: hiai@math.is.tohoku.ac.jp. Partially supported by Grant-in-Aid for Scientific Research
(B)17340043.
3E-mail: petz@math.bme.hu. Partially supported by the Hungarian Research Grant OTKAT068258.
http://arxiv.org/abs/0704.0046v1
1 Introduction
It was conjectured by Diósi, Feldmann and Kosloff in [4], based on thermodynamical
considerations, that the von Neumann entropy of a quantum state equal to a mixture
Rn :=
σ ⊗ ρ⊗(n−1) + ρ⊗ σ ⊗ ρ⊗(n−2) + · · · + ρ⊗(n−1) ⊗ σ
exceeds the entropy of a component asymptotically by the Umegaki relative entropy
S(σ‖ρ), that is,
S(Rn) − (n− 1)S(ρ) − S(σ) → S(σ‖ρ) (1)
as n → ∞. Here ρ and σ are density matrices acting on a finite dimensional Hilbert
space. Recall that S(σ) = −Tr σ log σ and
S(σ‖ρ) =
Tr σ(log σ − log ρ) if supp σ ≤ supp ρ
+∞ otherwise.
Concerning the background of quantum entropy quantities, we refer to [10, 12].
Apparently no exact proof of (1) has been published even for the classical case, al-
though for that case a heuristic proof is offered in [4].
In the paper first an analytic proof of (1) is given for the case supp σ ≤ supp ρ, using
an inequality between the Umegaki and the Belavkin-Staszewski relative entropies, and
the weak law of large numbers in the quantum case. In the second part of the paper, it
is clarified that the problem is related to the theory of classical-quantum channels. The
essential observation is the fact that S(Rn) − (n− 1)S(ρ) − S(σ) in the conjecture is a
Holevo quantity (classical-quantum mutual information) for a certain channel for which
the relative entropy emerges as the capacity per unit cost.
The two different proofs lead to two different generalizations of the conjecture.
2 An analytic proof of the conjecture
In this section we assume that supp σ ≤ supp ρ for the support projections of σ and ρ.
One can simply compute:
S(Rn‖ρ
⊗n) = Tr(Rn logRn − Rn log ρ
= −S(Rn) − (n− 1)Tr ρ log ρ− Trσ log ρ.
Hence the identity
S(Rn‖ρ
⊗n) = −S(Rn) + (n− 1)S(ρ) + S(σ‖ρ) + S(σ)
holds. It follows that the conjecture (1) is equivalent to the statement
S(Rn‖ρ
⊗n) → 0 as n → ∞
when supp σ ≤ supp ρ.
Recall the Belavkin-Staszewski relative entropy
SBS(ω‖ρ) = Tr(ω log(ω
1/2ρ−1ω1/2)) = −Tr(ρ η(ρ−1/2ωρ−1/2))
if suppω ≤ supp ρ, where η(t) := −t log t, see [1, 10]. It was proved by Hiai and Petz
S(ω‖ρ) ≤ SBS(ω‖ρ), (2)
see [6], or Proposition 7.11 in [10].
Theorem 1. If supp σ ≤ supp ρ, then S(Rn)− (n−1)S(ρ)−S(σ) → S(σ‖ρ) as n → ∞.
Proof: We want to use the quantum law of large numbers, see Proposition 1.17 in
[10]. Assume that ρ and σ are d × d density matrices and we may suppose that ρ is
invertible. Due to the GNS-construction with respect to the limit ϕ∞ of the product
states ϕn(A) = Tr ρ
⊗nA on the n-fold tensor product Md(C)
⊗n, n ∈ N, all finite tensor
products Md(C)
⊗n are embedded into a von Neumann algebra M acting on a Hilbert
space H. If γ denotes the right shift and X := ρ−1/2σρ−1/2, then Rn is written as
Rn = (ρ
1/2)⊗n
γi(X)
(ρ1/2)⊗n.
By inequality (2), we get
0 ≤ S(Rn‖ρ
⊗n) ≤ SBS(Rn‖ρ
= −Tr
ρ⊗n η
(ρ−1/2)⊗nRn(ρ
−1/2)⊗n
γi(X)
, (3)
where Ω is the cyclic vector in the GNS-construction.
The law of large numbers gives
γi(X) → I
in the strong operator topology in B(H), since ϕ(X) = Tr ρρ−1/2σρ−1/2 = 1.
Since the continuous functional calculus preserves the strong convergence (simply due
to approximation by polynomials on a compact set), we obtain
γi(X)
→ η(I) = 0 strongly.
This shows that the upper bound (3) converges to 0 and the proof is complete.
By the same proof one can obtain that for
Rm,n :=
σ⊗m ⊗ ρ⊗(n−1) + ρ⊗ σ⊗m ⊗ ρ⊗(n−2) + · · · + ρ⊗(n−1) ⊗ σ⊗m
the limit relation
S(Rm,n) − (n− 1)S(ρ) −mS(σ) → mS(σ‖ρ) (4)
holds as n → ∞ when m is fixed.
In the next theorem we treat the probabilistic case in a matrix language. The proof
includes the case when supp σ ≤ supp ρ is not true. Those readers who are not familiar
with the quantum setting of the previous theorem are suggested to follow the arguments
below.
Theorem 2. Assume that ρ and σ are commuting density matrices. Then S(Rn)− (n−
1)S(ρ) − S(σ) → S(σ‖ρ) as n → ∞.
Proof: We may assume that ρ = Diag(µ1, . . . , µℓ, 0, . . . , 0) and σ = Diag(λ1, . . . , λd)
are d×d diagonal matrices, µ1, . . . , µℓ > 0 and ℓ < d. (We may consider ρ, σ in a matrix
algebra of bigger size if ρ is invertible.) If supp σ ≤ supp ρ, then λℓ+1 = · · · = λd = 0;
this will be called the regular case. When supp σ ≤ supp ρ is not true, we may assume
that λd > 0 and we refer to the singular case.
The eigenvalues of Rn correspond to elements (i1, . . . , in) of {1, . . . , d}
(λi1µi2 · · ·µin + µi1λi2µi3 · · ·µin + · · · + µi1 · · ·µin−1λin). (5)
We divide the eigenvalues in three different groups as follows:
(a) A corresponds to (i1, . . . , in) ∈ {1, . . . , d}
n with 1 ≤ i1, . . . , in ≤ ℓ,
(b) B corresponds to (i1, . . . , in) ∈ {1, . . . , d}
n which contains exactly one d,
(c) C is the rest of the eigenvalues.
If the eigenvalue (5) is in group A, then it is
(λi1/µi1) + · · · + (λin/µin)
µi1µi2 · · ·µin .
First we compute
η(κ) =
i1,...,in
(λi1/µi1) + · · · + (λin/µin)
µi1 · · ·µin
Below the summations are over 1 ≤ i1, . . . , in ≤ ℓ:
i1,...,in
(λi1/µi1) + · · · + (λin/µin)
µi1 · · ·µin
i1,...,in
(λi1/µi1) + · · · + (λin/µin)
µi1 · · ·µin
log(µi1 · · ·µin) + Qn
i1,...,in
λi1µi2 · · ·µin log µik +
i1,...,in
λi1µi2 · · ·µin logµik
+ · · · +
i1,...,in
λi1µi2 · · ·µin log µik
(n− 1)
µik logµik +
λik logµik
= (n− 1)S(ρ) −
λi logµi + Qn,
where
Qn :=
i1,...,in
(µi1 · · ·µin)η
(λi1/µi1) + · · · + (λin/µin)
Consider a probability space
(Ω,P) :=
{1, . . . , ℓ}N, (µ1, . . . , µℓ)
where (µ1, . . . , µℓ)
N is the product of the measure on {1, . . . , ℓ} with the distribution
(µ1, . . . , µℓ). For each n ∈ N let Xn be a random variable on Ω depending on the
nth {1, . . . , ℓ} so that the value of Xn at i ∈ {1, . . . , ℓ} is λi/µi. Then X1, X2, . . . are
identically distributed independent random variables and Qn is the expectation value of
X1 + · · · + Xn
The strong law of large numbers says that
X1 + · · · + Xn
→ E(X1) =
λi almost surely.
Since η((X1 + · · · + Xn)/n) is uniformly bounded, the Lebesgue bounded convergence
theorem implies that
Qn → η
as n → ∞.
In the regular case
i=1 λi = 1, Qn → 0 and all non-zero eigenvalues are in group A.
Hence we have
S(Rn) − (n− 1)S(ρ) − S(σ) = −
λi logµi +
λi log λi + Qn = S(σ‖ρ) + Qn
and the statement is clear.
Next we consider the singular case, when we have
η(κ) = (n− 1)S(ρ) + O(1),
and we turn to eigenvalues in B. If the eigenvalue corresponding to (i1, . . . , in) ∈
{1, . . . , d}n is in group B and i1 = d, then the eigenvalue is
λdµi2 . . . µin .
It follows that
i2,...,in
(λdµi2 · · ·µin
(λdµi2 · · ·µin
i2,...,in
(µi2 · · ·µin) log(µi2 · · ·µin) −
(n− 1)S(ρ) −
When i2 = d, . . . , in = d, we get the same quantity, so this should be multiplied with n:
η(κ) = λd(n− 1)S(ρ) − λd log
We make a lower estimate to the entropy of Rn in such a way that we compute
κ η(κ)
when κ runs over A and B. It is clear now that
S(Rn) − (n− 1)S(ρ) − S(σ) ≥
η(κ) +
η(κ) − (n− 1)S(ρ) − S(σ)
≥ λd(n− 1)S(ρ) + λd log n + O(1) → +∞
as n → ∞.
3 Interpretation as capacity
A classical-quantum channel with classical input alphabet X transfers the input x ∈ X
into the output W (x) ≡ ρx which is a density matrix acting on a Hilbert space K. We
restrict ourselves to the case when X is finite and K is finite dimensional.
If a classical random variable X is chosen to be the input, with probability distribution
P = {p(x) : x ∈ X}, then the corresponding output is the quantum state ρX :=
x∈X p(x)ρx. When a measurement is performed on the output quantum system, it
gives rise to an output random variable Y which is jointly distributed with the input X .
If a partition of unity {Fy : y ∈ X} in B(K) describes the measurement, then
Prob(Y = y |X = x) = Tr ρxFy (x, y ∈ X ). (6)
According to the Holevo bound, we have
I(X ∧ Y ) := H(Y ) −H(Y |X) ≤ I(X,W ) := S(ρX) −
p(x)S(ρx), (7)
which is actually a simple consequence of the monotonicity of the relative entropy un-
der state transformation [7], see also [11]. I(X,W ) is the so-called Holevo quantity or
classical-quantum mutual information, and it satisfies the identity
p(x)S(ρx‖ρ) = I(X,W ) + S(ρX‖ρ), (8)
where ρ is an arbitrary density.
The channel is used to transfer sequences from the classical alphabet; x = (x1, x2, . . . , xn) ∈
X n is transferred into the quantum state W⊗n(x) = ρx := ρx1⊗ρx2⊗. . .⊗ρxn . A code for
the channel W⊗n is defined by a subset An ⊂ X
n, which is called a codeword set. The de-
coder is a measurement {Fy : y ∈ X
n}. The probability of error is Prob(X 6= Y ), where
X is the input random variable uniformly distributed on An and the output random
variable is determined by (6), where x and y are replaced by x and y.
The essential observation is the fact that S(Rn)−(n−1)S(ρ)−S(σ) in the conjecture
is a Holevo quantity in case of a channel with input sequences (x1, x2, . . . , xn) ∈ {0, 1}
and outputs ρx1 ⊗ ρx2 ⊗ . . . ⊗ ρxn, where ρ0 = σ, ρ1 = ρ and the codewords are all
sequences containing exactly one 0. More generally, we shall consider Holevo quantities
I(A, ρ0, ρ1) := S
S(ρx).
defined for any set A ⊂ {0, 1}n of binary sequences of length n.
The concept related to the conjecture we study is the channel capacity per unit cost
which is defined next for simplicity only in the case where X = {0, 1}, the cost of a
character 0 ∈ X is 1, while the cost of 1 ∈ X is 0.
For a memoryless channel with a binary input alphabet X = {0, 1} and an ε > 0, a
number R > 0 is called an ε-achievable rate per unit cost if for every δ > 0 and for any
sufficiently large T , there exists a code of length n > T with at least eT (R−δ) codewords
such that each of the codewords contains at most T 0’s and the error probability is at
most ε. The largest R which is an ε-achievable per unit cost for every ε > 0 is the
channel capacity per unit cost.
Lemma 1. For an arbitrary A ⊂ {0, 1}n,
I(A, ρ0, ρ1) ≤ c(A)S(ρ0‖ρ1)
holds, where
c(A) :=
|{i : xi = 0}|.
Proof: Let c(x) := |{i : xi = 0}| for x ∈ A. Since I(A, ρ0, ρ1) is a particular Holevo
quantity I(X,W⊗n), we can use the identity (8) to get an upper bound
S(ρx‖ρ
1 ) =
c(x)S(ρ0‖ρ1) = c(A)S(ρ0‖ρ1)
for I(A, ρ0, ρ1).
Lemma 2. If A ⊂ {0, 1}n is a code of the channel W⊗n, whose probability of error (for
some decoding scheme) does not exceed a given 0 < ε < 1, then
(1 − ε) log |A| − log 2 ≤ I(A, ρ0, ρ1).
Proof: The right-hand side is a bound for the classical mutual information I(X∧Y ) =
H(Y ) − H(Y |X), where Y is the channel output, see (7). Since the error probability
Prob(X 6= Y ) is smaller than ε, application of the Fano inequality (see [3]) gives
H(X|Y ) ≤ ε log |A| + log 2.
Therefore
I(X ∧ Y ) = H(X) −H(X|Y ) ≥ (1 − ε) log |A| − log 2,
and the proof is complete.
The above two lemmas shows that the relative entropy S(ρ0‖ρ1) is an upper bound
for the channel capacity per unit cost of the channel W (0) = ρ0 and W (1) = ρ1 with
a binary input alphabet. In fact, assume that R > 0 is an ε-achievable rate. For every
δ > 0 and T > 0 there is a code A ⊂ {0, 1}n for which we get by Lemmas 1 and 2
TS(ρ0‖ρ1) ≥ c(A)S(ρ0‖ρ1) ≥ I(A, ρ0, ρ1)
≥ (1 − ε) log |A| − log 2
≥ (1 − ε)T (R− δ) − log 2.
Since T is arbitrarily large and ε, δ are arbitrarily small, R ≤ S(ρ0‖ρ1) follows. That
S(ρ0‖ρ1) equals the channel capacity per unit cost will be verified below.
Theorem 3. Let the classical-quantum channel W : X = {0, 1} → B(K) be defined as
W (0) = ρ0 ≡ σ and W (1) = ρ1 ≡ ρ. Assume that An ⊂ {0, 1}
n is chosen such that
(a) each element x = (x1, x2, . . . , xn) ∈ An contains at most ℓ copies of 0,
(b) log |An|/ logn → c as n → ∞,
c(An) :=
|{i : xi = 0}| → c as n → ∞
for some real number c > 0 and for some natural number ℓ. If the random variable Xn
has a uniform distribution on An, then
S(ρXn) −
S(ρx)
= cS(σ‖ρ).
The proof of the theorem is divided into lemmas. We need the direct part of the
so-called quantum Stein lemma obtained in [6], see also [2, 5, 9, 12].
Lemma 3. Let ρ0 and ρ1 be density matrices. For every η > 0 and 0 < R < S(ρ0‖ρ1),
if N is sufficiently large, then there is a projection E ∈ B(K⊗N) such that
αN [E] := Tr ρ
0 (I − E) < η
and for βN [E] := Tr ρ
1 E the estimate
log βN [E] < −R
holds.
Note that αN is called the error of the first kind, while βN is the error of the second
kind.
Lemma 4. Assume that ε > 0, 0 < R < S(ρ0‖ρ1), ℓ is a positive integer and the
sequences x in An ⊂ {0, 1}
n contain at most ℓ copies of 0. Let the codewords be the
N-fold repetitions xN = (x,x, . . . ,x) of the sequences x ∈ An. If N is the integer part
and n is large enough, then there is a decoding scheme such that the error probability is
smaller than ε.
Proof: We follow the probabilistic construction in [13]. Let the codewords be the N -
fold repetitions xN = (x,x, . . . ,x) of the sequences x ∈ An. The corresponding output
density matrices act on the Hilbert space K⊗Nn ≡ (K⊗n)⊗N . We decompose this Hilbert
space into an N -fold product in a different way. For each 1 ≤ i ≤ n, let Ki be the
tensor product of the factors i, i + n, i + 2n, . . . , i + (N − 1)n. So K is identified with
K1 ⊗K2 ⊗ . . .⊗Kn.
For each 1 ≤ i ≤ n we perform a hypothesis testing on the Hilbert space Ki. The
0-hypothesis is that the ith component of the actually chosen x ∈ An is 0. Based on
the channel outputs at time instances i, i + n, . . . , i + (N − 1)n, the 0-hypothesis is
tested against the alternative hypothesis that the ith component of x is 1. According
to the quantum Stein lemma (Lemma 3), given any η > 0 and 0 < R < S(σ‖ρ), for N
sufficiently large, there exists a test Ei such that the probability of error of the first kind
is smaller than η, while the probability of error of the second kind is smaller than e−NR.
The projections Ei and I − Ei form a partition of unity in the Hilbert space Ki, and
the n-fold tensor product of these commuting projection will give a partition of unity in
K⊗Nn. Let y ∈ {0, 1}n and set Fy := ⊗
i=1Fyi , where Fyi = Ei if yi = 0 and Fyi = I −Ei
if yi = 1. Therefore, the result of decoding can be an arbitrary 0–1 sequence in {0, 1}
The decoding scheme gives y ∈ {0, 1}n in such a way that yi = 0 if the tests accepted
the 0-hypothesis for i and yi = 1 if the alternative was accepted. The error probability
should be estimated:
Prob(Y 6= X|X = x) =
y:y 6=x
Tr ρ⊗N
y:y 6=x
Tr ρ⊗Nxi Fyi
y:yi 6=xi
Tr ρ⊗Nxj Fyj ≤
Tr ρ⊗Nxi (I − Fxi).
If xi = 0, then
Tr ρ⊗Nxi (I − Fxi) = Tr ρ
0 (I −Ei) ≤ η,
because it is an error of the first kind. When xi = 1,
Tr ρ⊗Nxi (I − Fxi) = Tr ρ
1 Ei ≤ e
from the error of the second kind. It follows that ℓη + ne−NR is a bound for the error
probability. The first term will be small if η is small. The second term will be small
if N is large enough. If both terms are majorized by ε/2, then the statement of the
lemma holds. We can choose n so large that N defined by the statement should be large
enough.
Proof of Theorem 3: Since Lemma 1 gives an upper bound, that is,
lim sup
S(ρXn) −
S(ρx)
≤ cS(σ‖ρ),
it remains to prove that
lim inf
S(ρXn) −
S(ρx)
≥ cS(σ‖ρ).
Lemma 4 is about the N -times repeated input XN and describes a decoding scheme
with error probability at most ε. According to Lemma 2 we have
(1 − ε) log |An| − 1 ≤ S(ρXN ) −
S(ρxN ).
From the subadditivity of the entropy we have
S(ρXN ) ≤ NS(ρX)
S(ρxN ) = NS(ρx)
holds due to the additivity for product. It follows that
(1 − ε)
log |An|
≤ S(ρX) −
S(ρx).
From the choice of N in Lemma 4 we have
log |An|
log n
logn + log 2 − log ε
log |An|
and the lower bound is arbitrarily close to cR. Since R < S(ρ0‖ρ1) was arbitrary, the
proof is complete.
References
[1] V.P. Belavkin and P. Staszewski, C*-algebraic generalization of relative entropy and
entropy, Ann. Inst. Henri Poincaré, Sec. A 37(1982), 51–58.
[2] I. Bjelaković, J. Deuschel, T. Krüger, R. Seiler, R. Siegmund-Schultze and A. Szko la,
A quantum version of Sanov’s theorem, Comm. Math. Phys. 260(2005), 659–671.
[3] T. M. Cover and J. A. Thomas, Elements of Information Theory, Second edition,
Wiley-Interscience, Hoboken, NJ, 2006.
[4] L. Diósi, T. Feldmann and R. Kosloff, On the exact identity between thermodynamic
and informatic entropies in a unitary model of friction, Int. J. Quantum Information,
4(2006), 99–104.
[5] M. Hayashi, Quantum information. An introduction, Springer, 2006.
[6] F. Hiai and D. Petz, The proper formula for relative entropy and its asymptotics in
quantum probability, Comm. Math. Phys. 143(1991), 99–114.
[7] A.S. Holevo, Some estimates for the amount of information transmittable by a quan-
tum communication channel (in Russian), Problemy Peredachi Informacii, 9(1973),
3–11.
[8] M.A. Nielsen and I.L. Chuang, Quantum computation and quantum information,
Cambridge University Press, Cambridge, 2000.
[9] T. Ogawa and H. Nagaoka, Strong converse and Stein’s lemma in quantum hypoth-
esis testing, IEEE Tans. Inf. Theory 46(2000), 2428–2433.
[10] M. Ohya and D. Petz, Quantum Entropy and its Use, Springer, 1993.
[11] M. Ohya, D. Petz and N. Watanabe, On capacities of quantum channels, Prob.
Math. Stat. 17(1997), 179–196.
[12] D. Petz, Lectures on quantum information theory and quantum statistics, book
manuscript in preparation.
[13] S. Verdu, On channel capacity per unit cost, IEEE Trans. Inform. Theory 36(1990),
1019–1030.
	Introduction
	An analytic proof of the conjecture
	Interpretation as capacity
