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

Computational Aspects of the Trace Norm Contraction Coefficient

Idris Delsol, Omar Fawzi, Jan Kochanowski, Akshay Ramachandran

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

DOI
10.1109/tit.2026.3743741

Related papers

Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry

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 $ε$ in $\mathrm{poly}(1/ε, \text{input dimension})$ time.

arXiv:2308.15884•Aug 30, 2023•0 citations

Algorithmic aspects of optimal channel coding

Siddharth Barman, Omar Fawzi

A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1). 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/1-e-1. In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•3 citations

Average Contraction Coefficients of Quantum Channels

Rubén Ibarrondo, Daniel Stilck França

The data-processing inequality ensures quantum channels reduce state distinguishability, with contraction coefficients quantifying optimal bounds. However, these can be overly optimistic and not representative of the usual behavior. We study how noise contracts distinguishability of `typical' states, beyond the worst-case. To that end, we introduce and study a family of moments of contraction for quantum divergences, which interpolate between the worst-case contraction coefficient of a channel and its average behavior under a chosen ensemble of input states. We establish general properties of these moments, relate moments for different divergences, and derive bounds in terms of channel parameters like the entropy or purity of its Choi state. Focusing on the trace distance, we obtain upper and lower bounds on its average contraction under tensor-product noise channels, and prove that, depending on the local noise strength, there is a phase transition in the limit of many channel uses: below a critical error rate the average contraction remains near unity, whereas above it decays exponentially with system size. We extend these phase-transition phenomena to random quantum circuits with unital noise, showing that constant-depth noisy circuits do not shrink the trace distance on average, even when given highly entangled states as input. In contrast, even at $\log\log n$ depth, the average trace distance can become superpolynomially small. Finally, we explore moments of contraction for f-divergences and discuss applications to local differential privacy, demonstrating that noise regimes ensuring privacy can render outputs essentially indistinguishable on average. Thus, our results provide a fine-grained framework to quantify typical channel noise in quantum information and computation and unveil new phenomena in contraction coefficients, such as phase transitions for average contraction.

arXiv:2508.08214•Aug 11, 2025•0 citations

Algorithmic Aspects of Optimal Channel Coding

Siddharth Barman, Omar Fawzi

A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon, who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. The factor (1-e-1) can be improved arbitrarily close to 1 at the cost of slightly reducing the number of messages to be sent. Moreover, it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1) for the problem of computing the maximum success probability. 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most (1/(1 - e-1)). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.

arXiv:1508.04095•IEEE Transactions on Information Theory•Apr 24, 2017•22 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.

IEEE Transactions on Information Theory•Jul 16, 2025•0 citations

A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding

Hoang Ta, Hoang Anh Tran

Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.

quant-pharXiv:2609.09629•Sep 10, 2026•0 citations
We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.
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 εεε in poly(1/ε,input dimension)\mathrm{poly}(1/ε, \text{input dimension})poly(1/ε,input dimension) time.
A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1). 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/1-e-1. In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.
The data-processing inequality ensures quantum channels reduce state distinguishability, with contraction coefficients quantifying optimal bounds. However, these can be overly optimistic and not representative of the usual behavior. We study how noise contracts distinguishability of `typical' states, beyond the worst-case. To that end, we introduce and study a family of moments of contraction for quantum divergences, which interpolate between the worst-case contraction coefficient of a channel and its average behavior under a chosen ensemble of input states. We establish general properties of these moments, relate moments for different divergences, and derive bounds in terms of channel parameters like the entropy or purity of its Choi state. Focusing on the trace distance, we obtain upper and lower bounds on its average contraction under tensor-product noise channels, and prove that, depending on the local noise strength, there is a phase transition in the limit of many channel uses: below a critical error rate the average contraction remains near unity, whereas above it decays exponentially with system size. We extend these phase-transition phenomena to random quantum circuits with unital noise, showing that constant-depth noisy circuits do not shrink the trace distance on average, even when given highly entangled states as input. In contrast, even at log⁡log⁡n\log\log nloglogn depth, the average trace distance can become superpolynomially small. Finally, we explore moments of contraction for f-divergences and discuss applications to local differential privacy, demonstrating that noise regimes ensuring privacy can render outputs essentially indistinguishable on average. Thus, our results provide a fine-grained framework to quantify typical channel noise in quantum information and computation and unveil new phenomena in contraction coefficients, such as phase transitions for average contraction.
A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon, who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. The factor (1-e-1) can be improved arbitrarily close to 1 at the cost of slightly reducing the number of messages to be sent. Moreover, it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1) for the problem of computing the maximum success probability. 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most (1/(1 - e-1)). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.
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.
Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.