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

Heuristics in quantum error correction

Alex Rigby

Published Jan 1, 2021• 0 citations
Publisher

Abstract

Noise is a major obstacle in the development of practical schemes for quantum computation and communication. Similar to the case of classical communication, this noise can be protected against by employing a code, which provides a means for encoding quantum states prior to transmission and allows for errors to be inferred, and hopefully corrected, by a decoder at the receiver. Unfortunately, designing good codes and decoders is typically a difficult problem. This thesis focuses on developing low-complexity heuristic approaches to three such problems: the design of modified belief propagation decoders for quantum low-density parity-check codes, the design of stabilizer codes for asymmetric channels, and the design of codeword stabilized codes. Quantum low-density parity-check codes are stabilizer codes with low-weight generators. Such codes permit low-complexity decoding via the use of belief propagation, which is an iterative message passing algorithm that takes place on a factor graph defined by the code. However, the performance of such a decoder is limited both by code structure and the degenerate nature of quantum errors. To overcome these limitations, at least in part, a number of modifications to belief propagation are developed. Central among these is the augmented decoder, which in the case of a decoding error, iteratively reattempts decoding using modified factor graph. This heuristic modification simply involves the duplication of a randomly selected subset of the graph’s check nodes, which are in one-to-one correspondence with the code’s stabilizer generators. Across a range of codes, it is shown that the decoders developed perform as well as or better than other modified decoders presented in literature. For a number of channels of physical interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these so-called asymmetric channels, the decoding error rate can be minimized by tailoring the code used to the channel. However, assessing the performance of codes on a given channel is made difficult by the #P-completeness of optimal decoding. To address this complexity, it is shown that the decoding error rate can be accurately approximated using only a small fraction of the possible errors caused by the channel. This approximation is then used to identify a number of cyclic stabilizer codes that perform well on two different asymmetric channels. To further build on this, a heuristic is demonstrated for assessing code performance based on the decoding error rate of an associated classical code. The complexity of calculating this classical error rate is relatively low, and it is shown that it can be used as the basis for a hill-climbing search algorithm. Such searches have yielded a large number of highly performant codes satisfying various structure constraints. The family of codeword stabilized codes encompasses both the stabilizer codes as well as many of the best known nonadditive codes. Constructing a standard form codeword stabilized code is a matter of selecting a simple undirected graph and a binary classical code. This makes designing optimal codes difficult as the number of possible graphs grows exponentially with code length, and the clique search required to construct the classical code is NP-hard. To address the exponential growth of the search space, a heuristic is developed for assessing graphs. This heuristic is then employed by a genetic algorithm that also makes use of a novel crossover operation based on spectral bisection, which is show to be superior to more standard crossover operations. With a graph selected, it is demonstrated that the complexity of the clique search required to construct the associated classical code can be mitigated through the use of a heuristic clique finding algorithm. A number of best known codes are presented that have been found using this approach.

DOI
10.25959/100.00037900

Related papers

Optimizing short stabilizer codes for asymmetric channels

Alex Rigby, Jan Corne Olivier, Peter Jarvis

For a number of quantum channels of interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these asymmetric channels, the decoding error rate can be reduced by tailoring the code used to the channel. However, analyzing the performance of stabilizer codes on these channels is made difficult by the #P-completeness of optimal decoding. To address this, at least for short codes, we demonstrate that the decoding error rate can be approximated by considering only a fraction of the possible errors caused by the channel. Using this approximate error rate calculation, we extend a recent result to show that there are a number of $[[5\ensuremath{\le}n\ensuremath{\le}12,1\ensuremath{\le}k\ensuremath{\le}3]]$ cyclic stabilizer codes that perform well on two different asymmetric channels. We also demonstrate that an indication of a stabilizer code's error rate is given by considering the error rate of a classical binary code related to the stabilizer. This classical error rate is far less complex to calculate, and we use it as the basis for a hill-climbing algorithm, which we show to be effective at optimizing codes for asymmetric channels. Furthermore, we demonstrate that simple modifications can be made to our hill-climbing algorithm to search for codes with desired structure requirements.

arXiv:1911.04196•Physical Review A•Mar 19, 2020•0 citations

High-Rate Quantum Low-Density Parity-Check Codes Assisted by Reliable Qubits

