Is the quantum capacity of a channel computable? · revision history

Revision 2

Accepted · core change · record

Changes against revision 1:

Title · changed
Revision 1: Is the quantum capacity of a channel computable
Revision 2: Is the quantum capacity of a channel computable?
Plain
The quantum capacity of a channel is defined by a limit over ever more channel uses, and some channels show positive capacity only after arbitrarily many uses. Whether any algorithm can compute the capacity to a given accuracy, or even decide whether it is zero, is unknown.
Precise · changed · core
Revision 1: $Q(N) = \lim_{n \to \infty} (1/n) \max_\rho I_c(\rho, N^{(\mathrm{tensor}\ n)})$, with $I_c$ the coherent information. Is there an algorithm that, given a channel N with rational Kraus operators and $\epsilon > 0$, outputs $Q(N)$ to within $\epsilon$, or that decides whether $Q(N) > 0$? Cubitt et al. (Nat. Commun. 6, 7739, 2015, arXiv:1408.5115) showed that for every n there are channels with zero n-use coherent information and positive capacity.
Revision 2: $Q(N) = \lim_{n \to \infty} (1/n) \max_\rho I_c(\rho, N^{(\otimes\ n)})$, with $I_c$ the coherent information. Is there an algorithm that, given a channel N with rational Kraus operators and $\epsilon > 0$, outputs $Q(N)$ to within $\epsilon$, or that decides whether $Q(N) > 0$? Cubitt et al. (Nat. Commun. 6, 7739, 2015, arXiv:1408.5115) showed that for every n there are channels with zero n-use coherent information and positive capacity.
Settled by
A convergent algorithm with an explicit error bound for $Q(N)$, or a reduction from an undecidable problem to deciding $Q(N) > 0$.
Kind
well-posed
Answer type
yes-no
References
(empty)
Literature status
open
Status note
(empty)
Posed since
2015

Decisions