Is the quantum capacity of a channel computable?

36

No. 1,406 in all physics · No. 66 in Quantum Information and Foundations

Non-expert version

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

What would settle it

A convergent algorithm with an explicit error bound for $Q(N)$, or a reduction from an undecidable problem to deciding $Q(N) > 0$.

No solutions, ideas or subproblems yet.

How results are checked

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

Details, signature and history
Kind
Well-posed question
Answer
Yes no
Posed
2015
Topic review
R. Horodecki, P. Horodecki, M. Horodecki and K. Horodecki, Quantum entanglement, Reviews of Modern Physics, 2009. Link
Record
Revision 2 · notation repaired by the platform · compiled by AI, not yet reviewed by an editor
Batch approval
Approved for the batch by Victor Galitski (ORCID 0000-0001-5532-1096) · approval record · bundle This approves the batch, not each problem (what it means).
Earlier revisions
revision 1 bundle

Proof

Fingerprint
ef1018432235…
Public log
Entry 2,037, in checkpoint 2,123
In the log by
Block 969,698, 2026-10-03

This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.

History