Yuichiro Fujiwara, Alexander Gruner, Peter Vandendriessche

Quantum error correction is an important building block for reliable quantum information processing. A challenging hurdle in the theory of quantum error correction is that it is significantly more difficult to design error-correcting codes with desirable properties for quantum information processing than for traditional digital communications and computation. A typical obstacle to constructing a variety of strong quantum error-correcting codes is the complicated restrictions imposed on the structure of a code. Recently, promising solutions to this problem have been proposed in quantum information science, where in principle any binary linear code can be turned into a quantum error-correcting code by assuming a small number of reliable quantum bits. This paper studies how best to take advantage of these latest ideas to construct desirable quantum error-correcting codes of very high information rate. Our methods exploit structured high-rate low-density parity-check codes available in the classical domain and provide quantum analogues that inherit their characteristic low decoding complexity and high error correction performance even at moderate code lengths. Our approach to designing high-rate quantum error-correcting codes also allows for making direct use of other major syndrome decoding methods for linear codes, making it possible to deal with a situation where promising quantum analogues of low-density parity-check codes are difficult to find.

arXiv:1309.5587•IEEE Transactions on Information Theory•Jan 30, 2015•14 citations

Quantum Low-Density Parity-Check Codes

Bane V. Vasic, Valentin Savin, Michele Pacenti +2 more

Quantum error correction (QEC) is a cornerstone of quantum computing, enabling reliable information processing in the presence of noise. Sparse stabilizer codes -- referred to generally as quantum low-density parity-check (QLDPC) codes -- have risen to the forefront of QEC research in recent years. This can be attributed to several key factors. First, classical LDPC codes admit low-complexity belief propagation iterative decoding and near-capacity performance, which contributed to the early interest in QLDPC codes. Then, the result promising constant overhead fault tolerance using QLDPC codes led to the search for code families that go beyond the long-holding $\sqrt{n}$ scaling barrier of minimum distance for codelength $n$. This resulted in recent breakthroughs in the construction of QLDPC codes, which, combined with efficient decoding algorithms and the development of fault-tolerant protocols operating on QLDPC-encoded quantum information, provide a promising pathway to low-overhead, fault-tolerant quantum computation. However, despite their potential, challenges remain, particularly in constructing and decoding finite-length codes that account for, or efficiently leverage, specific characteristics of quantum hardware, such as connectivity, topology, native gate sets, and noise models. This article provides an in-depth examination of QLDPC codes and their iterative decoders, catering to an information theory audience with no or limited background in quantum mechanics. We discuss the theoretical underpinnings, explore unique characteristics of quantum channels, and delineate key code constructions and decoding algorithms, ultimately highlighting the impact and future prospects of QLDPC codes in quantum information science.

arXiv:2510.14090•IEEE BITS the Information Theory Magazine•Dec 1, 2025•0 citations

Decoding algorithms for quantum error correcting codes

Antonio de Mari i Olius

Quantum computers would prove a ground-breaking effect in several re- search fields to the advantage of our society due to their proved capacity for solving some problems deemed as too complex for classical comput- ers. Consequently, there is a generalized academic effort for constructing a quantum computer. Nonetheless, a real quantum computer does not suffice for implementing quantum algorithms reliably, it must be fault-tolerant. Quantum computers undergo noise due to a phenomenon generally named quantum decoherence, a fault-tolerant quantum computer has the capabil- ity to suppress the effects of decoherence to an extent. For that to happen, a quantum computer should consider quantum error correction, a process in which decoherence is studied and attempted to be corrected. Within the context of quantum error correction, the information from quantum proces- sors is to be stored in a larger, more redundant system named a quantum error correcting code. Afterwards, one can obtain a vector named syndrome which provides partial information on the effect decoherence has had on a code. The process of recovering the decoherence or error that the code has undergone is named decoding. This thesis studies decoders for quan- tum error correcting codes, their performance, complexity and adaption to different types of quantum decoherence.

•Jul 1, 2024•0 citations

Heuristic construction of codeword stabilized codes

Alex Rigby, Jan Corne Olivier, Peter Jarvis

