flip is an extremely simple and maximally local classical decoder which has been used to great effect in certain classes of classical codes. When applied to quantum codes there exist constant-weight errors (such as half of a stabiliser) which are uncorrectable for this decoder, so previous studies have considered modified versions of flip , sometimes in conjunction with other decoders. We argue that this may not always be necessary, and present numerical evidence for the existence of a threshold for flip when applied to the looplike syndromes of a three-dimensional toric code on a cubic lattice. This result can be attributed to the fact that the lowest-weight uncorrectable errors for this decoder are closer (in terms of Hamming distance) to correctable errors than to other uncorrectable errors, and so they are likely to become correctable in future code cycles after transformation by additional noise. Introducing randomness into the decoder can allow it to correct these "uncorrectable" errors with finite probability, and for a decoding strategy that uses a combination of belief propagation and probabilistic flip we observe a threshold of ∼5.5% under phenomenological noise. This is comparable to the best known threshold for this code ( ∼7.1% ) which was achieved using belief propagation and ordered statistics decoding [Higgott and Breuckmann, 2022], a strategy with a runtime of O(n3) as opposed to the O(n) ( O(1) when parallelised) runtime of our local decoder. We expect that this strategy could be generalised to work well in other low-density parity check codes, and hope that these results will prompt investigation of other previously overlooked decoders.
flip is an extremely simple and maximally local classical decoder which has been used to great effect in certain classes of classical codes. When applied to quantum codes there exist constant-weight errors (such as half of a stabiliser) which are uncorrectable for this decoder, so previous studies have considered modified versions of flip , sometimes in conjunction with other decoders. We argue that this may not always be necessary, and present numerical evidence for the existence of a threshold for flip when applied to the looplike syndromes of a three-dimensional toric code on a cubic lattice. This result can be attributed to the fact that the lowest-weight uncorrectable errors for this decoder are closer (in terms of Hamming distance) to correctable errors than to other uncorrectable errors, and so they are likely to become correctable in future code cycles after transformation by additional noise. Introducing randomness into the decoder can allow it to correct these "uncorrectable" errors with finite probability, and for a decoding strategy that uses a combination of belief propagation and probabilistic flip we observe a threshold of ∼5.5% under phenomenological noise. This is comparable to the best known threshold for this code ( ∼7.1% ) which was achieved using belief propagation and ordered statistics decoding [Higgott and Breuckmann, 2022], a strategy with a runtime of O(n3) as opposed to the O(n) ( O(1) when parallelised) runtime of our local decoder. We expect that this strategy could be generalised to work well in other low-density parity check codes, and hope that these results will prompt investigation of other previously overlooked decoders.
Quantum Low-Density Parity-Check (LDPC) codes provide a promising solution to protect quantum information from errors and are therefore considered an important step in the realisation of a fullscale fault-tolerant quantum computer. In this thesis, we study quantum LDPC codes under three different approaches, providing insights into renormalisation decoding for Kitaev’s toric code, establishing bounds on the minimum distance of geometrically-local codes, and constructing small instances of quantum Tanner codes. Kitaev’s toric code is a prominent quantum LDPC code that is currently the most widely pursued for experimental implementation. We focus on the probabilistic renormalisation decoders introduced by Duclos- Cianci and Poulin, a family of decoders that exhibit one of the best trade-offs between accuracy and efficiency. We study how they handle adversarial errors by introducing a deterministic renormalisation decoder that does not use a priori probabilities of the error model. We find that this renormalisation decoder allows for fractal-like uncorrectable error patterns, and we obtain a lower bound on the weight of such errors. Due to physical constraints, a lot of attention has gone into quantum LDPC codes whose stabilisers act only on a limited number of nearby qubits. We extend the well-known Bravyi-Terhal bound to quantum codes defined by local constraints on a lattice quotient, providing a crucial insight into the limitations of geometrically-local stabiliser codes. As an application, we provide upper bounds on the minimum distance of Abelian Two-Block Group Algebra codes, a family of quantum LDPC codes for which the minimum distance is currently unknown. In recent years, asymptotically good quantum LDPC codes were constructed, but provable results on their minimum distances only apply to impractically long codes. Following the effort in the design of near-term implementable codes, we construct short instances of quantum Tanner codes using square complexes obtained from lifted products of regular graphs. Several explicit instances of these codes exhibit minimum distances surpassing the square root of the code length.
In the quest for fault-tolerant quantum computation, the delicate nature of qubits demands the need for robust quantum error correction. Quantum error correcting codes, the quantum counterpart to classical error correcting codes in information theory, have been developed to address the unique challenges quantum bits face against the noise of their environment in storing information. These codes include but are not limited to the Kitaev surface code, toric code, rotated surface code, generalized bicycle code, and bivariate bicycle code. Fast and reliable decoders for these quantum error correcting codes are needed to correct errors and achieve fault tolerance on these qubits. The belief propagation algorithm, which is a efficient and reliable heuristic for decoding classical low-density parity check codes, has been generalized to different types of quantum error correction codes. Paired with the ordered statistics decoding algorithm as a post-processing step from the soft outputs of the belief propagation decoder, belief propagation and ordered statistics decoding has been one of the most promising avenues of efficient quantum error correction. This thesis combines the state-of-the-art belief propagation and ordered statistics decoding algorithms with the exploration of the neural belief propagation algorithm to leverage classical deep learning machines to learn message passing patterns in decoding the newest quantum codes, the rotated surface code and bivariate bicycle code. The neural network exploits the local lattice structure of these codes to adjust the trainable weights and biases to more learn message update patterns more efficiently than the vanilla belief propagation algorithm. In this thesis, we prove a new threshold for the physical error rate on the rotated surface code using a neural belief propagation algorithm and ordered statistics decoding that consistently outperforms the threshold established by the vanilla belief propagation algorithm with ordered statistics decoding. We additionally show the results for similar efforts on the bivariate bicycle codes, and discuss the difficulties in achieving a threshold using the current neural belief propagation algorithms.
In quantum computers, each logical qubit must be encoded in several physical qubits to protect against noise in physical qubits. The tetrahedral color code is such an encoding. In the primal lattice, the three-dimensional tetrahedral color code is a bitruncated octahedral lattice, and in the dual lattice, the tetrahedral color code is a four-colorable body-centered cubic lattice. This color code can be utilized for measurement-based quantum computing, for which all entanglement is present in a cluster state at the beginning of the computation and gate operations are performed by local measurements and classical operations. Moreover, this color code admits a gate set that is both transversal, i.e., realized by qubit-wise operations, and universal when supplemented by measurement and classical computing. During cluster state preparation and computation, errors may occur on the physical qubits. Therefore, it is necessary to have a decoder that, using the syndrome of these errors, finds a set of qubits to correct and performs the operations needed to correct those qubits. The decoder is considered successful if and only if the correction does not cause a logical error on the logical qubit. In this thesis, I present a decoder for Pauli Z, or phase-flip, errors on the three-dimensional tetrahedral color code with nonperiodic boundaries. This decoder for Z-errors includes as a subroutine a decoder for Pauli X errors. The decoder uses a restriction procedure to map the tetrahedral color code to a toric code. The toric code is another quantum error correcting code. Then, an existing toric code decoder interprets the error syndrome. This research on the bounded color code builds upon previous work on the unbounded color code and the two-dimensional color code. Under independently identically distributed noise, evidence indicates an error probability threshold for Z-errors between 0.01% and 0.02% and for X-errors between 2.5% and 3.3%. I also present example errors and illustrate how the decoder attempts to correct those errors.
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.
Different choices of quantum error-correcting codes can reduce the demands on the physical hardware needed to build a quantum computer. To achieve the full potential of a code, we must develop practical decoding algorithms that can correct errors that have occurred with high likelihood. Matching decoders are very good at correcting local errors while also demonstrating fast run times that can keep pace with physical quantum devices. We implement variations of a matching decoder for a three-dimensional, non-CSS, low-density parity check code known as the Chamon code, which has a non-trivial structure that does not lend itself readily to this type of decoding. The non-trivial structure of the syndrome of this code means that we can supplement the decoder with additional steps to improve the threshold error rate, below which the logical failure rate decreases with increasing code distance. We find that a generalized matching decoder that is augmented by a belief-propagation step prior to matching gives a threshold of 10.5% for depolarizing noise.
In this work, we study the single-shot performance of higher-dimensional hypergraph product codes decoded using belief propagation and ordered-statistics decoding [P.Panteleev and G. Kalachev, Quantum 5, 585 (2021)].We find that decoding data-qubit and syndrome-measurement errors together in a single stage leads to single-shot thresholds that greatly exceed all previously observed single-shot thresholds for these codes.For the three-dimensional toric code and a phenomenological noise model, our results are consistent with a sustainable threshold of 7.1% for Z errors, compared to the threshold of 2.90% previously found using a two-stage decoder [Quintavalle et al., 2021].For the four-dimensional (4D) toric code, for which both X and Z error correction is single shot, our results are consistent with a sustainable single-shot threshold of 4.3%, which is even higher than the threshold of 2.93% for the two-dimensional toric code for the same noise model but using L rounds of stabilizer measurement.We also explore the performance of balanced-product and 4D hypergraph-product codes, which we show lead to a reduction in qubit overhead compared the surface code for phenomenological error rates as high as 1%.