Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.14745 · IEEE Journal on Selected Areas in Information Theory

Union-Intersection Union-Find for Decoding Depolarizing Errors in Topological Codes

Tzu‐Hao Lin, Ching–Yi Lai

Published Jan 1, 2025• 2 citations
arXivHTMLPDF

Abstract

In this paper, we introduce the Union-Intersection Union-Find (UIUF) algorithm for decoding depolarizing errors in topological codes, combining the strengths of iterative and standard Union-Find (UF) decoding. While iterative UF improves performance at moderate error rates, it lacks an error correction guarantee. To address this, we develop UIUF, which maintains the enhanced performance of iterative UF while ensuring error correction up to half the code distance. Through simulations under code capacity, phenomenological, and biased noise models, we show that UIUF significantly outperforms UF, reducing the logical error rate by over an order of magnitude (at around 10-5). Moreover, UIUF achieves lower logical error rates than the Minimum Weight Perfect Matching (MWPM) decoder on rotated surface codes under both the code capacity and phenomenological noise models, while preserving efficient linear-time complexity.

DOI
10.1109/jsait.2025.3581810

Related papers

High-performance and efficient decoding of surface codes: an iterative reweighted union-find approach

Yi Tian, Yi-Cong Zheng, Xiaoting Wang

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.

International Symposium on Advances in Electrical, Electronics and Computer Engineering (ISAEECE)•Oct 16, 2024•2 citations

An interpretation of Union-Find Decoder on Weighted Graphs

Yue Wu, Namitha Liyanage, Lin Zhong

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.

arXiv:2211.03288•Nov 7, 2022•10 citations

NNUF: Nearest Neighbor Union-Find Decoder for Quantum Error Correction

Yuhang Gu, Hui Li

The realization of fault-tolerant quantum computers is critically dependent on efficient and accurate quantum error correction. For topological codes such as the surface code, the decoder often becomes a performance bottleneck. This paper presents an optimized nearest-neighbor union-find decoder, named NNUF, a novel algorithm designed to accelerate the traditional union-find (UF) decoder. NNUF leverages pre-computed nearest-neighbor information to form preliminary error clusters, which streamlines the subsequent decoding stages. We evaluated NNUF against standard benchmarks and demonstrated that it reduces the decoding time while maintaining the high error correction performance of the original UF decoder. Specifically, for large code distances where $d \geq 7$, our results reveal a speedup of up to $1.14 \times$ compared to a standard UF implementation. This establishes NNUF as a valuable tool for quantum systems requiring fast and reliable decoding, representing a practical step towards real-time error correction in large-scale quantum processors.

Asian Hardware Oriented Security and Trust Symposium (AsianHOST)•Dec 19, 2025•1 citation

Neural ensemble decoding for topological quantum error-correcting codes

Milap Sheth, Sara Zafar Jafarzadeh, Vlad Gheorghiu

Topological quantum error-correcting codes are a promising candidate for building fault-tolerant quantum computers. Decoding topological codes optimally, however, is known to be a computationally hard problem. Various decoders have been proposed that achieve approximately optimal error thresholds. Due to practical constraints, it is not known if there exists an obvious choice for a decoder. In this paper, we introduce a framework which can combine arbitrary decoders for any given code to significantly reduce the logical error rates. We rely on the crucial observation that two different decoding techniques, while possibly having similar logical error rates, can perform differently on the same error syndrome. We classify each error syndrome to the decoder which is more likely to decode it correctly using machine learning techniques. We apply our framework to an ensemble of minimum-weight perfect matching (MWPM) and hard-decision re-normalization-group decoders for the surface code in the depolarizing noise model. Our simulations show an improvement of 38.4%, 14.6%, and 7.1% over the pseudothreshold of MWPM in the instance of distance 5, 7, and 9 codes, respectively. Lastly, we discuss the advantages and limitations of our framework and applicability to other error-correcting codes. Our framework can provide a significant boost to error correction by combining the strengths of various decoders. In particular, it may allow for combining very fast decoders with moderate error-correcting capability to create a very fast ensemble decoder with high error-correcting capability.

