# Analytical calculation formulas for capacities of classical and classical-
quantum channels

Masahito Hayashi Masahito Hayashi is with Shenzhen Institute for Quantum
Science and Engineering, Southern University of Science and Technology,
Nanshan District, Shenzhen, 518055, China, International Quantum Academy
(SIQA), Futian District, Shenzhen 518048, China, Guangdong Provincial Key
Laboratory of Quantum Science and Engineering, Southern University of Science
and Technology, Nanshan District, Shenzhen 518055, China, and Graduate School
of Mathematics, Nagoya University, Nagoya, 464-8602, Japan.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We derive an analytical calculation formula for the channel capacity of a
classical channel without any iteration while its existing algorithms require
iterations and the number of iteration depends on the required precision
level. Hence, our formula is its first analytical formula without any
iteration. We apply the obtained formula to examples and see how the obtained
formula works in these examples. Then, we extend it to the channel capacity of
a classical-quantum (cq-) channel. Many existing studies proposed algorithms
for a cq-channel and all of them require iterations. Our extended analytical
algorithm have also no iteration and output the exactly optimum values.

###### Index Terms:

mutual information, maximization, channel capacity, classical-quantum channel,
analytical algorithm

##  I Introduction

One of key problems in classical and quantum information theory is the
maximization of information quantities. However, it is not so easy to perform
such a maximization analytically because all of existing methods require a
certain iterations, whose number depends on the required precision level. The
most common maximization problem is the channel capacity, which is given as
the maximization of mutual information [5], and its calculation has been
studied by Arimoto [1], Blahut [2], and their related studies [6, 7, 8].
However, these are iterative approximation algorithms to calculate the maximum
of the mutual information. In addition, the reference [3] calculated only its
upper bound and the references [23, 9] developed other type of method to
approximately calculate it. Hence, they cannot calculate the exact value for
the channel capacity. As variants, the references [13, 24] extended the above
method to the wire-tap capacity [11, 12] when the wire-tap channel is
degraded. Also, the references [14, 15, 16, 17, 18] extended it to the quantum
setting, so called the capacity of classical-quantum channel. However, these
results are also iterative approximation algorithms.

This paper proposes an algorithm to analytically calculate the channel
capacity of the classical channel without iteration. The proposed algorithm is
composed of solving simultaneous linear equations and calculation of
calculation of logarithm and exponential because it employs an information-
geometrical structure. However, the proposed method works under certain
conditions. Since our method is analytical, we can derive several analytical
formula for the capacity when these conditions are satisfied. Then, to see
this possibility, we apply our algorithm to several examples, and derives
analytical expressions of the capacities in these examples. Further, we extend
our analytical algorithm to the calculations of the capacity of classical-
quantum channel.

The remaining part of this paper is organized as follows. First, Section II
derives our algorithm for the capacity of a classical channel. Section III
applies the obtained result to several examples. Next, Section IV extends this
method to the capacity of classical-quantum channel. Finally, Section V
discusses the merit and the demerit of our method over existing methods.

##  II Capacity of classical channel

We consider the input and output alphabets
${\mathcal{X}}:=\\{1,\ldots,n_{1}\\}$ and
${\mathcal{Y}}:=\\{1,\ldots,n_{2}\\}$ that are finite sets. We denote the sets
of probability distributions on ${\mathcal{X}}$ and ${\mathcal{Y}}$ by ${\cal
P}_{{\mathcal{X}}}$ and ${\cal P}_{{\mathcal{Y}}}$, respectively. For
distributions $P,Q\in{\cal P}_{{\mathcal{X}}}$, the entropy $H(P)$ and the
divergence $D(P\|Q)$ are defined as

$\displaystyle H(P):=$ $\displaystyle-\sum_{x\in{\mathcal{X}}}P(x)\log P(x),$
(1) $\displaystyle D(P\|Q):=$
$\displaystyle\sum_{x\in{\mathcal{X}}}P(x)\log\frac{P(x)}{Q(x)}.$ (2)

A channel from ${\mathcal{X}}$ to ${\mathcal{Y}}$ is given as conditional
distribution on ${\mathcal{Y}}$ conditioned with ${\mathcal{X}}$. That is,
using the notation $W_{x}(y):=W(y|x)$, it can be considered as a map
$W:{\mathcal{X}}\rightarrow{\cal P}_{{\mathcal{Y}}}$. For $Q_{X}\in{\cal
P}_{{\mathcal{X}}}$ and $Q_{Y}\in{\cal P}_{{\mathcal{Y}}}$, $W\cdot
Q_{X}\in{\cal P}_{{\mathcal{Y}}}$, $W\times Q_{X}\in{\cal
P}_{{\mathcal{X}}\times{\mathcal{Y}}}$, and $Q_{X}\times
Q_{Y}\in\mathcal{P}_{{\mathcal{X}}\times{\mathcal{Y}}}$ are defined by
$(W\cdot Q_{X})(x,y):=\sum_{x\in{\mathcal{X}}}W(y|x)Q_{X}(x)$, $(W\times
Q_{X})(x,y):=W(y|x)Q_{X}(x)$, and $(Q_{Y}\times Q_{X})(x,y):=Q_{X}(x)Q_{Y}(y)$
respectively.

The channel capacity of a channel $W$ is given by [5], [26, p.124]

$\displaystyle C(W):=$ $\displaystyle\max_{Q_{X}\in{{\cal
P}_{{\mathcal{X}}}}}\sum_{x\in{\mathcal{X}}}Q_{X}(x)D(W_{x}\|W\cdot Q_{X})$
$\displaystyle=$ $\displaystyle\min_{Q_{Y}\in{\cal
P}_{{\mathcal{Y}}}}\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y})$ $\displaystyle=$
$\displaystyle\min_{Q_{X}\in{\cal
P}_{{\mathcal{X}}}}\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot Q_{X}).$ (3)

To discuss $C(W)$, we assume the following conditions.

(A)

$W_{1},\ldots,W_{n_{1}}$ are linearly independent.

Then, we have the following;

###### Lemma 1

Assume Condition (A). When a distribution $Q_{Y}=W\cdot Q_{X}$ realizes the
maximum in (3), it satisfies the following condition; $D(W_{x}\|Q_{Y})$ does
not depend on $x\in\mathop{\rm supp}(Q_{X})$.

Lemma 1 is shown in Appendix B. We define the set ${\cal M}_{0}$ as

$\displaystyle{\cal
M}_{0}:=\Big{\\{}Q_{Y}\in{\mathcal{P}}_{{\mathcal{Y}}}\Big{|}Q_{Y}=\sum_{x\in{\mathcal{X}}}c(x)W_{x},\quad\sum_{x\in{\mathcal{X}}\setminus{\mathcal{X}}_{0}}c(x)=1\Big{\\}}.$
(4)

Due to Condition (A), only one distribution $Q_{Y}\in{\cal M}_{0}$ satisfies
the following condition;

(B)

$D(W_{x}\|Q_{Y})$ does not depend on $x\in{\mathcal{X}}$.

In the following, we denote the element of ${\cal M}_{0}$ to satisfy the
condition (B) by $Q_{Y,*}$. Since $Q_{Y,*}$ belongs to ${\cal M}_{0}$, there
exists a function $\hat{Q}_{X,*}$ on ${\mathcal{X}}$ as the solution of the
following equation;

$\displaystyle\sum_{x\in{\mathcal{X}}}W(y|x)\hat{Q}_{X,*}(x)=Q_{Y,*}(y).$ (5)

Condition (A) guarantees the uniqueness of $\hat{Q}_{X,*}$. We have the
following theorem;

###### Theorem 1

Assume Condition (A). The following conditions are equivalent

(i)

The relation $D(W_{x}\|Q_{Y,*})=C(W)$ holds.

(ii)

The function $\hat{Q}_{X,*}$ satisfies the condition

$\displaystyle\hat{Q}_{X,*}(x)\geq 0\hbox{ for }x\in{\mathcal{X}}.$ (6)

Theorem 1 is shown in Appendix C

Hence, under the condition (ii), the capacity $C(W)$ is given by
$D(W_{x}\|Q_{Y,*})$. To consider the case that the condition (ii) does not
hold, we prepare the following theorem. For any function $f$ on
${\mathcal{X}}$, we define ${\cal N}(f):=\\{x\in{\mathcal{X}}|f(x)<0\\}$ and
${\cal N}^{c}(f):=\\{x\in{\mathcal{X}}|f(x)\geq 0\\}$.

###### Theorem 2

Assume Condition (A). Then, we have

$\displaystyle C(W)=\max_{Q_{X}\in{{\cal P}_{{\cal
N}^{c}(\hat{Q}_{X,*})}}}\sum_{x\in{\cal
N}^{c}(\hat{Q}_{X,*})}Q_{X}(x)D(W_{x}\|W\cdot Q_{X}).$ (7)

Theorem 2 is shown in Appendix D. Therefore, the capacity $C(W)$ is obtained
only with the input set ${\cal N}^{c}(\hat{Q}_{X,*})$. That is, the function
$\hat{Q}_{X,*}$ gives an important information for computing $C(W)$.

We choose $n_{2}-1$ linearly independent functions $f_{1},\ldots,f_{n_{2}-1}$
on ${\mathcal{Y}}$ such that

$\displaystyle\sum_{y\in{\mathcal{Y}}}W_{n_{2}}(y)f_{j}(y)=0$ (8)

for $j=1,\ldots,n_{2}-1$. We define the matrix $(h_{i,j})$

$\displaystyle h_{i,j}:=\sum_{y\in{\mathcal{Y}}}W_{i}(y)f_{j}(y).$ (9)

Given an $n_{2}-1$-dimensional parameter
$\theta=(\theta^{1},\ldots,\theta^{n_{2}-1})$, we define the distribution
$P_{\theta,Y}$ as

$\displaystyle
P_{\theta,Y}(y)=e^{\sum_{j=1}^{n_{2}-1}f_{j}(y)\theta^{j}-\phi(\theta)},$ (10)

where

$\displaystyle\phi(\theta):=\log\Big{(}\sum_{y\in{\mathcal{Y}}}e^{\sum_{j=1}^{n_{2}-1}f_{j}(y)\theta^{j}}\Big{)}.$
(11)

The parameterization (10) is called the natural parameter [4].

We have the following theorem.

###### Theorem 3

Assume that the parameters $\theta^{1},\ldots,\theta^{n_{2}-1}$ satisfies the
condition

$\displaystyle\sum_{j=1}^{n_{2}-1}h_{i,j}\theta^{j}=-H(W_{i})+H(W_{n_{2}}).$
(12)

Then, we have

$\displaystyle D(W_{x}\|P_{\theta,Y})=\phi(\theta)-H(W_{n_{2}}).$ (13)

for $x\in{\mathcal{X}}$.

Proof:  The condition (12) implies that

$\displaystyle\sum_{y\in{\mathcal{Y}}}W_{i}(y)\sum_{j=1}^{n_{2}-1}f_{j}(y)\theta^{j}=$
$\displaystyle\sum_{j=1}^{n_{2}-1}h_{i,j}\theta^{j}$ $\displaystyle=$
$\displaystyle-H(W_{i})+H(W_{n_{2}}).$ (14)

For $x(\neq n_{2})\in{\mathcal{X}}$, we have

