A Blahut-Arimoto Type Algorithm for Computing Classical-Quantum Channel Capacity
Haobo Li, Ning Cai
Based on Arimoto's work in 1978, we propose an iterative algorithm for
computing the capacity of a discrete memoryless classical-quantum channel with
a finite input alphabet and a finite dimensional output, which we call the
Blahut-Arimoto algorithm for classical-quantum channel, and an input cost
constraint is considered. We show that to reach $\varepsilon$ accuracy, the
iteration complexity of the algorithm is up bounded by $\frac{\log
n\log\varepsilon}{\varepsilon}$ where $n$ is the size of the input alphabet. In
particular, when the output state $\{\rho_x\}_{x\in \mathcal{X}}$ is linearly
independent in complex matrix space, the algorithm has a geometric convergence.
We also show that the algorithm reaches an $\varepsilon$ accurate solution with
a complexity of $O(\frac{m^3\log n\log\varepsilon}{\varepsilon})$, and
$O(m^3\log\varepsilon\log_{(1-\delta)}\frac{\varepsilon}{D(p^*||p^{N_0})})$ in
the special case, where $m$ is the output dimension and $D(p^*||p^{N_0})$ is
the relative entropy of two distributions and $\delta$ is a positive number.