arXiv:1905.02345•Physical Review A•Mar 23, 2020•25 citations

Proof of a finite threshold for the union-find decoder

Satoshi Yoshida, Ethan Lake, Hayata Yamasaki

Fast decoders that achieve strong error suppression are essential for fault-tolerant quantum computation (FTQC) from both practical and theoretical perspectives. The union-find (UF) decoder for the surface code is widely regarded as a promising candidate, offering almost-linear time complexity and favorable empirical error suppression supported by numerical evidence. However, the lack of a rigorous threshold theorem has left open whether the UF decoder can achieve fault tolerance beyond the error models and parameter regimes tested in numerical simulations. Here, we provide a rigorous proof of a finite threshold for the UF decoder on the surface code under the circuit-level local stochastic error model. To this end, we develop a refined error-clustering framework that extends techniques previously used to analyze cellular-automaton and renormalization-group decoders, by showing that error clusters can be separated by substantially larger buffers, thereby enabling analytical control over the behavior of the UF decoder. Using this guarantee, we further prove a quasi-polylogarithmic upper bound on the average runtime of a parallel UF decoder in terms of the code size. We also show that this framework yields a finite threshold for the greedy decoder, a simpler decoder with lower complexity but weaker empirical error suppression. These results provide a solid theoretical foundation for the practical use of UF-based decoders in the development of fault-tolerant quantum computers, while offering a unified framework for studying fault tolerance across these practical decoders.

quant-pharXiv:2602.20238•Feb 25, 2026•0 citations

Fault-Tolerant Hybrid Decoder for Quantum Surface Codes on Probabilistic Inference and Topological Clustering

Xingyu Qiao, Xiaomei Xu, Hongyang Ma +1 more

Quantum error correction is a prerequisite for quantum computing; however, the performance critically depends on the accuracy of the decoding algorithm. To address these challenges, we propose a hybrid decoding architecture, BP + UF + BP. The protocol initiates with a truncated global BP stage to extract probabilistic gradients without requiring full convergence. This soft information guides a reliability-based Union-Find (UF) algorithm to prioritize high-likelihood error mechanisms. Finally, a local subgraph BP refinement maximizes correction accuracy. Numerical simulations on rotated surface codes under circuit-level depolarizing noise demonstrate a fault-tolerance threshold of approximately 0.72%. This significantly outperforms standard Minimum Weight Perfect Matching (MWPM) and Union-Find (UF) baselines. Notably, our method significantly reduces the logical error rate compared to the conventional decoders. With its empirically near-linear scaling under fixed iteration, the proposed architecture presents a scalable solution for real-time fault-tolerant quantum computing.

