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:2601.09301 · IEEE International Symposium on Information Theory (ISIT)

A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms

Geng Liu, Masahito Hayashi

quant-phSubmitted Jan 14, 2026• Announced Jan 15, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

Related papers

Conditions for Global Optimality in Quantum Arimoto-Blahut Algorithms

Geng Liu, Masahito Hayashi

Generalized Arimoto--Blahut (AB) algorithms are widely used in information theory and quantum optimization, but monotonic objective decrease and numerical stabilization do not guarantee global optimality. We establish necessary and sufficient conditions for the global optimality of full-rank AB fixed points for convex differentiable objectives under linear constraints. An AB fixed point is globally optimal if and only if the AB update direction and the objective gradient differ by an element of the constraint normal space at that point. The same compatibility condition characterizes agreement between individual AB and mirror-descent (MD) updates, whereas pathwise equivalence requires it along the entire common trajectory. Thus, an AB algorithm may follow a trajectory different from MD and still reach the global optimum. We also develop a posteriori optimality certificates based on feasible directional derivatives, including finite-difference upper bounds on the objective gap that require only objective evaluations. For channel relative entropy between dephasing and depolarizing channels, we analytically identify the global minimizer as the unique full-rank AB fixed point, although pathwise equivalence fails. Numerical experiments illustrate convergence of AB and MD along different trajectories and validate the certificates. By contrast, an amplitude-damping example shows that a monotone AB iteration can stabilize at a suboptimal fixed point, whose nonoptimality is detected by the finite-difference certificate. These results provide structural and computable criteria for assessing global optimality in quantum AB algorithms.

cs.ITCross-listedarXiv:2609.09731•Sep 10, 2026•0 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

Convergence Analysis of the Quantum Blahut-Arimoto Algorithm and the Contraction Coefficient of Qubit Amplitude-Damping Channels

Junke Han, Yonglong Li

In this work, we investigate the convergence rate of the quantum Blahut-Arimoto (BA) algorithm proposed for computing the coherent information of less noisy quantum channels. Previous work established exponential convergence under certain restrictive assumptions on the channel. Using a Taylor expansion around a positive definite optimizer, we show that, for an injective degradable channel whose degrading channel has a relative-entropy contraction coefficient strictly less than one, the algorithm converges at an exponential rate after sufficiently many iterations. We further verify this condition for qubit amplitude-damping (AD) channels in the relevant parameter regime. In addition, by analyzing the Bogoliubov-Kubo-Mori (BKM) metric on the Bloch ball, we derive an explicit characterization of the relative-entropy contraction coefficient of qubit AD channels. The proposed approach is further extended to calculate the relative contraction coefficient and the relative expansion coefficient of two qubit AD channels.

quant-pharXiv:2610.29373•Oct 22, 2026•0 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•5 citations

A Bregman Proximal Perspective on Classical and Quantum Blahut-Arimoto Algorithms

Kerry He, James Saunderson, Hamza Fawzi

The Blahut-Arimoto algorithm is a well-known method to compute classical channel capacities and rate-distortion functions. Recent works have extended this algorithm to compute various quantum analogs of these quantities. In this paper, we show how these Blahut-Arimoto algorithms are special instances of mirror descent, which is a type of Bregman proximal method, and a well-studied generalization of gradient descent for constrained convex optimization. Using recently developed convex analysis tools, we show how analysis based on relative smoothness and strong convexity recovers known sublinear and linear convergence rates for Blahut-Arimoto algorithms. This Bregman proximal viewpoint allows us to derive related algorithms with similar convergence guarantees to solve problems in information theory for which Blahut-Arimoto-type algorithms are not directly applicable. We apply this framework to compute energy-constrained classical and quantum channel capacities, classical and quantum rate-distortion functions, and approximations of the relative entropy of entanglement, all with provable convergence guarantees.

arXiv:2306.04492•IEEE Transactions on Information Theory•Jun 11, 2024•11 citations

Certified bounds on optimization problems in quantum theory

Younes Naceur, Jie Wang, Victor Magron +1 more

