Where the quantum capacity sits in the arithmetical hierarchy

Quantum capacity can be approximated uniformly from below. For effectively described finite-dimensional channels, we give certified algorithms for every finite-block coherent-information maximum and an increasing rational sequence converging to the capacity Q. The closed threshold Q at least one half therefore lies in the second universal level of the arithmetical hierarchy. This contradicts the third-level hardness conjectured by Bhattacharyya, Mehta and Zhao, under standard computable reductions. Positivity of Q is semidecidable. On exact algebraic inputs it is decidable precisely when zero capacity has a complete effective certificate system; an activation-bound converse is conditional on decidability of the real exponential field. A measure-and-erase wrapper gives an undecidable all-length predicate for precisely specified MPO-generated families. For zero-error communication we distinguish known one-shot results from an unproved OR-repetition step. On the synchronous magic-square graph, all evaluated spectral families give six, including fractional Haemers bounds over every field, while a certified computation gives strong-square independence number 29. Either its Shannon capacity is six or a spectral point outside those families lies below six.