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

Physical Review Letters

Finite temperature error-correcting codes

Pál Ruján

Published May 10, 1993• 130 citations
Publisher

Abstract

The correspondence between error-correcting convolution codes and gauge invariant spin-glass models is used to show that the optimal way to recover the original message is by decoding at a finite temperature ${\mathit{T}}_{\mathit{N}}$(p)>0, where p is the strength of the channel noise and ${\mathit{T}}_{\mathit{N}}$(p) the Nishimori temperature. This improves upon the retrieval performance of the T=0 maximal likelihood Viterbi decoding algorithm without increasing its computational complexity. Numerical simulations support the theory.

DOI
10.1103/physrevlett.70.2968

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•5 citations

Spin glasses and error-correcting codes

M. Belongie

In this article, we study a model for error-correcting codes that comes from spin glass theory and leads to both new codes and a new decoding technique. Using the theory of spin glasses, it has been proven that a simple construction yields a family of binary codes whose performance asymptotically approaches the Shannon bound for the Gaussian channel. The limit is approached as the number of information bits per codeword approaches infinity while the rate of the code approaches zero. Thus, the codes rapidly become impractical. We present simulation results that show the performance of a few manageable examples of these codes. In the correspondence that exists between spin glasses and error-correcting codes, the concept of a thermal average leads to a method of decoding that differs from the standard method of finding the most likely information sequence for a given received codeword. Whereas the standard method corresponds to calculating the thermal average at temperature zero, calculating the thermal average at a certain optimum temperature results instead in the sequence of most likely information bits. Since linear block codes and convolutional codes can be viewed as examples of spin glasses, this new decoding method can be used to decode these codes in a way that minimizes the bit error rate instead of the codeword error rate. We present simulation results that show a small improvement in bit error rate by using the thermal average technique. I.

•Aug 15, 1994•0 citations

Statistical mechanics of error-correcting codes

Yoshiyuki Kabashima, David Saad

We investigate the performance of error-correcting codes, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon's bound for the channel capacity is recovered for large K and zero temperature when the code rate K / C is finite. Close to optimal error-correcting capability is obtained for finite K and C . We examine the finite-temperature case to assess the use of simulated annealing for decoding and extend the analysis to accommodate other types of noisy channels.

Europhysics Letters (EPL)•Jan 1, 1999•161 citations

Charge-Informed Quantum Error Correction

Vlad Temkin, Zack Weinstein, Ruihua Fan +2 more

We investigate the statistical physics of quantum error correction in ${\rm U}(1)$ symmetry-enriched topological quantum memories. Starting from a phenomenological error model of charge-conserving noise, we study the optimal decoder assuming the local charges of each anyon can be measured. The error threshold of the optimal decoder corresponds to a continuous phase transition in a disordered two-dimensional integer loop model on the Nishimori line. Using an effective replica field theory analysis and Monte Carlo numerics, we show that the optimal decoding transition exhibits Berezinskii-Kosterlitz-Thouless universality with a modified universal jump in winding number variance. We further generalize the model beyond the Nishimori line, which defines a large class of suboptimal decoders. At low nonzero temperatures and strong disorder, we find numerical evidence of a disorder-dominated loop-glass phase which corresponds to a "confidently incorrect" decoder. The zero-temperature limit defines the minimum-cost flow decoder, which serves as the ${\rm U}(1)$ analog of minimum-weight perfect matching in $\mathbb{Z}_2$ topological codes. Both the optimal and minimum-cost flow decoders are shown to dramatically outperform the charge-agnostic optimal decoder in symmetry-enriched topological codes.

quant-pharXiv:2512.22119•Dec 29, 2025•0 citations

Exact Decoding of Quantum Error-Correcting Codes

Hanyan Cao, S. J. Zhao, Dongyang Feng +8 more

We study the exact maximum-likelihood decoding of quantum error-correcting codes. Our primary focus is on the repetition code under circuit-level noise, which serves as a fundamental basis for quantum error correction experiments and is the only code that has achieved large distances and extremely low error rates. We uncover that the repetition code under circuit-level noise has an exact solution and propose an optimal maximum-likelihood decoding algorithm called "planar." This algorithm is based on the exact solution of the spin-glass partition function on planar graphs and has polynomial computational complexity. Through extensive numerical experiments, we demonstrate that our algorithm uncovers the exact threshold for depolarizing noise and realistic superconductor SI1000 noise. Furthermore, we apply our method to analyze data from recent quantum memory experiments conducted by Google Quantum AI, revealing that part of the error floor was attributed to the decoding algorithm used by Google. Finally, we implemented the repetition code quantum memory on superconducting systems using a 72-qubit quantum chip lacking reset gates, demonstrating that even with an unknown error model, the proposed algorithm achieves a significantly lower logical error rate than the matching-based algorithm. We also discuss the application of our approach to quantum codes whose maximum-likelihood decoding problem corresponds to a spin-glass problem, including the surface code under independent code-capacity noise.

Physical Review Letters•May 15, 2025•5 citations

Good quantum-convolutional error-correction codes and their decoding algorithm exist

H. F. Chau

