⚛️ quantum physics

Binary code rate bounds via classical--quantum channels

This paper unifies the derivation of the four principal asymptotic rate-distance bounds for binary codes under a single "pretty good criterion" theorem and leverages this framework to introduce new quantum-inspired channels that strictly improve upon the existing McEliece--Rodemich--Rumsey--Welch bounds.

Original authors: Omar Alrabiah, Venkatesan Guruswami

Published 2026-08-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Omar Alrabiah, Venkatesan Guruswami

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy room. Sometimes, the noise is just random static, like a radio losing signal; other times, it's a mischievous gremlin actively trying to scramble your words. In the world of information theory, scientists have spent decades trying to figure out the absolute limit of how much information you can pack into a message before the noise makes it impossible to read. This is the "rate-distance" problem: how fast can you talk (the rate) before the message gets so corrupted by errors (the distance) that it becomes gibberish? For binary codes—which are just messages made of 0s and 1s—there are famous "speed limits" that have stood for decades, acting like invisible walls that no one has been able to climb over. These limits tell us the best possible performance we can hope for, but they are based on classical physics, treating bits like simple light switches that are either on or off.

Now, enter the strange and wonderful world of quantum mechanics. Here, information isn't just a switch; it's more like a spinning coin that can be both heads and tails at the same time until you look at it. This paper takes a bold step by asking: what if we use these quantum tricks to re-evaluate those old speed limits? The authors introduce a new way of thinking called the "pretty good criterion." Imagine you are trying to guess a friend's secret number. Instead of just guessing the most likely number (which is the old way), you use a quantum super-compass that samples all possibilities at once to see which one feels "right." The paper proves that if this quantum compass can guess the message with a certain level of accuracy, then the message's speed cannot exceed a specific limit. By designing clever new "quantum channels" (the noisy rooms where the message travels), the authors found that these old speed limits aren't actually solid walls after all. They are more like low fences that can be jumped over.

The main finding of this paper is that the authors have discovered new, stricter limits on how fast binary codes can transmit data without errors. They did this by creating two new types of quantum channels: the "Mixed-Qubit Channel" (MQC) and the "Masked Mixed-Qubit Channel" (2MQC). Think of these channels as new, more complex ways to scramble a message. The authors showed that when you use these specific quantum scramblers, the theoretical maximum speed for sending data drops slightly below the best-known limits from the past 50 years. Specifically, their new limits are strictly lower than the famous "first MRRW bound" and the "second MRRW bound" for all error rates between 0 and 1/2. This means that for any binary code with a certain distance, the maximum amount of data you can send is actually a tiny bit less than what we previously thought was possible.

The paper is very confident in these results. The authors didn't just guess or simulate; they provided rigorous mathematical proofs. They demonstrated that their new channels, which mix pure quantum states with a bit of "noise" (like flipping a coin to decide whether to flip a bit), create a scenario where the information capacity is lower than before. They explicitly ruled out the idea that the old limits were the final word for quantum-assisted analysis. While they didn't claim to have built a physical device that breaks these limits, they proved mathematically that the old limits were too optimistic. They also showed that their method works for different types of codes, including those used in modern error-correcting systems like LDPC codes, and even suggested how this could apply to codes with more than just two symbols.

In essence, the authors used a quantum lens to look at an old problem and found that the view was sharper than anyone expected. By treating the decoding process as a quantum measurement problem rather than just a classical guessing game, they tightened the noose on how much information can be reliably sent. The "pretty good criterion" acts as a universal ruler, and when they measured the old limits against their new quantum rulers, the old limits shrank. This doesn't mean we can't send data fast; it just means the universe has a slightly stricter speed limit than we thought, and we now have a better map of where that limit actually lies.

Technical Summary: Binary Code Rate Bounds via Classical–Quantum Channels

Problem Statement
The paper addresses the fundamental problem of determining the asymptotic tradeoff between the rate and minimum distance of binary error-correcting codes. Specifically, it seeks to improve upon the long-standing upper bounds on the asymptotic rate function $R_2(\delta)$ , which describes the maximum achievable rate for a code with relative minimum distance $\delta$ . For nearly five decades, the tightest known general upper bounds have been the two McEliece–Rodemich–Rumsey–Welch (MRRW) bounds. While the Gilbert–Varshamov bound provides the best asymptotic lower bound, no general improvement over the MRRW upper bounds had been established for binary codes, even for linear codes.

Methodology: The "Pretty Good Criterion"
The authors introduce a unified framework that bridges the Hamming model (worst-case error correction) and the Shannon model (stochastic channel reliability) using classical–quantum (cq) channels. The core of their approach is the "pretty good criterion" (Theorem 1).

