Hypergraph Minimum-Weight Parity Factor Decoder for QEC

Minimum-Weight Perfect Matching (MWPM) decoder on graphs has been widely used for decoding errors in the surface code and shows high performance when noise is not correlated. However, it cannot effectively decode correlated noise or decode general codes where a single error produces multiple syndromes. In these cases, the decoding problem reduces to finding the Minimum-Weight Parity Factor (MWPF) on hypergraphs. In this work, we introduce and implement an approximate MWPF decoder on hypergraphs. We test the performance of the decoder for decoding correlated noise on the surface code and find that the decoding accuracy drastically improves compared to that of the MWPM decoder. Most importantly, it shows almost linear average time complexity given a sufficiently low physical error rate.