Fast Bounds on Matching Decoder Soft Output for the Surface Code

Surface code decoders like Minimum Weight Perfect Matching (MWPM) can also be used to estimate or bound the probability of a logical failure conditioned on the error syndrome commonly called ``soft outputs''. Estimates like the complementary gap of a matching, or others like the ``cluster gap'' are used to produce high fidelity magic states via post-selection. They are also helpful in reducing the overhead of fault-tolerant computation via code concatenation schemes like yoked surface codes. In this work we provide techniques to tightly lower bound the complementary gap of a rotated surface code syndrome block and provide fast parallel algorithms for computing this lower bound efficiently. Our algorithms run in real time for the moderate distances and reasonable physical noise rates required by these applications. We achieve latencies of the order of one to tens of microseconds on sufficiently fast CPU cores.