Topological codes, a kind of quantum error correction code, have been used for current quantum computers due to their local qubit layout and high threshold. With nearly linear complexity, syndrome-based belief propagation (BP) can be considered as a decoding candidate for topological codes. However, such highly degenerate codes will lead to multiple low-weight errors where the syndrome is identical so that the BP decoding is not able to distinguish it, resulting in degradation in performance. In this article, we propose a branch-assisted sign-flipping belief propagation (BSFBP) decoding method for topological codes based on the hypergraph product structure. In our algorithm, we introduce the criteria to enter the new decoding path branched from BP combined with a syndrome residual, which is obtained from the syndrome-pruning process. A sign-flipping process is also conducted to disturb the log-likelihood ratio of the selected variable nodes, which provides diversity in the syndrome residual. Simulation results show that using the proposed BSFBP decoding is able to outperform the BP decoding by about two orders of magnitude.
Topological codes, a kind of quantum error correction code, have been used for current quantum computers due to their local qubit layout and high threshold. With nearly linear complexity, syndrome-based belief propagation (BP) can be considered as a decoding candidate for topological codes. However, such highly degenerate codes will lead to multiple low-weight errors where the syndrome is identical so that the BP decoding is not able to distinguish it, resulting in degradation in performance. In this article, we propose a branch-assisted sign-flipping belief propagation (BSFBP) decoding method for topological codes based on the hypergraph product structure. In our algorithm, we introduce the criteria to enter the new decoding path branched from BP combined with a syndrome residual, which is obtained from the syndrome-pruning process. A sign-flipping process is also conducted to disturb the log-likelihood ratio of the selected variable nodes, which provides diversity in the syndrome residual. Simulation results show that using the proposed BSFBP decoding is able to outperform the BP decoding by about two orders of magnitude.
Hypergraph product codes are a class of constant-rate quantum low-density parity-check (LDPC) codes equipped with a linear-time decoder called small-set-flip (SSF). This decoder displays sub-optimal performance in practice and requires very large error correcting codes to be effective. In this work, we present new hybrid decoders that combine the belief propagation (BP) algorithm with the SSF decoder. We present the results of numerical simulations when codes are subject to independent bit-flip and phase-flip errors. We provide evidence that the threshold of these codes is roughly 7.5% assuming an ideal syndrome extraction, and remains close to 3% in the presence of syndrome noise. This result subsumes and significantly improves upon an earlier work by Grospellier and Krishna (arXiv:1810.03681). The low-complexity high-performance of these heuristic decoders suggests that decoding should not be a substantial difficulty when moving from zero-rate surface codes to constant-rate LDPC codes and gives a further hint that such codes are well-worth investigating in the context of building large universal quantum computers.
Topological quantum codes are promising candidates for realizing fault-tolerant quantum computing. In this context, belief propagation (BP) decoding is an efficient method for topological codes, offering high error-correction performance with low complexity. However, BP decoding suffers significant performance degradation due to quantum trapping sets (QTSs). Although various decoding schemes have been proposed to mitigate the performance degradation caused by QTSs, they incur high computational complexity and/or long latency. Moreover, they do not effectively address the presence of multiple QTSs that frequently arise as independent local structures in topological codes. To overcome this technical challenge, we propose a novel decoding scheme consisting of BP decoding and a low-complexity error-path detector. In particular, the proposed decoding scheme is designed to effectively break QTSs by exploiting paths with erroneous variable nodes (VNs) between unsatisfied check nodes. The proposed error-path detector identifies a set of paths associated with QTSs present in BP decoding failures. Then, the QTS-induced decoding failures are resolved by re-executing the BP decoding after modifying the prior information for the erroneous VNs in the identified paths. Numerical results show that the proposed decoding scheme achieves superior error-correction performance over state-of-the-art decoding schemes for various topological codes. Furthermore, we show that the proposed error-path detector operates with negligible computational overhead compared to BP per iteration. Thus, the proposed decoding scheme maintains the computational efficiency of BP decoding while effectively breaking multiple QTSs, making it a practical solution for decoding topological codes.
Finding good quantum low density parity check (LDPC) codes is an essential step for the design of efficient quantum fault-tolerant protocols. The hypergraph product construction [1] is a combinatorial way to build an LDPC CSS code with parameters [[n, Θ(n), Θ(√n)]] from a well chosen classical code. Moreover, the hypergraph product obtained from a classical expander code [2] can be used to perform fault-tolerant quantum computation with constant overhead in space and has the single-shot error correction property [3, 4]. Although these codes exhibit good features asymptotically, it is unknown whether they are suitable for small block lengths [5, 6, 7]. In this work, we take steps towards addressing this problem. Our motivations stem from classical coding theory. Sipser and Spielman discovered a linear time decoder for classical expander codes [2]. This inspired the quantum decoding algorithm small-set-flip introduced in [8]. The bit-flip algorithm, however, is never used in practice because it is outperformed by message passing algorithms such as belief propagation. Naively generalizing belief propagation to the quantum LDPC codes is ineffective due to degeneracy [9, 10, 11]. In particular, the belief propagation decoder does not perform well on hypergraph product codes [7]. In this work, we show that running the BP algorithm followed by the small-set-flip decoder significantly improves the decoding threshold and the finite-length behavior. In [5] it has been shown that an exponential time decoder achieves a threshold near 7% and [6] shows that the small-set-flip algorithm has a threshold near 4.5%. This work shows that combining the belief propagation and the small-set-flip decoder, leads to a threshold above 7% for hypergraph product codes with rate 4% constructed from (3, 4)-regular codes. In addition, running the small-set-flip decoder alone requires quantum codes with generators of weight at least 11 [6] whereas combining the two decoders allows us to use codes with generators of weight 7. Reducing the generators weight improves the running time of the decoder and is required to perform the corresponding quantum measurements on real devices.
We introduce a decoder for quantum CSS codes that is based on linear programming. Our definition is a priori slightly different from the one proposed by Li and Vontobel as we have a syndrome oriented approach instead of an error oriented one, but we show that the success condition is equivalent. Although we prove that this decoder fails for quantum codes that do not have good soundness property (i.e., having large errors with syndrome of small weight) such as the toric code, we obtain good results from simulations. We run our decoder for hypergraph products of two random LDPC codes, showing that it performs better than belief propagation, even combined with the small-set-flip decoder that can provably correct a constant fraction of random errors.
Abstract Quantum information needs to be protected by quantum error-correcting codes due to imperfect physical devices and operations. One would like to have an efficient and high-performance decoding procedure for the class of quantum stabilizer codes. A potential candidate is Gallager’s sum-product algorithm, also known as Pearl’s belief propagation (BP), but its performance suffers from the many short cycles inherent in a quantum stabilizer code, especially highly-degenerate codes. A general impression exists that BP is not effective for topological codes. In this paper, we propose a decoding algorithm for quantum codes based on quaternary BP with additional memory effects (called MBP). This MBP is like a recursive neural network with inhibitions between neurons (edges with negative weights), which enhance the perception capability of a network. Moreover, MBP exploits the degeneracy of a quantum code so that the most probable error or its degenerate errors can be found with high probability. The decoding performance is significantly improved over the conventional BP for various quantum codes, including quantum bicycle, hypergraph-product, surface and toric codes. For MBP on the surface and toric codes over depolarizing errors, we observe error thresholds of 16% and 17.5%, respectively.
Surface codes have gained widespread popularity as quantum error-correction codes due to their unique structural feature that encoders and decoders can be implemented by leveraging interactions between physically neighboring qubits. The implementational advantage of surface codes has driven extensive research into decoding algorithms for surface codes, aimed at improving error-rate performance and/or reducing decoding complexity. In this paper, we propose a low-complexity postprocessing algorithm that effectively resolves failures of a syndrome-based belief-propagation (SB-BP) decoder for surface codes. In particular, we carefully analyze the topological structure of surface codes and present a method for selecting reliable qubits, enabling efficient recovery operator identification through a simple syndrome matching technique with a lookup table. Furthermore, we present an efficient way to construct lookup tables tailored to the proposed postprocessing algorithm. Numerical results demonstrate that the proposed postprocessing algorithm requires substantially reduced complexity as compared to that of a competing postprocessing algorithm, the ordered statistics decoding in the depolarizing error model, while providing the same logical error-rate (LER) performance. It is also demonstrated that the combination of SB-BP decoding and the proposed postprocessing algorithm outperforms minimum weight perfect matching, a more computationally expensive decoding algorithm, in terms of LER and threshold at drastically reduced complexity.