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

arXiv:1904.11188 · IEEE International Symposium on Information Theory (ISIT)

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

Haobo Li, Ning Cai

Published Jul 1, 2019• 22 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit.2019.8849608

Related papers

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

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•3 citations

Efficient Approximation of Quantum Channel Capacities

David Sutter, Tobias Sutter, Peyman Mohajerin Esfahani +1 more

We propose an iterative method for approximating the capacity of classical-quantum channels with a discrete input alphabet and a finite-dimensional output under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To provide an additive ε-close estimate to the capacity, the presented algorithm requires O((N ν M)M3log(N)1/2ε-1) steps, where N denotes the input alphabet size and M denotes the output dimension. We then generalize the method to the task of approximating the capacity of classical-quantum channels with a bounded continuous input alphabet and a finite-dimensional output. This, using the idea of a universal encoder, allows us to approximate the Holevo capacity for channels with a finite-dimensional quantum mechanical input and output. In particular, we show that the problem of approximating the Holevo capacity can be reduced to a multi-dimensional integration problem. For certain families of quantum channels, we prove that the complexity to derive an additive ε-close solution to the Holevo capacity is subexponential or even polynomial in the problem size. We provide several examples to illustrate the performance of the approximation scheme in practice.

arXiv:1407.8202•IEEE Transactions on Information Theory•Nov 25, 2015•30 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•38 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•2 citations

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•8 citations
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.
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
We propose an iterative method for approximating the capacity of classical-quantum channels with a discrete input alphabet and a finite-dimensional output under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To provide an additive ε-close estimate to the capacity, the presented algorithm requires O((N ν M)M3log(N)1/2ε-1) steps, where N denotes the input alphabet size and M denotes the output dimension. We then generalize the method to the task of approximating the capacity of classical-quantum channels with a bounded continuous input alphabet and a finite-dimensional output. This, using the idea of a universal encoder, allows us to approximate the Holevo capacity for channels with a finite-dimensional quantum mechanical input and output. In particular, we show that the problem of approximating the Holevo capacity can be reduced to a multi-dimensional integration problem. For certain families of quantum channels, we prove that the complexity to derive an additive ε-close solution to the Holevo capacity is subexponential or even polynomial in the problem size. We provide several examples to illustrate the performance of the approximation scheme in practice.
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.