$\displaystyle
D(W_{x}\|P_{\theta,Y})=\sum_{y\in{\mathcal{Y}}}W_{x}(y)\big{(}\log
W_{x}(y)-\log P_{\theta,Y}(y)\big{)}$ $\displaystyle=$
$\displaystyle-H(W_{x})-\sum_{y\in{\mathcal{Y}}}W_{x}(y)\Big{(}\sum_{j=1}^{n_{2}-1}f_{j}(y)\theta^{j}-\phi(\theta)\Big{)}$
$\displaystyle=$
$\displaystyle-H(W_{x})-\Big{(}-H(W_{x})+H(W_{n_{2}})-\phi(\theta)\Big{)}$
$\displaystyle=$ $\displaystyle\phi(\theta)-H(W_{n_{2}}).$ (15)

Also, we have

$\displaystyle
D(W_{n}\|P_{\theta,Y})=\sum_{y\in{\mathcal{Y}}}W_{n_{2}}(y)(\log
W_{n_{2}}(y)-\log P_{\theta,Y}(y))$ $\displaystyle=$
$\displaystyle-H(W_{n_{2}})-\sum_{y\in{\mathcal{Y}}}W_{x}(y)\Big{(}\sum_{j=1}^{n_{2}-1}f_{j}(y)\theta^{j}-\phi(\theta)\Big{)}$
$\displaystyle=$
$\displaystyle-H(W_{n_{2}})-\big{(}-\phi(\theta)\big{)}=\phi(\theta)-H(W_{n_{2}}).$
(16)

We define the set ${\cal E}_{0}$ as

$\displaystyle{\cal E}_{0}:=\\{P_{\theta,Y}|\hbox{ The condition \eqref{MXP}
holds.}\\}$ (17)

###### Lemma 2

The set ${\cal M}_{0}\cap{\cal E}_{0}$ is composed of one element
$P_{\theta_{*},Y}$.

Lemma 2 is shown in Appendix E. Therefore, $P_{\theta_{*},Y}$ equals
$Q_{Y,*}$.

Now, we assume the following condition (Condition (C)).

(C)

$n_{1}=n_{2}$ and $W_{1},\ldots,W_{n_{1}}$ are linearly independent.

Then, only one set of parameters $\theta^{1},\ldots,\theta^{n_{2}-1}$
satisfies the condition (12). Due to Theorem 3, solving the equation (12), we
find $Q_{Y,*}$ as $P_{\theta,Y}$. To construct our algorithm, we add the
$n_{2}$-th function $f_{n_{2}}$ on ${\mathcal{Y}}$ and define $h_{i,j}$ by (9)
for $i,j=1,\ldots,n_{2}$. We rewrite the equation (5) as

$\displaystyle\sum_{x\in{\mathcal{X}}}\hat{Q}_{X,*}(x)h_{x,j}=$
$\displaystyle\sum_{x\in{\mathcal{X}}}\hat{Q}_{X,*}(x)\sum_{y\in
Y}W_{x}(y)f_{j}(y)$ $\displaystyle=$
$\displaystyle\sum_{y\in{\mathcal{Y}}}P_{\theta,Y}(y)f_{j}(y).$ (18)

We obtain the function $\hat{Q}_{X,*}$ on ${\mathcal{X}}$ as the solution of
(18), and $W\cdot\hat{Q}_{X,*}=Q_{Y,*}$ satisfies the condition (B). When the
function $\hat{Q}_{X,*}$ satisfies the condition (6), the value
$D(W_{x}\|P_{\theta,Y})$ is the capacity of the channel $W$ due to Theorem 3.
Therefore, we have Algorithm 1 to compute $C(W)$ under Condition (C).

In fact, $(W_{i}(j))_{i,j}$ and $(f_{j}(i))_{i,j}$ form $n_{2}\times n_{2}$
matrices. When $(f_{j}(i))_{i,j}$ is the inverse matrix of $(W_{i}(j))_{i,j}$,
$(h_{i,j})_{i,j}$ is the identity matrix. Due to Theorem 1, Theorem 3 does not
necessarily work for calculating $C(W)$. Hence, based on Theorems 1 and 3, we
propose Algorithm 1 to check the condition in Theorem 1 and output compute
$C(W)$ under this condition.

In Algorithm 1, Step 1 has calculation complexity $O(n_{2}^{3})$. Steps 2 and
3 have calculation complexity $O(n_{2}^{2})$ because $h_{i,j}$ is an upper
triangle matrix. Step 5 has calculation complexity $O(n_{2}^{2})$. Hence, the
total calculation complexity is $O(n_{2}^{3})$.

Algorithm 1 Exact algorithm for classical channel capacity

Step 1: Choose $f_{1},\ldots,f_{n_{2}}$ such that $(f_{j}(i))_{i,j}$ is the
inverse matrix of $(W_{i}(j))_{i,j}$. Hence, $h_{i,j}=\delta_{i,j}$.

Step 2: Set the parameter $\theta^{i}=-H(W_{i})+H(W_{n_{2}})$ for
$i=1,\ldots,n_{2}-1$, which is the solution of (12).

Step 3: Calculate $\phi(\theta)$ by using (11).

Step 4: Calculate
$\hat{Q}_{X,*}(x):=\sum_{y\in{\mathcal{Y}}}P_{\theta,Y}(y)f_{x}(y)$, where
$P_{\theta,Y}(y)$ is calculated by (10). This step follows from (18).

Step 5: If the condition (6) holds, we consider that the condition in Theorem
1 holds and output $\phi(\theta)-H(W_{n})$ as the capacity. Otherwise, we
consider that the condition in Theorem 1 does not hold and output “the
capacity cannot be computed.”

Next, instead of Condition (C), we consider the following condition.

(C’)

The relation $n_{1}\geq n_{2}$ holds. Any $n_{2}$ elements among
$W_{1},\ldots,W_{n_{1}}$ are linearly independent.

Under this condition, we choose $n_{2}$ elements $x_{1},\ldots,x_{n_{2}}$ in
${\mathcal{X}}$ so that we can apply Algorithm 1. If the capacity is
calculated, it is denoted by $C(W;x_{1},\ldots,x_{n_{2}})$.

In this case, we need to try ${n_{1}\choose n_{2}}$ combinations, which
requires too large calculation amount. However, it is possible to avoid such
repetition as follows. First, we apply the conventional iterative algorithm by
[1, 2] or the improved iterative algorithm by [8]. Then, we obtain an
approximately optimal input distribution. If the distribution has the majority
of the probability in $n_{2}$ elements of ${\mathcal{X}}$, we apply Algorithm
1 to the case when ${\mathcal{X}}$ is the above $n_{2}$ elements. In this
case, we do not need ${n_{1}\choose n_{2}}$ repetitions. That is, the above
hybrid method works for exact calculation.

However, if $C(W;x_{1},\ldots,x_{n_{2}})$ depends on the choice of $n_{2}$
elements $x_{1},\ldots,x_{n_{2}}$, and the difference is very small, this idea
does not work. In this case, it is expected that the approximately optimal
input distribution the majority of the probability in more than $n_{2}$
elements of ${\mathcal{X}}$. Hence, the above method does not work.

Also, even under Condition (C’), there is the case that the support of the
optimal input distribution is composed of a smaller element than $n_{2}$. In
this case, even when we apply Algorithm 1 for ${n_{1}\choose n_{2}}$
combinations, we cannot obtain the capacity.

When only Condition (A) holds, $Q_{Y,*}$ can be characterized as follows.

###### Theorem 4

Assume that $h_{i,j}=0$ for $j=n_{1}+,\ldots,n_{2}-1$ and the parameters
$\theta^{1},\ldots,\theta^{n_{1}-1}$ satisfies the condition (9). When the
parameters $\theta^{n_{1}},\ldots,\theta^{n_{2}-1}$ are given as

$\displaystyle(\theta^{n_{1}},\ldots,\theta^{n_{2}-1})=\mathop{\rm
argmin}\limits_{\eta^{n_{1}},\ldots,\eta^{n_{2}-1}}\phi(\theta^{1},\ldots,\theta^{n_{1}-1},\eta^{n_{1}},\ldots,\eta^{n_{2}-1}),$
(19)

we have $P_{\theta,Y}=Q_{Y,*}$.

Proof:  Since the objective function in (19), the parameters
$\theta^{n_{1}},\ldots,\theta^{n_{2}-1}$ achieves the minimum (19) if and only
if

$\displaystyle\frac{\partial\phi(\theta^{1},\ldots,\theta^{n_{2}-1})}{\partial\theta^{j}}=0\hbox{
for }j=n_{1},\ldots,n_{2}-1.$ (20)

The above condition is equivalent to

$\displaystyle\sum_{y\in{\mathcal{Y}}}f_{j}(y)P_{\theta,Y}(y)=0\hbox{ for
}j=n_{1},\ldots,n_{2}-1.$ (21)

Due to (183), when $\theta^{n_{1}},\ldots,\theta^{n_{2}-1}$ are given by (19),
$P_{\theta,Y}$ belongs to ${\cal M}_{0}$. Due to the uniqueness by Lemma 2, we
obtain the desired statement.

Theorem 4 guarantees that $Q_{Y,*}$ is given as the solution of the
minimization (19), which is a convex minimization. While the analytical
solution of (19) is difficult in general, it is possible in the following
case. We impose the following condition for the functions
$f_{n_{1}},\ldots,f_{n_{2}-1}$; (i) $f_{j}(y)$ takes non-zero value only with
two elements $y_{j},y_{j}^{\prime}\in{\mathcal{Y}}$ for
$j=n_{1}+,\ldots,n_{2}-1$. (ii) The sets $\\{y_{j},y_{j}^{\prime}\\}$ for
$j=n_{1}+,\ldots,n_{2}-1$ are disjoint with each other.

In this case, the relation (19), i.e., (20), can be simplified as

$\displaystyle
f_{j}(y_{j})e^{f_{j}(y_{j})\theta^{j}+\sum_{i=1}^{n_{1}-1}f_{i}(y_{j})\theta^{i}}+f_{j}(y_{j}^{\prime})e^{f_{j}(y_{j}^{\prime})\theta^{j}+\sum_{i=1}^{n_{1}-1}f_{i}(y_{j}^{\prime})\theta^{i}}=0$
(22)

for $j=n_{1}+,\ldots,n_{2}-1$. The equation (22) is solved as

$\displaystyle\theta^{j}=\frac{1}{f_{j}(y_{j})-f_{j}(y_{j}^{\prime})}(\sum_{i=1}^{n_{1}-1}(f_{i}(y_{j}^{\prime})-f_{i}(y_{j}))\theta^{i}+\log\frac{-f_{j}(y_{j}^{\prime})}{f_{j}(y_{j})})$
(23)

for $j=n_{1}+,\ldots,n_{2}-1$. Therefore, we can analytically calculate
$P_{\theta,Y}=Q_{Y,*}$ under the conditions (i) and (ii).

##  III Example

###  III-A Output system with two elements

First, we consider the case with $Y=\\{1,2\\}$. When ${\mathcal{X}}$ and the
channel $W$ satisfies Condition (C’) in this case, the method described after
Condition (C’) works well as follows. For any two elements $x_{1}\neq
x_{2}\in{\mathcal{X}}$, the channel only with two inputs $x_{1},x_{2}$ always
satisfies the condition (6) because $Q_{Y,*}$ is located between $W_{x_{1}}$
and $W_{x_{2}}$. Hence, the condition in Theorem 1 holds. Therefore, it is
sufficient to derive a general formula for the capacity when two elements in
${\mathcal{X}}$ are fixed.

Therefore, in the following, we consider the case with
${\mathcal{X}}=\\{1,2\\}$ and $Y=\\{1,2\\}$. We define the distributions
$W_{x}$ for $x\in{\mathcal{X}}$ by the following vector form;

