Binary code rate bounds via classical--quantum channels
2026-08-10 • Information Theory
Information Theory
AI summaryⓘ
The authors show that several important limits on how well binary error-correcting codes can perform are all linked through a single principle called the "pretty good criterion." This idea uses a quantum measurement concept to connect the maximum transmission rate of a code to how often errors occur. By looking at different related quantum channels, the authors recover known classical bounds and also find new channels that give improved bounds on code performance. Their work turns the problem of finding code limits into designing appropriate quantum-like channels with certain error properties.
binary codesrate-distance tradeoffpretty good measurement (PGM)classical-quantum (cq) channelPlotkin boundElias-Bassalygo boundMRRW boundsbinary erasure channel (BEC)binary symmetric channel (BSC)pure-state channel (PSC)
Authors
Omar Alrabiah, Venkatesan Guruswami
Abstract
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $δ$, then every length-$n$ binary code, linear or nonlinear, of relative distance $δ$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly. This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < δ< \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.