On the undecidability of quantum channel capacities
This addresses a fundamental distinction in information theory between classical and quantum channels, with implications for quantum computing and communication, though it is incremental as it builds on existing evidence of uncomputability.
The paper tackles the problem of computing quantum channel capacities, showing that for a general quantum channel, computing its quantum capacity is QMA-hard and the entanglement-assisted zero-error capacity under some restrictions is uncomputable, indicating potential undecidability.
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.