We introduce a stochastic resonance based decoding paradigm for quantum codes using an error correction circuit made of a combination of noisy and noiseless logic gates. The quantum error correction circuit is based on iterative syndrome decoding of quantum low-density parity check codes, and uses the positive effect of errors in gates to correct errors due to decoherence. We analyze how the proposed stochastic algorithm can escape from short cycle trapping sets present in the dual containing Calderbank, Shor and Steane (CSS) codes. Simulation results show improved performance of the stochastic algorithm over the deterministic decoder.
We introduce a stochastic resonance based decoding paradigm for quantum codes using an error correction circuit made of a combination of noisy and noiseless logic gates. The quantum error correction circuit is based on iterative syndrome decoding of quantum low-density parity check codes, and uses the positive effect of errors in gates to correct errors due to decoherence. We analyze how the proposed stochastic algorithm can escape from short cycle trapping sets present in the dual containing Calderbank, Shor and Steane (CSS) codes. Simulation results show improved performance of the stochastic algorithm over the deterministic decoder.
Protecting logical information in the form of a classical bit or a quantum bit (qubit) is an essential step in ensuring fault-tolerant classical or quantum computation. Error correction codes and their decoders perform this step by adding redundant information that aids the decoder to recover or protect the logical information even in the presence of noise. Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems. Similarly, their quantum analogues, quantum LDPC codes are being actively pursued as excellent prospects for error correction in future fault-tolerant quantum systems due to their asymptotically non-zero rates, sparse parity check matrices, and efficient iterative decoding algorithms. This dissertation deals with failure configurations, known as \emph{trapping sets} of classical and quantum LDPC codes when decoded with iterative message passing decoding algorithms, and the \emph{error floor phenomenon} - the degradation of logical error rate performance at low physical noise regime. The study of quantum trapping sets will enable the construction of better quantum LDPC codes and also help in modifying iterative quantum decoders to achieve higher fault-tolerant thresholds and lower error floors. Towards this goal, the dissertation also presents iterative decoders for classical and quantum LDPC codes using the \emph{deep neural network framework}, novel iterative decoding algorithms, and a decoder-aware \emph{expansion-contraction method} for error floor estimation. In this dissertation, we first establish a systematic methodology by which one can identify and classify \emph{quantum trapping sets} (QTSs) according to their topological structure and decoder used. For this purpose, we leverage the known harmful configurations in the Tanner graph, called \emph{trapping sets} (TSs), from the classical error correction world. The conventional definition of a trapping set of classical LDPC codes is generalized to address the syndrome decoding scenario for quantum LDPC codes. Furthermore, we show that the knowledge of QTSs can be used to design better quantum LDPC codes and decoders. In the context of the development of novel decoders, we extend the stochastic resonance based decoders to quantum LDPC codes, propose iteration-varying message passing decoders with their message update rules learned by neural networks tuned for low logical error rate, and present a syndrome based generalized belief propagation algorithm for tackling convergence failure of iterative decoders due to the presence of short cycles. Our analysis of TSs of a layered decoding architecture clearly reveals the dependence of the harmfulness of TSs (classical or quantum) on the iterative decoder, and thus on the error floor estimates. We present a computationally efficient method for estimating error floors of LDPC codes over the binary symmetric channel without any prior knowledge of its trapping sets. The sub-graph expansion-contraction method is a general procedure for TS characterization, which lists all harmful error patterns up to a given weight for the LDPC code and decoder. Based on this decoder-aware trapping set characterization for LDPC codes, we propose a model-driven deep neural network (DNN) framework that unfolds the decoding iterations, to design the \emph{decoder diversity of finite alphabet iterative decoders (FAIDs)}. Our decoder diversity DNN-FAID delivers excellent waterfall performance along with a low error floor.
This paper contains a survey on iterative decoders of low-density parity-check (LDPC) codes made of unreliable logic gates that are capable to provide lower probability of error, when compared to their perfectly reliable counterparts. We have recently shown that the error-floor performance of message-passing decoders can be improved, if randomness that exists in unreliable logic gates is incorporated into decoding deliberately, without any complexity cost. Furthermore, we have shown that controlling the level of unreliability enable us to exploit the stochastic resonance phenomenon, previously observed in theoretical physics, electronic and magnetic systems. In contrary to common belief, we have shown that for a narrow range of gate failure probability the overall decoding performance is dramatically increased. In this paper, we show that the effect of stochastic resonance is even more noticeable for the case of the gradient descent bit-flipping (GDBF) algorithm. This decoder combines the simplest iterative decoding algorithm with gradient descent optimization, making it an attractive solution for a variety of low complexity storage systems, or code-based cryptosystems. In addition, we show that getting the most of the stochastic resonance is essentially a deep learning problem, since setting the levels of unreliability for individual parts of the decoder by a training process is a step toward incorporating the machine learning techniques into design and analysis of iterative decoders of LDPC codes.
In the 1960s-70s, Taylor and Kuznetsov obtained a remarkable result that information can be reliably retrieved from a noisy channel even if a decoder is made of noisy components. The results of Vasic and Chilappagari presented at the ITA Workshop ten years ago have revived the interest in decoders made of noisy hardware and since then a number of improvements of the iterative decoders have been made to bring their performance closer to that of their perfect counterparts. However, a common mantra has been that noisy decoders cannot be better than their perfect counterparts. In this talk we report an unexpected phenomenon we have recently discovered - noise can actually improve the error correction process by reducing the probability of decoding error, in some cases by more that two orders of magnitude. This new form of stochastic resonance enables us to use logic gate errors to correct channel errors. This novelty recognizes that the decoder - essentially an iterative minimization of the Bethe free energy on the code graph - can get trapped in local minima, and random perturbations help the decoder to escape from these minima and converge to a correct code-word. In the spirit of Marcus Tullius Cicero's “Clavus clavo eicitur,” (“one nail drives out another”) they operate on the principle: Error errore eicitur” - “one error drives out another.” Crucially, such useful random perturbations require neither additional hardware nor energy, as they are built into the low-powered, noisy hardware itself.
Quantum errors are primarily detected and corrected using the measurement of syndrome information which itself is an unreliable step in practical error correction implementations. Typically, such faulty or noisy syndrome measurements are modeled as a binary measurement outcome flipped with some probability. However, the measured syndrome is in fact a discretized value of the continuous voltage or current values obtained in the physical implementation of the syndrome extraction. In this paper, we use this "soft" or analog information without the conventional discretization step to benefit the iterative decoders for decoding quantum low-density parity-check (QLDPC) codes. Syndrome-based iterative belief propagation decoders are modified to utilize the syndrome-soft information to successfully correct both data and syndrome errors simultaneously, without repeated measurements. We demonstrate the advantages of extracting the soft information from the syndrome in our improved decoders, not only in terms of comparison of thresholds and logical error rates for quasi-cyclic lifted-product QLDPC code families, but also for faster convergence of iterative decoders. In particular, the new BP decoder with noisy syndrome performs as good as the standard BP decoder under ideal syndrome.
Quantum error correction is essential for building scalable quantum computers. Within the stabilizer formalism, the Calderbank-Shor-Steane framework constructs quantum codes from pairs of classical linear codes. A distinctive feature in this setting is degeneracy, where multiple equivalent error estimates exist-a phenomenon that has no classical counterpart, and the lack of a meaningful classical coding-theoretic interpretation of which has remained a gap in the literature. In this paper, we demonstrate that degeneracy is closely related to the classical operation of shortening of a linear block code. Interestingly, the shortening here takes place at the decoder rather than at the encoder. Leveraging this insight, we present a parallel decoding scheme for quantum low-density parity-check codes, which we term impulse decoding, that significantly outperforms belief propagation with ordered statistics decoding, as well as several other existing techniques, under both code-capacity and circuit-level noise, with significantly lesser complexity. We then present another algorithm based on decoding of residual errors, which when combined with impulse decoding achieves further performance improvement under circuit-level noise.
Erasure decoding of quantum low-density paritycheck (QLDPC) codes has recently received a lot of interest as qubit erasures occur in many physical systems such as neutralatom systems, trapped-ion systems etc. However, decoding of QLDPC codes heavily relies on syndrome information, which may be unreliable as syndrome extraction circuits are prone to errors in practice. While syndrome errors are usually modeled as flipping of a binary syndrome bit, typically, measurement outcomes yield analog voltage/current values, which are then discretized to obtain the binary syndrome. Prior work on correcting qubit errors in the presence of syndrome noise shows that this soft (i.e., analog) information can be exploited to achieve performance improvement. In this paper, we consider the case of qubit erasures and present an iterative decoding algorithm, based on the hardware-friendly min-sum algorithm, that incorporates this soft information to perform check node updates. We show via simulations on hypergraph product codes and lifted product codes that our decoder achieves performance very close to that in the case of noiseless syndrome for a certain noise regime.