$\displaystyle W_{1}:=$ $\displaystyle\left(\begin{array}[]{c}1-p\\\
p\end{array}\right),\quad W_{2}:=\left(\begin{array}[]{c}1-q\\\
q\end{array}\right).$ (28)

For simplicity, we assume that $q>p$. We define the $2\times 2$ matrix $V$ as
$V:=(W_{1},W_{1})$. The inverse matrix is

$\displaystyle V^{-1}=$
$\displaystyle\frac{1}{q-p}\left(\begin{array}[]{cc}q&q-1\\\
-p&1-p\end{array}\right)$ (31)

In this case, the parameter $\theta$ is one-dimensional and is solved to
$h(q)-h(p)$, where $h(p)$ is the binary entropy. Then, $\phi(\theta)$ is
calculated as

$\displaystyle\phi(\theta)=$
$\displaystyle\log(e^{\frac{q(h(q)-h(p))}{q-p}}+e^{\frac{-p(h(q)-h(p))}{q-p}})$
$\displaystyle=$
$\displaystyle\log(e^{\frac{q(h(q)-h(p))}{q-p}}(1+e^{\frac{-(q+p)(h(q)-h(p))}{q-p}}))$
$\displaystyle=$
$\displaystyle\frac{q(h(q)-h(p))}{q-p}+\log(1+e^{\frac{-(q+p)(h(q)-h(p))}{q-p}}).$
(32)

The capacity is calculated as

$\displaystyle C(W)=$ $\displaystyle\phi(\theta)-h(p)$ $\displaystyle=$
$\displaystyle\frac{ph(q)-qh(p)}{q-p}+\log(1+e^{\frac{-(q+p)(h(q)-h(p))}{q-p}}),$
(33)

which is a general capacity formula with ${\mathcal{X}}=\\{1,2\\}$ and
$Y=\\{1,2\\}$. Then,

$\displaystyle
P_{\theta,Y}=\left(\begin{array}[]{c}e^{\frac{q(h(q)-h(p))}{q-p}-\phi(\theta)}\\\
e^{\frac{-p(h(q)-h(p))}{q-p}-\phi(\theta)}\end{array}\right).$ (36)

Hence, the optimal input distribution is

$\displaystyle\hat{Q}_{X,*}=\left(\begin{array}[]{c}\frac{1}{q-p}\Big{(}q-e^{\frac{-p(h(q)-h(p))}{q-p}-\phi(\theta)}\Big{)}\\\
\frac{1}{q-p}\Big{(}-p+e^{\frac{-p(h(q)-h(p))}{q-p}-\phi(\theta)}\Big{)}\end{array}\right).$
(39)

###  III-B Output system with three elements

####  III-B1 General problem description

Next, we consider the case with $Y=\\{1,2,3\\}$. In this case, Algorithm 1
does not necessarily work even under the condition (C). Moreover, the method
described after Condition (C’) does not necessarily work even under the
condition (C’). To see such a case, we consider the following example with
${\mathcal{X}}=\\{1,2,3,4\\}$ and ${\mathcal{Y}}=\\{1,2,3\\}$ with
$\epsilon\in[0,1/2]$. We define the distributions $W_{x}$ for
$x\in{\mathcal{X}}$ by the following vector form;

$\displaystyle W_{1}:=$ $\displaystyle\left(\begin{array}[]{c}1-\epsilon\\\
0\\\ \epsilon\end{array}\right),\quad W_{2}:=\left(\begin{array}[]{c}0\\\
1-\epsilon\\\ \epsilon\end{array}\right)$ (46) $\displaystyle W_{3}:=$
$\displaystyle\left(\begin{array}[]{c}\frac{1}{2}\\\ \frac{1}{2}\\\
0\end{array}\right),\quad
W_{4}:=\left(\begin{array}[]{c}\frac{1}{2}-\epsilon\\\ \frac{1}{2}-\epsilon\\\
2\epsilon\end{array}\right).$ (53)

We define $3\times 3$ matrix $V_{j}$ for $j\in{\mathcal{X}}$ as
$V_{1}:=(W_{2},W_{3},W_{4})$, $V_{2}:=(W_{1},W_{3},W_{4})$,
$V_{3}:=(W_{1},W_{2},W_{4})$, $V_{4}:=(W_{1},W_{2},W_{3})$. Their inverse
matrices are

$\displaystyle V_{1}^{-1}=$
$\displaystyle\left(\begin{array}[]{ccc}-\frac{1}{1-\epsilon}&\frac{1}{1-\epsilon}&0\\\
\frac{3-2\epsilon}{2(1-\epsilon)}&\frac{1-2\epsilon}{2(1-\epsilon)}&\frac{-1+2\epsilon}{2\epsilon}\\\
\frac{1}{2(1-\epsilon)}&-\frac{1}{2(1-\epsilon)}&\frac{1}{2\epsilon}\\\
\end{array}\right)$ (57) $\displaystyle V_{2}^{-1}=$
$\displaystyle\left(\begin{array}[]{ccc}\frac{1}{1-\epsilon}&-\frac{1}{1-\epsilon}&0\\\
\frac{1-2\epsilon}{2(1-\epsilon)}&\frac{3-2\epsilon}{2(1-\epsilon)}&\frac{-1+2\epsilon}{2\epsilon}\\\
-\frac{1}{2(1-\epsilon)}&\frac{1}{2(1-\epsilon)}&\frac{1}{2\epsilon}\end{array}\right)$
(61) $\displaystyle V_{3}^{-1}=$
$\displaystyle\left(\begin{array}[]{ccc}\frac{3-2\epsilon}{2(1-\epsilon)}&\frac{1-2\epsilon}{2(1-\epsilon)}&-\frac{1-2\epsilon}{2\epsilon}\\\
\frac{1-2\epsilon}{2(1-\epsilon)}&\frac{3-2\epsilon}{2(1-\epsilon)}&-\frac{1-2\epsilon}{2\epsilon}\\\
-1&-1&\frac{1-\epsilon}{\epsilon}\end{array}\right)$ (65) $\displaystyle
V_{4}^{-1}=$
$\displaystyle\left(\begin{array}[]{ccc}\frac{1}{2(1-\epsilon)}&-\frac{1}{2(1-\epsilon)}&\frac{1}{2\epsilon}\\\
-\frac{1}{2(1-\epsilon)}&\frac{1}{2(1-\epsilon)}&\frac{1}{2\epsilon}\\\
1&1&\frac{-1+\epsilon}{\epsilon}\end{array}\right).$ (69)

Also, we have

$\displaystyle H(W_{1})=$ $\displaystyle H(W_{2})=h(\epsilon)$ (70)
$\displaystyle H(W_{3})=$ $\displaystyle\log 2,\quad
H(W_{4})=h(2\epsilon)+(1-2\epsilon)\log 2.$ (71)

When we apply Algorithm 1 to the three components in $V_{j}$, we denote
$\theta$, $\phi(\theta)$, $P_{\theta,Y}$, $\hat{Q}_{X,*}$, and
$\phi(\theta)-H(W_{n})$ by $\theta_{j}$, $\phi_{j}(\theta_{j})$, $P_{j,Y}$ and
$\hat{Q}_{j,X}$, and $C_{j}$, respectively. In the following, we discuss our
model dependently of the value of $j$.

####  III-B2 Case that $j=4$

First, we consider the case that $j=4$, i.e., the channel is composed of three
inputs $\\{1,2,3\\}$. Then, we have

$\displaystyle\theta_{4}=\left(\begin{array}[]{c}h_{4,\epsilon}\\\
h_{4,\epsilon}\end{array}\right)$ (74)

with $h_{4,\epsilon}:=\log 2-h(\epsilon)$ and

$\displaystyle\phi_{4}(\theta_{4})=$
$\displaystyle\log(2+e^{\frac{h_{4,\epsilon}}{\epsilon}}).$ (75)

Thus,

$\displaystyle C_{4}=\phi_{4}(\theta_{4})-\log
2=\log(1+\frac{e^{\frac{h_{4,\epsilon}}{\epsilon}}}{2})$ (76)

Hence,

$\displaystyle P_{4,Y}=\left(\begin{array}[]{c}e^{-\phi_{4}(\theta_{4})}\\\
e^{-\phi_{4}(\theta_{4})}\\\
e^{\frac{h_{4,\epsilon}}{\epsilon}-\phi_{4}(\theta_{4})}\end{array}\right).$
(80)

Therefore,

$\displaystyle\hat{Q}_{4,X}=V_{4}^{-1}P_{4,Y}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{c}\frac{1}{2\epsilon}e^{\frac{h_{4,\epsilon}}{\epsilon}-\phi_{4}(\theta_{4})}\\\
\frac{1}{2\epsilon}e^{\frac{h_{4,\epsilon}}{\epsilon}-\phi_{4}(\theta_{4})}\\\
2e^{-\phi_{4}(\theta_{4})}-\frac{1-\epsilon}{\epsilon}e^{\frac{h_{4,\epsilon}}{\epsilon}-\phi_{4}(\theta_{4})}\end{array}\right).$
(84)

While the first and second components of $\hat{Q}_{4,X}$ are always positive
value, the third component has a possibility to have a negative value. The
non-negativity of the first component is equivalent to the following
condition;

$\displaystyle 1\geq g_{1}(\epsilon),$ (85)

where
$g_{1}(\epsilon):=\frac{1-\epsilon}{2\epsilon}e^{\frac{h_{4,\epsilon}}{\epsilon}}$.
In (85), the first inequality corresponds to the non-negativity of the third
component and the second inequality corresponds to the non-negativity of the
first component. Fig. 1 numerically plots the function $g_{1}(\epsilon)$. It
shows that $\hat{Q}_{4,X}$ is a probability distribution when
$0.3588\leq\epsilon$. That is, $C_{4}$ is achievable for $0.3588\leq\epsilon$.
When $\epsilon<0.3588$, the third component of $\hat{Q}_{4,X}$ is negative.
Hence, $C_{4}$ is not achievable. Due to Theorem 2, the optimal input
distribution in this case has the support in $\\{1,2\\}$. In this case, due to
the symmetry, the uniform distribution on $\\{1,2\\}$ is optimal. That is, the
capacity with the input set $\\{1,2,3\\}$ is

$\displaystyle{C}_{*}:=-(1-\epsilon)\log\frac{1-\epsilon}{2}-\epsilon\log\epsilon-h(\epsilon)=(1-\epsilon)\log
2.$ (86)

Figure 1: Graphs of functions $g_{1},g_{2},$ and $g_{3}$ with logarithmic
scale. Red dashed curve expresses $g_{1}$. Blue dashed curve expresses
$g_{2}$. Purple solid curve expresses $g_{3}$. Green solid line expresses $1$.
Red dashed curve $g_{1}$ and Blue dashed curve $g_{2}$ across Green solid line
at $0.3588$ and $0.4286$, respectively.

####  III-B3 Case that $j=3$

We consider the case that $j=3$, i.e., the channel is composed of three inputs
$\\{1,2,4\\}$. Then, we have

$\displaystyle\theta_{3}=\left(\begin{array}[]{c}h_{3,\epsilon}\\\
h_{3,\epsilon}\end{array}\right)$ (89)

with $h_{3,\epsilon}:=h(2\epsilon)+(1-2\epsilon)\log 2-h(\epsilon)$ and

$\displaystyle\phi_{3}(\theta_{3})=$
$\displaystyle\log(2e^{2h_{3,\epsilon}}+e^{-\frac{(1-2\epsilon)h_{3,\epsilon}}{\epsilon}})$
$\displaystyle=$
$\displaystyle\log(2+e^{-\frac{h_{3,\epsilon}}{\epsilon}})+2h_{3,\epsilon}.$
(90)

