⚛️ quantum physics

Reed-Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables

This paper establishes that Reed-Muller codes achieve the Holevo capacity on binary-input symmetric classical-quantum channels by deriving a new correlation bound for quantum observables, which proves that any prescribed set of $2^{o(\sqrt{\log N})}$ bits can be decoded sequentially with vanishing error probability when the code rate is below capacity.

Original authors: Avijit Mandal, Henry D. Pfister

Published 2026-07-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Avijit Mandal, Henry D. Pfister

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. In the classical world, the noise is just static or a muffled voice, and we have clever mathematical tricks called "codes" to fix the mistakes. But now, imagine the room isn't just noisy; it's a place where the laws of physics get weird. The message isn't just a sound wave; it's a fragile quantum state, like a spinning coin that is both heads and tails at the same time until you look at it. This is the world of classical-quantum channels. Here, the "noise" isn't just static; it's the fundamental uncertainty of quantum mechanics, and the "receiver" has to perform a special kind of measurement to read the message without breaking the quantum spell.

For decades, scientists have been asking a big question: Can a specific type of code, called Reed-Muller codes, work perfectly in this quantum world? These codes are famous in the regular world because they are incredibly efficient and have a special "Russian nesting doll" structure that helps them fix errors. We know they work great on classical channels, but quantum channels are trickier because the rules of math change when you deal with quantum states. If these codes can work here, it would mean we can send information over quantum networks with almost zero errors, which is a huge step toward a future quantum internet.

This paper takes a deep dive into that question. The authors, Avijit Mandal and Henry D. Pfister, set out to see if Reed-Muller codes can achieve "capacity"—the absolute maximum speed at which information can be sent reliably—on these binary-input symmetric classical-quantum (BSCQ) channels. They didn't just guess; they built a new mathematical framework to prove it.

Here is what they found, explained through a story of detectives and magic mirrors.

The Detective and the Magic Mirrors

Imagine you are a detective trying to figure out if a suspect (the "bit" of information) is guilty (1) or innocent (0). In the classical world, you look at clues. In the quantum world, your clues are quantum states, which are like magic mirrors that reflect the suspect's identity but are also slightly blurry. To solve the case, you need to choose the perfect "lens" (a mathematical object called an observable) to look through. If you pick the wrong lens, you might miss the truth. The authors figured out exactly how to pick the best lens to minimize the chance of making a mistake. They call this the Minimum Mean-Squared Error (MMSE) approach. It's like finding the sharpest possible focus for your detective's eye.

The real magic happens because Reed-Muller codes have a special nesting structure. Think of the code as a giant puzzle made of smaller puzzles. The big puzzle is made of two slightly different versions of a smaller puzzle. The authors discovered that if you can solve the smaller puzzles, you can use that knowledge to solve the big one.

They proved that if the speed at which you are sending the message is slightly slower than the channel's maximum limit (the Holevo capacity), the error rate doesn't just go down; it vanishes incredibly fast. Specifically, they showed that for a code of a certain size, you can decode a small group of bits one by one, and the chance of making an error drops to almost zero.

The "Two-Look" Trick and the Quantum Bound

How did they prove this? They used a clever trick they call a "two-look" approach, but with a quantum twist. Imagine you have two detectives looking at the same crime scene from slightly different angles. In the classical world, you can compare their notes easily. In the quantum world, their notes are quantum states that might not even agree on what "agreement" means (a concept called non-commuting).

The authors invented a new correlation bound. This is a mathematical rule that says: "Even though these quantum notes are weird, if the detectives are looking at overlapping parts of the scene, their errors are linked in a predictable way." They showed that because the code is so symmetrical (like a snowflake that looks the same no matter how you rotate it), the errors in the smaller puzzles cancel each other out when you combine them to solve the big puzzle.

They proved that as the code gets bigger (which they call increasing the parameter $m$ ), the error probability for any single bit shrinks exponentially fast. The formula they found looks like $e^{-c\eta\sqrt{m}}$ , which is a fancy way of saying "the bigger the code, the safer the message."

The Final Verdict

The paper concludes that Reed-Muller codes do work on these quantum channels, but with a specific condition: you can decode a small set of bits (specifically, a set of size $2^{o(\sqrt{\log N})}$ ) sequentially with a vanishing error probability. This means that if you pick a group of bits that isn't too huge compared to the total message size, you can read them one after another, and the chance of getting any of them wrong will disappear as the message gets longer.

The authors are very careful to note that they haven't solved the entire puzzle yet. They proved that individual bits can be decoded perfectly, but they haven't yet proven that the entire block of bits can be decoded perfectly at the same time. That is the next big mountain to climb. If they can climb it, it would solve a long-standing mystery about how to keep secrets safe on the "wiretap" channels of the future.

