Splitting decoders for correcting hypergraph faults

Abstract

The surface code is one of the most popular quantum error correction codes. It comes with efficient decoders, such as the Minimum Weight Perfect Matching (MWPM) decoder and the Union-Find (UF) decoder, allowing for fast quantum error correction. For a general linear code or stabilizer code, the decoding problem is NP-hard. What makes it tractable for the surface code is the special structure of faults and checks: Each X and Z fault triggers at most two checks. As a result, faults can be interpreted as edges in a graph whose vertices are the checks, and the decoding problem can be solved using standard graph algorithms such as Edmonds' minimum-weight perfect matching algorithm. For general codes, this decoding graph is replaced by a hypergraph making the decoding problem more challenging. In this work, we propose two heuristic algorithms for splitting the hyperedges of a decoding hypergraph into edges. After splitting, hypergraph faults can be decoded using any surface code decoder. Due to the complexity of the decoding problem, we do not expect this strategy to achieve a good error correction performance for a general code. However, we empirically show that this strategy leads to a good performance for some classes of LDPC codes because they are defined by low weight checks. We apply this splitting decoder to Floquet codes for which some faults trigger up to four checks and verify numerically that this decoder achieves the maximum code distance for two instances of Floquet codes.