Thus,

$\displaystyle C_{3}=\phi_{3}(\theta_{3})-h(2\epsilon)-(1-2\epsilon)\log 2$
$\displaystyle=$
$\displaystyle\log(2+e^{-\frac{h_{3,\epsilon}}{\epsilon}})+2h_{3,\epsilon}-h(2\epsilon)-(1-2\epsilon)\log
2$ $\displaystyle=$
$\displaystyle\log(2+e^{-\frac{h_{3,\epsilon}}{\epsilon}})+h(2\epsilon)+(1-2\epsilon)\log
2-2h(\epsilon)$ (91)

Hence,

$\displaystyle
P_{3,Y}=\frac{1}{2+e^{-\frac{h_{3,\epsilon}}{\epsilon}}}\left(\begin{array}[]{c}1\\\
1\\\ e^{-\frac{h_{3,\epsilon}}{\epsilon}}\end{array}\right).$ (95)

Therefore,

$\displaystyle\hat{Q}_{3,X}=V_{3}^{-1}P_{3,Y}$ $\displaystyle=$
$\displaystyle\frac{1}{2+e^{-\frac{h_{3,\epsilon}}{\epsilon}}}\left(\begin{array}[]{c}1-\frac{1-2\epsilon}{2\epsilon}e^{-\frac{h_{3,\epsilon}}{\epsilon}}\\\
1-\frac{1-2\epsilon}{2\epsilon}e^{-\frac{h_{3,\epsilon}}{\epsilon}}\\\
-2+\frac{1-\epsilon}{\epsilon}e^{-\frac{h_{3,\epsilon}}{\epsilon}}\end{array}\right).$
(99)

While the first and second components of $\hat{Q}_{3,X}$ are always positive
value, the third component has a possibility to have a negative value. The
non-negativity of the first component is equivalent to the following
condition;

$\displaystyle g_{2}(\epsilon)\geq 1\geq g_{3}(\epsilon),$ (100)

where
$g_{2}(\epsilon):=\frac{1-\epsilon}{2\epsilon}e^{-\frac{h_{3,\epsilon}}{\epsilon}}$
and
$g_{3}(\epsilon):=\frac{1-2\epsilon}{2\epsilon}e^{-\frac{h_{3,\epsilon}}{\epsilon}}$.
In (100), the first inequality corresponds to the non-negativity of the third
component and the second inequality corresponds to the non-negativity of the
first component. However, as numerically plotted in Fig. 1,
$g_{3}(\epsilon)\leq 1$ for $\epsilon<\frac{1}{2}$ and $g_{2}(\epsilon)<1$ for
$\epsilon<0.4286$. Hence, when $\epsilon\geq 0.4286$, $C_{3}$ is achievable,
i.e., it gives the capacity under the case $j=3$.

When $\epsilon<0.4286$, the third component of $\hat{Q}_{3,X}$ is negative. In
this case, due to Theorem 2, the optimal distribution has support $\\{1,2\\}$.
Hence, the capacity with the input set $\\{1,2,4\\}$ is $C_{*}$ defined in
(86).

####  III-B4 Case that $j=1$

Next, we consider the case that $j=1$, i.e., the channel is composed of three
inputs $\\{2,3,4\\}$. Then, we have

$\displaystyle\theta_{1}=\left(\begin{array}[]{c}h_{3,\epsilon}\\\
h_{1,\epsilon}\end{array}\right)$ (103)

with $h_{1,\epsilon}:=h(2\epsilon)-2\epsilon\log 2$ and

$\displaystyle\phi_{1}(\theta_{1})=$
$\displaystyle\log(e^{-\frac{1}{1-\epsilon}h_{3,\epsilon}+(\frac{1}{2(1-\epsilon)}+1)h_{1,\epsilon}}$
$\displaystyle+e^{\frac{1}{1-\epsilon}h_{3,\epsilon}+(-\frac{1}{2(1-\epsilon)}+1)h_{1,\epsilon}}+e^{(-\frac{1}{2\epsilon}+1)h_{1,\epsilon}})$
$\displaystyle=$
$\displaystyle\log\Big{(}\frac{1}{1-\epsilon}(\frac{1-2\epsilon}{4})^{\frac{1-2\epsilon}{2-2\epsilon}}+(1-\epsilon)(\frac{1-2\epsilon}{4})^{-\frac{1-2\epsilon}{2-2\epsilon}}+4\epsilon(1-2\epsilon)^{\frac{1-2\epsilon}{2\epsilon}}\Big{)}+h_{1,\epsilon}$
(104)

Thus,

$\displaystyle C_{1}=\phi_{1}(\theta_{1})-h(2\epsilon)-(1-2\epsilon)\log 2$
$\displaystyle=$
$\displaystyle\log\Big{(}\frac{1}{1-\epsilon}(\frac{1-2\epsilon}{4})^{\frac{1-2\epsilon}{2-2\epsilon}}+(1-\epsilon)(\frac{1-2\epsilon}{4})^{-\frac{1-2\epsilon}{2-2\epsilon}}+4\epsilon(1-2\epsilon)^{\frac{1-2\epsilon}{2\epsilon}}\Big{)}-\log
2$ (105)

Since

$\displaystyle
e^{-\frac{1}{2\epsilon}h_{1,\epsilon}}=4\epsilon(1-2\epsilon)^{\frac{1-2\epsilon}{2\epsilon}},$
(106)

we have

$\displaystyle P_{1,Y}=$
$\displaystyle\left(\begin{array}[]{c}e^{-\frac{1}{1-\epsilon}h_{3,\epsilon}+(\frac{1}{2(1-\epsilon)}+1)h_{1,\epsilon}-\phi_{1}(\theta_{1})}\\\
e^{\frac{1}{1-\epsilon}h_{3,\epsilon}+(-\frac{1}{2(1-\epsilon)}+1)h_{1,\epsilon}-\phi_{1}(\theta_{1})}\\\
e^{(-\frac{1}{2\epsilon}+1)h_{1,\epsilon}-\phi_{1}(\theta_{1})}\end{array}\right)$
(110) $\displaystyle=$ $\displaystyle
e^{h_{1,\epsilon}-\phi_{1}(\theta_{1})}\left(\begin{array}[]{c}\frac{1}{1-\epsilon}(\frac{1-2\epsilon}{4})^{\frac{1-2\epsilon}{2-2\epsilon}}\\\
(1-\epsilon)(\frac{1-2\epsilon}{4})^{-\frac{1-2\epsilon}{2-2\epsilon}}\\\
4\epsilon(1-2\epsilon)^{\frac{1-2\epsilon}{2\epsilon}}\end{array}\right).$
(113)

Therefore,

$\displaystyle\hat{Q}_{1,X}=V_{1}^{-1}P_{1,Y}$ $\displaystyle=$ $\displaystyle
e^{h_{1,\epsilon}-\phi_{1}(\theta_{1})}\left(\begin{array}[]{c}-\frac{1}{(1-\epsilon)^{2}}(\frac{1-2\epsilon}{4})^{\frac{1-2\epsilon}{2-2\epsilon}}+(\frac{1-2\epsilon}{4})^{-\frac{1-2\epsilon}{2-2\epsilon}}\\\
\frac{3-2\epsilon}{2(1-\epsilon)^{2}}(\frac{1-2\epsilon}{4})^{\frac{1-2\epsilon}{2-2\epsilon}}+\frac{1-2\epsilon}{2}(\frac{1-2\epsilon}{4})^{-\frac{1-2\epsilon}{2-2\epsilon}}+(-2+4\epsilon)(1-2\epsilon)^{\frac{1-2\epsilon}{2\epsilon}}\\\
\frac{1}{2(1-\epsilon)^{2}}(\frac{1-2\epsilon}{4})^{\frac{1-2\epsilon}{2-2\epsilon}}-\frac{1}{2}(\frac{1-2\epsilon}{4})^{-\frac{1-2\epsilon}{2-2\epsilon}}+2(1-2\epsilon)^{\frac{1-2\epsilon}{2\epsilon}}\end{array}\right).$
(117)

Taking the limit $\epsilon\to 0$, we have

$\displaystyle\lim_{\epsilon\to
0}\hat{Q}_{1,X}=\frac{2}{5}\left(\begin{array}[]{c}\frac{3}{2}\\\
\frac{7}{4}-\frac{2}{e}\\\
\frac{2}{e}-\frac{3}{4}\end{array}\right)=\left(\begin{array}[]{c}\frac{3}{5}\\\
\frac{7}{10}-\frac{4}{5e}\\\ \frac{4}{5e}-\frac{3}{10}\end{array}\right).$
(124)

Figure 2: Graph of the function $\hat{Q}_{1,X}$. Black solid curve expresses
$\hat{Q}_{1,X}(2)$. Red dashed curve expresses $\hat{Q}_{1,X}(3)$. Green solid
line expresses $\hat{Q}_{1,X}(4)$. The values $\hat{Q}_{1,X}(3)$ and
$\hat{Q}_{1,X}(4)$ are always positive. The value $\hat{Q}_{1,X}(2)$ is
positive only when $\epsilon\leq 0.3972$.

Fig. 2 shows numerical plots of $\hat{Q}_{1,X}(2),$ $\hat{Q}_{1,X}(3),$ and
$\hat{Q}_{1,X}(4)$. Although $\hat{Q}_{1,X}(3)$ and $\hat{Q}_{1,X}(4)$ are
always positive, $\hat{Q}_{1,X}(2)$ is positive only for $\epsilon\geq
0.3972$. Hence, when $\epsilon<0.3972$, due to Theorem 2, the capacity of case
$j=1$ equals the capacity of the channel with inputs $3$ and $4$. In this
case, we cannot use Algorithm 1 because the number of input system is smaller
than the number of the output system. Assume that $P_{X}(3)=1-p$ and
$P_{X}(4)=p$. The mutual information between $X$ and $Y$ is

$\displaystyle(1-2\epsilon p)\log 2+h(2\epsilon p)-(1-p)\log
2-p(h(2\epsilon)+(1-2\epsilon)\log 2)$ $\displaystyle=$ $\displaystyle
h(2\epsilon p)-ph(2\epsilon).$ (125)

Then, the maximum mutual information is achieved when
$p=\frac{1}{2\epsilon(1+e^{\frac{h(2\epsilon)}{2\epsilon}})}=\frac{1}{2\epsilon(1+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}(2\epsilon)^{-1})}=\frac{1}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}}$.
The capacity of this case is

$\displaystyle
C_{**}:=h(\frac{2\epsilon}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}})-\frac{h(2\epsilon)}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}}$
$\displaystyle=$
$\displaystyle\frac{2\epsilon}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}}\log(2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}})$
$\displaystyle-(1-\frac{2\epsilon}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}})\log(1-\frac{2\epsilon}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}})-\frac{1-2\epsilon}{2\epsilon+(1-2\epsilon)^{-\frac{1-2\epsilon}{2\epsilon}}})\log(1-2\epsilon)$
(126)

Due to the symmetry, we can discuss the case with $j=2$.

####  III-B5 Derivation of $C(W)$

Based on the above discussion, we discuss the capacity of the channel $W$ with
input system ${\mathcal{X}}=\\{1,2,3,4\\}$. When $0\leq\epsilon\leq 0.3588$,
$C_{1}$ is the capacity for the case $j=1$, and $C_{*}$ is the capacity for
the cases $j=3,4$. Since $C_{*}\geq C_{1}$ in this case, $C_{*}$ is the
capacity of the channel $W$.

