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

arXiv:cond-mat/0512296

Two Lectures on Iterative Coding and Statistical Mechanics

Andrea Montanari A

Published Dec 14, 2005• 5 citations
arXivHTMLPDF

Abstract

These are the notes for two lectures delivered at the Les Houches summer school Mathematical Statistical Mechanics, held in July 2005. I review some basic notions on sparse graph error correcting codes with emphasis on `modern' aspects, such as, iterative belief propagation decoding. Relations with statistical mechanics, inference and random combinatorial optimization are stressed, as well as some general mathematical ideas and open problems.

DOI
10.48550/arxiv.cond-mat/0512296

Related papers

On the iterative decoding of sparse quantum codes

David Poulin, Yeojin Chung

We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.

Quantum Information and Computation•Nov 1, 2008•5 citations

Les Houches lectures on random quantum circuits and monitored quantum dynamics

Romain Vasseur

These lecture notes are based on lectures given by the author at the Les Houches 2025 summer school on "Exact Solvability and Quantum Information". The central theme of these notes is to apply the philosophy of statistical mechanics to study the dynamics of quantum information in ideal and monitored random quantum circuits -- for which an exact description of individual realizations is expected to be generically intractable.

quant-pharXiv:2602.17258•SciPost Physics Lecture Notes•Feb 20, 2026•1 citation

On the iterative decoding of sparse quantum codes

David Poulin, Yeojin Chung

We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.

Quantum Information and Computation•Nov 1, 2008•154 citations

On the iterative decoding of sparse quantum codes

David Poulin, Yeojin Chung

We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.

arXiv:0801.1241•Jan 8, 2008•2 citations

Statistical physics methods for sparse graph codes

Shrinivas Kudekar

This thesis deals with the asymptotic analysis of coding systems based on sparse graph codes. The goal of this work is to analyze the decoder performance when transmitting over a general binary-input memoryless symmetric-output (BMS) channel. We consider the two most fundamental decoders, the optimal maximum a posteriori (MAP) decoder and the sub-optimal belief propagation (BP) decoder. The BP decoder has low-complexity and its performance analysis is, hence, of great interest. The MAP decoder, on the other hand, is computationally expensive. However, the MAP decoder analysis provides fundamental limits on the code performance. As a result, the MAP-decoding analysis is important in designing codes which achieve the ultimate Shannon limit. It would be fair to say that, over the binary erasure channel (BEC), the performance of the MAP and BP decoder has been thoroughly understood. However, much less is known in the case of transmission over general BMS channels. The combinatorial methods used for analyzing the case of BEC do not extend easily to the general case. The main goal of this thesis is to advance the analysis in the case of transmission over general BMS channels. To do this, we use the recent convergence of statistical physics and coding theory. Sparse graph codes can be mapped into appropriate statistical physics spin-glass models. This allows us to use sophisticated methods from rigorous statistical mechanics like the correlation inequalities, interpolation method and cluster expansions for the purpose of our analysis. One of the main results of this thesis is that in some regimes of noise, the BP decoder is optimal for a typical code in an ensemble of codes. This result is a pleasing extension of the same result for the case of BEC. An important consequence of our results is that the heuristic predictions of the replica and cavity methods of spin-glass theory are correct in the realm of sparse graph codes.

•Jan 1, 2009•3 citations

Statistical mechanics of integrable quantum spin systems

Frank Göhmann

This script is based on the notes the author prepared to give a set of six lectures at the Les Houches School ``Integrability in Atomic and Condensed Matter Physics'' in the summer of 2018. The responsibility for the selection of the material is partially with the organisers, Jean-Sebastien Caux, Nikolai Kitanine, Andreas Klümper and Robert Konik. The school had its focus on the application of integrability based methods to problems in non-equilibrium statistical mechanics. My lectures were meant to complement this subject with background material on the equilibrium statistical mechanics of quantum spin chains from a vertex model perspective. I was asked to provide a minimal introduction to quantum spin systems including notions like the reduced density matrix and correlation functions of local observables. I was further asked to explain the graphical language of vertex models and to introduce the concepts of the Trotter decomposition and the quantum transfer matrix. This was basically the contents of the first four lectures presented at the school. In the remaining two lectures I started filling these notions with life by deriving an integral representation of the free energy per lattice site for the Heisenberg-Ising chain (alias XXZ model) using techniques based on non-linear integral equations. Up to small corrections the following sections 1-6 display the six lectures almost literally. The only major change is that the example of the XXZ chain has been moved from section 5 to 2. During the school it was not really necessary to introduce the model, since other speakers had explained it before. But for these notes I thought it might be useful to introduce the main example rather early. I also supplemented each lecture with a comment section which contains additional references and material of the type that was discussed informally with the participants.

arXiv:1909.09967•SciPost Physics Lecture Notes•Aug 17, 2020•23 citations
These are the notes for two lectures delivered at the Les Houches summer school Mathematical Statistical Mechanics, held in July 2005. I review some basic notions on sparse graph error correcting codes with emphasis on `modern' aspects, such as, iterative belief propagation decoding. Relations with statistical mechanics, inference and random combinatorial optimization are stressed, as well as some general mathematical ideas and open problems.
We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.
We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.
We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.
This thesis deals with the asymptotic analysis of coding systems based on sparse graph codes. The goal of this work is to analyze the decoder performance when transmitting over a general binary-input memoryless symmetric-output (BMS) channel. We consider the two most fundamental decoders, the optimal maximum a posteriori (MAP) decoder and the sub-optimal belief propagation (BP) decoder. The BP decoder has low-complexity and its performance analysis is, hence, of great interest. The MAP decoder, on the other hand, is computationally expensive. However, the MAP decoder analysis provides fundamental limits on the code performance. As a result, the MAP-decoding analysis is important in designing codes which achieve the ultimate Shannon limit. It would be fair to say that, over the binary erasure channel (BEC), the performance of the MAP and BP decoder has been thoroughly understood. However, much less is known in the case of transmission over general BMS channels. The combinatorial methods used for analyzing the case of BEC do not extend easily to the general case. The main goal of this thesis is to advance the analysis in the case of transmission over general BMS channels. To do this, we use the recent convergence of statistical physics and coding theory. Sparse graph codes can be mapped into appropriate statistical physics spin-glass models. This allows us to use sophisticated methods from rigorous statistical mechanics like the correlation inequalities, interpolation method and cluster expansions for the purpose of our analysis. One of the main results of this thesis is that in some regimes of noise, the BP decoder is optimal for a typical code in an ensemble of codes. This result is a pleasing extension of the same result for the case of BEC. An important consequence of our results is that the heuristic predictions of the replica and cavity methods of spin-glass theory are correct in the realm of sparse graph codes.
This script is based on the notes the author prepared to give a set of six lectures at the Les Houches School ``Integrability in Atomic and Condensed Matter Physics'' in the summer of 2018. The responsibility for the selection of the material is partially with the organisers, Jean-Sebastien Caux, Nikolai Kitanine, Andreas Klümper and Robert Konik. The school had its focus on the application of integrability based methods to problems in non-equilibrium statistical mechanics. My lectures were meant to complement this subject with background material on the equilibrium statistical mechanics of quantum spin chains from a vertex model perspective. I was asked to provide a minimal introduction to quantum spin systems including notions like the reduced density matrix and correlation functions of local observables. I was further asked to explain the graphical language of vertex models and to introduce the concepts of the Trotter decomposition and the quantum transfer matrix. This was basically the contents of the first four lectures presented at the school. In the remaining two lectures I started filling these notions with life by deriving an integral representation of the free energy per lattice site for the Heisenberg-Ising chain (alias XXZ model) using techniques based on non-linear integral equations. Up to small corrections the following sections 1-6 display the six lectures almost literally. The only major change is that the example of the XXZ chain has been moved from section 5 to 2. During the school it was not really necessary to introduce the model, since other speakers had explained it before. But for these notes I thought it might be useful to introduce the main example rather early. I also supplemented each lecture with a comment section which contains additional references and material of the type that was discussed informally with the participants.