The family of codeword stabilized codes encompasses the stabilizer codes as well as many of the best known nonadditive codes. However, constructing optimal $n$-qubit codeword stabilized codes is made difficult by two main factors. The first of these is the exponential growth with $n$ of the number of graphs on which a code can be based. The second is the NP-hardness of the maximum clique search required to construct a code from a given graph. We address the second of these issues through the use of a heuristic clique finding algorithm. This approach has allowed us to find $((9,97\ensuremath{\le}K\ensuremath{\le}100,2))$ and $((11,387\ensuremath{\le}K\ensuremath{\le}416,2))$ codes, which are larger than any previously known codes. To address the exponential growth of the search space, we demonstrate that graphs that give large codes typically yield clique graphs with a large number of nodes. The number of such nodes can be determined relatively efficiently, and we demonstrate that $n$-node graphs yielding large clique graphs can be found using a genetic algorithm. This algorithm uses a crossover operation based on spectral bisection that we demonstrate to be superior to more standard crossover operations. Using this genetic algorithm approach, we have found ((13, 18, 4)) and ((13, 20, 4)) codes that are larger than any previously known code. We also consider codes for the amplitude damping channel. We demonstrate that for $n\ensuremath{\le}9$, optimal codeword stabilized codes correcting a single amplitude damping error can be found by considering standard form codes that detect one of only three of the ${3}^{n}$ possible equivalent error sets. By combining this error-set selection with the genetic algorithm approach, we have found ((11, 68)) and ((11, 80)) codes capable of correcting a single amplitude damping error and ((11, 4)), ((12, 4)), ((13, 8)), and ((14, 16)) codes capable of correcting two amplitude damping errors.

arXiv:1907.04537•Physical Review A•Dec 2, 2019•4 citations

Error correction for reliable quantum computing

Patricio Fuentes

Quantum computers herald the arrival of a new era in which previously intractable computational problems will be solved efficiently. However, quantum technology is held down by decoherence, a phenomenon that is omnipresent in the quantum paradigm and that renders quantum information useless when left unchecked. The science of quantum error correction, a discipline that seeks to combine and protect quantum information from the effects of decoherence using structures known as codes, has arisen to meet this challenge. Stabilizer codes, a particular subclass of quantum codes, have enabled fast progress in the field of quantum error correction by allowing parallels to be drawn with the widely studied field of classical error correction. This has resulted in the construction of the quantum counterparts of well-known capacity-approaching classical codes like sparse codes and quantum turbo codes. However, quantum codes obtained in this manner do not entirely evoke the stupendous error correcting abilities of their classical counterparts. This occurs because classical strategies ignore important differences between the quantum and classical paradigms, an issue that needs to be addressed if quantum error correction is to succeed in its battle with decoherence. In this dissertation we study a phenomenon exclusive to the quantum paradigm, known as degeneracy, and its effects on the performance of sparse quantum codes. Furthermore, we also analyze and present methods to improve the performance of a specific family of sparse quantum codes in various different scenarios.