When $0.3588<\epsilon\leq 0.3972$, $C_{1}$ is the capacity for the case $j=1$,
$C_{*}$ is the capacity for the cases $j=3$, and $C_{4}$ is the capacity for
the cases $j=4$. Since $C_{4}\geq C_{*},C_{1}$ in this case, $C_{4}$ is the
capacity of the channel $W$.

In fact, as seen in Fig. 4, 4 curves $C_{1}$, $C_{3}$, $C_{4}$, and $C_{**}$
intersect at $0.3972$. For $0.3972<\epsilon\leq\frac{1}{2}$, $C_{**}$ is the
capacity for the case $j=1$, $C_{3}$ or $C_{*}$ is the capacity for the cases
$j=3$, and $C_{4}$ is the capacity for the cases $j=4$. Since $C_{**}\geq
C_{*},C_{3},C_{4}$ in this case, $C_{**}$ is the capacity of the channel $W$.
Overall, the capacity $C(W)$ of the channel $W$ is calculated as follows.

$\displaystyle C(W)=\left\\{\begin{array}[]{ll}C_{*}&\hbox{ when
}0\leq\epsilon\leq 0.3588\\\ C_{4}&\hbox{ when }0.3588<\epsilon\leq 0.3972\\\
C_{**}&\hbox{ when }0.3972<\epsilon\leq 1/2\end{array}\right.$ (130)

Figure 3: Graphs of functions $C_{1},C_{3},C_{4},C_{*}$ and $C_{**}$. Black
solid curve expresses $C_{1}$. Blue dashed curve expresses $C_{3}$. Red dashed
curve expresses $C_{4}$. Green solid line expresses $C_{*}$. Purple solid
curve expresses $C_{**}$. Its enlarged view is given as Fig. 4.  Figure 4:
Enlarged view of graphs of functions $C_{1},C_{3},C_{4},C_{*}$ and $C_{**}$.
The explanations for 5 curves are the same as Fig. 3. 4 curves $C_{1}$,
$C_{3}$, $C_{4}$, and $C_{**}$ intersect at $0.3972$. In particular, $C_{1}$
touches $C_{**}$ at $0.3972$ $C_{3}$ and $C_{4}$ touch $C_{*}$ at $0.3588$ and
$0.4286$, respectively. That is, the inequalities $C_{1}\geq C_{**}$ and
$C_{3},C_{4}\geq C_{*}$ hold always.

##  IV Capacity of classical-quantum channel

Next, we discuss a classical-quantum channel from the classical system ${\cal
X}:=\\{1,\ldots,n_{1}\\}$ to the quantum system ${\cal H}$ with dimension
$n_{2}$, which is given as a set of density matrices
$\\{W_{j}\\}_{j=1}^{n_{1}}$. We denote the set of density matrices on ${\cal
H}$ by ${\cal S}({\cal H})$. For density matrices $\rho,\sigma\in{\cal
S}({\cal H})$, the entropy $H(\rho)$ and the divergence $D(\rho\|\sigma)$ are
defined as

$\displaystyle H(\rho):=-\operatorname{\mathrm{Tr}}\rho\log\rho,\quad
D(\rho\|\sigma):=\operatorname{\mathrm{Tr}}\rho(\log\rho-\log\sigma).$ (131)

Under this classical-quantum channel, given an input probability distribution
$P\in{\cal P}_{{\cal X}}$ on the classical system ${\cal X}$, the capacity of
classical-quantum channel $W=\\{W_{j}\\}_{j=1}^{n_{1}}$ is defined as [27, 28,
29, 30]

$\displaystyle C_{q}(W):=\max_{P\in{\cal P}_{{\cal
X}}}\sum_{x\in{\mathcal{X}}}P(x)D\bigg{(}W_{x}\bigg{\|}\sum_{x^{\prime}\in{\mathcal{X}}}P(x^{\prime})W_{x^{\prime}}\bigg{)}.$
(132)

The capacity of classical-quantum channel has the following form [31, 32]

$\displaystyle C_{q}(W)=\min_{\sigma\in{\cal S}({\cal
H})}\max_{x\in{\mathcal{X}}}D(W_{x}\|\sigma),$ (133)

Statements similar to statements in section II can be shown in this case of
cq-channel by using quantum information geometry based on Kubo-Mori-Bogoliubov
Fisher information, which is directly linked to quantum relative entropy (131)
[4], [38, Chapter 7]. Here, for the calculation of $C_{q}(W)$, we consider
only the algorithm corresponding to Algorithm 1. Hence, we consider the case
under the following condition similar to Condition (C).

(D)

$n_{1}=n_{2}^{2}$ and $W_{1},\ldots,W_{n_{2}^{2}}$ are linearly independent.

Then, we consider the following condition;

(E)

$D(W_{x}\|\sigma)$ does not depend on $x\in{\mathcal{X}}$.

Since the dimension of the convex full of $\\{W_{x}\\}_{x\in{\mathcal{X}}}$
equals the dimension of ${\cal S}({\cal H})$, due to Condition (D), only one
density matrix $\sigma$ on ${\cal H}$ satisfies the condition (E). We denote
such a density matrix by $\sigma_{*}$. The relation (133) guarantees that

$\displaystyle C_{q}(W)\leq D(W_{x}\|\sigma_{*})$ (134)

for $x\in{\mathcal{X}}$.

We choose $n^{2}-1$ linearly independent Hermitian matrices
$A_{1},\ldots,A_{n_{2}^{2}-1}$ on ${\cal H}$ such that

$\displaystyle\operatorname{\mathrm{Tr}}W_{n_{2}^{2}}A_{j}=0$ (135)

for $j=1,\ldots,n_{2}^{2}-1$. We define the matrix $(h_{i,j})$

$\displaystyle h_{i,j}:=\operatorname{\mathrm{Tr}}W_{i}A_{j}.$ (136)

Given an $n_{2}^{2}-1$-dimensional parameter
$\theta=(\theta^{1},\ldots,\theta^{n_{2}^{2}-1})$, we define the density
matrix $\rho_{\theta}$ as

$\displaystyle\rho_{\theta}=\exp\Big{(}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}-\phi(\theta)\Big{)},$
(137)

where

$\displaystyle\phi(\theta):=\log\operatorname{\mathrm{Tr}}\exp\Big{(}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}\Big{)}.$
(138)

We have the following theorem.

###### Theorem 5

Assume that the parameters $\theta^{1},\ldots,\theta^{n_{2}^{2}-1}$ satisfies
the condition

$\displaystyle\sum_{j=1}^{n_{2}^{2}-1}h_{i,j}\theta^{j}=-H(W_{i})+H(W_{n_{2}^{2}}).$
(139)

Then, we have

$\displaystyle
D(W_{x}\|\rho_{\theta})=\phi(\theta)-H(W_{n_{2}^{2}})=C_{q}(W).$ (140)

for $x\in{\cal A}$.

Proof:  The condition (12) implies that

$\displaystyle\operatorname{\mathrm{Tr}}W_{i}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}=\sum_{j=1}^{n_{2}^{2}-1}h_{i,j}\theta^{j}=-H(W_{i})+H(W_{n_{2}^{2}}).$
(141)

For $x(\neq n_{2}^{2})\in{\mathcal{X}}$, we have

$\displaystyle D(W_{x}\|\rho_{\theta})=\operatorname{\mathrm{Tr}}W_{x}(\log
W_{x}-\log\rho_{\theta})$ $\displaystyle=$
$\displaystyle-H(W_{x})-\operatorname{\mathrm{Tr}}W_{x}\Big{(}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}-\phi(\theta)\Big{)}$
$\displaystyle=$
$\displaystyle-H(W_{x})-\big{(}-H(W_{x})+H(W_{n_{2}^{2}})-\phi(\theta)\big{)}$
$\displaystyle=$ $\displaystyle\phi(\theta)-H(W_{n_{2}^{2}}).$ (142)

Also, we have

$\displaystyle
D(W_{n_{2}^{2}}\|\rho_{\theta})=\operatorname{\mathrm{Tr}}W_{n_{2}^{2}}(\log
W_{n_{2}^{2}}-\log\rho_{\theta})$ $\displaystyle=$
$\displaystyle-H(W_{n_{2}^{2}})-\operatorname{\mathrm{Tr}}W_{x}\big{(}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}-\phi(\theta)\big{)}$
$\displaystyle=$
$\displaystyle-H(W_{n_{2}^{2}})-(-\phi(\theta))=\phi(\theta)-H(W_{n_{2}^{2}}).$
(143)

Hence, when $D(W_{x}\|\rho_{\theta})$ does not depend on $x\in{\mathcal{X}}$,
it realizes the capacity.

Due to Theorem 5, when $\theta$ satisfies the condition (139), the density
matrix $\rho_{\theta}$ equals $\sigma_{*}$. To construct our algorithm, we add
the $n_{2}^{2}$-th Hermitian matrix $A_{n_{2}^{2}}$ and define $h_{i,j}$ by
(136) for $i,j=1,\ldots,n_{2}^{2}$. To find the input distribution
$\hat{Q}_{X,*}$ to achieve the maximum (133), we consider the equation
$\sum_{x}W(y|x)\hat{Q}_{X,*}(x)=\rho_{\theta}$, which can be rewritten as

$\displaystyle\sum_{x\in{\mathcal{X}}}\hat{Q}_{X,*}(x)h_{x,j}\Big{(}=\sum_{x\in{\mathcal{X}}}\hat{Q}_{X,*}(x)\operatorname{\mathrm{Tr}}W_{x}A_{j}\Big{)}$
$\displaystyle=\operatorname{\mathrm{Tr}}\rho_{\theta}A_{j}.$ (144)

If we have

$\displaystyle\hat{Q}_{X,*}(x)\geq 0\hbox{ for }x\in{\mathcal{X}},$ (145)

since $\rho_{\theta}=\sigma_{*}$, (134) guarantees that

$\displaystyle D(W_{x}\|\rho_{\theta})=C_{q}(W),$ (146)

i.e., the solution gives the capacity.

Therefore, in the same way as Algorithm 1, we propose Algorithm 2 based on
Theorem 5. Now, we describe two Hermitian matrices $X,Y$on ${\mathcal{H}}$ by
two $n^{2}$-dimensional vectors $x=(x_{j})_{j=1}^{n_{2}^{2}}$ and
$y=(y_{j})_{j=1}^{n_{2}^{2}}$ as follows.

$\displaystyle X=$ $\displaystyle\sum_{j=1}^{n_{2}}x_{j}|j\rangle\langle j|$
$\displaystyle+\sum_{j=1}^{n_{2}-1}\sum_{j^{\prime}=1}^{j-1}\frac{x_{n_{2}+j(j-1)/2+j^{\prime}}}{\sqrt{2}}(|j\rangle\langle
j^{\prime}|+|j^{\prime}\rangle\langle j|)$
$\displaystyle+\sum_{j=1}^{n_{2}-1}\sum_{j^{\prime}=1}^{j-1}\frac{x_{n_{2}(n_{2}+1)/2+j(j-1)/2+j^{\prime}}}{\sqrt{2}}(i|j\rangle\langle
j^{\prime}|-i|j^{\prime}\rangle\langle j|).$ (147)

Then, we have

$\displaystyle\operatorname{\mathrm{Tr}}XY=\sum_{j=1}^{n_{2}^{2}}x_{j}y_{j}.$
(148)