Applied Sciences•Mar 8, 2026•0 citations
In this paper, we introduce the Union-Intersection Union-Find (UIUF) algorithm for decoding depolarizing errors in topological codes, combining the strengths of iterative and standard Union-Find (UF) decoding. While iterative UF improves performance at moderate error rates, it lacks an error correction guarantee. To address this, we develop UIUF, which maintains the enhanced performance of iterative UF while ensuring error correction up to half the code distance. Through simulations under code capacity, phenomenological, and biased noise models, we show that UIUF significantly outperforms UF, reducing the logical error rate by over an order of magnitude (at around 10-5). Moreover, UIUF achieves lower logical error rates than the Minimum Weight Perfect Matching (MWPM) decoder on rotated surface codes under both the code capacity and phenomenological noise models, while preserving efficient linear-time complexity.
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.
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.
The realization of fault-tolerant quantum computers is critically dependent on efficient and accurate quantum error correction. For topological codes such as the surface code, the decoder often becomes a performance bottleneck. This paper presents an optimized nearest-neighbor union-find decoder, named NNUF, a novel algorithm designed to accelerate the traditional union-find (UF) decoder. NNUF leverages pre-computed nearest-neighbor information to form preliminary error clusters, which streamlines the subsequent decoding stages. We evaluated NNUF against standard benchmarks and demonstrated that it reduces the decoding time while maintaining the high error correction performance of the original UF decoder. Specifically, for large code distances where d≥7d \geq 7d≥7, our results reveal a speedup of up to 1.14×1.14 \times1.14× compared to a standard UF implementation. This establishes NNUF as a valuable tool for quantum systems requiring fast and reliable decoding, representing a practical step towards real-time error correction in large-scale quantum processors.
Topological quantum error-correcting codes are a promising candidate for building fault-tolerant quantum computers. Decoding topological codes optimally, however, is known to be a computationally hard problem. Various decoders have been proposed that achieve approximately optimal error thresholds. Due to practical constraints, it is not known if there exists an obvious choice for a decoder. In this paper, we introduce a framework which can combine arbitrary decoders for any given code to significantly reduce the logical error rates. We rely on the crucial observation that two different decoding techniques, while possibly having similar logical error rates, can perform differently on the same error syndrome. We classify each error syndrome to the decoder which is more likely to decode it correctly using machine learning techniques. We apply our framework to an ensemble of minimum-weight perfect matching (MWPM) and hard-decision re-normalization-group decoders for the surface code in the depolarizing noise model. Our simulations show an improvement of 38.4%, 14.6%, and 7.1% over the pseudothreshold of MWPM in the instance of distance 5, 7, and 9 codes, respectively. Lastly, we discuss the advantages and limitations of our framework and applicability to other error-correcting codes. Our framework can provide a significant boost to error correction by combining the strengths of various decoders. In particular, it may allow for combining very fast decoders with moderate error-correcting capability to create a very fast ensemble decoder with high error-correcting capability.
Fast decoders that achieve strong error suppression are essential for fault-tolerant quantum computation (FTQC) from both practical and theoretical perspectives. The union-find (UF) decoder for the surface code is widely regarded as a promising candidate, offering almost-linear time complexity and favorable empirical error suppression supported by numerical evidence. However, the lack of a rigorous threshold theorem has left open whether the UF decoder can achieve fault tolerance beyond the error models and parameter regimes tested in numerical simulations. Here, we provide a rigorous proof of a finite threshold for the UF decoder on the surface code under the circuit-level local stochastic error model. To this end, we develop a refined error-clustering framework that extends techniques previously used to analyze cellular-automaton and renormalization-group decoders, by showing that error clusters can be separated by substantially larger buffers, thereby enabling analytical control over the behavior of the UF decoder. Using this guarantee, we further prove a quasi-polylogarithmic upper bound on the average runtime of a parallel UF decoder in terms of the code size. We also show that this framework yields a finite threshold for the greedy decoder, a simpler decoder with lower complexity but weaker empirical error suppression. These results provide a solid theoretical foundation for the practical use of UF-based decoders in the development of fault-tolerant quantum computers, while offering a unified framework for studying fault tolerance across these practical decoders.
Quantum error correction is a prerequisite for quantum computing; however, the performance critically depends on the accuracy of the decoding algorithm. To address these challenges, we propose a hybrid decoding architecture, BP + UF + BP. The protocol initiates with a truncated global BP stage to extract probabilistic gradients without requiring full convergence. This soft information guides a reliability-based Union-Find (UF) algorithm to prioritize high-likelihood error mechanisms. Finally, a local subgraph BP refinement maximizes correction accuracy. Numerical simulations on rotated surface codes under circuit-level depolarizing noise demonstrate a fault-tolerance threshold of approximately 0.72%. This significantly outperforms standard Minimum Weight Perfect Matching (MWPM) and Union-Find (UF) baselines. Notably, our method significantly reduces the logical error rate compared to the conventional decoders. With its empirically near-linear scaling under fixed iteration, the proposed architecture presents a scalable solution for real-time fault-tolerant quantum computing.