We propose a decoder for the correction of erasures with hypergraph product codes, which form one of the most popular families of quantum LDPC codes. Our numerical simulations show that this decoder provides a close approximation of the maximum likelihood decoder that can be implemented in O ( N 2 ) bit operations where N is the length of the quantum code. A probabilistic version of this decoder can be implemented in O ( N 1.5 ) bit operations.
We propose a decoder for the correction of erasures with hypergraph product codes, which form one of the most popular families of quantum LDPC codes. Our numerical simulations show that this decoder provides a close approximation of the maximum likelihood decoder that can be implemented in O ( N 2 ) bit operations where N is the length of the quantum code. A probabilistic version of this decoder can be implemented in O ( N 1.5 ) bit operations.
To be able to perform useful computations employing quantum computers we need to make quantum information more robust against noise. One promising approach is to protect the information using quantum LDPC codes, however they are useless without a powerful decoder. In this thesis we will study the decoding of LDPC quantum codes, and in particular of hypergraph product codes with several decoders. We first study a decoder solely focused on performance obtained from the combination of two already existing decoders, BP and SSF. We show through simulations that it has improved performance on random hypergraph product codes compared to each of the decoders alone. Later we concentrate on a decoder easier to analyse which exhibits interesting theoretical guarantees by continuing the work started by Li and Vontobel of importing the LP decoder to quantum error correction. We manage to prove negative results affecting the asymptotic performance on several LDPC quantum codes, while showing that it still performs well on hypergraph product codes of realistic size. Finally we focus on local decoders for the decoding of quantum LDPC code. In particular we numerically study a parallel variant of SSF in its fastest and most local implementation.
We introduce a new erasure decoder that applies to arbitrary quantum LDPC codes. Dubbed the cluster decoder, it generalizes the decomposition idea of Vertical-Horizontal (VH) decoding introduced by Connolly et al. in 2022. Like the VH decoder, the idea is to first run the peeling decoder and then post-process the resulting stopping set. The cluster decoder breaks the stopping set into a tree of clusters, which can be solved sequentially via Gaussian Elimination. By allowing clusters of unconstrained size, this decoder achieves maximum-likelihood (ML) performance with reduced complexity compared with full Gaussian Elimination. When Gaussian Elimination is applied only to clusters whose sizes are less than a constant, the performance is degraded, but the complexity becomes linear in the block length. Our simulation results show that, for hypergraph product codes, the cluster decoder with constant cluster size achieves near-ML performance similar to VH decoding in the low-erasure-rate regime. For the general quantum LDPC codes we studied, the cluster decoder can be used to estimate the ML performance curve with reduced complexity over a wide range of erasure rates.
Hypergraph product codes introduced by Tillich and Zémor are a class of quantum LDPC codes with constant rate and distance scaling with the square-root of the block size. Quantum expander codes, a subclass of these codes, can be decoded using the linear time small-set-flip algorithm of Leverrier, Tillich and Zémor. In this paper, we numerically estimate the performance for the hypergraph product codes under independent bit and phase flip noise. We focus on two families of hypergraph product codes. The first family has rate 1/61∼1.6%, has qubits of weight 10 or 12 and stabilizers of weight 11. We report a threshold near 4.6% for the small-set-flip decoder. We also show that for similar rate, the performance of the hypergraph product is better than the performance of the toric code as soon as we deal with more than 500 logical qubits and that for 3600 logical qubits, the logical error rate for the hypergraph product code is several orders of magnitude smaller. The second family has rate 0.2, qubits of weight 10 and 20 and stabilizers of weight 15. We report a threshold near 2% for the small-set-flip decoder.
Hypergraph product (HGP) codes are one of the most popular family of quantum low-density parity-check (LDPC) codes. Circuit-level simulations show that they can achieve the same logical error rate as surface codes with a reduced qubit overhead. They have been extensively optimized by importing classical techniques such as the progressive edge growth, or through random search, simulated annealing or reinforcement learning techniques. In this work, instead of machine learning (ML) algorithms that improve the code performance through local transformations, we impose additional global symmetries, that are hard to discover through ML, and we perform an exhaustive search. Precisely, we focus on the hypergraph product of two cyclic codes, which we call CxC codes and we study C2 codes which are the product a cyclic code with itself and CxR codes which are the product of a cyclic codes with a repetition code. We discover C2 codes and CxR codes that significantly outperform previously optimized HGP codes, achieving better parameters and a logical error rate per logical qubit that is up to three orders of magnitude better. Moreover, some C2 codes achieve simultaneously a lower logical error rate and a smaller qubit overhead than state-of-the-art LDPC codes such as the bivariate bicycle codes, at the price of a larger block length. Finally, leveraging the cyclic symmetry imposed on the codes, we design an efficient planar layout for the QCCD architecture, allowing for a trapped ion implementation of the syndrome extraction circuit in constant depth.
Quantum low density parity-check (QLDPC) codes represent an attractive candidate for achieving fault-tolerant quantum computation. Erasure decoding of QLDPC codes has gained traction recently as many physical systems such as neutral-atom systems, photonic systems, trapped-ion systems etc. suffer from qubit erasures. Techniques for erasure decoding of QLDPC codes via belief propagation (BP) have been proposed in the literature, such as BP with guided decimation (BP-GD), where decimation refers to sequentially fixing hard values for the variable nodes. We provide an alternative decimation-based BP algorithm, which we term the BP with degree-based decimation (BP-DD) algorithm, that intelligently chooses a check node based on its degree and subsequently decimates a variable node in its neighborhood. We apply the BP-DD algorithm to two families of QLDPC codes, namely hypergraph product codes and lifted product codes, and show improved logical error performance over the BP-GD algorithm, without incurring additional complexity. Our simulations show that the BP-DD algorithm provides a versatile solution for erasure decoding of QLDPC codes, in contrast to some techniques in the literature that are applicable to only specific classes of QLDPC codes.
We design low-complexity, fault-tolerant decoders for quantum low-density parity-check (QLDPC) codes with the goal of reducing decoding latency. We target two major bottlenecks of decoding under the \emph{circuit-level} noise model: (i) post-processing via order-statistics decoding (OSD), and (ii) the large number of auxiliary variable nodes commonly introduced to represent CNOT-induced correlations during syndrome extraction. Our key observation is that propagating CNOT faults (\emph{hook errors}) create \emph{stabilizer-induced} trapping sets (TSs) that are intrinsic to hypergraph-product (HGP) and lifted-product (LP) constructions. Therefore, instead of modeling each such fault with an explicit correlation node and relying on OSD to clean up the resulting failures, we design message-passing decoders that resolve the corresponding \emph{stabilizer-induced} TSs directly. We obtain these decoders by deriving QLDPC decoders from decoders for the parent classical LDPC codes and using them collectively to correct broad families of \emph{stabilizer-induced} TSs. For CNOT faults that manifest primarily as syndrome errors, we show that their effect is equivalent to a data error together with syndrome-bit measurement errors. Consequently, given repeated measurements and a decoding graph that already includes nodes representing syndrome-bit errors, no distinct variable node is needed for each CNOT fault. Using a \emph{phenomenological} Tanner graph with nodes representing only data errors and syndrome-bit errors, simulations on LP codes show a significant improvement in logical error rate relative to BP+OSD. Moreover, the improved error correction relies on low-complexity finite-state iterative decoders, targeted for fast and low-latency FPGA implementation.