In this sense, $(W_{1},\ldots,W_{n_{2}^{2}})$ and
$(A_{1},\ldots,A_{n_{2}^{2}})$ can be considered as $n_{2}^{2}\times
n_{2}^{2}$ matrices. Then, Step 1 of Algorithm 2 can be done by calculating
the inverse matrix of the matrix corresponding to
$(W_{1},\ldots,W_{n_{2}^{2}})$. Hence, Step 1 has calculation complexity
$O(n_{2}^{6})$. In Step 2, the calculation of all of $H(W_{i})$ needs
calculation complexity $O(n_{1}n_{2}^{3})=O(n_{2}^{5})$. Hence, Step 2 has
calculation complexity $O(n_{2}^{5})$ in total. In Step 3, the calculation of
$\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}$ has calculation complexity
$O(n_{2}^{4})$. and the calculation of
$\exp\Big{(}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}\Big{)}$ and its trace has
calculation complexity $O(n_{2}^{3})$. Step 3 has calculation complexity
$O(n_{2}^{4})$ in total. In Step 5, the calculation of all of
$\operatorname{\mathrm{Tr}}\rho_{\theta}A_{j}$ has calculation complexity
$O(n_{1}n_{2}^{2})=O(n_{2}^{4})$ since
$\exp\Big{(}\sum_{j=1}^{n_{2}^{2}-1}A_{j}\theta^{j}\Big{)}$ and its trace are
already calculated. Hence, the total calculation complexity is $O(n_{2}^{6})$.

Algorithm 2 Exact algorithm for classical channel capacity

Step 1: Choose $A_{1},\ldots,A_{n_{2}^{2}}$ such that $h_{i,j}$ is the
identity matrix.

Step 2: Set the parameter $\theta^{i}=-H(W_{i})+H(W_{n_{2}^{2}})$ for
$i=1,\ldots,n_{2}^{2}-1$, which isthe solution of (139).

Step 3: Calculate $\phi(\theta)$ by using (138).

Step 4: Calculate
$\hat{Q}_{X,*}(x):=\operatorname{\mathrm{Tr}}\rho_{\theta}A_{j}$, where
$\rho_{\theta}$ is calculated by (137).

Step 5: If the condition (145) holds, we consider that (146) holds and output
$\phi(\theta)-H(W_{n})$ as the capacity. Otherwise, we output “the capacity
cannot be computed.”

##  V Comparison

In the calculation of the capacity of classical channel, when an error
$\epsilon$ is allowed, the conventional method [1, 2] has calculation amount
$O(\frac{n_{1}n_{2}\log n_{1}}{\epsilon})$ because each iteration has
calculation amount $n_{1}n_{2}$ and the number of iteration is $O(\frac{\log
n_{1}}{\epsilon})$. While it is smaller than our method (Algorithm 1) when
$n_{1}=n_{2}$, our method derives the exact value of the maximum without
iteration.

When only Condition (A) holds, we can consider to solve the minimization (19)
due to Theorem 4. However, it is difficult to analytically solve (19) in
general. Since this method needs larger calculation amount to obtain
$\theta^{1},\ldots,\theta^{n_{1}-1}$, the algorithm based on Theorem 4 does
not have advantage over the conventional method [1, 2] except for the case
that the minimization (19) is analytically solved.

Next, we compare Algorithm 2 with existing algorithms for the capacity of a
classical-quantum channel. The algorithm by [14, 18] has calculation
complexity $O(\frac{(n_{1}n_{2}^{2}+n_{2}^{3})\log
n_{1}}{\epsilon}+n_{1}n_{2}^{3})$ The algorithm by [16] has calculation
complexity $O(\frac{\max(n_{1},n_{2})n_{2}^{3}\sqrt{\log n_{1}}}{\epsilon})$.
Unfortunately, these existing algorithms are smaller than our method,
Algorithm2 when $n_{1}=n_{3}(n_{2}-1)+1$ or $n_{1}=n_{2}^{2}$. However, our
method derives the exact value of the maximum without iteration, which is an
advantage over existing methods.

##  VI Conclusion and future study

We have proposed an exact algorithm to calculate the channel capacities of
classical and classical-quantum channels. However, we have various conditions
to apply our formulas. Therefore, it is a future problem to remove conditions.
Indeed, Toyota [10] studied information geometrical structure [4] for Arimoto-
Blahut algorithm for the capacity of a classical channel. Hence, it is an
interesting topic to derive an information theoretical characterization of our
method.

Further, it is a challenging problem to extend our method to the maximization
of Gallager’s function, i.e., Rényi mutual information, including classical-
quantum setting, which is related to the exponential decreasing rate [33, 34]
of the decoding error probability and the strong converse exponent [35, 36,
37]. As another future study, we can consider an extension of our formulas to
wire-tap channel capacity [11, 12, 13, 24].

## Acknowledgments

The author was supported in part by the National Natural Science Foundation of
China (Grant No. 62171212) and Guangdong Provincial Key Laboratory (Grant No.
2019B121203002). The author is very grateful to Mr. Shoji Toyota for helpful
discussions.

##  Appendix A Summary for information geometry

To show Theorems 1 and 2, we summarize basic knowledge for information
geometry, which was established in the reference [4]. The following contents
are used in Appendices C and D. Given a finite probability space
${\mathcal{X}}$ and a distribution $P_{X}$ on ${\mathcal{X}}$, we define an
exponential family as follows. Consider $l$ linearly independent random
variables $f_{1},\ldots,f_{l}$ on ${\mathcal{X}}$. We define the distribution
$P_{\theta,X}$ as

$\displaystyle
P_{\theta,X}(x):=P_{X}(x)e^{\sum_{j=1}^{l}\theta^{j}f_{j}(x)-\phi(\theta)},$
(149)

where
$\phi(\theta):=\log\sum_{x\in{\mathcal{X}}}P_{X}(x)e^{\sum_{j=1}^{l}\theta^{j}f_{j}(x)}$.
The set ${\cal E}:=\\{P_{\theta,X}|\theta\in\mathbb{R}^{l}\\}\subset{\cal
P}_{{\mathcal{X}}}$ is called an exponential family generated by random
variables $f_{1},\ldots,f_{l}$. Also, the set

$\displaystyle{\cal M}:=\\{Q_{X}\in{\cal P}_{{\mathcal{X}}}|Q_{X}\hbox{
satisfies }\eqref{XXP}.\\}$ (150)

is called the mixture family generated by the constraint

$\displaystyle\sum_{x\in{\mathcal{X}}}f_{j}(x)Q_{X}(x)=a_{j}.$ (151)

The following is a typical example of a mixture family. For a subset
${\mathcal{X}}_{0}\subset{\mathcal{X}}$, we define the mixture family ${\cal
M}_{{\mathcal{X}}_{0}}$ as

$\displaystyle{\cal
M}_{{\mathcal{X}}_{0}}:=\Big{\\{}Q_{Y}\in{\mathcal{P}}_{{\mathcal{Y}}}\Big{|}Q_{Y}=\sum_{x\in{\mathcal{X}}\setminus{\mathcal{X}}_{0}}c(x)W_{x},\quad\sum_{x\in{\mathcal{X}}\setminus{\mathcal{X}}_{0}}c(x)=1\Big{\\}}.$
(152)

When ${\mathcal{X}}_{0}$ is the empty set, ${\cal M}_{{\mathcal{X}}_{0}}$
coincides with ${\cal M}_{0}$. Also, we simplify ${\cal M}_{\\{x\\}}$ to
${\cal M}_{x}$.

The following is known as Pythagorean theorem [4].

###### Theorem 6

There uniquely exists an element $P_{X,*}\in{\cal E}\cap{\cal M}$. Any
elements $P_{X,1}\in{\cal M}$ and $P_{X,2}\in{\cal E}$ satisfy

$\displaystyle D(P_{X,1}\|P_{X,2})=D(P_{X,1}\|P_{X,*})+D(P_{X,*}\|P_{X,2}).$
(153)

Using this theorem, we can show the following corollaries.

###### Corollary 1

Given a distribution $Q_{X}$ on ${\mathcal{X}}$, there uniquely exists an
element $Q_{X,*}\in{\cal M}$ such that

$\displaystyle D(P_{X,1}\|Q_{X})=D(P_{X,1}\|Q_{X,*})+D(Q_{X,*}\|Q_{X})$ (154)

for any element $P_{X,1}\in{\cal M}$. $Q_{X,*}$ is called the projection of
$Q_{X}$ to ${\cal M}$, and is denoted by $\Gamma_{{\cal M}}^{(m)}(Q_{X})$.

###### Corollary 2

Given a distribution $Q_{X}$ on ${\mathcal{X}}$, there uniquely exists an
element $Q_{X,*}\in{\cal E}$ such that

$\displaystyle D(Q_{X}\|P_{X,2})=D(Q_{X}\|Q_{X,*})+D(Q_{X,*}\|P_{X,2})$ (155)

for any element $P_{X,2}\in{\cal E}$. $Q_{X,*}$ is called the projection of
$Q_{X}$ to ${\cal E}$, and is denoted by $\Gamma_{{\cal E}}^{(e)}(Q_{X})$.

Now, we consider a one-parameter exponential family $\\{P_{t}\\}$.

###### Lemma 3

For $t_{1}\leq t_{2}\leq t_{3}$, we have

$\displaystyle D(P_{t_{1}}\|P_{t_{2}})+D(P_{t_{2}}\|P_{t_{3}})\leq
D(P_{t_{1}}\|P_{t_{3}}).$ (156)

Proof:  Let $J_{t}$ be the Fisher information in the one-parameter exponential
family $\\{P_{t}\\}$. Then, we have

$\displaystyle
D(P_{t}\|P_{t^{\prime}})=\int_{t^{\prime}}^{s}J_{s}(s-t^{\prime})ds.$ (157)

The expression (157) implies (156).

##  Appendix B Proof of Lemma 1

This lemma can be shown by contradiction. If $D(W_{x}\|Q_{Y})$ depends on
$x\in\mathop{\rm supp}(Q_{X})$, we define
${\mathcal{X}}_{0}:=\\{x_{0}\in{\mathcal{X}}|D(W_{x_{0}}\|Q_{Y})<\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y})\\}$.
With a small $\epsilon>0$, we choose $Q_{X,\epsilon}$ as

$\displaystyle Q_{X,\epsilon}(x_{0})$
$\displaystyle:=Q_{X}(x_{0})+\frac{\epsilon}{|{\mathcal{X}}_{0}|}$ (158)
$\displaystyle Q_{X,\epsilon}(x)$
$\displaystyle:=Q_{X}(x)-\frac{\epsilon}{|{\mathcal{X}}\setminus{\mathcal{X}}_{0}|}$
(159)

for $x_{0}\in{\mathcal{X}}_{0}$ and
$x\in{\mathcal{X}}\setminus{\mathcal{X}}_{0}$. Then, we have
$D(W_{x_{0}}\|W\cdot Q_{X,\epsilon})<D(W_{x_{0}}\|W\cdot Q_{X})$ and
$D(W_{x}\|W\cdot Q_{X,\epsilon})>D(W_{x}\|W\cdot Q_{X})$. Hence, with
sufficiently small $\epsilon>0$, we have

$\displaystyle\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot
Q_{X,\epsilon})<\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot Q_{X}),$ (160)

which contradicts the assumption of contradiction.

##  Appendix C Proof of Theorem 1

Assume the condition (ii). For
$Q_{X}(\neq\hat{Q}_{X,*})\in{\mathcal{P}}_{{\mathcal{X}}}$, we have
$\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot
Q_{X})>\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot\hat{Q}_{X,*})$. Hence,
$Q_{Y,*}$ achieves $C(W)$, which implies Condition (i).

Assume the condition (i). There exists $Q_{X}\in P_{{\mathcal{X}}}$ such that
$D(W_{x}\|Q_{Y,*})=\sum_{x\in{\mathcal{X}}}Q_{X}(x)D(W_{x}\|W\cdot Q_{X})$.
For $x\in\mathop{\rm supp}(Q_{X})$, we have

