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.
The noise threshold below which the qubit depolarizing channel retains positive quantum capacity has been studied since 1996. The classic constructions come with exact finite formulae, but in every reported threshold to date -- most recently the record of Agarwal et al. -- the final step, the sign of the coherent information at the reported point, is a floating-point evaluation. We give the first exact-arithmetic, independently machine-checkable positivity proofs in this regime: an explicit 45-copy rank-two input state
A, published as a 1,472-byte witness, with certified
Ic>0 at the exact rational
p=16239/250000=0.064956 (per-Pauli convention; total error rate
3p=0.194868) -- beyond both the best value printed in the Agarwal et al. paper (
0.064657) and the strongest state in the same authors' public repository (
≈0.064911), both numerical. Because the depolarizing family is a semigroup under composition, fixed-input coherent information is nonincreasing in
p on
[0,1/4], so a single certified point extends to the entire interval below it. The same machinery confines the positivity boundaries of
A and of the strongest public state of Agarwal et al. to disjoint rational intervals separated by more than
1/25000 -- to our knowledge the first proven ordering of the positivity boundaries of two explicit competing code states. Every computational claim in the paper reduces to a finite list of big-integer comparisons, checkable by a dependency-free few-hundred-line verifier whose soundness rests on three self-contained half-page lemmas. Payloads, certificates, and verifier accompany the paper as a supplementary artifact.
The quantum capacity of a noisy channel quantifies the maximum rate at which quantum information can be transmitted reliably. For general channels, its evaluation requires an optimization over arbitrarily many channel uses. Degradable channels form a central exception: their capacity is given by the single-letter coherent information, while antidegradable channels have zero capacity. Nevertheless, even for these fundamental classes, it has remained open whether communication above capacity becomes possible when a fixed non-maximal error is tolerated. Here we resolve this problem by proving an exponential strong converse for every finite-dimensional degradable and antidegradable channel: at any rate above capacity, the fidelity of every coding scheme decays exponentially with the number of channel uses. As an immediate consequence, we establish the first all-code exponential strong converse for the quantum erasure channel throughout its full parameter range, strengthening previous results that applied only to almost all codes. We also show that exponential strong-converse bounds are preserved under receiver post-processing. This yields efficiently computable semidefinite-programming bounds for arbitrary finite-dimensional channels, improved bounds for Pauli channels, and an exact exponential strong converse for a nondegradable multilevel amplitude-damping family.
Several ways to ask whether one quantum channel preserves more information turn out to give the same answer when every finite quantum reference is allowed. That complete comparison remains undecidable, even for strictly positive rational measurements. The result. Quantum channels can be compared by their preservation of relative entropy, Holevo information or symmetric logarithmic derivative Fisher information. Allowing an arbitrary finite untouched quantum reference makes these three comparisons equivalent. Passing to complementary channels reverses the order. The resulting comparison problem is coRE-complete, already for measurements with strictly positive rational-complex effects. The paper also gives an additive bounded entropy defect whose value cannot be computed to any fixed positive rational additive accuracy. How the argument works. An untouched reference is an auxiliary quantum system that may be correlated with the input. Its freedom connects local Fisher-information tests to global entropy comparisons through coherent blocks and resolvent identities. A purification identity relates information retained by the receiver to information lost to the environment. For the undecidability reduction, finite nonlocal games are encoded into inverse Sylvester kernels and then into strictly positive measurement effects. Finite witnesses detect failed comparisons, but their required reference dimensions have no computable uniform bound. Scope. Each individual channel, measurement and test is finite dimensional. Completeness quantifies over every finite reference dimension, with no common bound. The equivalence is a statistical information order; it does not by itself assert that one channel can be obtained by physically processing the other. The fixed-accuracy obstruction concerns the bounded entropy defect defined in the paper. Its conclusion depends on the complete comparison and the specified exact input representation. Related work. From complete channel order to capacity and one-way distillation.
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.
An information advantage can be converted into a positive communication rate using the constructed channel itself. The reduction makes exact-zero quantum and private capacity, and related one-way distillation questions, undecidable. The result. The paper turns a pair of quantum channels into one flagged channel with a four-dimensional auxiliary input. Complete information dominance holds exactly when the constructed channel has zero private capacity, and exactly when it has zero quantum capacity. A failed comparison therefore produces a positive communication rate. The construction transfers the companion paper’s undecidability to exact-zero capacity and to one-way entanglement and key distillation, even with a prescribed positive lower bound on two-way distillation. How the argument works. The comparison witness may involve a large quantum reference, which communication does not supply for free. Repeated uses of the flagged channel distribute that reference in quantum shares together with a classical key. The routing and key structure make unsuccessful patterns harmless and retain a finite positive private-information witness. Further uses of the same channel realize the helper needed to convert this private advantage into positive coherent information. All transmission and activation resources are provided by the constructed channel; no separate reference channel is assumed. Scope. The capacities are the ordinary unassisted quantum and private classical capacities of a finite-dimensional memoryless channel. The witnessing reference dimension, blocklength and positive rate may depend on the input channel pair. The undecidability distinguishes exactly zero from strictly positive capacity. It supplies no uniform positive rate gap and does not by itself obstruct additive approximation of capacity. The distillation consequences use the constructions and hypotheses stated in the paper. Related work. Complete information orders of quantum channels: equivalence and undecidability.
Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.