Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Solvay Conference on Physics

STATISTICAL MECHANICS APPROACH TO ERROR-CORRECTING CODES

Nicolas Sourlas

Published Aug 1, 2003• 2 citations
Publisher

Abstract

I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. Convolutional codes correspond to one-dimensional spin systems and Viterbi’s decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.

DOI
10.1142/9789812704634_0042

Related papers

Statistical Mechanics and error-correction Codes

Nicolas Sourlas

I will show that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. In particular minimum error probability decoding is equivalent to finding the ground state of the corresponding spin system. The most probable value of a symbol is related to the magnetization at a different temperature. Convolutional codes correspond to one-dimensional spin systems and Viterbi's decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. A particular spin-glass model, which is exactly soluble, corresponds to an ideal code, i.e. a code which allows error-free communication if the rate is below channel capacity.

arXiv:cond-mat/9811406•Nov 29, 1998•11 citations

LDPC Decoding Based On Statistical Mechanics Of Spin-Glasses: A Study

Z. JADDI, Abdessalam Aït Madi, Mohammed Benbrahim

In this paper, the LDPC (Low Density Parity Check Codes) decoding algorithm has been investigated using statistical mechanics properties. The main advantage of LDPC codes is their performance that works in near Shannon limit, and the ability to use iterative decoding algorithms. In 1989 N. Sourlas showed that error-correcting codes can be considered as Spin-Glass systems thus making it possible to model LDPC codes as an Ising model, opening the way for information theorists to solve coding problems with the power of statistical mechanics. According to N. Sourlas, the decoding problem can be solved by finding the ground state of the corresponding spin-system Hamiltonian. The main goal of this paper is to review as simple as possible the statistical properties of LDPC codes, and how it is used especially facing the decoding problem.

International Conference on Innovative Research in Applied Science, Engineering and Technology (IRASET)•Apr 1, 2020•0 citations

Maximum Likelihood Decoding of Quantum Error Correction Codes

Hanyan Cao, Ge Yan, Yuxuan Du +1 more

Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.

quant-pharXiv:2605.17230•May 19, 2026•5 citations

Statistical mechanics of low-density parity-check codes

Yoshiyuki Kabashima, David Saad

We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.

Journal of Physics A Mathematical and General•Jan 28, 2004•79 citations

Spin glass reflection of the decoding transition for quantum error correcting codes

Alexey A. Kovalev, Leonid P. Pryadko

We study the decoding transition for quantum error correcting codes with the help of a mapping to random-bond Wegner spin models. Families of quantum low density parity-check (LDPC) codes with a finite decoding threshold lead to both known models (e.g., random bond Ising and random plaquette $\Z2$ gauge models) as well as unexplored earlier generally non-local disordered spin models with non-trivial phase diagrams. The decoding transition corresponds to a transition from the ordered phase by proliferation of ``post-topological'' extended defects which generalize the notion of domain walls to non-local spin models. In recently discovered quantum LDPC code families with finite rates the number of distinct classes of such extended defects is exponentially large, corresponding to extensive ground state entropy of these codes. Here, the transition can be driven by the entropy of the extended defects, a mechanism distinct from that in the local spin models where the number of defect types (domain walls) is always finite.

arXiv:1311.7688•Quantum Information and Computation•Jul 1, 2015•19 citations

Statistical physics of regular low-density parity-check error-correcting codes

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad +1 more

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

arXiv:cond-mat/0003121•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 1, 2000•91 citations
I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. Convolutional codes correspond to one-dimensional spin systems and Viterbi’s decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.
I will show that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. In particular minimum error probability decoding is equivalent to finding the ground state of the corresponding spin system. The most probable value of a symbol is related to the magnetization at a different temperature. Convolutional codes correspond to one-dimensional spin systems and Viterbi's decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. A particular spin-glass model, which is exactly soluble, corresponds to an ideal code, i.e. a code which allows error-free communication if the rate is below channel capacity.
In this paper, the LDPC (Low Density Parity Check Codes) decoding algorithm has been investigated using statistical mechanics properties. The main advantage of LDPC codes is their performance that works in near Shannon limit, and the ability to use iterative decoding algorithms. In 1989 N. Sourlas showed that error-correcting codes can be considered as Spin-Glass systems thus making it possible to model LDPC codes as an Ising model, opening the way for information theorists to solve coding problems with the power of statistical mechanics. According to N. Sourlas, the decoding problem can be solved by finding the ground state of the corresponding spin-system Hamiltonian. The main goal of this paper is to review as simple as possible the statistical properties of LDPC codes, and how it is used especially facing the decoding problem.
Quantum error correction (QEC) is indispensable for realizing fault-tolerant quantum computation, yet its effectiveness hinges critically on the classical decoding algorithm that interprets noisy syndrome measurements. Among all possible decoding strategies, maximum likelihood decoding (MLD) is provably optimal, since it identifies the logical group with largest likelihood by summing over all possible errors within logical class consistent with the observed syndrome. Despite its optimality, MLD is computationally intractable in general (#P-hard), motivating a rich landscape of exact and approximate algorithms. In this topical review, we provide a unified perspective on MLD by surveying recent advances through three complementary lenses: statistical mechanics, tensor networks, and artificial intelligence. From the statistical mechanics viewpoint, the MLD problem maps onto evaluating partition functions of disordered spin models, enabling exact solutions for certain codes and noise models as well as threshold estimation via phase-transition analysis. From the tensor network perspective, approximate contraction of tensor networks on the code's factor graph yields decoders that closely approach MLD accuracy with polynomial computational cost. From the artificial intelligence perspective, neural-network-based decoders, including autoregressive generative models and recurrent transformers, learn to approximate the MLD distribution from data, achieving high accuracy with the parallelism afforded by modern hardware accelerators. We discuss the connections among these three approaches, review their application to both simulated and experimental quantum hardware, and outline open challenges including real-time decoding, scalability to large code distances, and generalization to high-rate quantum low-density parity-check codes.
We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.
We study the decoding transition for quantum error correcting codes with the help of a mapping to random-bond Wegner spin models. Families of quantum low density parity-check (LDPC) codes with a finite decoding threshold lead to both known models (e.g., random bond Ising and random plaquette Z2\Z2Z2 gauge models) as well as unexplored earlier generally non-local disordered spin models with non-trivial phase diagrams. The decoding transition corresponds to a transition from the ordered phase by proliferation of ``post-topological'' extended defects which generalize the notion of domain walls to non-local spin models. In recently discovered quantum LDPC code families with finite rates the number of distinct classes of such extended defects is exponentially large, corresponding to extensive ground state entropy of these codes. Here, the transition can be driven by the entropy of the extended defects, a mechanism distinct from that in the local spin models where the number of defect types (domain walls) is always finite.
A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.