$\displaystyle D(W_{x}\|W\cdot Q_{X})=D(W_{x}\|Q_{Y,*}).$ (161)

Then, the distribution $\bar{Q}_{Y,*}:=\Gamma_{{\cal M}_{0}}^{(m)}(Q_{Y,*})$
satisfies
$D(W_{x}\|Q_{Y,*})=D(W_{x}\|\bar{Q}_{Y,*})+D(\bar{Q}_{Y,*}\|Q_{Y,*})$. Hence,
$D(W_{x}\|Q_{Y,*})\geq D(W_{x}\|\bar{Q}_{Y,*})$. Since $\min_{Q_{Y}\in{\cal
P}_{{\mathcal{Y}}}}\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y})=\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot
Q_{X})$, we have $D(W_{x}\|W\cdot
Q_{X})=D(W_{x}\|Q_{Y,*})=D(W_{x}\|\bar{Q}_{Y,*})$ for $x\in\mathop{\rm
supp}(Q_{X})$. Hence, $D(\bar{Q}_{Y,*}\|Q_{Y,*})=0$, i.e.,
$\bar{Q}_{Y,*}=Q_{Y,*}$. That is, $Q_{Y,*}$ belongs to ${\cal M}_{0}$. Due to
Condition (A), the condition (161) uniquely determines $Q_{Y,*}$. Hence,
$W\cdot\hat{Q}_{X,*}=Q_{Y,*}=W\cdot Q_{X}$. Due to Condition (A),
$\hat{Q}_{X,*}=Q_{X}$, which implies the condition (ii).

##  Appendix D Proof of Theorem 2

Due to Condition (A), there uniquely exists a distribution
$Q_{X,*}\in{\mathcal{P}}_{{\mathcal{X}}}$ to achieve the capacity $C(W)$. It
is sufficient to show that $Q_{X,*}(x_{0})=0$ for any element $x_{0}\in{\cal
N}(\hat{Q}_{X,*})$. For this aim, we fix an arbitrary element $x_{0}\in{\cal
N}(\hat{Q}_{X,*})$.

Step 1: We show that there exists a distribution $Q_{Y,0}\in{\cal M}_{x_{0}}$
such that

$\displaystyle\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y,*})\geq\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y,0})=D(W_{x^{\prime}}\|Q_{Y,0})$
(162)

for $x^{\prime}\in{\mathcal{X}}\setminus\\{x_{0}\\}$.

We choose a function $f_{x_{0}}$ on ${\mathcal{X}}$ such that

$\displaystyle\sum_{y\in{\mathcal{Y}}}f_{x_{0}}(y)W_{x_{0}}(y)$
$\displaystyle=1,$ (163)
$\displaystyle\sum_{y\in{\mathcal{Y}}}f_{x_{0}}(y)W_{x}(y)$ $\displaystyle=0$
(164)

for $x(\neq x_{0})\in{\mathcal{X}}$. We denote $-\hat{Q}_{X,*}(x_{0})>0$ by
$a$. Then, we have

$\displaystyle\frac{1}{1+a}Q_{Y,*}+\frac{a}{1+a}W_{x_{0}}\in{\cal M}_{x_{0}}.$
(165)

The combination of (164) and (165) implies that

$\displaystyle\sum_{y\in{\mathcal{Y}}}f_{x_{0}}(y)(\frac{1}{1+a}Q_{Y,*}(y)+\frac{a}{1+a}W_{x_{0}}(y))=0.$
(166)

Then, the combination of (163) and (166) yields that

$\displaystyle\sum_{y\in{\mathcal{Y}}}f_{x_{0}}(y)Q_{Y,*}(y)=-a.$ (167)

The distribution $Q_{Y,0}:=\Gamma_{{\cal M}_{x_{0}}}^{(m)}(Q_{Y,*})\in{\cal
M}_{x_{0}}$ satisfies

$\displaystyle D(Q_{Y}\|Q_{Y,*})=D(Q_{Y}\|Q_{Y,0})+D(Q_{Y,0}\|Q_{Y,*})$ (168)

for any $Q_{Y}\in{\cal M}_{x_{0}}$. We define the exponential family ${\cal
E}_{1}:=\\{Q_{Y,t}\\}_{t\in\mathbb{R}}$ as

$\displaystyle Q_{Y,t}(y):=Q_{Y,0}(y)e^{tf_{x_{0}}(y)-\varphi(y)},$ (169)

where

$\displaystyle\varphi(y):=\log\sum_{y\in{\mathcal{Y}}}Q_{Y,0}(y)e^{tf_{x_{0}}(y)}.$
(170)

Hence, $Q_{Y,0}$ coincides with the case with $t=0$. We choose $t_{*}$ such
that $Q_{Y,t_{*}}=Q_{Y,*}$. The relation (167) guarantees that $t_{*}<0$.
Also, we choose $t_{0}$ as $Q_{Y,t_{0}}=\Gamma_{{\cal
E}_{1}}^{(e)}(W_{x_{0}})$. Then, we have

$\displaystyle
D(W_{x_{0}}\|Q_{Y,t})=D(W_{x_{0}}\|Q_{Y,t_{0}})+D(Q_{Y,t_{0}}\|Q_{Y,t}).$
(171)

for any $t_{0}\in\mathbb{R}$. The relation (167) guarantees that $t_{0}>0$.
Since $t_{*}<0$ and $t_{0}>0$, Lemma 3 yields that

$\displaystyle D(Q_{Y,t_{0}}\|Q_{Y,0})\leq
D(Q_{Y,t_{0}}\|Q_{Y,t_{*}})-D(Q_{Y,0}\|Q_{Y,t_{*}}).$ (172)

Figure 5: Relation for ${\cal E}_{1}$, ${\cal M}_{x_{0}}$,
$Q_{Y,*}=Q_{Y,t_{*}},Q_{Y,0}$, and $Q_{Y,t_{0}}$.

The combination of (171) and (172) guarantees that

$\displaystyle
D(W_{x_{0}}\|Q_{Y,0})\stackrel{{\scriptstyle(a)}}{{=}}D(W_{x_{0}}\|Q_{Y,t_{0}})+D(Q_{Y,t_{0}}\|Q_{Y,0})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
D(W_{x_{0}}\|Q_{Y,t_{0}})+D(Q_{Y,t_{0}}\|Q_{Y,t_{*}})-D(Q_{Y,0}\|Q_{Y,t_{*}})\stackrel{{\scriptstyle(c)}}{{=}}D(W_{x_{0}}\|Q_{Y,t_{*}})-D(Q_{Y,0}\|Q_{Y,t_{*}})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}$ $\displaystyle
D(W_{x_{0}}\|Q_{Y,*})-D(Q_{Y,0}\|Q_{Y,*})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}$ $\displaystyle
D(W_{x^{\prime}}\|Q_{Y,*})-D(Q_{Y,0}\|Q_{Y,*})\stackrel{{\scriptstyle(f)}}{{=}}D(W_{x^{\prime}}\|Q_{Y,0})$
(173)

for $x^{\prime}\in{\mathcal{X}}\setminus\\{x_{0}\\}$. Each step is shown in
the following way. Steps $(a)$ and $(c)$ follow from (171). Step $(b)$ follows
from (172). Step $(d)$ follows from $Q_{Y,t_{*}}=Q_{Y,*}$. Step $(e)$ follows
from $D(W_{x_{0}}\|Q_{Y,*})=D(W_{x^{\prime}}\|Q_{Y,*})$. Step $(f)$ follows
from (168). Then, we have

$\displaystyle\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y,*})\geq
D(W_{x^{\prime}}\|Q_{Y,*})\stackrel{{\scriptstyle(a)}}{{\geq}}D(W_{x^{\prime}}\|Q_{Y,0})\stackrel{{\scriptstyle(b)}}{{=}}\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y,0}),$
(174)

where each step is shown as follows. Step $(a)$ follows from (168). Step $(b)$
follows from (173). Hence, we obtain (162).

Step 2: We choose a function $\hat{Q}_{X,1}$ on
${\mathcal{X}}\setminus\\{x_{0}\\}$ such that

$\displaystyle\sum_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}\hat{Q}_{X,1}(x)W_{x}=Q_{Y,1},$
(175)

where $\hat{Q}_{X,1}$ uniquely exists because $Q_{Y,1}\in{\cal M}_{x_{0}}$. We
show the desired statement $Q_{X,*}(x_{0})=0$ when $\hat{Q}_{X,1}(x)\leq 0$
for $x\in{\mathcal{X}}\setminus\\{x_{0}\\}$.

In this case, it is sufficient to show that $Q_{X,*}(x_{0})=\hat{Q}_{X,1}$,
i.e., $\hat{Q}_{X,1}$ achieves the capacity $C(W)$. We have

$\displaystyle\sum_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}Q_{X,1}(x)D(W_{x}\|Q_{Y,1})\stackrel{{\scriptstyle(a)}}{{=}}\max_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}D(W_{x}\|Q_{Y,1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$
$\displaystyle\max_{Q_{X}\in{{\cal
P}_{{\mathcal{X}}\setminus\\{x_{0}\\}}}}\sum_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}Q_{X}(x)D(W_{x}\|W\cdot
Q_{X})$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$
$\displaystyle\min_{Q_{X}\in{{\cal
P}_{{\mathcal{X}}\setminus\\{x_{0}\\}}}}\max_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}D(W_{x}\|W\cdot
Q_{X})$ $\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}$
$\displaystyle\min_{Q_{Y}\in{\cal
M}_{x_{0}}}\max_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}D(W_{x}\|Q_{Y})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}$
$\displaystyle\min_{Q_{X}\in{{\cal
P}_{{\mathcal{X}}}}}\max_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}D(W_{x}\|W\cdot
Q_{X})$ $\displaystyle{\leq}$ $\displaystyle\min_{Q_{X}\in{{\cal
P}_{{\mathcal{X}}}}}\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot Q_{X})$
$\displaystyle{\leq}$ $\displaystyle\max_{x\in{\mathcal{X}}}D(W_{x}\|W\cdot
Q_{X,1}).$ (176)

Each step is shown in the following way. Step $(a)$ follows from the second
equation in (162). Step $(b)$ follows from Theorem 1. Step $(c)$ follows from
(3). Step $(d)$ is shown as follows. Since $Q_{Y}\mapsto D(W_{x}\|Q_{Y})$ is
convex,
$Q_{Y}\mapsto\max_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}D(W_{x}\|Q_{Y})$ is
also convex. Since $Q_{Y,1}$ achieves a local minimum, it also achieve the
global minimum in ${\cal M}_{x_{0}}$.

Step $(e)$ is shown as follows. For $Q_{X}\in{\mathcal{P}}_{{\mathcal{X}}}$,
the distribution $Q_{Y}^{\prime}:=\Gamma_{{\cal M}_{x_{0}}}^{(m)}(W\cdot
Q_{X})$ satisfies

$\displaystyle D(W_{x}\|W\cdot
Q_{X})=D(W_{x}\|Q_{Y}^{\prime})+D(Q_{Y}^{\prime}\|W\cdot Q_{X})\geq
D(W_{x}\|Q_{Y}^{\prime})\hbox{ for }x\in{\mathcal{X}}\setminus\\{x_{0}\\},$
(177)

which shows $(e)$.

Hence, we have

$\displaystyle
C(W)=\sum_{x\in{\mathcal{X}}\setminus\\{x_{0}\\}}Q_{X,1}(x)D(W_{x}\|W\cdot
Q_{X,1}).$ (178)

