Lifting decoders for classical codes to decoders for quantum codes

classical resources. The lift and the correctness proof of the decoder have a purely algebraic nature that draws on the discovery of some novel homological invariants of the hypergraph product codespace. While the decoder works perfectly for adversarial errors, it is not suitable for more realistic stochastic noise models and therefore can not be used to establish an error correcting threshold.

Related papers

ReShape: A Decoder for Hypergraph Product Codes

Armanda O. Quintavalle, Earl T. Campbell

The design of decoding algorithms is a significant technological component in the development of fault-tolerant quantum computers. Often design of quantum decoders is inspired by classical decoding algorithms, but there are no general principles for building quantum decoders from classical decoders. Given any pair of classical codes, we can build a quantum code using the hypergraph product, yielding a hypergraph product code. Here we show we can also lift the decoders for these classical codes. That is, given oracle access to a minimum weight decoder for the relevant classical codes, the corresponding $[[n,k,d]]$ quantum code can be efficiently decoded for any error of weight smaller than $(d-1)/2$ . The quantum decoder requires only $O(k)$ oracle calls to the classical decoder and $O(n^{2})$ classical resources. The lift and the correctness proof of the decoder have a purely algebraic nature that draws on the discovery of some novel homological invariants of the hypergraph product codespace. While the decoder works perfectly for adversarial errors, that is errors of weight up to half the code distance, it is not suitable for more realistic stochastic noise models and therefore can not be used to establish an error correcting threshold.The design of decoding algorithms is a significant technological component in the development of fault-tolerant quantum computers. Often design of quantum decoders is inspired by classical decoding algorithms, but there are no general principles for building quantum decoders from classical decoders. Given any pair of classical codes, we can build a quantum code using the hypergraph product, yielding a hypergraph product code. Here we show we can also lift the decoders for these classical codes. That is, given oracle access to a minimum weight decoder for the relevant classical codes, the corresponding$[[n,k,d]]$quantum code can be efficiently decoded for any error of weight smaller than$(d-1)/2$. The quantum decoder requires only$O(k)$oracle calls to the classical decoder and$O(n^{2})$classical resources. The lift and the correctness proof of the decoder have a purely algebraic nature that draws on the discovery of some novel homological invariants of the hypergraph product codespace. While the decoder works perfectly for adversarial errors, that is errors of weight up to half the code distance, it is not suitable for more realistic stochastic noise models and therefore can not be used to establish an error correcting threshold.

arXiv:2105.02370IEEE Transactions on Information TheoryJun 17, 202214 citations

Combining Hard and Soft Decoders for Hypergraph Product Codes

Antoine Grospellier, Lucien Grouès, Anirudh Krishna +1 more

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.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.

Jul 29, 201911 citations

Linear Time Iterative Decoders for Hypergraph-Product and Lifted-Product Codes

Asit Kumar Pradhan, Nithin Raveendran, Narayanan Rengaswamy +1 more

Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.

arXiv:2504.01728IEEE Transactions on Information TheoryApr 27, 20260 citations

Energy Barrier in Quantum Error Correcting Codes

Guangqi Zhao

Quantum error correction is necessary for the building of a useful fault-tolerant quantum computer. However, in practice, error correction requires a large amount of fault-tolerance overheads and fast decoding. One promising approach to overcome this challenge is to use codes with a macroscopic energy barrier, which can be used to build self-correcting quantum memory. So far, rigorous bounds on the energy barrier have typically been derived only for specific codes. Determining a lower bound for the energy barrier of codes is generally challenging due to two reasons: there are too many possible error paths (sequences of local errors) that can implement a fixed logical operator, and the logical operator itself is defined only modulo stabilizers. In this thesis, we prove tight bounds on the energy barrier that are applicable to any quantum code obtained from the hypergraph product of two classical codes. If the underlying classical codes are low-density parity-check codes (LDPC), the energy barrier of the quantum code is shown to be the minimum energy barrier of the underlying classical codes (and their transposes) up to an additive $O(1)$ constant. Hypergraph product codes, at best, preserve the energy barrier of the underlying classical codes. Constructing a quantum code with a macroscopic energy barrier requires the underlying classical codes to feature an extensive energy barrier. However, determining the energy barrier for classical codes is challenging, although it is comparatively simpler than for quantum codes because of the absence of stabilizer effects. Utilizing a property of tensor product codes, we demonstrate that higher-dimensional hypergraph products may construct quantum codes with a macroscopic energy barrier, even when the underlying classical codes lack this property. Specifically, the 3D hypergraph product enhances the energy barrier of one type of logical operator.Quantum error correction is necessary for the building of a useful fault-tolerant quantum computer. However, in practice, error correction requires a large amount of fault-tolerance overheads and fast decoding. One promising approach to overcome this challenge is to use codes with a macroscopic energy barrier, which can be used to build self-correcting quantum memory. So far, rigorous bounds on the energy barrier have typically been derived only for specific codes. Determining a lower bound for the energy barrier of codes is generally challenging due to two reasons: there are too many possible error paths (sequences of local errors) that can implement a fixed logical operator, and the logical operator itself is defined only modulo stabilizers. In this thesis, we prove tight bounds on the energy barrier that are applicable to any quantum code obtained from the hypergraph product of two classical codes. If the underlying classical codes are low-density parity-check codes (LDPC), the energy barrier of the quantum code is shown to be the minimum energy barrier of the underlying classical codes (and their transposes) up to an additive $O(1)$ constant. Hypergraph product codes, at best, preserve the energy barrier of the underlying classical codes. Constructing a quantum code with a macroscopic energy barrier requires the underlying classical codes to feature an extensive energy barrier. However, determining the energy barrier for classical codes is challenging, although it is comparatively simpler than for quantum codes because of the absence of stabilizer effects. Utilizing a property of tensor product codes, we demonstrate that higher-dimensional hypergraph products may construct quantum codes with a macroscopic energy barrier, even when the underlying classical codes lack this property. Specifically, the 3D hypergraph product enhances the energy barrier of one type of logical operator.

