The Metric Structure of Linear Codes

M. V. Kozlov

Eimear Byrne, Johan Vester Dinesen, Ragnar Freij-Hollanti +1 more

We study information leakage in secure linear network coding schemes based on nested rank-metric codes. We show that the amount of information leaked to an adversary that observes a subset of network links is characterized by the conditional rank function of a representable $q$-polymatroid associated with the underlying rank-metric code pair. Building on this connection, we introduce the notions of $q$-polymatroid ports and $q$-access structures and describe their structural properties. Moreover, we relate minimal codewords in the rank-metric setting to minimal reconstructing spaces and prove a $q$-analogue of the Brickell--Davenport theorem.

David G. Glynn, Thomas Aaron Gulliver, Manish K. Gupta

Dor Elimelech, Victor V. Albert, Alexander Barg

We develop a theory of approximate quantum error correction (QEC) based on the error-set model, complemented by general methods for code construction. Exact QEC has a powerful error-set structure: by the Knill-Laflamme conditions, a code correcting a given error set automatically protects against every channel whose Kraus operators lie in their linear span. This linearity gives rise to code distance, the equivalence between erasures and general errors, and a theory of asymptotically good codes. A longstanding view has been that these features do not extend to AQEC, leaving the theory essentially channel-by-channel. We show instead that, although full Knill--Laflamme linearity fails, a restricted form survives and suffices to extend all three structural features to the approximate setting. Specifically, a common error-set criterion governs families of channels whose Kraus operators are linear combinations of a given error set and whose coefficient matrices satisfy a spectral constraint. Using the Bény-Oreshkov worst-case and Petz average-case frameworks, we derive uniform fidelity guarantees for these families in terms of two new code parameters--the \emph{environment-leakage distance}, controlling worst-case performance, and the \emph{Knill-Laflamme Hellinger distance}, characterizing the average-case performance of Petz recovery. To demonstrate the scope of this model, we develop partition-based constructions across diverse quantum systems and geometries, placing exact and approximate correction on equal footing. These constructions lead to a metric--error alignment hierarchy for Hilbert spaces, metrics, and error families, which in turn characterizes the resulting recovery guarantees. They yield the first known asymptotically good code families for fermionic systems, one-dimensional Rydberg-blockaded systems, and deletion errors, and extend to other physical platforms.

Toshihiro Niinomi, Hideki Yagi, Shigeichi Hirasawa

In channel decoding, a decoder with suboptimal metrics may be used because of the uncertainty of the channel statistics or the limitations of the decoder. In this case, the decoding metric is different from the actual channel metric, and thus it is called mismatched decoding. In this paper, applying the technique of the DS2 bound, we derive an upper bound on the error probability of mismatched decoding over a regular channel for the ensemble of linear block codes, which was defined by Hof, Sason and Shamai. Assuming the ensemble of random linear block codes defined by Gallager, we show that the obtained bound is not looser than the conventional bound. We also give a numerical example for the ensemble of LDPC codes also introduced by Gallager, which shows that our proposed bound is tighter than the conventional bound. Furthermore, we obtain a single letter error exponent for linear block codes.

Martin Bossert, F. Hergert