Step 3: We show the desired statement $Q_{X,*}(x_{0})=0$ when there exists
$x_{1}\in{\mathcal{X}}\setminus\\{x_{0}\\}$ such that $Q_{X,1}(x_{1})<0$.
Applying the same discussion as Step 1, we find that there exists a
distribution $Q_{Y,2}\in{\cal M}_{\\{x_{0},x_{1}\\}}$ such that

$\displaystyle\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y,1})\geq\max_{x\in{\mathcal{X}}}D(W_{x}\|Q_{Y,2})=D(W_{x^{\prime}}\|Q_{Y,2})$
(179)

for $x^{\prime}\in{\mathcal{X}}\setminus\\{x_{0},x_{1}\\}$. Then, we choose
$\hat{Q}_{X,2}$ in the same way as (175). If $\hat{Q}_{X,2}(x)\geq 0$ for
$x\in{\mathcal{X}}\setminus\\{x_{0},x_{1}\\}$, we find that $Q_{X,*}(x_{0})=0$
in the same way as Step 2. Otherwise, we repeat the above procedure up to $i$
times until we have $\hat{Q}_{X,i}(x)\geq 0$ for
$x\in{\mathcal{X}}\setminus\\{x_{0},x_{1},\ldots,x_{i-1}\\}$. Once we obtain
the above condition, we find $Q_{X,*}(x_{0})=0$ in the same way as Step 2.

##  Appendix E Proof of Lemma 2

To show Lemma 2, we prepare functions $\bar{f}_{1},\ldots,\bar{f}_{n_{2}-1}$
to satisfy the condition in Theorem 4. We denote the distribution defined in
(10) based on these functions $\bar{f}_{1},\ldots,\bar{f}_{n_{2}-1}$ by
$\bar{P}_{\theta,Y}$. Such functions are given as linear combination of the
original functions ${f}_{1},\ldots,{f}_{n_{2}-1}$ by using coefficient
$a^{j}_{j^{\prime}}$ as

$\displaystyle\sum_{j}{f}_{j}a^{j}_{j^{\prime}}=\bar{f}_{j^{\prime}}.$ (180)

Hence, we have

$\displaystyle\sum_{j^{\prime}=1}^{n_{2}-1}\bar{f}_{j^{\prime}}(y)\theta^{j^{\prime}}=\sum_{j=1}^{n_{2}-1}{f}_{j}(y)(\sum_{j^{\prime}=1}^{n_{2}-1}a^{j}_{j^{\prime}}\theta^{j^{\prime}}).$
(181)

Using this relation, we find that $\bar{P}_{\theta,Y}={P}_{\bar{\theta},Y}$,
where
$\bar{\theta}^{j}=\sum_{j^{\prime}=1}^{n_{2}-1}a^{j}_{j^{\prime}}\theta^{j^{\prime}}$.
Thus, the set ${\cal E}_{0}$ can be characterized with the new functions
$\bar{f}_{1},\ldots,\bar{f}_{n_{2}-1}$. Therefore, without loss of generality,
we can assume that the functions ${f}_{1},\ldots,{f}_{n_{2}-1}$ satisfies the
condition in Theorem 4.

We choose $\theta^{1},\ldots,\theta^{n_{1}-1}$ satisfies the condition (9).
Then, we have

$\displaystyle{\cal
E}_{0}=\\{P_{\theta^{1},\ldots,\theta^{n_{1}-1},\eta^{n_{1}},\ldots,\eta^{n_{2}-1},Y}|(\eta^{n_{1}},\ldots,\eta^{n_{2}-1})\in\mathbb{R}^{n_{2}-n_{1}}\\}.$
(182)

Hence, ${\cal E}_{0}$ is an exponential family generated by
${f}_{n_{1}},\ldots,{f}_{n_{2}-1}$.

Since $f_{i,j}=0$ for $j=n_{1}+,\ldots,n_{2}-1$, ${\cal M}_{0}$ can be written
as

$\displaystyle{\cal M}_{0}=\\{Q_{Y}\in{\cal
P}_{{\mathcal{Y}}}|\sum_{y\in{\mathcal{Y}}}f_{j}(y)Q_{Y}(y)=0\hbox{ for
}j=n_{1},\ldots,n_{2}-1\\}.$ (183)

Hence, ${\cal M}_{0}$ is a mixture family generated by the same functions
${f}_{n_{1}},\ldots,{f}_{n_{2}-1}$. Therefore, Theorem 6 implies Lemma 2.

## References

  * [1] S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” IEEE Trans. Inform. Theory, vol. 18, no. 1, 14 – 20 (1972).
  * [2] R. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Trans. Inform. Theory, vol. 18, no. 4, 460 – 473 (1972).
  * [3] M. Chiang and S. Boyd, “Geometric programming duals of channel capacity and rate distortion,” IEEE Trans. Inform. Theory, vol. 50, no. 2, 245 – 258 (2004).
  * [4] S. Amari and H. Nagaoka, Methods of Information Geometry (AMS and Oxford, 2000).
  * [5] C. E. Shannon,“A Mathematical Theory of Communication,” Bell System Technical Journal, vol.27, 379–423 and 623–656 (1948).
  * [6] G. Matz and P. Duhamel, “Information geometric formulation and interpretation of accelerated Blahut-Arimoto-Type algorithms,” in Proc. Information Theory Workshop, 24–29, San Antonio, Texas, October, (2004).
  * [7] Yaming Yu, “Squeezing the Arimoto-Blahut algorithm for faster convergence,” IEEE Trans. Inform. Theory, vol. 56, 3149 – 3157 (2010).
  * [8] T. Sutter, D. Sutter, P. Mohajerin Esfahani, and J. Lygeros, “Efficient Approximation of Channel Capacities,” IEEE Trans. Inform. Theory, vol. 61, no. 4, 1649 – 1666 (2015).
  * [9] K. Nakagawa, K. Watabe, and T. Sabu, “On the Search Algorithm for the Output Distribution That Achieves the Channel Capacity,” IEEE Trans. Inform. Theory, vol. 63, 1043 – 1062 (2017).
  * [10] S. Toyota,“Geometry of Arimoto algorithm,” Information Geometry, vol. 3, 183 – 198 (2020)
  * [11] A. D. Wyner, “The wire-tap channel,” Bell. Sys. Tech. Jour., 54 1355 – 1387 (1975).
  * [12] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Trans. Inform. Theory, vol. 24, no. 3, 339 – 348 (1978).
  * [13] K. Yasui, T. Suko, and T. Matsushima, “An Algorithm for Computing the Secrecy Capacity of Broadcast Channels with Confidential Messages,” Proc. 2007 IEEE Int. Symp. Information Theory (ISIT 2007), Nice, France, 24-29 June 2007, pp. 936 – 940.
  * [14] H. Nagaoka, “Algorithms of Arimoto-Blahut type for computing quantum channel capacity,” Proc. 1998 IEEE Int. Symp. Information Theory (ISIT 1998), Cambridge, MA, USA, 16-21 Aug. 1998, pp. 354.
  * [15] F. Dupuis, W. Yu, and F. Willems, “Blahut-Arimoto algorithms for computing channel capacity and rate-distortion with side information,” Proc. 2014 IEEE Int. Symp. Information Theory (ISIT 2014), Chicago, IL, USA, 27 June-2 July 2004, pp. 179.
  * [16] D. Sutter, T. Sutter, P. M. Esfahani, and R. Renner, “Efficient approximation of quantum channel capacities,” IEEE Trans. Inform. Theory, vol. 62, 578 – 598 (2016).
  * [17] H. Li and N. Cai, “A Blahut-Arimoto Type Algorithm for Computing Classical-Quantum Channel Capacity,” Proc. 2019 IEEE Int. Symp. Information Theory (ISIT 2019), Paris, France, 7-12 July 2019, pp. 255–259.
  * [18] N. Ramakrishnan, R. Iten. V. B. Scholz, and M. Berta, “Computing Quantum Channel Capacities,” IEEE Trans. Inform. Theory, vol. 67, 946 – 960 (2021).
  * [19] A.S. Holevo, “The capacity of the quantum channel with general signal states,” IEEE Trans. Inform. Theory, vol. 44, 269 (1998)
  * [20] B. Schumacher, and M.D. Westmoreland, “Sending classical information via noisy quantum channelsm” Phys. Rev. A vol. 56, 131 (1997)
  * [21] M. Hayashi, H. Imai, K. Matsumoto, M. B. Ruskai and T. Shimono, “Qubit channels which require four inputs to achieve capacity: Implications for additivity conjectures,” Quantum Information and Computation, vol.5, 032 - 040 (2005).
  * [22] K. Kato, M. Oto, H. Imai, and K. Imai, “Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence”, Computational Geometry Analysis of Quantum State Space and Its Applications, pp 67-108 (2008)
  * [23] J. Huang and S. P. Meyn, “Characterization and computation of optimal distributions for channel coding,” IEEE Trans. Inf. Theory, vol. 51, no. 7, pp. 2336 – 2351, Jul. 2005.
  * [24] K. Yasui, T. Suko, and T. Matsushima, “On the Global Convergence Property of Extended Arimoto-Blahut Algorithm,” IEICE Trans. Fundamentals, vol.J91-A, no.9, pp.846-860, (2008).
  * [25] K. Nakagawa and F. Kanaya, “A new geometric capacity characterization of a discrete memoryless channel,” IEEE Trans. Inf. Theory, vol. 34, no. 2, pp. 318 – 321, Mar. 1988.
  * [26] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press; Second edition (2011)
  * [27] A.S. Holevo, Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii 9, 3 – 11 (1973) (in Russian). (English translation: Probl. Inf. Transm. 9, 177 – 183 (1975))
  * [28] A.S. Holevo, On the capacity of quantum communication channel. Problemly Peredachi Informatsii 15, 4, 3 – 11 (1979) (in Russian). (English translation: Probl. Inf. Transm. 15, 247– 253 (1979).)
  * [29] A.S. Holevo, The capacity of the quantum channel with general signal states. IEEE Trans. Inf. Theory 44, 269 (1998)
  * [30] B. Schumacher, M.D. Westmoreland, Sending classical information via noisy quantum channels. Phys. Rev. A 56, 131 (1997)
  * [31] M. Ohya and D. Petz, N. Watanabe, “On capacities of quantum channels,” Prob. Math. Stat. 17, 179 – 196 (1997)
  * [32] B. Schumacher and M.D. Westmoreland, “Optimal signal ensembles,” Phys. Rev. A 63, 022308 (2001)
  * [33] R.G.Gallager, Information theory and reliable communication, John Wiley and Sons, 1968
  * [34] J.I. Fujii, R. Nakamoto, and K. Yanagi “Concavity of the Auxiliary Function Appearing in Quantum Reliability Function,” IEEE Trans. Inform. Theory, vol. IT-52, pp. 3310 – 3313, 2006.
  * [35] S. Arimoto, “On the converse to the coding theorem for discrete memoryless channels,” IEEE Trans. Inform. Theory, vol. IT-19, pp. 357 – 359, 1973.
  * [36] T. Ogawa, and H. Nagaoka, “Strong Converse to the Quantum Channel Coding Theorem,” IEEE Trans. Inform. Theory, vol. 45, no. 7, pp. 2486-2489, 1999.
  * [37] M. Mosonyi and T. Ogawa, “Strong converse exponent for classical-quantum channel coding,” Communications in Mathematical Physics 355 (1), 373-426
  * [38] M. Hayashi, Quantum Information Theory: Mathematical Foundation, Graduate Texts in Physics, Springer (2017). (First edition was published from Springer in 2006).