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

On the undecidability of quantum channel capacities

Archishna Bhattacharyya, Arthur Mehta, Yuming Zhao

quant-phcs.CCcs.ITSubmitted Jan 30, 2026• Announced Feb 2, 2026• 0 citations• Revised Mar 30, 2026 (v3)
v1 · Jan 30, 2026v2 · Feb 10, 2026v3 · Mar 30, 2026
arXivHTMLPDF

Abstract

An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.

Journal reference
2026 IEEE 67th Annual Symposium on Foundations of Computer Science (FOCS)
Comments
29 pages, 2 figures, v2 contained an error in Section 4 which is corrected in v3 by updating Section 4 and Section 2. The introduction is also updated

Related papers

The computational two-way quantum capacity

Johannes Jakob Meyer, Jacopo Rizzo, Asad Raza +3 more

Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.

quant-pharXiv:2601.15393•Jan 23, 2026•0 citations

Computing Quantum Channel Capacities

Navneeth Ramakrishnan, Raban Iten, Volkher B. Scholz +1 more

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.

arXiv:1905.01286•IEEE Transactions on Information Theory•Oct 28, 2020•33 citations

Potential Capacities of Quantum Channels

Andreas Winter, Dong Yang

We introduce potential capacities of quantum channels in an operational way and provide upper bounds for these quantities, which quantify the ultimate limit of usefulness of a channel for a given task in the best possible context. Unfortunately, except for a few isolated cases, potential capacities seem to be as hard to compute as their plain analogues. We thus study upper bounds on some potential capacities. For the classical capacity, we give an upper bound in terms of the entanglement of formation. To establish a bound for the quantum and private capacity, we first lift the channel to a Hadamard channel and then prove that the quantum and private capacity of a Hadamard channel is strongly additive, implying that for these channels, potential and plain capacity are equal. Employing these upper bounds, we show that if a channel is noisy, however close it is to the noiseless channel, then it cannot be activated into the noiseless channel by any other contextual channel; this conclusion holds for all the three capacities. We also discuss the so-called environment-assisted quantum capacity, because we are able to characterize its potential version.

arXiv:1505.00907•IEEE Transactions on Information Theory•Jan 21, 2016•37 citations

Coding Theorems for Hybrid Channels. II

A. A. Kuznetsova, Alexander Semenovich Holevo

The present paper continues investigation of the capacities of measurement (quantum-classical) channels in the most general setting, initiated in [A. A. Kuznetsova and A. S. Holevo, Theory Probab. Appl., 58 (2014), pp. 264--285]. The proof of coding theorems is given for the classical capacity and entanglement-assisted classical capacity of the measurement channel with arbitrary output alphabet, without assuming that the channel is given by a bounded operator-valued density.

arXiv:1408.3255•Theory of Probability and Its Applications•Jan 1, 2015•5 citations

Bounding quantum capacities via partial orders and complementarity

Christoph Hirche, Felix Leditzky

Quantum capacities are fundamental quantities that are notoriously hard to compute and can exhibit surprising properties such as superadditivity. Thus a vast amount of literature is devoted to finding close and computable bounds on these capacities. We add a new viewpoint by giving operationally motivated bounds on several capacities, including the quantum capacity and private capacity of a channel and the one-way distillable entanglement and private key of a bipartite state. Our bounds themselves are generally given by certain capacities of the complementary channel or state. As a tool to obtain these bounds we discuss partial orders on quantum channels, such as the less noisy and the more capable order. Our bounds help to further understand the interplay between different capacities and give operational limitations on superadditivity properties and the difference between capacities. They can also be used as a new approach towards numerically bounding capacities, as discussed with some examples.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•3 citations

Quantum Entanglement Assistance Improves the Capacity and Activates the Zero-Error Capacity of Classical Channels with Causal CSIT

Yuhang Yao, Syed A. Jafar

For classical point-to-point channels, it has been shown by Bennett et al. that quantum entanglement assistance cannot improve their capacity, and by Cubitt et al. that entanglement assistance cannot activate (increase from zero to non-zero) their zero-error capacity. In contrast, we show that for classical point-to-point channels with causal CSIT (channel state information at the transmitter), quantum entanglement assistance can in some cases improve their capacity, and in some cases activate their zero-error capacity.

quant-pharXiv:2603.20416•Mar 24, 2026•0 citations
An important distinction in our understanding of capacities of classical versus quantum channels is marked by the following question: is there an algorithm which can compute (or even efficiently compute) the capacity? While there is overwhelming evidence suggesting that quantum channel capacities may be uncomputable, a formal proof of any such statement is elusive. We initiate the study of the hardness of computing quantum channel capacities. We show that, for a general quantum channel, it is QMA-hard to compute its quantum capacity, and that the entanglement-assisted zero-error capacity under some restrictions is uncomputable; indicative of the fact that quantum channel capacities may generally be undecidable.
Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.
The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.
We introduce potential capacities of quantum channels in an operational way and provide upper bounds for these quantities, which quantify the ultimate limit of usefulness of a channel for a given task in the best possible context. Unfortunately, except for a few isolated cases, potential capacities seem to be as hard to compute as their plain analogues. We thus study upper bounds on some potential capacities. For the classical capacity, we give an upper bound in terms of the entanglement of formation. To establish a bound for the quantum and private capacity, we first lift the channel to a Hadamard channel and then prove that the quantum and private capacity of a Hadamard channel is strongly additive, implying that for these channels, potential and plain capacity are equal. Employing these upper bounds, we show that if a channel is noisy, however close it is to the noiseless channel, then it cannot be activated into the noiseless channel by any other contextual channel; this conclusion holds for all the three capacities. We also discuss the so-called environment-assisted quantum capacity, because we are able to characterize its potential version.
Quantum capacities are fundamental quantities that are notoriously hard to compute and can exhibit surprising properties such as superadditivity. Thus a vast amount of literature is devoted to finding close and computable bounds on these capacities. We add a new viewpoint by giving operationally motivated bounds on several capacities, including the quantum capacity and private capacity of a channel and the one-way distillable entanglement and private key of a bipartite state. Our bounds themselves are generally given by certain capacities of the complementary channel or state. As a tool to obtain these bounds we discuss partial orders on quantum channels, such as the less noisy and the more capable order. Our bounds help to further understand the interplay between different capacities and give operational limitations on superadditivity properties and the difference between capacities. They can also be used as a new approach towards numerically bounding capacities, as discussed with some examples.
For classical point-to-point channels, it has been shown by Bennett et al. that quantum entanglement assistance cannot improve their capacity, and by Cubitt et al. that entanglement assistance cannot activate (increase from zero to non-zero) their zero-error capacity. In contrast, we show that for classical point-to-point channels with causal CSIT (channel state information at the transmitter), quantum entanglement assistance can in some cases improve their capacity, and in some cases activate their zero-error capacity.