CQ Channel Framework: The authors consider a binary-input, output-symmetric classical–quantum channel $\Phi_\sigma$ with output density matrices $\sigma_0$ and $\sigma_1$ .
Pretty Good Measurement (PGM): Instead of relying on Maximum-A-Posteriori (MAP) decoding, which lacks certain structural properties in the quantum setting, the authors utilize the Pretty Good Measurement (PGM), the quantum analog of posterior sampling.
The Criterion: The central theorem states that if the posterior bit error rate of the PGM for a given cq channel is less than $\delta$ $δ$ , then the rate of any binary code with relative distance $\delta$ $δ$ is upper-bounded by the channel's Holevo information (capacity), up to an $O(n^{-1/2})$ $O (n^{- 1/2})$ correction.
- Formally: If $p_e(\sigma_0, \sigma_1) < \delta$ , then $R_2(\delta) \leq \chi(\sigma_0, \sigma_1)$ .
Reduction to Channel Design: This criterion reduces the problem of finding rate bounds to an optimization problem: designing a cq channel that minimizes the Holevo information $\chi$ subject to the constraint that the PGM bit error rate $p_e$ remains below $\delta$ .

Key Contributions and Results

Unification of Known Bounds: The framework successfully recovers four principal known bounds by selecting specific classical or quantum channels:
- Plotkin Bound: Derived from the Binary Erasure Channel (BEC).
- Elias–Bassalygo Bound: Derived from the Binary Symmetric Channel (BSC).
- First MRRW Bound: Derived from the Pure-State Channel (PSC), where outputs are coherent superpositions of error patterns.
- Second MRRW Bound: Derived from a "Masked" PSC, which involves higher-dimensional output states and non-uniform priors.
Strict Improvements via Mixed States: The primary novelty lies in demonstrating that the MRRW bounds are not optimal within this framework. By introducing channels with mixed quantum outputs (as opposed to pure states), the authors derive strictly tighter bounds:
- Mixed-Qubit Channel (MQC): By passing the PSC output through a bit-flip channel (introducing classical noise to the quantum state), the authors construct the MQC. They prove that the resulting rate bound $R_{MQC}(\delta)$ is strictly smaller than the first MRRW bound for all $\delta \in (0, 1/2)$ . This bound also never falls below the Elias–Bassalygo bound.
- Masked Mixed-Qubit Channel (2MQC): By applying the masking operation to the MQC, the authors construct the 2MQC. They prove that the resulting rate bound $R_{2MQC}(\delta)$ is strictly smaller than the second MRRW bound for all $\delta \in (0, 1/2)$ .
Extension to LDPC Codes: The framework is adapted to codes with structural constraints, specifically Low-Density Parity-Check (LDPC) codes with duals generated by low-weight parity checks. By leveraging the bitwise optimality of the PGM for linear codes, the authors derive a new rate bound for LDPC codes ( $U_{PSC}^3$ ) that strictly improves upon the first MRRW bound and the Shangguan–Yang bound for specific distance regimes.
Extension to $q$ -ary Codes: The paper sketches a generalization of the pretty good criterion to $q$ -ary codes, defining $q$ -ary output-symmetric channels and providing a blueprint for deriving $q$ -ary rate bounds, recovering known $q$ -ary Plotkin, Elias–Bassalygo, and Delsarte–Levenshtein bounds.

Significance and Claims
The paper claims that the "pretty good criterion" provides a powerful, modular tool for deriving rate-distance bounds. Its significance is twofold:

Theoretical Unification: It offers a single theorem that recovers all major known upper bounds (Plotkin, Elias–Bassalygo, MRRW I & II) by simply changing the channel model, revealing a deep connection between code distance and channel capacity in the quantum regime.
Breaking Barriers: It demonstrates that the MRRW bounds, which have stood as the state-of-the-art for decades, are not the ultimate limit. By utilizing genuinely quantum features—specifically mixed states and non-commuting output ensembles—the authors achieve strict improvements over these bounds. The paper posits that the search for better bounds is now equivalent to the search for optimal cq channel designs, opening a new avenue for information-theoretic analysis of coding limits.

The authors note that while their framework yields improvements, the exact optimal channel (and thus the tightest possible bound) across all finite dimensions remains an open problem. They also clarify that their work is purely information-theoretic; the PGM used in the converse is not necessarily efficiently implementable, distinguishing their approach from algorithmic quantum decoding results.

More like this