Binary code rate bounds via classical--quantum channels
Omar Alrabiah, Venkatesan Guruswami
cs.IT, math.CO, quant-ph
2026-08-10
A pretty good criterion turns binary rate-distance bounds into cq channel design. Mixed-qubit channels strictly improve both MRRW bounds for every δ in (0, 1/2).
Error-correcting codes are scored on two rulers. Hamming's asks for worst-case distance: a code of minimum distance δn corrects every pattern of fewer than δn/2 flips. Shannon's asks for typical-case reliability: capacity is the highest rate at which a memoryless channel can be used with vanishing block error.
Capacity was settled in 1948. The asymptotic rate-distance function R₂(δ) was not. The best general lower bound is still Gilbert-Varshamov, R₂(δ) ≥ 1−h(δ). On the upper side, the two McEliece-Rodemich-Rumsey-Welch (MRRW) bounds from 1977 sat as the benchmark for nearly five decades. Plotkin already forces rate zero at relative distance 1/2, while the binary symmetric channel still has positive capacity at every flip probability below 1/2. That gap is the whole subject.
Alrabiah and Guruswami collapse the four classical upper bounds into one test, the pretty good criterion. Take any binary-input, output-symmetric classical-quantum (cq) channel. Decode it with the pretty good measurement (PGM), the quantum analog of posterior sampling: draw a hypothesis from the posterior rather than taking the mode. If the PGM bit error rate pe sits strictly below δ, every binary code of length n and relative distance δ, linear or not, has rate at most the channel's Holevo capacity, plus O(n^{-1/2}).
The operational content is a constant-probability block decode. PGM is closed under coarse-graining, so each coordinate of a block sample is a posterior sample of that bit. Expected Hamming distance is then at most n·pe. A wrong codeword is at least δn away, so the success probability is at least 1 − pe/δ. Once pe < δ, that probability is a positive constant. The strong converse for cq channel coding says that rates above capacity drive block error to one. A constant chance of success is already enough to pin the rate.
Four old bounds fall out by picking the channel:
Restricted to classical binary-input channels, the criterion cannot beat Elias-Bassalygo. Stronger bounds need noncommuting outputs.
The new mixed-qubit channel (MQC) is PSC after a bit-flip layer, with the classical error discarded. Mixing lowers Holevo information and raises PGM error; the bound tightens when the former drops faster. Masking the MQC produces 2MQC.
MQC lies strictly below the first MRRW bound for every δ in (0, 1/2). At δ=1/4, the first MRRW value is about 0.3545789, the second about 0.3537105, and the numerical MQC minimizer about 0.3503791. Near δ→1/2 the gap shrinks as ε⁴ log e with ε=1/2−δ, so the low-rate end is almost glued together.
2MQC lies strictly below the second MRRW bound on the same interval. The table is a floating-point estimate, not a certified global optimum. The largest listed gap is at δ=0.25: second MRRW ≈ 0.353711 versus 2MQC ≈ 0.350379, a difference of about 0.00333. At δ=0.05 the gap is only 6.6×10^{-7}.
| relative distance δ | second MRRW | 2MQC estimate | gap |
| 0.10 | 0.692741 | 0.692727 | 1.3×10^{-5} |
| 0.25 | 0.353711 | 0.350379 | 0.00333 |
| 0.40 | 0.081469 | 0.081337 | 1.3×10^{-4} |
For LDPC codes whose dual is generated by checks of weight at most 3, a one-check PSC decoder yields U₃^{PSC}. It sits below the first MRRW bound on the whole interval, and below the Shangguan-Yang 2026 curve B₃^{SY} for δ ≥ 1/6. At δ=3/10: U₃^{PSC}≈0.2065, B₃^{SY}≈0.2476, first MRRW≈0.2502.
The q-ary extension is a blueprint: cyclic output-symmetry plus the same PGM-to-capacity test. Erasure, symmetric, pure-state, and mixed families recover known q-ary bounds. No new numerical record is claimed.
The fifty-year general upper bound for binary codes has been moved, and the search itself has been recast as a channel-design problem: minimize Holevo information subject to pe ≤ δ. MQC and 2MQC are two feasible points, not the optimum.
OpenAI independently improved both MRRW bounds by a different route. The paper states that its own results were obtained before that announcement. A check with GPT-5.6 Sol Pro suggested that the first-MRRW improvements match, and that OpenAI's second-MRRW improvement may sit inside some four-dimensional cq channel; the authors did not finish that verification. The selling point here is modularity: the same criterion absorbs q-ary alphabets and LDPC locality.
Fano plus Holevo keep the method from crossing Gilbert-Varshamov. Proving that linear codes meet 1−h(δ) still waits on a fully classical question: does maximum-likelihood decoding on BSC(δ−ε) succeed with high probability, uniformly over every linear code of distance δn? The best general guarantee stops at the Johnson radius.
The optimal cq channel is open. Pure outputs cannot beat the first MRRW bound, and the exact minimum over all finite dimensions is unknown. How this optimization sits against older linear-programming barriers of Samorodnitsky and Navon-Samorodnitsky is also left unmapped.
The 2MQC table is labeled as floating-point estimates, not certified optima. At δ=1/4 the MQC number sits below the second MRRW curve; the paper treats that comparison as numerical. The analytic guarantee is only "below the first MRRW bound."
Most of the improvement is tiny. At δ=0.05 the second MRRW bound is shaved by less than one part in a million. None of this yields an explicit code or a practical decoder. It is an existence upper bound on the asymptotic rate function.
GPT-5.2 through 5.6 were used heavily in the heuristic search for channels; Codex and Claude Code helped draft. The authors take responsibility for the mathematics. The AI-use statement records that MQC as a candidate was first proposed by the model.