{"id":"arxiv/2601.22471","url":"https://arxiv.org/abs/2601.22471","tags":["quant-ph","cs.CC","cs.IT"],"score":0,"title":"On the undecidability of quantum channel capacities","domain":"quant-ph","source":"arxiv","authors":["Archishna Bhattacharyya","Arthur Mehta","Yuming Zhao"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-30","reactions":{}}