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:2308.15884 · IEEE Transactions on Information Theory

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

Yeow Meng Chee, Hoang Ta, Van Khu Vu

Published Jul 16, 2025• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2025.3589660

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

Quantum Coding via Semidefinite Programming

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

We derive converging hierarchies of efficiently computable semidefinite programming outer bounds on the optimal fidelity for the transmission of quantum information over noisy quantum channels. Based on positive partial transpose conditions we give a sufficient criterion for the exact convergence at any given level of the hierarchies. The worst case convergence speed of our hierarchies is quantified via positive semidefinite representable outer approximations on the set of separable Choi states, which are based on novel finite de Finetti theorems for quantum channels.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•1 citation

Semidefinite Programming for Quantum Channel Learning

Mikhail Gennadievich Belov, Victor Victorovich Dubov, Vadim Konstantinovich Ivanov +3 more

The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.

cs.LGCross-listedarXiv:2601.12502•Physical review. E•Jan 20, 2026•0 citations

On approximate quantum error correction for symmetric noise

Gereon Koßmann, Julius A. Zeiss, Omar Fawzi +1 more

We revisit the extendability-based semi-definite programming hierarchy introduced by Berta et al. [Mathematical Programming, 1 - 49 (2021)], which provides converging outer bounds on the optimal fidelity of approximate quantum error correction (AQEC). As our first contribution, we introduce a measurement-based rounding scheme that extracts inner sequences of certifiably good encoder-decoder pairs from this outer hierarchy. To address the computational complexity of evaluating fixed levels of the hierarchy, we investigate the use of symmetry-based dimension reduction. In particular, we combine noise symmetries - such as those present in multiple copies of the qubit depolarizing channel - with the permutational symmetry arising from the extendability of the optimization variable. This framework is illustrated through basic, but already challenging numerical examples that showcase its practical effectiveness. Our results contribute to narrowing the gap between theoretical developments in quantum information theory and their practical applications in the analysis of small-scale quantum error-correcting codes.

arXiv:2507.12326•Jul 16, 2025•4 citations

Semidefinite Programming Converse Bounds for Quantum Communication

Xin Wang, Kun Fang, Runyao Duan

We derive several efficiently computable converse bounds for quantum communication over quantum channels in both the one-shot and asymptotic regime. First, we derive one-shot semidefinite programming (SDP) converse bounds on the amount of quantum information that can be transmitted over a single use of a quantum channel, which improve the previous bound from [Tomamichel/Berta/Renes, Nat. Commun. 7, 2016]. As applications, we study quantum communication over depolarizing channels and amplitude damping channels with finite resources. Second, we find an SDP-strong converse bound for the quantum capacity of an arbitrary quantum channel, which means the fidelity of any sequence of codes with a rate exceeding this bound will vanish exponentially fast as the number of channel uses increases. Furthermore, we prove that the SDP-strong converse bound improves the partial transposition bound introduced by Holevo and Werner. Third, we prove that this SDP strong converse bound is equal to the so-called max-Rains information, which is an analog to the Rains information introduced in [Tomamichel/Wilde/Winter, IEEE Trans. Inf. Theory 63:715, 2017]. Our SDP strong converse bound is weaker than the Rains information, but it is efficiently computable for general quantum channels.

arXiv:1709.00200•IEEE Transactions on Information Theory•Oct 5, 2018•76 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
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 ϵinpoly(1/ϵ,input dimension)\mathrm {poly}(1/\epsilon, \text {input dimension})poly(1/ϵ,input dimension)time, compared to theexp⁡(1/ϵ,input dimension)\exp (1/\epsilon, \text {input dimension})exp(1/ϵ,input dimension)running time required for direct computation.
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 $.
We derive converging hierarchies of efficiently computable semidefinite programming outer bounds on the optimal fidelity for the transmission of quantum information over noisy quantum channels. Based on positive partial transpose conditions we give a sufficient criterion for the exact convergence at any given level of the hierarchies. The worst case convergence speed of our hierarchies is quantified via positive semidefinite representable outer approximations on the set of separable Choi states, which are based on novel finite de Finetti theorems for quantum channels.
The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.
We revisit the extendability-based semi-definite programming hierarchy introduced by Berta et al. [Mathematical Programming, 1 - 49 (2021)], which provides converging outer bounds on the optimal fidelity of approximate quantum error correction (AQEC). As our first contribution, we introduce a measurement-based rounding scheme that extracts inner sequences of certifiably good encoder-decoder pairs from this outer hierarchy. To address the computational complexity of evaluating fixed levels of the hierarchy, we investigate the use of symmetry-based dimension reduction. In particular, we combine noise symmetries - such as those present in multiple copies of the qubit depolarizing channel - with the permutational symmetry arising from the extendability of the optimization variable. This framework is illustrated through basic, but already challenging numerical examples that showcase its practical effectiveness. Our results contribute to narrowing the gap between theoretical developments in quantum information theory and their practical applications in the analysis of small-scale quantum error-correcting codes.
We derive several efficiently computable converse bounds for quantum communication over quantum channels in both the one-shot and asymptotic regime. First, we derive one-shot semidefinite programming (SDP) converse bounds on the amount of quantum information that can be transmitted over a single use of a quantum channel, which improve the previous bound from [Tomamichel/Berta/Renes, Nat. Commun. 7, 2016]. As applications, we study quantum communication over depolarizing channels and amplitude damping channels with finite resources. Second, we find an SDP-strong converse bound for the quantum capacity of an arbitrary quantum channel, which means the fidelity of any sequence of codes with a rate exceeding this bound will vanish exponentially fast as the number of channel uses increases. Furthermore, we prove that the SDP-strong converse bound improves the partial transposition bound introduced by Holevo and Werner. Third, we prove that this SDP strong converse bound is equal to the so-called max-Rains information, which is an analog to the Rains information introduced in [Tomamichel/Wilde/Winter, IEEE Trans. Inf. Theory 63:715, 2017]. Our SDP strong converse bound is weaker than the Rains information, but it is efficiently computable for general quantum channels.
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.