Bubble Clustering Decoder for Quantum Topological Codes
Diego Forlivesi, Lorenzo Valentini, and Marco Chiani · 2025
Read Bubble Clustering Decoder for Quantum Topological Codes by Diego Forlivesi, Lorenzo Valentini, and Marco Chiani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01654.txt.
Introduction
Diego Forlivesi, Lorenzo Valentini, and Marco Chiani design a faster decoder for quantum surface codes. Quantum data fade fast, so faults must be read and fixed in real time. The standard decoder, MWPM, is exact but slow. Their 2025 bubble clustering decoder grows bubbles around each defect to group faults, and skips the slow merge steps of older cluster methods.
The speed gain costs a small drop in fixing power. Cost checks show the work grows with the square of the defect count. At mild fault rates that equals a straight-line cost in the number of data qubits. The trade suits machines where decode lag, not raw power, is the binding limit. It is pitched as a stand-in for MWPM in live fault-tolerant rigs.
Catalog record
| CREATOR | Diego Forlivesi, Lorenzo Valentini, and Marco Chiani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01654
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bubble Clustering Decoder for Quantum Topological Codes Diego Forlivesi, Lorenzo Valentini, and Marco Chiani Abstract Quantum computers are highly vulnerable to noise, necessitating the use of error-correcting codes to protect stored data. Errors must be continuously corrected over time to counteract decoherence using appropriate decoders. Therefore, fast decoding strategies capable of handling real-time syndrome extraction are crucial for achieving fault-tolerant quantum computing. In this paper, we introduce the bubble clustering (BC) decoder for quantum surface codes, which serves as a low-latency replacement for MWPM, achieving significantly faster execution at the cost of a slight performance degradation. This speed boost is obtained leveraging an efficient cluster generation based on bubbles centered on defects, and avoiding the computational overhead associated with cluster growth and merging phases, commonly adopted in traditional decoders. Our complexity analysis reveals that the proposed decoder operates with a complexity on the order of the square of the number of defects. For moderate physical error rates, this is equivalent to linear complexity in the number of data qubits. AWGN additive white Gaussian noise BCH Bose–Chaudhuri–Hocquenghem BC bubble clustering CDF cumulative distribution function CRC cyclic redundancy code LDPC low-density parity-check LUT lookup table ML maximum likelihood MWPM minimum weight perfect matching QECC quantum error correcting code PDF probability density function PMF probability mass function MPS matrix product state WEP weight enumerator polynomial WE weight enumerator BD bounded distance QLDPC quantum low density parity check CSS Calderbank, Shor, and Steane MST minimum spanning tree PruST pruned spanning tree RFire Rapid-Fire UF union-find LEMON library for efficient modeling and optimization in networks STM spanning tree matching i.i.d. independent identically distributed QEC quantum error correction BP belief propagation I Introduction The groundbreaking potential of quantum computing is fundamentally constrained by the fragility of quantum states, which are highly vulnerable to decoherence [ 1 , 2 , 3 ] . To address this challenge, QEC ( QEC ) has emerged as a critical area of research to enable quantum computing and communication [ 4 , 5 , 6 , 7 ] . In this context, numerous short QECC have been proposed in the literature as early methods for encoding quantum information [ 3 , 8 , 9 , 10 , 11 , 12 , 13 ] . In recent years, significant efforts have been made to find quantum codes that are easier to implement. Among them, one of the most promising approaches in quantum error correction is represented by surface codes [ 14 , 15 ] . These topological surface codes encode logical qubits onto a two-dimensional lattice of physical qubits, offering robust error protection with relatively practical implementation requirements [ 16 , 17 ] . With their high error threshold, locality, and scalability, surface codes have therefore emerged as a leading candidate for implementation in fault-tolerant quantum computing architectures [ 18 , 19 , 20 ] . The MWPM ( MWPM ) decoder is currently the prevalent choice for surface code decoding [ 21 , 22 ] . While it offers high threshold error rates, its high order polynomial time complexity can lead to latency issues, potentially hindering the performance of quantum computation architectures [ 23 , 24 ] . Indeed, if the decoder is unable to process measurements quickly enough, the accumulating backlog of syndrome information can lead to an exponential increase in computation time [ 25 ] . To overcome this latency problem, the PyMatching sparse blossom implementation was introduced, delivering a speed boost of up to 100 times compared to the standard MWPM decoder [ 26 ] . This improvement was achieved by focusing exclusively on the essential edges of the lattice needed for the blossom algorithm and by incorporating techniques such as compressed tracking. A specialized version of the Sparse Blossom algorithm was optimized for the decoding of surface codes with distance d=5 and d=7 [ 25 ] . It operates by employing multiple threads to process syndrome information from different spacetime regions, which are combined to find a global minimum-weight perfect matching. Hereby, a greedy edge reweighting strategy accounts for Y-type error correlations and improves accuracy. Among the alternatives to the MWPM discussed in the literature, the UF ( UF ) decoder stands out as a prominent choice [ 27 , 28 ] . This decoder achieves an almost-linear worst-case runtime relative to the number of physical qubits. However, despite its ability to correct errors up to the code distance, the UF decoder is less accurate than the MWPM decoder [ 29 , 30 ] . The most time-consuming step of this decoding procedure is the syndrome validation phase. Specifically, the UF decoding begins by initializing clusters, each containing a single vertex representing an ancilla that has detected an error during the syndrome measurement, often referred to as defect. Finally, each cluster is processed in order to obtain a suitable matching. Alternative approaches are provided by the STM ( STM ) and RFire ( RFire ) decoders [ 31 ] . Specifically, we define the defect graph as a complete graph in which the vertices represent defects, and the edges are weighted based on the error probabilities of the qubits that lie between each pair of defects. In the case of i.i.d. ( i.i.d. ) data qubit errors, these weights are equivalent to the number of qubits separating the pair. It has been proven that, under a particular metric, all distinct matchings in the defect graph of a surface code are equivalent to the minimum-weight matching. Consequently, using this metric to identify errors ensures accurate correction up to the code minimum distance. Building on this, the algorithms compute a minimum spanning tree over the defect graph to identify an appropriate matching for localizing the errors. These decoders offer a notable improvement in decoding time compared to the standard LEMON implementation of the MWPM decoder, though it comes with some trade-off in performance. Finally, several promising developments in neural network-based decoders for surface codes have been reported. Specifically, an artificial neural network decoder designed for large surface code distances is introduced in [ 32 ] . A key advantage of this approach is its near-constant execution time as the code distance increases. Additionally, a neural network decoder for quantum surface codes, scalable to tens of thousands of qubits, has been proposed under depolarizing noise [ 33 ] . This method demonstrates improved error thresholds for depolarizing noise across various physical error rates, outperforming the standard union-find decoder. Moreover, in [ 34 ] , the authors propose a BP ( BP ) decoder for toric codes using overcomplete check matrices, and extend the neural BP decoder from suboptimal binary to quaternary BP decoding. As evidenced by the numerous proposals in the field, the pursuit of a fast decoder suitable for real-time decoding of surface codes remains a highly active research topic [ 26 , 27 , 28 , 29 , 30 , 31 , 35 , 36 , 37 , 38 , 39 ] . In this paper, we introduce the BC ( BC ) decoder for quantum topological codes. In particular, our decoder can be used to decode any topological code that is typically decoded using MWPM -based decoders. For the sake of clarity and exposition, we focus on