A quantum-convolutional code was introduced recently as an alternative way to protect vital quantum information. To complete the analysis of the quantum-convolutional code, I report a way to decode certain quantum-convolutional codes based on the classical Viterbi decoding algorithm. This decoding algorithm is optimal for a memoryless channel. I also report three simple criteria to test if decoding errors in a quantum-convolutional code will terminate after a finite number of decoding steps whenever the Hilbert space dimension of each quantum register is a prime power. Finally, I show that certain quantum-convolutional codes are in fact stabilizer codes. And hence, these quantum stabilizer convolutional codes have fault-tolerant implementations.

arXiv:quant-ph/9806032•Physical Review A•Sep 1, 1999•24 citations
The correspondence between error-correcting convolution codes and gauge invariant spin-glass models is used to show that the optimal way to recover the original message is by decoding at a finite temperature TN{\mathit{T}}_{\mathit{N}}TN​(p)>0, where p is the strength of the channel noise and TN{\mathit{T}}_{\mathit{N}}TN​(p) the Nishimori temperature. This improves upon the retrieval performance of the T=0 maximal likelihood Viterbi decoding algorithm without increasing its computational complexity. Numerical simulations support the theory.
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 article, we study a model for error-correcting codes that comes from spin glass theory and leads to both new codes and a new decoding technique. Using the theory of spin glasses, it has been proven that a simple construction yields a family of binary codes whose performance asymptotically approaches the Shannon bound for the Gaussian channel. The limit is approached as the number of information bits per codeword approaches infinity while the rate of the code approaches zero. Thus, the codes rapidly become impractical. We present simulation results that show the performance of a few manageable examples of these codes. In the correspondence that exists between spin glasses and error-correcting codes, the concept of a thermal average leads to a method of decoding that differs from the standard method of finding the most likely information sequence for a given received codeword. Whereas the standard method corresponds to calculating the thermal average at temperature zero, calculating the thermal average at a certain optimum temperature results instead in the sequence of most likely information bits. Since linear block codes and convolutional codes can be viewed as examples of spin glasses, this new decoding method can be used to decode these codes in a way that minimizes the bit error rate instead of the codeword error rate. We present simulation results that show a small improvement in bit error rate by using the thermal average technique. I.
We investigate the performance of error-correcting codes, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon's bound for the channel capacity is recovered for large K and zero temperature when the code rate K / C is finite. Close to optimal error-correcting capability is obtained for finite K and C . We examine the finite-temperature case to assess the use of simulated annealing for decoding and extend the analysis to accommodate other types of noisy channels.
We investigate the statistical physics of quantum error correction in U(1){\rm U}(1)U(1) symmetry-enriched topological quantum memories. Starting from a phenomenological error model of charge-conserving noise, we study the optimal decoder assuming the local charges of each anyon can be measured. The error threshold of the optimal decoder corresponds to a continuous phase transition in a disordered two-dimensional integer loop model on the Nishimori line. Using an effective replica field theory analysis and Monte Carlo numerics, we show that the optimal decoding transition exhibits Berezinskii-Kosterlitz-Thouless universality with a modified universal jump in winding number variance. We further generalize the model beyond the Nishimori line, which defines a large class of suboptimal decoders. At low nonzero temperatures and strong disorder, we find numerical evidence of a disorder-dominated loop-glass phase which corresponds to a "confidently incorrect" decoder. The zero-temperature limit defines the minimum-cost flow decoder, which serves as the U(1){\rm U}(1)U(1) analog of minimum-weight perfect matching in Z2\mathbb{Z}_2Z2​ topological codes. Both the optimal and minimum-cost flow decoders are shown to dramatically outperform the charge-agnostic optimal decoder in symmetry-enriched topological codes.
We study the exact maximum-likelihood decoding of quantum error-correcting codes. Our primary focus is on the repetition code under circuit-level noise, which serves as a fundamental basis for quantum error correction experiments and is the only code that has achieved large distances and extremely low error rates. We uncover that the repetition code under circuit-level noise has an exact solution and propose an optimal maximum-likelihood decoding algorithm called "planar." This algorithm is based on the exact solution of the spin-glass partition function on planar graphs and has polynomial computational complexity. Through extensive numerical experiments, we demonstrate that our algorithm uncovers the exact threshold for depolarizing noise and realistic superconductor SI1000 noise. Furthermore, we apply our method to analyze data from recent quantum memory experiments conducted by Google Quantum AI, revealing that part of the error floor was attributed to the decoding algorithm used by Google. Finally, we implemented the repetition code quantum memory on superconducting systems using a 72-qubit quantum chip lacking reset gates, demonstrating that even with an unknown error model, the proposed algorithm achieves a significantly lower logical error rate than the matching-based algorithm. We also discuss the application of our approach to quantum codes whose maximum-likelihood decoding problem corresponds to a spin-glass problem, including the surface code under independent code-capacity noise.
A quantum-convolutional code was introduced recently as an alternative way to protect vital quantum information. To complete the analysis of the quantum-convolutional code, I report a way to decode certain quantum-convolutional codes based on the classical Viterbi decoding algorithm. This decoding algorithm is optimal for a memoryless channel. I also report three simple criteria to test if decoding errors in a quantum-convolutional code will terminate after a finite number of decoding steps whenever the Hilbert space dimension of each quantum register is a prime power. Finally, I show that certain quantum-convolutional codes are in fact stabilizer codes. And hence, these quantum stabilizer convolutional codes have fault-tolerant implementations.