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

IEEE International Symposium on Information Theory (ISIT)

Algorithms of Arimoto-Blahut type for computing quantum channel capacity

Hiroshi Nagaoka

Published Nov 27, 2002• 30 citations
Publisher

Abstract

In the Arimoto-Blahut (1972) algorithm for computing the capacity of a classical discrete memoryless channel, maximization of the mutual information is converted to more tractable alternating maximization of a two-variable function. We apply the same idea to computation of the capacity of a quantum memoryless channel.
DOI
10.1109/isit.1998.708959

Related papers

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

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 Classical-Quantum Channel Capacity Using Blahut–Arimoto Type Algorithm: A Theoretical and Numerical Analysis

Haobo Li, Ning Cai

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.

Entropy•Feb 16, 2020•2 citations

Algorithms for Computing the Petz-Augustin Capacity

Chun-Neng Chu, Wei-Fu Tseng, Yen-Huan Li

We propose the first algorithms with non-asymptotic convergence guarantees for computing the Petz-Augustin capacity, which generalizes the channel capacity and characterizes the optimal error exponent in classical-quantum channel coding. This capacity can be equivalently expressed as the maximization of two generalizations of mutual information: the Petz-Rényi information and the Petz-Augustin information. To maximize the Petz-Rényi information, we show that it corresponds to a convex Hölder-smooth optimization problem, and hence the universal fast gradient method of Nesterov (2015), along with its convergence guarantees, readily applies. Regarding the maximization of the Petz-Augustin information, we adopt a two-layered approach: we show that the objective function is smooth relative to the negative Shannon entropy and can be efficiently optimized by entropic mirror descent; each iteration of entropic mirror descent requires computing the Petz-Augustin information, for which we propose a novel fixed-point algorithm and establish its contractivity with respect to the Thompson metric. Notably, this two-layered approach can be viewed as a generalization of the mirror-descent interpretation of the Blahut-Arimoto algorithm due to He et al. (2024).

cs.ITCross-listedarXiv:2601.06492•IEEE International Symposium on Information Theory (ISIT)•Jan 13, 2026•1 citation

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

Non-Commutative Blahut-Arimoto Algorithms

Mario Berta, Navneeth Ramakrishnan, Raban Iten +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 Holevo quantity of classical-quantum channels, the coherent information of less noisy quantum channels, and the thermodynamic capacity of quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive $\varepsilon$-approximations after $\mathcal{O}\left(\varepsilon^{-1}\log N\right)$ 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.

•May 3, 2019•4 citations
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
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.
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.
We propose the first algorithms with non-asymptotic convergence guarantees for computing the Petz-Augustin capacity, which generalizes the channel capacity and characterizes the optimal error exponent in classical-quantum channel coding. This capacity can be equivalently expressed as the maximization of two generalizations of mutual information: the Petz-Rényi information and the Petz-Augustin information. To maximize the Petz-Rényi information, we show that it corresponds to a convex Hölder-smooth optimization problem, and hence the universal fast gradient method of Nesterov (2015), along with its convergence guarantees, readily applies. Regarding the maximization of the Petz-Augustin information, we adopt a two-layered approach: we show that the objective function is smooth relative to the negative Shannon entropy and can be efficiently optimized by entropic mirror descent; each iteration of entropic mirror descent requires computing the Petz-Augustin information, for which we propose a novel fixed-point algorithm and establish its contractivity with respect to the Thompson metric. Notably, this two-layered approach can be viewed as a generalization of the mirror-descent interpretation of the Blahut-Arimoto algorithm due to He et al. (2024).
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 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 Holevo quantity of classical-quantum channels, the coherent information of less noisy quantum channels, and the thermodynamic capacity of quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive ε\varepsilonε-approximations after O(ε−1log⁡N)\mathcal{O}\left(\varepsilon^{-1}\log N\right)O(ε−1logN) iterations, where NNN 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.