We show that belief propagation combined with ordered statistics post-processing is a general decoder for quantum low-density parity-check codes constructed from the hypergraph product.To this end, we run numerical simulations of the decoder applied to three families of hypergraph product code: topological codes, fixed-rate random codes, and a new class of codes that we call semitopological codes.Our new code families share properties of both topological and random hypergraph product codes, with a construction that allows for a finely controlled trade-off between code threshold and stabilizer locality.Our results indicate thresholds across all three families of hypergraph product code, and provide evidence of exponential suppression in the low error regime.For the toric code, we observe a threshold in the range 9.9% ± 0.2%.This result improves upon previous quantum decoders based on belief propagation, and approaches the performance of the minimum-weight perfectmatching algorithm.We expect semitopological codes to have the same threshold as toric codes, as they are identical in the bulk, and we present numerical evidence supporting this observation.
We show that belief propagation combined with ordered statistics post-processing is a general decoder for quantum low-density parity-check codes constructed from the hypergraph product.To this end, we run numerical simulations of the decoder applied to three families of hypergraph product code: topological codes, fixed-rate random codes, and a new class of codes that we call semitopological codes.Our new code families share properties of both topological and random hypergraph product codes, with a construction that allows for a finely controlled trade-off between code threshold and stabilizer locality.Our results indicate thresholds across all three families of hypergraph product code, and provide evidence of exponential suppression in the low error regime.For the toric code, we observe a threshold in the range 9.9% ± 0.2%.This result improves upon previous quantum decoders based on belief propagation, and approaches the performance of the minimum-weight perfectmatching algorithm.We expect semitopological codes to have the same threshold as toric codes, as they are identical in the bulk, and we present numerical evidence supporting this observation.
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.
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.
Quantum low-density parity-check (QLDPC) codes are an important class of quantum error-correcting codes that have low-weight stabilizer generators and typically offer encoding rates much higher than popular topological quantum codes such as surface and toric codes. While recent constructions of QLDPC codes have been aimed at two-level quantum systems, several hardware platforms for quantum computing, including superconducting and photonic systems, support a much larger Hilbert space. This makes the design of qudit-based quantum LDPC codes an issue of paramount significance in harnessing the increased flexibility afforded by high -dimensional quantum systems. In this paper, we forge the first steps in addressing this gap and explore the generalization of QLDPC constructions to qudit systems. We review two methods of generalizing binary quantum codes to qudit codes, namely, the stack and merge constructions, and investigate the application of these two meth-ods to the well-known hypergraph product and lifted-product codes. Subsequently, we provide upper and lower bounds for the encoding rates of the resulting qudit codes. We also prove an interesting relationship between the qudit hypergraph product and qudit lifted-product codes: the merge construction applied to the lifted product code is equivalent to the stack construction applied to the hypergraph product code under certain conditions. We evaluate the performance of these qudit codes under non-binary belief-propagation decoding and observe that qudit codes offer us a greater degree of flexibility in optimizing their rate-performance trade-off. We also demonstrate that, under certain conditions, qudit codes can simultaneously achieve higher rates and higher frame error rate (FER) performance than their binary counterparts.
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%.
We study the performance of medium-length quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes with the maximal stabilizer weight much smaller than their minimum distance are considered. It is shown that with the help of OSD-like post-processing the performance of the standard belief propagation (BP) decoder on many QLDPC codes can be improved by several orders of magnitude. Using this new BP-OSD decoder we study the performance of several known classes of degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah's cubic codes. We also construct several interesting examples of short generalized bicycle codes. Some of them have an additional property that their syndromes are protected by small BCH codes, which may be useful for the fault-tolerant syndrome measurement. We also propose a new large family of QLDPC codes that contains the class of hypergraph product codes, where one of the used parity-check matrices is square. It is shown that in some cases such codes have better performance than hypergraph product codes. Finally, we demonstrate that the performance of the proposed BP-OSD decoder for some of the constructed codes is better than for a relatively large surface code decoded by a near-optimal decoder.
Belief propagation (BP) is well-known as a low complexity decoding algorithm with a strong performance for important classes of quantum error correcting codes, e.g. notably for the quantum low-density parity check (LDPC) code class of random expander codes. However, it is also well-known that the performance of BP breaks down when facing topological codes such as the surface code, where naive BP fails entirely to reach a below-threshold regime, i.e. the regime where error correction becomes useful. Previous works have shown, that this can be remedied by resorting to post-processing decoders outside the framework of BP. In this work, we present a generalized belief propagation method with an outer re-initialization loop that successfully decodes surface codes, i.e. opposed to naive BP it recovers the sub-threshold regime known from decoders tailored to the surface code and from statistical-mechanical mappings. We report a threshold of 17% under independent bit-and phase-flip data noise (to be compared to the ideal threshold of 20.6% ) and a threshold value of 14% under depolarizing data noise (compared to the ideal threshold of 18.9% ), which are on par with thresholds achieved by non-BP post-processing methods.