On the undecidability of quantum channel capacities
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917370070564864 |
|---|---|
| author | Bhattacharyya, Archishna Mehta, Arthur Zhao, Yuming |
| author_facet | Bhattacharyya, Archishna Mehta, Arthur Zhao, Yuming |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22471 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the undecidability of quantum channel capacities Bhattacharyya, Archishna Mehta, Arthur Zhao, Yuming Quantum Physics Computational Complexity Information Theory 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. |
| title | On the undecidability of quantum channel capacities |
| topic | Quantum Physics Computational Complexity Information Theory |
| url | https://arxiv.org/abs/2601.22471 |