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:2311.11188 · Quantum Science and Technology

Generalized quantum Arimoto–Blahut algorithm and its application to quantum information bottleneck

Masahito Hayashi, Geng Liu

Published Aug 13, 2024• 8 citations
arXivHTMLPDF

Abstract

Abstract Quantum information bottleneck was proposed by Grimsmo and Still (2016 Phys. Rev. A 94 012338) as a promising method for quantum supervised machine learning. To study this method, we generalize the quantum Arimoto–Blahut algorithm by Ramakrishnan et al (2021 IEEE Trans. Inf. Theory 67 946) to a function defined over a set of density matrices with linear constraints so that our algorithm can be applied to optimizations of quantum operations. This algorithm has wider applicability, and we apply our algorithm to the quantum information bottleneck with three quantum systems. We numerically compare our obtained algorithm with the existing algorithm by Grimsmo and Still. Our numerical analysis shows that our algorithm is better than their algorithm.

DOI
10.1088/2058-9565/ad6eb1

Related papers

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 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

Algorithms of Arimoto-Blahut type for computing quantum channel capacity

Hiroshi Nagaoka

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.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•32 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

Efficient algorithms for quantum information bottleneck

Masahito Hayashi, Yuxiang Yang

The ability to extract relevant information is critical to learning. An ingenious approach as such is the information bottleneck, an optimisation problem whose solution corresponds to a faithful and memory-efficient representation of relevant information from a large system. The advent of the age of quantum computing calls for efficient methods that work on information regarding quantum systems. Here we address this by proposing a new and general algorithm for the quantum generalisation of information bottleneck. Our algorithm excels in the speed and the definiteness of convergence compared with prior results. It also works for a much broader range of problems, including the quantum extension of deterministic information bottleneck, an important variant of the original information bottleneck problem. Notably, we discover that a quantum system can achieve strictly better performance than a classical system of the same size regarding quantum information bottleneck, providing new vision on justifying the advantage of quantum machine learning.

arXiv:2208.10342•Quantum•Mar 2, 2023•15 citations

Quantum Machine Learning For Classical Data

Leonard Wossnig

In this dissertation, we study the intersection of quantum computing and supervised machine learning algorithms, which means that we investigate quantum algorithms for supervised machine learning that operate on classical data. This area of research falls under the umbrella of quantum machine learning, a research area of computer science which has recently received wide attention. In particular, we investigate to what extent quantum computers can be used to accelerate supervised machine learning algorithms. The aim of this is to develop a clear understanding of the promises and limitations of the current state of the art of quantum algorithms for supervised machine learning, but also to define directions for future research in this exciting field. We start by looking at supervised quantum machine learning (QML) algorithms through the lens of statistical learning theory. In this framework, we derive novel bounds on the computational complexities of a large set of supervised QML algorithms under the requirement of optimal learning rates. Next, we give a new bound for Hamiltonian simulation of dense Hamiltonians, a major subroutine of most known supervised QML algorithms, and then derive a classical algorithm with nearly the same complexity. We then draw the parallels to recent "quantum-inspired" results, and will explain the implications of these results for quantum machine learning applications. Looking for areas which might bear larger advantages for QML algorithms, we finally propose a novel algorithm for Quantum Boltzmann machines, and argue that quantum algorithms for quantum data are one of the most promising applications for QML with potentially exponential advantage over classical approaches.

arXiv:2105.03684•May 8, 2021•14 citations
Abstract Quantum information bottleneck was proposed by Grimsmo and Still (2016 Phys. Rev. A 94 012338) as a promising method for quantum supervised machine learning. To study this method, we generalize the quantum Arimoto–Blahut algorithm by Ramakrishnan et al (2021 IEEE Trans. Inf. Theory 67 946) to a function defined over a set of density matrices with linear constraints so that our algorithm can be applied to optimizations of quantum operations. This algorithm has wider applicability, and we apply our algorithm to the quantum information bottleneck with three quantum systems. We numerically compare our obtained algorithm with the existing algorithm by Grimsmo and Still. Our numerical analysis shows that our algorithm is better than their algorithm.
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 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.
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.
The ability to extract relevant information is critical to learning. An ingenious approach as such is the information bottleneck, an optimisation problem whose solution corresponds to a faithful and memory-efficient representation of relevant information from a large system. The advent of the age of quantum computing calls for efficient methods that work on information regarding quantum systems. Here we address this by proposing a new and general algorithm for the quantum generalisation of information bottleneck. Our algorithm excels in the speed and the definiteness of convergence compared with prior results. It also works for a much broader range of problems, including the quantum extension of deterministic information bottleneck, an important variant of the original information bottleneck problem. Notably, we discover that a quantum system can achieve strictly better performance than a classical system of the same size regarding quantum information bottleneck, providing new vision on justifying the advantage of quantum machine learning.
In this dissertation, we study the intersection of quantum computing and supervised machine learning algorithms, which means that we investigate quantum algorithms for supervised machine learning that operate on classical data. This area of research falls under the umbrella of quantum machine learning, a research area of computer science which has recently received wide attention. In particular, we investigate to what extent quantum computers can be used to accelerate supervised machine learning algorithms. The aim of this is to develop a clear understanding of the promises and limitations of the current state of the art of quantum algorithms for supervised machine learning, but also to define directions for future research in this exciting field. We start by looking at supervised quantum machine learning (QML) algorithms through the lens of statistical learning theory. In this framework, we derive novel bounds on the computational complexities of a large set of supervised QML algorithms under the requirement of optimal learning rates. Next, we give a new bound for Hamiltonian simulation of dense Hamiltonians, a major subroutine of most known supervised QML algorithms, and then derive a classical algorithm with nearly the same complexity. We then draw the parallels to recent "quantum-inspired" results, and will explain the implications of these results for quantum machine learning applications. Looking for areas which might bear larger advantages for QML algorithms, we finally propose a novel algorithm for Quantum Boltzmann machines, and argue that quantum algorithms for quantum data are one of the most promising applications for QML with potentially exponential advantage over classical approaches.