For now, this paper is a massive step forward. It shows that the elegant, symmetrical structure of Reed-Muller codes isn't just a classical trick; it survives the weirdness of the quantum world, provided you know how to look at it with the right mathematical glasses.

Technical Summary: Reed–Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables

Problem Statement
The paper addresses the fundamental question of whether Reed–Muller (RM) codes achieve capacity on binary-input symmetric classical–quantum (BSCQ) channels. While it is established that RM codes achieve capacity on classical binary memoryless symmetric (BMS) channels (specifically regarding bit-error and block-error probabilities), the extension to the non-commutative setting of classical–quantum channels remains an open challenge. In the quantum setting, the decoding of a single bit is not a scalar likelihood-ratio problem but a binary quantum hypothesis-testing problem involving non-commuting density matrices. The authors investigate whether the symmetry and nested structural arguments that drive RM capacity results in the classical domain have a valid quantum analogue.

Methodology
The authors develop a framework that replaces classical Boolean decoding functions with operator-valued quantum observables. The core methodological steps include:

MMSE Formulation: The authors formulate binary classical–quantum estimation as a mean-squared error (MSE) optimization over Hermitian observables. They characterize the optimal observable (the MMSE-achieving observable) as the unique solution to a Sylvester equation involving the channel's output states.
EXIT-Area Argument: Utilizing the transitive symmetry of RM codes, the authors establish an EXIT-area identity for BSCQ channels. This identity relates the gap between the code rate and the Holevo capacity to the extrinsic entropy (uncertainty) of a single coordinate. This entropy bound is then converted into a bound on the initial MMSE.
Orthogonal Decomposition and Correlation Bound: A central technical contribution is the development of a weighted Gelfand–Naimark–Segal (GNS) orthogonal decomposition for quantum observables. This allows the authors to treat observables analogously to Fourier expansions of classical functions. Using this decomposition, they derive a new correlation inequality for observables with overlapping supports and transitive symmetry. This inequality bounds the correlation between observables associated with nested projections of the code.
Recursive MMSE Decay: By leveraging the nested structure of RM codes (where projections of a code $RM(r, m)$ yield smaller codes $RM(r, m-1)$), the authors derive a recursive relationship for the extrinsic MMSE. The correlation bound ensures that the MMSE decays geometrically as the blocklength increases, provided the rate remains below the Holevo capacity.
Error Probability Conversion: The derived MMSE bounds are converted into bit-error probability bounds using the relationship between MMSE and the Helstrom error probability (the optimal quantum hypothesis testing error). Finally, Gao's quantum union bound is applied to extend the result from single-bit decoding to the sequential decoding of small sets of bits.

Key Contributions

MMSE Characterization: The paper formulates binary CQ estimation as an optimization over Hermitian observables, characterizes the optimal observable, and relates the resulting minimum MSE to the Helstrom error probability.
EXIT-Area Identity: An EXIT-area identity is established for transitive codes on BSCQ channels, linking the rate gap below the Holevo capacity to the extrinsic uncertainty of a single coordinate.
New Correlation Inequality: The authors develop a weighted GNS orthogonal decomposition and prove a novel correlation inequality for quantum observables with overlapping supports and transitive symmetry. This serves as the operator analogue of the classical two-look correlation bound used in previous RM analyses.
Achievability Result: These tools are applied to the RM nesting structure to prove that for RM code sequences with rates below the Holevo capacity, any prescribed set of $2^{o(\sqrt{\log N})}$ bits can be decoded sequentially with vanishing error probability.

Results
The main result (Theorem 1) states that for a BSCQ channel with Holevo capacity $C$ , and for any rate gap $\eta > 0$ , there exist constants such that for sufficiently large blocklengths, the bit-error probability $P_b$ for any single bit in an RM code sequence satisfies:
$P_b \leq e^{-c\eta\sqrt{m}}$
where $m$ is the parameter defining the blocklength $N=2^m$ . Consequently, any set of $2^{o(\sqrt{\log N})}$ coordinates can be decoded sequentially with vanishing error probability.

Significance and Claims
The paper claims to demonstrate that the "symmetry-and-nesting" arguments underlying RM capacity results on classical channels survive in the non-commutative classical–quantum setting, provided the classical decoding function is replaced by a quantum observable. The work establishes vanishing bit-error probability for RM codes below the Holevo capacity in a "small-set" sense.

The authors explicitly note that establishing vanishing block-error probability at all rates below capacity remains an open problem. They highlight that resolving this would also settle the long-standing question of whether RM codes achieve strong secrecy on the binary symmetric channel (BSC) via classical–quantum channel duality. The paper positions itself as a complementary step toward this goal, focusing on bitwise optimality rather than low-complexity decoder design.

The Detective and the Magic Mirrors

The "Two-Look" Trick and the Quantum Bound

The Final Verdict

More like this