Jan 1, 20260 citations

General Construction of Quantum Error-Correcting Codes from Multiple Classical Codes

Yue Wu, Meng-Yuan Li, Chengshu Li +1 more

The hypergraph product (HGP) construction of quantum error-correcting codes (QECC) offers a general and explicit method for building a QECC from two classical codes, thereby paving the way for the discovery of good quantum low-density parity-check codes. In this letter, we propose a general and explicit construction recipe for QECCs from a total of D classical codes for arbitrary D. Following this recipe guarantees the obtainment of a QECC within the stabilizer formalism and nearly exhausts all possible constructions. As examples, we demonstrate that our construction recovers the HGP construction when D = 2 and leads to four distinct types of constructions for D = 3, including a previously studied case as one of them. When the input classical codes are repetition codes, our D = 3 constructions unify various three-dimensional lattice models into a single framework, encompassing the three-dimensional toric code model, a fracton model, and two other intriguing models not previously investigated. Among these, two types of constructions exhibit a trade-off between code distance and code dimension for a fixed number of qubits by adjusting the lengths of the different classical codes, and the optimal choice can simultaneously achieve relatively large values for both code distance and code dimension. Our general construction protocol provides another perspective for enriching the structure of QECCs and enables the exploration of richer possibilities for good codes.The hypergraph product (HGP) construction of quantum error-correcting codes (QECC) offers a general and explicit method for building a QECC from two classical codes, thereby paving the way for the discovery of good quantum low-density parity-check codes. In this letter, we propose a general and explicit construction recipe for QECCs from a total of D classical codes for arbitrary D. Following this recipe guarantees the obtainment of a QECC within the stabilizer formalism and nearly exhausts all possible constructions. As examples, we demonstrate that our construction recovers the HGP construction when D = 2 and leads to four distinct types of constructions for D = 3, including a previously studied case as one of them. When the input classical codes are repetition codes, our D = 3 constructions unify various three-dimensional lattice models into a single framework, encompassing the three-dimensional toric code model, a fracton model, and two other intriguing models not previously investigated. Among these, two types of constructions exhibit a trade-off between code distance and code dimension for a fixed number of qubits by adjusting the lengths of the different classical codes, and the optimal choice can simultaneously achieve relatively large values for both code distance and code dimension. Our general construction protocol provides another perspective for enriching the structure of QECCs and enables the exploration of richer possibilities for good codes.

quant-pharXiv:2512.22116Physical review. B./Physical review. BDec 29, 20250 citations

Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes

Anthony Leverrier, Gilles Zémor

We introduce and analyse an efficient decoder for quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n\log n})$ . We also work on the link between quantum Tanner codes and the lifted product codes of Panteleev and Kalachev and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.We introduce and analyse an efficient decoder for quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n\log n})$ . We also work on the link between quantum Tanner codes and the lifted product codes of Panteleev and Kalachev and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.

ACM Transactions on AlgorithmsMay 7, 20246 citations

[[n,k,d]]

quantum code can be efficiently decoded for any error of weight smaller than

(d-1)/2

. The quantum decoder requires only

O(k)

oracle calls to the classical decoder and

O(n^2)

[[n,k,d]]

quantum code can be efficiently decoded for any error of weight smaller than

(d-1)/2

. The quantum decoder requires only

O(k)

oracle calls to the classical decoder and

O(n^{2})

classical resources. The lift and the correctness proof of the decoder have a purely algebraic nature that draws on the discovery of some novel homological invariants of the hypergraph product codespace. While the decoder works perfectly for adversarial errors, that is errors of weight up to half the code distance, it is not suitable for more realistic stochastic noise models and therefore can not be used to establish an error correcting threshold.

O(1)

constant. Hypergraph product codes, at best, preserve the energy barrier of the underlying classical codes. Constructing a quantum code with a macroscopic energy barrier requires the underlying classical codes to feature an extensive energy barrier. However, determining the energy barrier for classical codes is challenging, although it is comparatively simpler than for quantum codes because of the absence of stabilizer effects. Utilizing a property of tensor product codes, we demonstrate that higher-dimensional hypergraph products may construct quantum codes with a macroscopic energy barrier, even when the underlying classical codes lack this property. Specifically, the 3D hypergraph product enhances the energy barrier of one type of logical operator.

O(\sqrt{n\log n})

. We also work on the link between quantum Tanner codes and the lifted product codes of Panteleev and Kalachev and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.