Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Entropy

Computing Classical-Quantum Channel Capacity Using Blahut–Arimoto Type Algorithm: A Theoretical and Numerical Analysis

Haobo Li, Ning Cai

Published Feb 16, 2020• 2 citations
Publisher

Abstract

Based on Arimoto’s work in 1972, 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 ε accuracy, the iteration complexity of the algorithm is upper bounded by log n log ε ε where n is the size of the input alphabet. In particular, when the output state { ρ x } x ∈ X is linearly independent in complex matrix space, the algorithm has a geometric convergence. We also show that the algorithm reaches an ε accurate solution with a complexity of O ( m 3 log n log ε ε ) , and O ( m 3 log ε log ( 1 − δ ) ε D ( p * | | p N 0 ) ) in the special case, where m is the output dimension, D ( p * | | p N 0 ) is the relative entropy of two distributions, and δ is a positive number. Numerical experiments were performed and an approximate solution for the binary two-dimensional case was analysed.

DOI
10.3390/e22020222

Related papers

A Blahut-Arimoto Type Algorithm for Computing Classical-Quantum Channel Capacity

Haobo Li, Ning Cai

Based on Arimoto's work in 1978 [1], 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 ε accuracy, the iteration complexity of the algorithm is up bounded by log n log ε ε where n is the size of the input alphabet. In particular, when the output state {ρx}x∈Xis linearly independent in complex matrix space, the algorithm has a geometric convergence. We also show that the algorithm reaches an ε accurate solution with a complexity of O(m3log n log ε/ε), and O(m3log ε log(1-δ)D(ε/p*||pN(0))) in the special case, where m is the output dimension and D(p*||pN(0)) is the relative entropy of two distributions and δ is a positive number.

arXiv:1904.11188•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•20 citations

Computing the Classical-Quantum channel capacity: experiments on a Blahut-Arimoto type algorithm and an approximate solution for the binary inputs, two-dimensional outputs channel

Haobo Li, Ning Cai

In our previous work, we presented a Blahut-Arimoto type algorithm for computing the discrete memoryless (DM) classical-quantum channel capacity. And the speed of convergence is analyzed. In this paper, we present numerical experiment to show that the algorithm converged much faster than the theoretical prediction. Also we present an explicit approximate solution for the binary inputs, two dimensional outputs classical-quantum channel, which has an error within $3\times10^{-4}$

arXiv:1905.08235•May 18, 2019•2 citations

Computing Quantum Channel Capacities

Navneeth Ramakrishnan, Raban Iten, Volkher B. Scholz +1 more

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.

arXiv:1905.01286•IEEE Transactions on Information Theory•Oct 28, 2020•33 citations

A Mirror-Descent Algorithm for Computing the Petz-Rényi Capacity of Classical-Quantum Channels

Yu-Hong Lai, Hao-Chung Cheng

We study the computation of the $α$-Rényi capacity of a classical-quantum (c-q) channel for $α\in(0,1)$. We propose an exponentiated-gradient (mirror descent) iteration that generalizes the Blahut-Arimoto algorithm. Our analysis establishes relative smoothness with respect to the entropy geometry, guaranteeing a global sublinear convergence of the objective values. Furthermore, under a natural tangent-space nondegeneracy condition (and a mild spectral lower bound in one regime), we prove local linear (geometric) convergence in Kullback-Leibler divergence on a truncated probability simplex, with an explicit contraction factor once the local curvature constants are bounded.

quant-pharXiv:2601.10558•IEEE International Symposium on Information Theory (ISIT)•Jan 16, 2026•1 citation

Quantum Blahut-Arimoto Algorithms

Navneeth Ramakrishnan, Raban Iten, Volkher B. Scholz +1 more

We generalize alternating optimization algorithms of Blahut-Arimoto type to the quantum setting. In particular, we give iterative algorithms to compute the mutual information of quantum channels, the thermodynamic capacity of quantum channels, the coherent information of less noisy quantum channels, and the Holevo quantity of classical-quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive ε-approximations after O (ε-1log N) iterations, where N denotes the input dimension of the channel. We complement our analysis with an a posteriori stopping criterion which allows us to terminate the algorithm after significantly fewer iterations compared to the a priori criterion in numerical examples. Finally, we discuss heuristics to accelerate the convergence.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•5 citations

A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms

Geng Liu, Masahito Hayashi

