The union-find decoder is a leading algorithmic approach to the correction of quantum errors on the surface code, achieving code thresholds comparable to minimum-weight perfect matching (MWPM) with amortized computational time scaling near-linearly in the number of physical qubits. This complexity is achieved via optimizations provided by the disjoint-set data structure. We demonstrate, however, that the behavior of the decoder at scale underutilizes this data structure for twofold analytic and algorithmic reasons, and that improvements and simplifications can be made to architectural designs to reduce resource overhead in practice. To reinforce this, we model the behavior of erasure clusters formed by the decoder and show that there does not exist a percolation threshold within the data structure for any mode of operation. This yields a linear-time worst-case complexity for the decoder at scale, even with a naive implementation omitting popular optimizations. Published by the American Physical Society 2024
The union-find decoder is a leading algorithmic approach to the correction of quantum errors on the surface code, achieving code thresholds comparable to minimum-weight perfect matching (MWPM) with amortized computational time scaling near-linearly in the number of physical qubits. This complexity is achieved via optimizations provided by the disjoint-set data structure. We demonstrate, however, that the behavior of the decoder at scale underutilizes this data structure for twofold analytic and algorithmic reasons, and that improvements and simplifications can be made to architectural designs to reduce resource overhead in practice. To reinforce this, we model the behavior of erasure clusters formed by the decoder and show that there does not exist a percolation threshold within the data structure for any mode of operation. This yields a linear-time worst-case complexity for the decoder at scale, even with a naive implementation omitting popular optimizations. Published by the American Physical Society 2024
Efficient and accurate decoders are essential for quantum error correction. Surface codes are due to their high error threshold and scalability. The Minimum Weight Perfect Matching (MWPM) decoder and Union-Find (UF) decoder are the two most commonly used decoders for quantum surface codes, known for their accuracy and decoding speed, respectively. In this paper, we design an iteratively reweighted UF (IRUF) decoder considering the correlation of bit flip error and phase flip error in the depolarization noise channel. It has higher decoding accuracy than the MWPM decoder and UF decoder, and the decoding threshold is 11.5% and 6.3% higher respectively. Notably the IRUF decoder almost retains the same linear time complexity as the UF decoder, which is far better than the MWPM decoder.
Quantum error correction is needed for future quantum computers. Classical error correcting codes are not suitable for this due to the nature of quantum mechanics. Therefore, new codes need to be developed. A promising candidate is the toric code, a surface code, because of its locality and its high error correcting capability and thresholds (the error probability below which increasing the size of the code decreases the failure rate). This thesis provides an introduction to quantum error correction and the stabilizer formalism, which is used to introduce the toric code. Several decoders are looked at, including the Minimum Weight Perfect Matching (MWPM) decoder and a recently developed decoder, the Union-Find (UF) decoder. The UF decoder is useful because of its almost-linear time complexity, while only reducing the threshold by a marginal amount compared to the MWPM decoder. In this thesis, the time complexity of the weighted growth version of the UF decoder is analysed. The toric code and the decoders have been implemented and simulated, and the thresholds have been determined. For the MWPM decoder, the threshold was determined to be 11.5±0.2%, which is not in agreement with the threshold in literature of 10.3%, and should not be possible according to the optimal threshold of about 11%. This probably is a result of the low grid sizes (up to a gridsize of 11) of the code used due to the time needed to simulate the MWPM decoder. For the UF decoder, the threshold found was 9.7 ± 0.9%, which is in agreement with the threshold of 9.9% found by N. Delfosse and N. Nickerson. The time complexity of the UF decoder has also been determined, and is indeed almost-linear as expected by the analysis.
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 but is considered somewhat inferior, in terms of decoding accuracy. In this work we present an interpretation of UF decoders that explains why UF and MWPM decoders perform closely in some cases: the UF decoder is an approximate implementation of the blossom algorithm used for MWPM. This interpretation allows a generalization of UF decoders for weighted decoding graphs and explains why UF decoders achieve high accuracy for certain surface codes.
Quantum error correction (QEC) is considered essential for the development of scalable, fault-tolerant quantum computers in the medium- to long-term. By encoding quantum information across many physical qubits, carefully designed measurements can be taken to gain limited knowledge as to errors which may have occurred in the system, known as the error syndrome, with out causing quantum decoherence. In surface codes, qubits are arranged in a two-dimensional topological space, such as a torus or plane. In quantum low-density parity-check (qLDPC) codes, this is generalised to effectively arbitrary arrangements of qubits and syndrome checks. This work studies decoders: the algorithms responsible for inferring error correcting decisions from syndromes. In particular, the union–find decoder is studied in terms of its performance at scale. A simulation of a union–find decoding architecture is used to identify computational bottlenecks and pro pose improvements. In literature, it is assumed that the decoder runs in time scaling quadratically in the number of qubits under a naive implementation, but near-linearly when including two well-known optimisations. A key result is that, under independent and phenomenological noise models on surface codes, this complexity is strictly linear regardless of these optimisations. A supporting analytical argument is presented using percolation theory. Generalisation of the decoding problem to qLDPC codes is also studied, with approaches broadly relying on Gaussian elimination to find appropriate solutions. A strategy is proposed which uses a novel online variant of the Gaussian elimination algorithm to solve this linear system incrementally on growing local clusters, with accompanying complexity analysis and empir ical data demonstrating a reduction in runtime. An investigation into the use of metachecks is also presented, inspired by single-shot decoding, with implications for how such qLDPC decoders could be further improved.
Reliable large-scale quantum computation relies on fault-tolerant architectures, where quantum error correction (QEC) continuously extracts and decodes error syndromes in real time. A critical component in QEC is the decoder, a classical subsystem that must simultaneously deliver high logical accuracy and ultra-low latency. This paper presents a novel algorithm-hardware co-design that improves the accuracy-latency trade-off over existing approaches such as vanilla Minimum-Weight Perfect Matching (MWPM) and Union-Find (UF) decoders. At the algorithmic level, we introduce coset ensemble decoding, which improves UF decoding by explicitly exploiting logically equivalent cosets. Our method performs ensemble forest exploration to generate multiple coset-consistent candidates and aggregates them to approximate coset-level maximum-likelihood decoding. We further reduce computational and memory complexity via reverse-order elimination and lossless graph compression, without sacrificing accuracy. At the hardware level, we design a domain-specific architecture that temporally reuses resources, avoiding the code-distance-proportional resource growth in prior spatial architectures. Several optimizations, such as multi-bank memory hashing and hierarchical ID mapping, are proposed to mitigate pipeline stalls and memory conflicts under highly concurrent access patterns. Under a circuit-level depolarizing noise model, our co-design approach achieves a better accuracy-latency trade-off than prior MWPM- and UF-based decoders, while reducing FPGA LUT consumption by up to 8.2 times compared with reported UF-based decoder resources. The tunable candidate number further exposes a flexible design knob, enabling users to tailor decoding performance to the requirements of different fault-tolerant workloads. Our implementation is publicly available at https://github.com/IMSeonL/coset-ensemble-decoder.
Ising model-based Quantum Error Correction decoders reduce topological complexity compared to classical decoders. However, the SOTA Ising decoder has a higher time complexity than union-find (UF) and a lower threshold than minimum-weight perfect-matching (MWPM). We propose the Weighted Range-Constrained Ising Model-Based (WRIM) decoder. WRIM uses a polygonal region to enclose flipped syndromes, ensuring the coverage of all potential error chains while optimizing coupling and external field coefficients. WRIM reduces the variable count by 97.8x, achieves microsecondlevel decoding, and has a worst-case time complexity of O(n), outperforming UF. WRIM exhibits threshold behavior up to 10.711.0%, surpassing the MWPM’s highest reported threshold.