finite.works
Results · Quantum channels and memory

Where the quantum capacity sits in the arithmetical hierarchy

Seth Douglas and Nidhal Mghirbi · version 1.0.0 · Zenodo, · 15 pages · doi:10.5281/zenodo.23875900 · PDF

In plain wordsAn algorithm can produce certified lower bounds that converge to the quantum capacity of any effectively described finite-dimensional channel, without knowing how close each one is; this puts the question “is the capacity at least this much?” one level lower among unsolvable problems than a recent conjecture said.

The result

As the paper states it, in briefFor effectively described finite-dimensional channels, the quantum capacity Q is approximated uniformly from below by an increasing computable sequence of rationals, so the threshold problem for Q lies in Π20 and its gapped version is computably enumerable; consequently the conjecture of Bhattacharyya, Mehta and Zhao that the threshold problem is Π30-hard is false as printed under computable reductions. Positivity of Q is semi-decidable, and, on exact algebraic inputs, decidable exactly when the zero-capacity channels form a computably enumerable set. For the magic-square game graph every evaluated spectral bound equals 6, and the independence number of its strong square is exactly 29.

How this was checked

Blind checks
The main result derived twice independently and every result blind-checked
Blind audits
A blind audit of the whole note and a fix-check
Exact certificates
The graph certificates replayed with independent SAT solvers and checked DRAT proof traces.
Lean
None.
Peer review
Not yet.

Every check here is internal. How we check results.

Label checked .

Novelty and credit

Novelty
New, with named precedent: it applies standard effective finite-dimensional optimization and an effective form of Fekete’s lemma, both credited, and Oskouei and Mancini's approximability; Bhattacharyya, Mehta and Zhao printed the gapped bound. The contribution is the channel application and its consequences for the hierarchy. The one-shot zero-error statements are recoveries of prior work.

Versionsone, each with its own DOI

Every archived version, newest first. Dates are Zenodo publication dates.
VersionDateDOINotes
1.0.010.5281/zenodo.23875900 PDF hosted here.

Paper, code and links

PDF

papers/capacity-hierarchy-v1.0.0.pdf, version 1.0.0, 502,443 bytes, 15 pages.

SHA-256 dce097a16f0a247b891bb00ef47e03eacb20512555ef9cf6f499cb483eaf2d08

Corrections

None so far.

All corrections, and what counts as one.

Cite

@misc{douglas2026capacityhierarchy,
  author  = {Douglas, Seth and Mghirbi, Nidhal},
  title   = {Where the quantum capacity sits in the arithmetical hierarchy},
  year    = {2026},
  version = {1.0.0},
  doi     = {10.5281/zenodo.23875900},
  url     = {https://doi.org/10.5281/zenodo.23875900}
}

capacity-hierarchy.bibAll papers as BibTeX