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)

A hierarchy of efficient bounds on quantum capacities exploiting symmetry

Omar Fawzi, Ala Shayeghi, Hoang Ta

Published Jul 12, 2021• 5 citations
Publisher

Abstract

Optimal rates for achieving an information processing task are often characterized in terms of regularized information measures. In many cases of quantum tasks, we do not know how to compute such quantities. Here, we exploit the symmetries in the recently introduced divergence$\mathrm{D}^{\#}$in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As an application, we describe a general procedure to give efficient bounds on the regularized Umegaki channel divergence and on the classical capacity of quantum channels, and in particular we obtain slight improvements for the capacity of the amplitude damping channel.

DOI
10.1109/isit45174.2021.9517913

Related papers

A Hierarchy of Efficient Bounds on Quantum Capacities Exploiting Symmetry

Omar Fawzi, Ala Shayeghi, Hoang Ta

Optimal rates for achieving an information processing task are often characterized in terms of regularized information measures. In many cases of quantum tasks, we do not know how to compute such quantities. Here, we exploit the symmetries in the recently introduced$\mathrm {D}^{\#}$in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As applications, we give a general procedure to give efficient bounds on the regularized Umegaki channel divergence as well as the classical capacity and two-way assisted quantum capacity of quantum channels. In particular, we obtain slight improvements for the capacity of the amplitude damping channel. We also prove that for fixed input and output dimensions, the regularized sandwiched Rényi divergence between any two quantum channels can be approximated up to an$\epsilon $accuracy in time that is polynomial in$1/\epsilon $.

arXiv:2203.02127•IEEE Transactions on Information Theory•Jun 10, 2022•18 citations

An Efficient Parameterized Algorithm for Computing Quantum Channel Fidelity via Symmetries Exploitation

Yeow Meng Chee, Hoang Ta, Van Khu Vu

Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon $in$\mathrm {poly}(1/\epsilon, \text {input dimension})$time, compared to the$\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.

arXiv:2308.15884•IEEE Transactions on Information Theory•Jul 16, 2025•5 citations

Semidefinite optimization for quantum information

Xin Wang

This thesis aims to improve our understanding of the structure of quantum entanglement and the limits of information processing with quantum systems. It presents new results relevant to three threads of quantum information: the theory of quantum entanglement, the communication capabilities of quantum channels, and the quantum zero-error information theory. \nIn the first part, we investigate the fundamental features of quantum entanglement and develop quantitative approaches to better exploit the power of entanglement. First, we introduce a computable and additive entanglement measure to quantify the amount of entanglement, which also plays an important role as the improved semidefinite programming (SDP) upper bound of distillable entanglement. Second, we show that the Rains bound is neither additive nor equal to the asymptotic relative entropy of entanglement. Third, we establish SDP lower bounds for the entanglement cost and demonstrate the irreversibility of asymptotic entanglement manipulation under positive-partial-transpose-preserving quantum operations, resolving a major open problem in quantum information theory. \nIn the second part, we develop a framework of semidefinite programs to evaluate the classical and quantum communication capabilities of quantum channels in both the non-asymptotic and asymptotic regimes. In particular, we establish the first general SDP strong converse bound on the classical capacity of an arbitrary quantum channel and give in particular the best known upper bound on the classical capacity of the amplitude damping channel. We further establish a finite resource analysis of classical communication over quantum erasure channels, including the first second-order expansion of classical capacity beyond entanglement-breaking channels. For quantum communication, we establish the best SDP-computable strong converse bound and refine it as the so-called max-Rains information. \nIn the third part, we investigate the quantum zero-error information theory. In contrast to the conventional Shannon theory, there is a very different-looking information theory when errors are required to be precisely zero, where the communication problem reduces to the analysis of the so-called confusability graph (noncommutative graph) of a classical channel (quantum channel). We develop an activated communication model and explore its novel properties. Notably, we separate the quantum Lovász number and the entanglement-assisted zero-error capacity, resolving an intriguing open problem in the area of zero-error information.

•Jan 1, 2018•7 citations

Efficient optimization of the quantum relative entropy

Hamza Fawzi, Omar Fawzi

Abstract Many quantum information measures can be written as an optimization of the quantum relative entropy between sets of states. For example, the relative entropy of entanglement of a state is the minimum relative entropy to the set of separable states. The various capacities of quantum channels can also be written in this way. We propose a unified framework to numerically compute these quantities using off-the-shelf semidefinite programming solvers, exploiting the approximation method proposed in Fawzi, Saunderson and Parrilo (2017 arXiv: 1705.00812). As a notable application, this method allows us to provide numerical counterexamples for a proposed lower bound on the quantum conditional mutual information in terms of the relative entropy of recovery.

arXiv:1705.06671•Journal of Physics A Mathematical and Theoretical•Feb 27, 2018•72 citations

Defining quantum divergences via convex optimization

Hamza Fawzi, Omar Fawzi

We introduce a new quantum Rényi divergence Dα# for α∈(1,∞) defined in terms of a convex optimization program. This divergence has several desirable computational and operational properties such as an efficient semidefinite programming representation for states and channels, and a chain rule property. An important property of this new divergence is that its regularization is equal to the sandwiched (also known as the minimal) quantum Rényi divergence. This allows us to prove several results. First, we use it to get a converging hierarchy of upper bounds on the regularized sandwiched α -Rényi divergence between quantum channels for α>1 . Second it allows us to prove a chain rule property for the sandwiched α -Rényi divergence for α>1 which we use to characterize the strong converse exponent for channel discrimination. Finally it allows us to get improved bounds on quantum channel capacities.

arXiv:2007.12576•Quantum•Jan 26, 2021•49 citations

Permutation Invariant Optimization Problems in Quantum Information Theory: A Framework for Channel Fidelity and Beyond

Bjarne Bergh, Marco Parentin

Exploiting permutation invariance to reduce the exponential scaling of semidefinite programs in quantum information has emerged as a powerful computational technique. In this work, we develop a systematic framework for using this reduction via Schur-Weyl duality for optimization problems, and establish methods that allow one to work fully inside the permutation invariant subspace while performing operations such as (partially) applying channels and taking (partial) traces, or computing expressions like the quantum relative entropy. We then apply our techniques to the problem of computing efficient lower bounds on the channel fidelity over $n$ parallel uses of a quantum channel. The algorithm, which we call symmetric seesaw method, exploits permutation-invariant codes to yield improved lower bounds on the channel fidelity over $n$ uses of the depolarizing and amplitude-damping channel in the regime of tens of channel uses, and was used in [arxiv:2604.27042] to demonstrate non-asymptotic superactivation of quantum capacity for $n = 17$. An implementation of our methods, aimed at being suitable for various quantum information theoretic optimization problems, is also available as an open-source Python package.

quant-pharXiv:2604.27040•Apr 30, 2026•3 citations
Optimal rates for achieving an information processing task are often characterized in terms of regularized information measures. In many cases of quantum tasks, we do not know how to compute such quantities. Here, we exploit the symmetries in the recently introduced divergenceD#\mathrm{D}^{\#}D#in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As an application, we describe a general procedure to give efficient bounds on the regularized Umegaki channel divergence and on the classical capacity of quantum channels, and in particular we obtain slight improvements for the capacity of the amplitude damping channel.
Optimal rates for achieving an information processing task are often characterized in terms of regularized information measures. In many cases of quantum tasks, we do not know how to compute such quantities. Here, we exploit the symmetries in the recently introducedD#\mathrm {D}^{\#}D#in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As applications, we give a general procedure to give efficient bounds on the regularized Umegaki channel divergence as well as the classical capacity and two-way assisted quantum capacity of quantum channels. In particular, we obtain slight improvements for the capacity of the amplitude damping channel. We also prove that for fixed input and output dimensions, the regularized sandwiched Rényi divergence between any two quantum channels can be approximated up to an$\epsilon $accuracy in time that is polynomial in$1/\epsilon $.
Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon ininin\mathrm {poly}(1/\epsilon, \text {input dimension})time,comparedtothetime, compared to thetime,comparedtothe\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.
This thesis aims to improve our understanding of the structure of quantum entanglement and the limits of information processing with quantum systems. It presents new results relevant to three threads of quantum information: the theory of quantum entanglement, the communication capabilities of quantum channels, and the quantum zero-error information theory. \nIn the first part, we investigate the fundamental features of quantum entanglement and develop quantitative approaches to better exploit the power of entanglement. First, we introduce a computable and additive entanglement measure to quantify the amount of entanglement, which also plays an important role as the improved semidefinite programming (SDP) upper bound of distillable entanglement. Second, we show that the Rains bound is neither additive nor equal to the asymptotic relative entropy of entanglement. Third, we establish SDP lower bounds for the entanglement cost and demonstrate the irreversibility of asymptotic entanglement manipulation under positive-partial-transpose-preserving quantum operations, resolving a major open problem in quantum information theory. \nIn the second part, we develop a framework of semidefinite programs to evaluate the classical and quantum communication capabilities of quantum channels in both the non-asymptotic and asymptotic regimes. In particular, we establish the first general SDP strong converse bound on the classical capacity of an arbitrary quantum channel and give in particular the best known upper bound on the classical capacity of the amplitude damping channel. We further establish a finite resource analysis of classical communication over quantum erasure channels, including the first second-order expansion of classical capacity beyond entanglement-breaking channels. For quantum communication, we establish the best SDP-computable strong converse bound and refine it as the so-called max-Rains information. \nIn the third part, we investigate the quantum zero-error information theory. In contrast to the conventional Shannon theory, there is a very different-looking information theory when errors are required to be precisely zero, where the communication problem reduces to the analysis of the so-called confusability graph (noncommutative graph) of a classical channel (quantum channel). We develop an activated communication model and explore its novel properties. Notably, we separate the quantum Lovász number and the entanglement-assisted zero-error capacity, resolving an intriguing open problem in the area of zero-error information.
Abstract Many quantum information measures can be written as an optimization of the quantum relative entropy between sets of states. For example, the relative entropy of entanglement of a state is the minimum relative entropy to the set of separable states. The various capacities of quantum channels can also be written in this way. We propose a unified framework to numerically compute these quantities using off-the-shelf semidefinite programming solvers, exploiting the approximation method proposed in Fawzi, Saunderson and Parrilo (2017 arXiv: 1705.00812). As a notable application, this method allows us to provide numerical counterexamples for a proposed lower bound on the quantum conditional mutual information in terms of the relative entropy of recovery.
We introduce a new quantum Rényi divergence Dα# for α∈(1,∞) defined in terms of a convex optimization program. This divergence has several desirable computational and operational properties such as an efficient semidefinite programming representation for states and channels, and a chain rule property. An important property of this new divergence is that its regularization is equal to the sandwiched (also known as the minimal) quantum Rényi divergence. This allows us to prove several results. First, we use it to get a converging hierarchy of upper bounds on the regularized sandwiched α -Rényi divergence between quantum channels for α>1 . Second it allows us to prove a chain rule property for the sandwiched α -Rényi divergence for α>1 which we use to characterize the strong converse exponent for channel discrimination. Finally it allows us to get improved bounds on quantum channel capacities.
Exploiting permutation invariance to reduce the exponential scaling of semidefinite programs in quantum information has emerged as a powerful computational technique. In this work, we develop a systematic framework for using this reduction via Schur-Weyl duality for optimization problems, and establish methods that allow one to work fully inside the permutation invariant subspace while performing operations such as (partially) applying channels and taking (partial) traces, or computing expressions like the quantum relative entropy. We then apply our techniques to the problem of computing efficient lower bounds on the channel fidelity over nnn parallel uses of a quantum channel. The algorithm, which we call symmetric seesaw method, exploits permutation-invariant codes to yield improved lower bounds on the channel fidelity over nnn uses of the depolarizing and amplitude-damping channel in the regime of tens of channel uses, and was used in [arxiv:2604.27042] to demonstrate non-asymptotic superactivation of quantum capacity for n=17n = 17n=17. An implementation of our methods, aimed at being suitable for various quantum information theoretic optimization problems, is also available as an open-source Python package.