Computability of ordinary quantum capacity

Problem

Is the ordinary unassisted quantum capacity a computable function of a finite description of a finite-dimensional quantum channel? Let \(\mathcal N:\mathcal L(A)\to\mathcal L(B)\) be specified either by an exact finite list of Kraus matrices with computable algebraic entries (including rational entries) or by a finite quantum circuit over a fixed algebraic gate set, allowing state preparation and partial trace. For a complementary channel \(\mathcal N^c\), define coherent information and quantum capacity by

\begin{equation} I_c(\rho,\mathcal N) :=S(\mathcal N(\rho))-S(\mathcal N^c(\rho)), \qquad Q(\mathcal N) :=\sup_{n\geq1}\frac1n \max_{\rho_{A^{\otimes n}}} I_c(\rho_{A^{\otimes n}},\mathcal N^{\otimes n}), \tag{1} \end{equation}

where \(S(\tau):=-\operatorname{Tr}(\tau\log_2\tau)\). Writing \(\langle\mathcal N\rangle\) for either finite encoding above, the question is whether there exists a Turing machine \(T\) satisfying

\begin{equation} \forall\,\langle\mathcal N\rangle\ \forall k\in\mathbb N: \quad T(\langle\mathcal N\rangle,k)=q_{\mathcal N,k}\in\mathbb Q, \qquad |q_{\mathcal N,k}-Q(\mathcal N)|\leq2^{-k}. \tag{2} \end{equation}

Determine whether the algorithm in Eq. (2) exists for the capacity in Eq. (1), without imposing a running-time bound.

Source

Wilde explicitly asks whether quantum channel capacities are computable or undecidable. Bhattacharyya, Mehta, and Zhao formalize the complexity question for succinct circuit descriptions and state that uncomputability of ordinary quantum capacity remains unresolved [Wil17], [BMZ26].

Progress

Cubitt, Elkouss, Matthews, Ozols, Pérez-García, and Strelchuk prove that no universal fixed tensor power detects all positive quantum capacities. For every \(m\in\mathbb N\), they construct a channel \(\mathcal N_m\) such that

\begin{equation} \max_{\rho_{A^{\otimes m}}} I_c(\rho_{A^{\otimes m}},\mathcal N_m^{\otimes m})=0, \qquad Q(\mathcal N_m)>0. \tag{3} \end{equation}

Equation (3) rules out evaluating Eq. (1) at one channel-independent blocklength, but it does not rule out a different terminating algorithm [CEM+15].
Bhattacharyya, Mehta, and Zhao prove that, for a channel supplied by a succinct quantum-circuit description, deciding whether \(Q(\mathcal N)\geq3/4\) or \(Q(\mathcal N)\leq1/4\), under that promise, is QMA-hard. This is a lower bound on efficient computation, not a proof that the unrestricted Turing machine in Eq. (2) cannot exist [BMZ26].
The same 2026 preprint proves an uncomputability result only for the restricted one-shot zero-error classical quantity \(C^{(1)}_{0,\mathrm{PME}}\) of classical–quantum channels, where the shared state is maximally entangled and decoding is by a projective measurement. That theorem is not an ordinary-quantum-capacity result and therefore does not settle Eq. (2). The cited work is an unrefereed version 3 preprint; its authors report that version 2 contained an error in the undecidability section that version 3 corrects [BMZ26].

Comment

The precise gap is computability with no complexity bound, as formalized in Eq. (2). QMA-hardness for succinct inputs, failure of every universal fixed-block truncation, and uncomputability of a restricted zero-error assisted capacity are all compatible with either answer to this problem.

References

[Wil17]: M. M. Wilde, Quantum Information Theory, 2nd ed., Cambridge University Press (2017), Sec. 26.6.DOI arXiv
[CEM+15]: T. Cubitt, D. Elkouss, W. Matthews, M. Ozols, D. Pérez-García, and S. Strelchuk, “Unbounded Number of Channel Uses May Be Required to Detect Quantum Capacity,” Nature Communications 6, 6739 (2015).DOI arXiv
[BMZ26]: A. Bhattacharyya, A. Mehta, and Y. Zhao, “On the Undecidability of Quantum Channel Capacities,” arXiv preprint (2026), version 3.arXiv

Computability of ordinary quantum capacity

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems