How decodable are binary codes against quantum noise?

A binary code of distance δn is a set of n-bit strings, any two of which differ in at least δn positions. Such codes possess the property that they protect against worst-case noise, correcting any pattern of fewer than δn/2 bit flips on any of their codewords. Determining how large such a code can asymptotically be is a central open problem in coding theory.

We approach this classical worst-case noise problem through Shannon’s random noise model, where the analogous question of how large a reliably decodable code can be is answered exactly by the channel’s capacity. This includes, in particular, classical–quantum (cq) channels, wherein the output may consist of qubits and not just classical bits. Our main result is a simple criterion under which every code of distance δn is decodable over a given cq channel, which would imply that the code’s size is upper bounded by the channel’s capacity, thereby reducing upper bounds on code size to the design of suitable channels.

Through this criterion, we not only rederive the code size bounds that have stood since 1977 but also improve upon them. More broadly, this channel coding lens opens up a new paradigm in which binary codes of distance δn are reinterpreted as channel-oblivious error-correcting codes.

This is based on joint work with Venkat Guruswami (https://arxiv.org/pdf/2608.09347).