arXiv:2202.08599•Feb 14, 2022•3 citations
Noise is a major obstacle in the development of practical schemes for quantum computation and communication. Similar to the case of classical communication, this noise can be protected against by employing a code, which provides a means for encoding quantum states prior to transmission and allows for errors to be inferred, and hopefully corrected, by a decoder at the receiver. Unfortunately, designing good codes and decoders is typically a difficult problem. This thesis focuses on developing low-complexity heuristic approaches to three such problems: the design of modified belief propagation decoders for quantum low-density parity-check codes, the design of stabilizer codes for asymmetric channels, and the design of codeword stabilized codes. Quantum low-density parity-check codes are stabilizer codes with low-weight generators. Such codes permit low-complexity decoding via the use of belief propagation, which is an iterative message passing algorithm that takes place on a factor graph defined by the code. However, the performance of such a decoder is limited both by code structure and the degenerate nature of quantum errors. To overcome these limitations, at least in part, a number of modifications to belief propagation are developed. Central among these is the augmented decoder, which in the case of a decoding error, iteratively reattempts decoding using modified factor graph. This heuristic modification simply involves the duplication of a randomly selected subset of the graph’s check nodes, which are in one-to-one correspondence with the code’s stabilizer generators. Across a range of codes, it is shown that the decoders developed perform as well as or better than other modified decoders presented in literature. For a number of channels of physical interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these so-called asymmetric channels, the decoding error rate can be minimized by tailoring the code used to the channel. However, assessing the performance of codes on a given channel is made difficult by the #P-completeness of optimal decoding. To address this complexity, it is shown that the decoding error rate can be accurately approximated using only a small fraction of the possible errors caused by the channel. This approximation is then used to identify a number of cyclic stabilizer codes that perform well on two different asymmetric channels. To further build on this, a heuristic is demonstrated for assessing code performance based on the decoding error rate of an associated classical code. The complexity of calculating this classical error rate is relatively low, and it is shown that it can be used as the basis for a hill-climbing search algorithm. Such searches have yielded a large number of highly performant codes satisfying various structure constraints. The family of codeword stabilized codes encompasses both the stabilizer codes as well as many of the best known nonadditive codes. Constructing a standard form codeword stabilized code is a matter of selecting a simple undirected graph and a binary classical code. This makes designing optimal codes difficult as the number of possible graphs grows exponentially with code length, and the clique search required to construct the classical code is NP-hard. To address the exponential growth of the search space, a heuristic is developed for assessing graphs. This heuristic is then employed by a genetic algorithm that also makes use of a novel crossover operation based on spectral bisection, which is show to be superior to more standard crossover operations. With a graph selected, it is demonstrated that the complexity of the clique search required to construct the associated classical code can be mitigated through the use of a heuristic clique finding algorithm. A number of best known codes are presented that have been found using this approach.
For a number of quantum channels of interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these asymmetric channels, the decoding error rate can be reduced by tailoring the code used to the channel. However, analyzing the performance of stabilizer codes on these channels is made difficult by the #P-completeness of optimal decoding. To address this, at least for short codes, we demonstrate that the decoding error rate can be approximated by considering only a fraction of the possible errors caused by the channel. Using this approximate error rate calculation, we extend a recent result to show that there are a number of $[[5\ensuremath{\le}n\ensuremath{\le}12,1\ensuremath{\le}k\ensuremath{\le}3]]$ cyclic stabilizer codes that perform well on two different asymmetric channels. We also demonstrate that an indication of a stabilizer code's error rate is given by considering the error rate of a classical binary code related to the stabilizer. This classical error rate is far less complex to calculate, and we use it as the basis for a hill-climbing algorithm, which we show to be effective at optimizing codes for asymmetric channels. Furthermore, we demonstrate that simple modifications can be made to our hill-climbing algorithm to search for codes with desired structure requirements.
Quantum error correction is an important building block for reliable quantum information processing. A challenging hurdle in the theory of quantum error correction is that it is significantly more difficult to design error-correcting codes with desirable properties for quantum information processing than for traditional digital communications and computation. A typical obstacle to constructing a variety of strong quantum error-correcting codes is the complicated restrictions imposed on the structure of a code. Recently, promising solutions to this problem have been proposed in quantum information science, where in principle any binary linear code can be turned into a quantum error-correcting code by assuming a small number of reliable quantum bits. This paper studies how best to take advantage of these latest ideas to construct desirable quantum error-correcting codes of very high information rate. Our methods exploit structured high-rate low-density parity-check codes available in the classical domain and provide quantum analogues that inherit their characteristic low decoding complexity and high error correction performance even at moderate code lengths. Our approach to designing high-rate quantum error-correcting codes also allows for making direct use of other major syndrome decoding methods for linear codes, making it possible to deal with a situation where promising quantum analogues of low-density parity-check codes are difficult to find.
Quantum error correction (QEC) is a cornerstone of quantum computing, enabling reliable information processing in the presence of noise. Sparse stabilizer codes -- referred to generally as quantum low-density parity-check (QLDPC) codes -- have risen to the forefront of QEC research in recent years. This can be attributed to several key factors. First, classical LDPC codes admit low-complexity belief propagation iterative decoding and near-capacity performance, which contributed to the early interest in QLDPC codes. Then, the result promising constant overhead fault tolerance using QLDPC codes led to the search for code families that go beyond the long-holding n\sqrt{n}n​ scaling barrier of minimum distance for codelength nnn. This resulted in recent breakthroughs in the construction of QLDPC codes, which, combined with efficient decoding algorithms and the development of fault-tolerant protocols operating on QLDPC-encoded quantum information, provide a promising pathway to low-overhead, fault-tolerant quantum computation. However, despite their potential, challenges remain, particularly in constructing and decoding finite-length codes that account for, or efficiently leverage, specific characteristics of quantum hardware, such as connectivity, topology, native gate sets, and noise models. This article provides an in-depth examination of QLDPC codes and their iterative decoders, catering to an information theory audience with no or limited background in quantum mechanics. We discuss the theoretical underpinnings, explore unique characteristics of quantum channels, and delineate key code constructions and decoding algorithms, ultimately highlighting the impact and future prospects of QLDPC codes in quantum information science.
Quantum computers would prove a ground-breaking effect in several re- search fields to the advantage of our society due to their proved capacity for solving some problems deemed as too complex for classical comput- ers. Consequently, there is a generalized academic effort for constructing a quantum computer. Nonetheless, a real quantum computer does not suffice for implementing quantum algorithms reliably, it must be fault-tolerant. Quantum computers undergo noise due to a phenomenon generally named quantum decoherence, a fault-tolerant quantum computer has the capabil- ity to suppress the effects of decoherence to an extent. For that to happen, a quantum computer should consider quantum error correction, a process in which decoherence is studied and attempted to be corrected. Within the context of quantum error correction, the information from quantum proces- sors is to be stored in a larger, more redundant system named a quantum error correcting code. Afterwards, one can obtain a vector named syndrome which provides partial information on the effect decoherence has had on a code. The process of recovering the decoherence or error that the code has undergone is named decoding. This thesis studies decoders for quan- tum error correcting codes, their performance, complexity and adaption to different types of quantum decoherence.
The family of codeword stabilized codes encompasses the stabilizer codes as well as many of the best known nonadditive codes. However, constructing optimal nnn-qubit codeword stabilized codes is made difficult by two main factors. The first of these is the exponential growth with nnn of the number of graphs on which a code can be based. The second is the NP-hardness of the maximum clique search required to construct a code from a given graph. We address the second of these issues through the use of a heuristic clique finding algorithm. This approach has allowed us to find $((9,97\ensuremath{\le}K\ensuremath{\le}100,2))$ and $((11,387\ensuremath{\le}K\ensuremath{\le}416,2))$ codes, which are larger than any previously known codes. To address the exponential growth of the search space, we demonstrate that graphs that give large codes typically yield clique graphs with a large number of nodes. The number of such nodes can be determined relatively efficiently, and we demonstrate that nnn-node graphs yielding large clique graphs can be found using a genetic algorithm. This algorithm uses a crossover operation based on spectral bisection that we demonstrate to be superior to more standard crossover operations. Using this genetic algorithm approach, we have found ((13, 18, 4)) and ((13, 20, 4)) codes that are larger than any previously known code. We also consider codes for the amplitude damping channel. We demonstrate that for $n\ensuremath{\le}9$, optimal codeword stabilized codes correcting a single amplitude damping error can be found by considering standard form codes that detect one of only three of the 3n{3}^{n}3n possible equivalent error sets. By combining this error-set selection with the genetic algorithm approach, we have found ((11, 68)) and ((11, 80)) codes capable of correcting a single amplitude damping error and ((11, 4)), ((12, 4)), ((13, 8)), and ((14, 16)) codes capable of correcting two amplitude damping errors.
Quantum computers herald the arrival of a new era in which previously intractable computational problems will be solved efficiently. However, quantum technology is held down by decoherence, a phenomenon that is omnipresent in the quantum paradigm and that renders quantum information useless when left unchecked. The science of quantum error correction, a discipline that seeks to combine and protect quantum information from the effects of decoherence using structures known as codes, has arisen to meet this challenge. Stabilizer codes, a particular subclass of quantum codes, have enabled fast progress in the field of quantum error correction by allowing parallels to be drawn with the widely studied field of classical error correction. This has resulted in the construction of the quantum counterparts of well-known capacity-approaching classical codes like sparse codes and quantum turbo codes. However, quantum codes obtained in this manner do not entirely evoke the stupendous error correcting abilities of their classical counterparts. This occurs because classical strategies ignore important differences between the quantum and classical paradigms, an issue that needs to be addressed if quantum error correction is to succeed in its battle with decoherence. In this dissertation we study a phenomenon exclusive to the quantum paradigm, known as degeneracy, and its effects on the performance of sparse quantum codes. Furthermore, we also analyze and present methods to improve the performance of a specific family of sparse quantum codes in various different scenarios.