One-shot zero-error communication with normal entanglement is Σ⁰₂-complete

As the paper states it, in briefDeciding whether a finite rational classical channel, used once, can send a given number of messages without error when sender and receiver share an arbitrary normal state on a tensor product of Hilbert spaces is Σ⁰₂-complete; the same classification holds when the resource must have finite marginal entropy. A separate channel admits a normal zero-error code, while every normal code achieving its specified message count has infinite marginal entropy on both sides. The proof extends Mančinska’s finite-dimensional game-to-channel correspondence to trace-class operators; finite-dimensional resources give Σ⁰₁-completeness and commuting operators Π⁰₁-completeness.

Verification

Independent reviews of the operator arguments, attribution, complexity reductions and entropy calculations; exact and numerical finite checks of strategy and code matrices, bridge constants, spectrum identities and Catalan generating-function identities.

Lean

None.

Peer review

Not yet.

Novelty

New, with named prior work. To our knowledge, the normal trace-class correspondence, the ${\mathrm{\Sigma }}_2^0$ classification for normal resources, the summability threshold of the compiled games, the infinite-entropy-only channel and the saturation reduction for commuting codes are new; the paper calls this priority statement provisional. The finite-dimensional core is Mančinska’s: clique saturation, the converse with its square-root state map and the entanglement-assisted independence-number characterization, which the paper extends to trace-class operators; the finite-dimensional ${\mathrm{\Sigma }}_1^0$ row is a corollary of her correspondence and of Ji, Natarajan, Vidick, Wright and Yuen’s MIP* = RE. The operator characterization of entanglement-assisted zero-error codes is due to Cubitt, Leung, Matthews and Winter; the commuting row starts from Slofstra’s ${\mathrm{\Pi }}_1^0$-hardness, reproved by Mousavi, Nezhadi and Yuen; Bhattacharyya, Mehta and Zhao proved undecidability for a restricted one-shot parameter of classical-to-quantum channels. The compiler and the Catalan assembly come from the authors’ Σ⁰₂ paper and entropy-game paper.

As the paper states, the finite checks do not prove infinite-dimensional existence, compactness or arithmetical hardness; those rest on the written proofs and the cited source reductions. The hardness results concern one use of the channel; its capacity statements are upper bounds on computability.

Every check here is internal. How we check results.

Label checked 3 November 2026.

PDF

papers/zero-error-v1.0.0.pdf, version 1.0.0, 567,518 bytes, 23 pages.

SHA-256 25ed40a9f9a6e1032bd034128b4aa65a3f16dd22dc1817df67eefe897ea115ac

Of paper/main.pdf, 567,518 bytes, in the Zenodo archive; identical in the repository at that commit. The same file is hosted here: papers/zero-error-v1.0.0.pdf.

DOI

10.5281/zenodo.23924869; all versions 10.5281/zenodo.23924868

Code

github.com/Apsiape/zero-error-entanglement

Commit

7410e3b2c96185ea8c0a0849ef578cfc14de1f7c

The commit archived on Zenodo (Apsiape/zero-error-entanglement, tag v1.0.0). The main branch has since recorded the DOI.

Licence

Paper and documentation CC BY 4.0; scripts MIT or Apache 2.0, at your option.

None so far.

All corrections, and what counts as one.

@misc{douglas2026zeroerror,
  author  = {Douglas, Seth and Mghirbi, Nidhal},
  title   = {One-shot zero-error communication with normal entanglement is $\Sigma^0_2$-complete},
  year    = {2026},
  version = {1.0.0},
  doi     = {10.5281/zenodo.23924869},
  url     = {https://doi.org/10.5281/zenodo.23924869}
}

zero-error.bibAll papers as BibTeX