Interpretation of Union-Find Decoder on Weighted Graphs and Application to XZZX Surface Code

Union-Find (UF) and Minimum-Weight Perfect Matching (MWPM) are popular decoder designs for surface codes. The former has significantly lower time complexity than the latter. On the other hand UF is considered somewhat inferior to MWPM, in terms of decoding accuracy. In this work we present an interpretation of UF decoder on weighted graphs. This interpretation provides an explanation of why UF and MWPM decoders perform closely: UF decoder is an approximate implementation of the blossom algorithm used for MWPM. This interpretation also shows that UF decoder should work very well with the XZZX code when noise in the underlying hardware is strongly biased. With analytics and numerical simulations, we show that the accuracy of the UF decoder is identical to that of MWPM for XZZX surface code when noise is infinitely biased and measurements are perfect. When circuit-level noise is taken into account then the UF decoder has a threshold of only 6% less than that of the MWPM decoder. In a practical setting with noise bias of 100, the threshold of UF decoder is 2% less with perfect measurements and 9% less with circuit-level noise than that of the MWPM decoder.