Quantum devices suffer from high error-rates, which makes them ineffective for running practical applications. Quantum computers can be made fault tolerant using \textit{Quantum Error Correction} (QEC), which encodes logical qubits using data qubits and parity qubits. To detect errors, the parity qubits are measured periodically to produce a syndrome, which is decoded by a classical {\em decoder} to identify the location and type of errors. To prevent errors from accumulating and causing a logical error, decoders must accurately correct errors in real time, necessitating the use of hardware for real-time decoding because software decoders are slow. Ideally, a real-time decoder should match the performance of the \textit{Minimum-Weight Perfect Matching} (MWPM) decoder. However, due to the complexity of the underlying Blossom algorithm, state-of-the-art decoders either use lookup tables, which are not scalable, or use approximate decoding, which significantly increases in logical error rates. In this paper, we leverage two key insights to enable practical real-time MWPM decoding. First, for near-term implementations (up-to $d=7$) of surface codes, the Hamming weight of the syndromes tend to be quite small (less than or equal to 10). For this regime, we propose {\em Astrea}, which simply does a brute-force search for the few hundred possible options to perform accurate decoding within a few nanoseconds (1ns average, 456ns worst-case), thus representing the first decoder to be able to do MWPM in real-time up-to distance 7. Second, even for codes that produce syndromes with higher Hamming weights (e.g. $d=9$) the search for optimal pairings can be made more efficient by simply discarding the weights that denote significantly lower probability than the logical error-rate of the code. For this regime, we propose a greedy design called {\em Astrea-G}, which filters high-cost weights and reorders the search from high-likelihood pairings to low-likelihood pairings to produce the most likely decoding within $1\mu$s (average 450ns). Our evaluations show that Astrea-G provides similar logical error-rates as the software-based MWPM for up-to $d=9$ codes while meeting the real-time constraints.

Version for artifact evaluation @ ISCA 2023.