Combining Hard and Soft Decoders for Hypergraph Product Codes - Archive ouverte HAL Access content directly
Conference Papers Year :

Combining Hard and Soft Decoders for Hypergraph Product 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.
Abstract.pdf (60.62 Ko) Télécharger le fichier
Slides.pdf (922.77 Ko) Télécharger le fichier
Format : Short paper
Origin : Files produced by the author(s)
Format : Presentation

Dates and versions

hal-02429542 , version 1 (07-01-2020)


  • 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⟩
63 View
67 Download


Gmail Facebook Twitter LinkedIn More