Semidefinite relaxations of polynomial optimization have become a central tool for addressing the non-convex optimization problems over non-commutative operators that are ubiquitous in quantum information theory and, more in general, quantum physics. Yet, as these global relaxation methods are solved numerically, the bounds issued by the semidefinite solver can - and often do - exceed the global optimum, undermining their certifiability. To counter this issue, we introduce a framework for extracting rigorous certified bounds on non-commutative optimization problems from inexact numerical data, and apply it to several paradigmatic problems in quantum information theory. An extension to sparsity and symmetry-adapted semidefinite relaxations is also provided and compared to the general dense scheme. Our results establish rational post-processing as a practical route to reliable certification, pushing semidefinite optimization toward a certifiable standard for quantum information science.

quant-pharXiv:2512.17713•Quantum•Dec 22, 2025•7 citations
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.
Generalized Arimoto--Blahut (AB) algorithms are widely used in information theory and quantum optimization, but monotonic objective decrease and numerical stabilization do not guarantee global optimality. We establish necessary and sufficient conditions for the global optimality of full-rank AB fixed points for convex differentiable objectives under linear constraints. An AB fixed point is globally optimal if and only if the AB update direction and the objective gradient differ by an element of the constraint normal space at that point. The same compatibility condition characterizes agreement between individual AB and mirror-descent (MD) updates, whereas pathwise equivalence requires it along the entire common trajectory. Thus, an AB algorithm may follow a trajectory different from MD and still reach the global optimum. We also develop a posteriori optimality certificates based on feasible directional derivatives, including finite-difference upper bounds on the objective gap that require only objective evaluations. For channel relative entropy between dephasing and depolarizing channels, we analytically identify the global minimizer as the unique full-rank AB fixed point, although pathwise equivalence fails. Numerical experiments illustrate convergence of AB and MD along different trajectories and validate the certificates. By contrast, an amplitude-damping example shows that a monotone AB iteration can stabilize at a suboptimal fixed point, whose nonoptimality is detected by the finite-difference certificate. These results provide structural and computable criteria for assessing global optimality in quantum AB algorithms.
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.
In this work, we investigate the convergence rate of the quantum Blahut-Arimoto (BA) algorithm proposed for computing the coherent information of less noisy quantum channels. Previous work established exponential convergence under certain restrictive assumptions on the channel. Using a Taylor expansion around a positive definite optimizer, we show that, for an injective degradable channel whose degrading channel has a relative-entropy contraction coefficient strictly less than one, the algorithm converges at an exponential rate after sufficiently many iterations. We further verify this condition for qubit amplitude-damping (AD) channels in the relevant parameter regime. In addition, by analyzing the Bogoliubov-Kubo-Mori (BKM) metric on the Bloch ball, we derive an explicit characterization of the relative-entropy contraction coefficient of qubit AD channels. The proposed approach is further extended to calculate the relative contraction coefficient and the relative expansion coefficient of two qubit AD channels.
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.
The Blahut-Arimoto algorithm is a well-known method to compute classical channel capacities and rate-distortion functions. Recent works have extended this algorithm to compute various quantum analogs of these quantities. In this paper, we show how these Blahut-Arimoto algorithms are special instances of mirror descent, which is a type of Bregman proximal method, and a well-studied generalization of gradient descent for constrained convex optimization. Using recently developed convex analysis tools, we show how analysis based on relative smoothness and strong convexity recovers known sublinear and linear convergence rates for Blahut-Arimoto algorithms. This Bregman proximal viewpoint allows us to derive related algorithms with similar convergence guarantees to solve problems in information theory for which Blahut-Arimoto-type algorithms are not directly applicable. We apply this framework to compute energy-constrained classical and quantum channel capacities, classical and quantum rate-distortion functions, and approximations of the relative entropy of entanglement, all with provable convergence guarantees.
Semidefinite relaxations of polynomial optimization have become a central tool for addressing the non-convex optimization problems over non-commutative operators that are ubiquitous in quantum information theory and, more in general, quantum physics. Yet, as these global relaxation methods are solved numerically, the bounds issued by the semidefinite solver can - and often do - exceed the global optimum, undermining their certifiability. To counter this issue, we introduce a framework for extracting rigorous certified bounds on non-commutative optimization problems from inexact numerical data, and apply it to several paradigmatic problems in quantum information theory. An extension to sparsity and symmetry-adapted semidefinite relaxations is also provided and compared to the general dense scheme. Our results establish rational post-processing as a practical route to reliable certification, pushing semidefinite optimization toward a certifiable standard for quantum information science.