Combining Hard and Soft Decoders for Hypergraph Product Codes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Combining Hard and Soft Decoders for Hypergraph Product Codes

Résumé

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 : Papier court
Origine : Fichiers produits par l'(les) auteur(s)
Format : Présentation

Dates et versions

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

Identifiants

  • HAL Id : hal-02429542 , version 1

Citer

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⟩
67 Consultations
99 Téléchargements

Partager

Gmail Facebook X LinkedIn More