Skip to Main content Skip to Navigation
Conference papers

Combining Hard and Soft Decoders for Hypergraph Product Codes

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Lucien Grouès <>
Submitted on : Tuesday, January 7, 2020 - 11:20:52 AM
Last modification on : Wednesday, February 10, 2021 - 10:10:03 AM



  • HAL Id : hal-02429542, version 1



Antoine Grospellier, Lucien Grouès, Anirudh Krishna, Anthony Leverrier. Combining Hard and Soft Decoders for Hypergraph Product Codes. QEC19 - 5th International Conference on Quantum Error Correction, Jul 2019, London, United Kingdom. ⟨hal-02429542⟩



Record views


Files downloads