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:quant-ph/0304161 · IEEE Transactions on Information Theory

Sparse-Graph Codes for Quantum Error Correction

David Mackay, Graeme Mitchison, Paul L. McFadden

Published Sep 28, 2004• 400 citations
arXivHTMLPDF

Abstract

Sparse-graph codes appropriate for use in quantum error-correction are presented. Quantum error-correcting codes based on sparse graphs are of interest for three reasons. First, the best codes currently known for classical channels are based on sparse graphs. Second, sparse-graph codes keep the number of quantum interactions associated with the quantum error-correction process small: a constant number per quantum bit, independent of the block length. Third, sparse-graph codes often offer great flexibility with respect to block length and rate. We believe some of the codes we present are unsurpassed by previously published quantum error-correcting codes.

DOI
10.1109/tit.2004.834737

Related papers

Quantum error-correcting codes associated with graphs

Dirk-M. Schlingemann, Reinhard F. Werner

We present a construction for quantum error correcting codes. The basic ingredients are a graph and a finite Abelian group, from which the code can explicitly be obtained. We prove necessary and sufficient conditions for the graph such that the resulting code corrects a certain number of errors. This allows a simple verification of the one-error correcting property of codes of length 5 in any dimension. As examples, we construct a large class of maximum distance separable codes, i.e. codes saturating the Singleton bound, as well as a code of length 10 detecting three errors.

arXiv:quant-ph/0012111•Physical Review A•Dec 11, 2001•423 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•68 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.

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

Quantum error-correction using codes with low density generator matrix

Hatuying Lou, Javier Garcia‐Frias

We propose the use of linear codes with low-density generator matrix in the context of quantum error correction. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Sep 12, 2005•16 citations

GRAPH BASED LINEAR ERROR CORRECTING CODES

Monika Polak

In this article we present a construction of error correcting codes, that have representation as very sparse matrices and belong to the class of Low Density Parity Check Codes. LDPC codes are in the classical Hamming metric. They are very close to well known Shannon bound. The ability to use graphs for code construction was first discussed by Tanner in 1981 and has been used in a number of very effective implementations. We describe how to construct such codes by using special a family of graphs introduced by Ustimenko and Woldar. Graphs that we used are bipartite, bi-regular, very sparse and do not have short cycles C4. Due to the very low density of such graphs, the obtained codes are fast decodable. We describe how to choose parameters to obtain a desired code rate. We also show results of computer simulations of BER (bit error rate) of the obtained codes in order to compare them with other known LDPC codes.

arXiv:1612.03279•Albanian Journal of Mathematics•Jun 15, 2016•1 citation

Graph-theoretic approach to quantum error correction

Robert R. Vandermolen, Duncan Wright

We investigate a class of quantum error-correcting codes to correct errors on both qubits and higher-state quantum systems represented as qudits. These codes arise from an original graph-theoretic representation of sets of quantum errors. In this framework, we represent the algebraic conditions for error correction in terms of edge avoidance between graphs providing a visual representation of the interplay between errors and error-correcting codes. Most importantly, this framework supports the development of quantum codes that correct against a predetermined set of errors, in contrast to current methods. A heuristic algorithm is presented, providing steps to develop codes that correct against an arbitrary noisy channel. We benchmark the correction capability of reflexive stabilizer codes for the case of single-qubit errors by comparison to existing stabilizer codes that are widely used. In addition, we present two instances of optimal encodings: an optimal encoding for fully correlated noise, which achieves a higher encoding rate than previously known, and a minimal encoding for single-qudit errors on a four-state system..

arXiv:2110.08414•Physical Review A•Mar 29, 2022•5 citations
Sparse-graph codes appropriate for use in quantum error-correction are presented. Quantum error-correcting codes based on sparse graphs are of interest for three reasons. First, the best codes currently known for classical channels are based on sparse graphs. Second, sparse-graph codes keep the number of quantum interactions associated with the quantum error-correction process small: a constant number per quantum bit, independent of the block length. Third, sparse-graph codes often offer great flexibility with respect to block length and rate. We believe some of the codes we present are unsurpassed by previously published quantum error-correcting codes.
We present a construction for quantum error correcting codes. The basic ingredients are a graph and a finite Abelian group, from which the code can explicitly be obtained. We prove necessary and sufficient conditions for the graph such that the resulting code corrects a certain number of errors. This allows a simple verification of the one-error correcting property of codes of length 5 in any dimension. As examples, we construct a large class of maximum distance separable codes, i.e. codes saturating the Singleton bound, as well as a code of length 10 detecting three errors.
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.
In this article we present a construction of error correcting codes, that have representation as very sparse matrices and belong to the class of Low Density Parity Check Codes. LDPC codes are in the classical Hamming metric. They are very close to well known Shannon bound. The ability to use graphs for code construction was first discussed by Tanner in 1981 and has been used in a number of very effective implementations. We describe how to construct such codes by using special a family of graphs introduced by Ustimenko and Woldar. Graphs that we used are bipartite, bi-regular, very sparse and do not have short cycles C4. Due to the very low density of such graphs, the obtained codes are fast decodable. We describe how to choose parameters to obtain a desired code rate. We also show results of computer simulations of BER (bit error rate) of the obtained codes in order to compare them with other known LDPC codes.
We investigate a class of quantum error-correcting codes to correct errors on both qubits and higher-state quantum systems represented as qudits. These codes arise from an original graph-theoretic representation of sets of quantum errors. In this framework, we represent the algebraic conditions for error correction in terms of edge avoidance between graphs providing a visual representation of the interplay between errors and error-correcting codes. Most importantly, this framework supports the development of quantum codes that correct against a predetermined set of errors, in contrast to current methods. A heuristic algorithm is presented, providing steps to develop codes that correct against an arbitrary noisy channel. We benchmark the correction capability of reflexive stabilizer codes for the case of single-qubit errors by comparison to existing stabilizer codes that are widely used. In addition, we present two instances of optimal encodings: an optimal encoding for fully correlated noise, which achieves a higher encoding rate than previously known, and a minimal encoding for single-qudit errors on a four-state system..