https://hal.inria.fr/hal-02429542Grospellier, AntoineAntoineGrospellierSECRET - Security, Cryptology and Transmissions - Inria de Paris - Inria - Institut National de Recherche en Informatique et en AutomatiqueGrouès, LucienLucienGrouèsSU - Sorbonne UniversitéKrishna, AnirudhAnirudhKrishnaUdeS - Université de SherbrookeLeverrier, AnthonyAnthonyLeverrierSECRET - Security, Cryptology and Transmissions - Inria de Paris - Inria - Institut National de Recherche en Informatique et en AutomatiqueCombining Hard and Soft Decoders for Hypergraph Product CodesHAL CCSD2019[PHYS.QPHY] Physics [physics]/Quantum Physics [quant-ph]Grouès, Lucien2020-01-07 11:20:522022-12-09 12:20:392020-01-07 11:30:23enConference papers1Finding 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.