The generalized quantum Arimoto--Blahut (QAB) algorithm is a powerful derivative-free iterative method in quantum information theory. A key obstacle to its broader use is that existing convergence guarantees typically rely on analytical conditions that are either overly restrictive or difficult to verify for concrete problems. We address this issue by introducing an a posteriori certification viewpoint: instead of requiring fully a priori verifiable assumptions, we provide convergence and error guarantees that can be validated directly from the iterates produced by the algorithm. Specifically, we prove a generalized global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer. This theorem yields a practical certification procedure: by checking explicit inequalities along the computed trajectory, one can certify global optimality and bound the suboptimality of the obtained value. As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels, a fundamental measure of distinguishability in quantum dynamics. This quantity is notoriously challenging to evaluate numerically: gradient-based methods are impeded by the complexity of matrix functions such as square roots and logarithms, while recent semidefinite programming approaches can become computationally and memory intensive at high precision. Our method avoids these bottlenecks by combining the QAB iteration with a posteriori certification, yielding an efficient and scalable algorithm. Numerical experiments demonstrate rapid convergence and improved scalability and adaptivity compared with SDP-based approaches.

quant-pharXiv:2601.09301•IEEE International Symposium on Information Theory (ISIT)•Jan 15, 2026•1 citation
Based on Arimoto’s work in 1972, 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 ε accuracy, the iteration complexity of the algorithm is upper bounded by log n log ε ε where n is the size of the input alphabet. In particular, when the output state { ρ x } x ∈ X is linearly independent in complex matrix space, the algorithm has a geometric convergence. We also show that the algorithm reaches an ε accurate solution with a complexity of O ( m 3 log n log ε ε ) , and O ( m 3 log ε log ( 1 − δ ) ε D ( p * | | p N 0 ) ) in the special case, where m is the output dimension, D ( p * | | p N 0 ) is the relative entropy of two distributions, and δ is a positive number. Numerical experiments were performed and an approximate solution for the binary two-dimensional case was analysed.
Based on Arimoto's work in 1978 [1], 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 ε accuracy, the iteration complexity of the algorithm is up bounded by log n log ε ε where n is the size of the input alphabet. In particular, when the output state {ρx}x∈Xis linearly independent in complex matrix space, the algorithm has a geometric convergence. We also show that the algorithm reaches an ε accurate solution with a complexity of O(m3log n log ε/ε), and O(m3log ε log(1-δ)D(ε/p*||pN(0))) in the special case, where m is the output dimension and D(p*||pN(0)) is the relative entropy of two distributions and δ is a positive number.
In our previous work, we presented a Blahut-Arimoto type algorithm for computing the discrete memoryless (DM) classical-quantum channel capacity. And the speed of convergence is analyzed. In this paper, we present numerical experiment to show that the algorithm converged much faster than the theoretical prediction. Also we present an explicit approximate solution for the binary inputs, two dimensional outputs classical-quantum channel, which has an error within 3×10−43\times10^{-4}3×10−4
The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.
We study the computation of the ααα-Rényi capacity of a classical-quantum (c-q) channel for α∈(0,1)α\in(0,1)α∈(0,1). We propose an exponentiated-gradient (mirror descent) iteration that generalizes the Blahut-Arimoto algorithm. Our analysis establishes relative smoothness with respect to the entropy geometry, guaranteeing a global sublinear convergence of the objective values. Furthermore, under a natural tangent-space nondegeneracy condition (and a mild spectral lower bound in one regime), we prove local linear (geometric) convergence in Kullback-Leibler divergence on a truncated probability simplex, with an explicit contraction factor once the local curvature constants are bounded.
We generalize alternating optimization algorithms of Blahut-Arimoto type to the quantum setting. In particular, we give iterative algorithms to compute the mutual information of quantum channels, the thermodynamic capacity of quantum channels, the coherent information of less noisy quantum channels, and the Holevo quantity of classical-quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive ε-approximations after O (ε-1log N) iterations, where N denotes the input dimension of the channel. We complement our analysis with an a posteriori stopping criterion which allows us to terminate the algorithm after significantly fewer iterations compared to the a priori criterion in numerical examples. Finally, we discuss heuristics to accelerate the convergence.
The generalized quantum Arimoto--Blahut (QAB) algorithm is a powerful derivative-free iterative method in quantum information theory. A key obstacle to its broader use is that existing convergence guarantees typically rely on analytical conditions that are either overly restrictive or difficult to verify for concrete problems. We address this issue by introducing an a posteriori certification viewpoint: instead of requiring fully a priori verifiable assumptions, we provide convergence and error guarantees that can be validated directly from the iterates produced by the algorithm. Specifically, we prove a generalized global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer. This theorem yields a practical certification procedure: by checking explicit inequalities along the computed trajectory, one can certify global optimality and bound the suboptimality of the obtained value. As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels, a fundamental measure of distinguishability in quantum dynamics. This quantity is notoriously challenging to evaluate numerically: gradient-based methods are impeded by the complexity of matrix functions such as square roots and logarithms, while recent semidefinite programming approaches can become computationally and memory intensive at high precision. Our method avoids these bottlenecks by combining the QAB iteration with a posteriori certification, yielding an efficient and scalable algorithm. Numerical experiments demonstrate rapid convergence and improved scalability and adaptivity compared with SDP-based approaches.