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:2602.20238

Proof of a finite threshold for the union-find decoder

Satoshi Yoshida, Ethan Lake, Hayata Yamasaki

quant-phSubmitted Feb 23, 2026• Announced Feb 25, 2026• 0 citations• Revised May 6, 2026 (v2)
v1 · Feb 23, 2026v2 · May 6, 2026
arXivHTMLPDF

Abstract

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.

Comments
20 pages, 6 figures

Related papers

Design of an Online Surface Code Decoder Using Union-Find Algorithm

Takuya Kasamura, Junichiro Kadomoto, Hidetsugu Irie

Real-time Quantum Error Correction (QEC) for Fault-Tolerant Quantum Computing (FTQC) demands immediate surface code decoding with both high accuracy and low latency. The highly accurate Union-Find (UF) algorithm has traditionally been limited to batch-processing, as its iterative cluster growth is incompatible with the concurrent initiation of decoding with each syndrome measurement round, required for real-time QEC. This research presents a novel online UF decoder microarchitecture designed to overcome these limitations. Our key innovation decomposes UF cluster growth into incremental, per-cycle steps managed by a dedicated SHIFT stage. ASIC evaluation of our implementation demonstrates a$\mathbf{1 0 2. 3 8}$ns latency for a surface code with a distance of 23 and an approximate 1.4% threshold, meeting critical QEC performance targets. By demonstrating a viable online UF decoder with competitive performance, this research offers a crucial building block for the practical realization of scalable FTQC.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Nov 10, 2025•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

Probing Threshold Behavior of Adaptive Cascaded Quantum Codes Under Variable Biased Noise for Practical Fault-Tolerant Quantum Computing

Yongnan Chen, Zaixu Fan, Haopeng Wang +2 more

This paper proposes a resource optimized cascaded quantum surface repetition code architecture integrated with a Union Find (UF) enhanced hybrid decoder, which suppresses biased noise and improves the scalability of quantum error correction through synergistic inner outer quantum code collaboration. The hybrid architecture employs inner quantum repetition codes for local error suppression and outer rotated quantum surface codes for topological robustness, reducing auxiliary quantum qubits by 12.5% via shared stabilizers and compact lattice embedding. An optimized UF decoder employing path compression and adaptive cluster merging achieves near-linear time complexity O(nα(n)), outperforming minimum-weight perfect matching (MWPM) decoders O(n2.5). Under Z-biased noise η=10, simulations demonstrate a 28.2% error threshold, 2.6% higher than standard quantum surface codes, and 15% lower logical error rates via dynamic boundary expansion. At code distance d=7, resource savings reach 9.3% with maximum relative error below 8.5%, fulfilling fault-tolerance criteria. The UF decoder exhibits 38% threshold advantage over MWPM at low bias η≈10−3 and 15% less degradation at high noise p=0.5, enabling scalable real-time decoding. This framework bridges theoretical thresholds with practical resource constraints, offering a noise-adaptive QEC solution for near-term quantum devices including photonic quantum systems referenced in the paper’s background on repetition cat qubits.

Electronics•Jan 19, 2026•0 citations

Fault-tolerant weighted union-find decoding on the toric code

Shilin Huang, Michael Newman, Kenneth R. Brown

Quantum error correction requires decoders that are both accurate and efficient. To this end, union-find decoding has emerged as a promising candidate for error correction on the surface code. In this work, we benchmark a weighted variant of the union-find decoder on the toric code under circuit-level depolarizing noise. This variant preserves the almost-linear time complexity of the original while significantly increasing the performance in the fault-tolerance setting. In this noise model, weighting the union-find decoder increases the threshold from $0.38%$ to $0.62%$, compared to an increase from $0.65%$ to $0.72%$ when weighting a matching decoder. Further assuming quantum nondemolition measurements, weighted union-find decoding achieves a threshold of $0.76%$ compared to the $0.90%$ threshold when matching. We additionally provide comparisons of timing as well as low error rate behavior.

arXiv:2004.04693•Physical Review A•Jul 16, 2020•56 citations

Scalable Quantum Error Correction for Surface Codes Using FPGA

Namitha Liyanage, Yue Wu, Alexander Deters +1 more

A fault-tolerant quantum computer must decode and correct errors faster than they appear. The faster errors can be corrected, the more time the computer can do useful work. The Union-Find (UF) decoder is promising with an average time complexity slightly higher than$O(d^{3}$. We report a distributed version of the UF decoder that exploits parallel computing resources for further speedup. Using an FPGA-based implementation, we empirically show that this distributed UF decoder has$a$sublinear average time complexity with regard to$d$given$O(d^{3}$parallel computing resources. The decoding time per measurement round decreases as$d$increases, a first time for a quantum error decoder. The implementation employs a scalable architecture called Helios that organizes parallel computing resources into a hybrid tree-grid structure. We are able to implement$d$up to 21 with a Xilinx VCU129 FPGA, for which an average decoding time is 11.5 ns per measurement round under phenomenological noise of 0.1 %, significantly faster than any existing decoder implementation. Since the decoding time per measurement round of Helios decreases with d, Helios can decode a surface code of arbitrarily large$d$without a growing backlog.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•34 citations

Even More Efficient Soft-Output Decoding with Extra-Cluster Growth and Early Stopping

Kaito Kishi, Riki Toshio, Jun Fujisaki +3 more

In fault-tolerant quantum computing, soft outputs from real-time decoders play a crucial role in improving decoding accuracy, post-selecting magic states, and accelerating lattice surgery. A recent paper by Meister et al. [arXiv:2405.07433 (2024)] proposed an efficient method to evaluate soft outputs for cluster-based decoders, including the Union-Find (UF) decoder. However, in parallel computing environments, its computational complexity is comparable to or even surpasses that of the UF decoder itself, resulting in a substantial overhead. Furthermore, this method requires global information about the decoding graph, making it poorly suited for existing hardware implementations of the UF decoder on Field-Programmable Gate Arrays (FPGAs). In this paper, to alleviate these issues, we develop more efficient methods for evaluating high-quality soft outputs in cluster-based decoders by introducing several early-stopping techniques. Our central idea is that the precise value of a large soft output is often unnecessary in practice. Based on this insight, we introduce two types of novel soft-outputs: the bounded cluster gap and the extra-cluster gap. The former reduces the computational complexity of Meister's method by terminating the calculation at an early stage. Our numerical simulations show that this method achieves improved scaling with code distance $d$ compared to the original proposal. The latter, the extra-cluster gap, quantifies decoder reliability by performing a small, additional growth of the clusters obtained by the decoder. This approach offers the significant advantage of enabling soft-output computation without modifying the existing architecture of FPGA-implemented UF decoders. These techniques offer lower computational complexity and higher hardware compatibility, laying a crucial foundation for future real-time decoders with soft outputs.

quant-pharXiv:2602.03336•Feb 4, 2026•0 citations
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.
Real-time Quantum Error Correction (QEC) for Fault-Tolerant Quantum Computing (FTQC) demands immediate surface code decoding with both high accuracy and low latency. The highly accurate Union-Find (UF) algorithm has traditionally been limited to batch-processing, as its iterative cluster growth is incompatible with the concurrent initiation of decoding with each syndrome measurement round, required for real-time QEC. This research presents a novel online UF decoder microarchitecture designed to overcome these limitations. Our key innovation decomposes UF cluster growth into incremental, per-cycle steps managed by a dedicated SHIFT stage. ASIC evaluation of our implementation demonstrates a102.38\mathbf{1 0 2. 3 8}102.38ns latency for a surface code with a distance of 23 and an approximate 1.4% threshold, meeting critical QEC performance targets. By demonstrating a viable online UF decoder with competitive performance, this research offers a crucial building block for the practical realization of scalable FTQC.
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.
This paper proposes a resource optimized cascaded quantum surface repetition code architecture integrated with a Union Find (UF) enhanced hybrid decoder, which suppresses biased noise and improves the scalability of quantum error correction through synergistic inner outer quantum code collaboration. The hybrid architecture employs inner quantum repetition codes for local error suppression and outer rotated quantum surface codes for topological robustness, reducing auxiliary quantum qubits by 12.5% via shared stabilizers and compact lattice embedding. An optimized UF decoder employing path compression and adaptive cluster merging achieves near-linear time complexity O(nα(n)), outperforming minimum-weight perfect matching (MWPM) decoders O(n2.5). Under Z-biased noise η=10, simulations demonstrate a 28.2% error threshold, 2.6% higher than standard quantum surface codes, and 15% lower logical error rates via dynamic boundary expansion. At code distance d=7, resource savings reach 9.3% with maximum relative error below 8.5%, fulfilling fault-tolerance criteria. The UF decoder exhibits 38% threshold advantage over MWPM at low bias η≈10−3 and 15% less degradation at high noise p=0.5, enabling scalable real-time decoding. This framework bridges theoretical thresholds with practical resource constraints, offering a noise-adaptive QEC solution for near-term quantum devices including photonic quantum systems referenced in the paper’s background on repetition cat qubits.
Quantum error correction requires decoders that are both accurate and efficient. To this end, union-find decoding has emerged as a promising candidate for error correction on the surface code. In this work, we benchmark a weighted variant of the union-find decoder on the toric code under circuit-level depolarizing noise. This variant preserves the almost-linear time complexity of the original while significantly increasing the performance in the fault-tolerance setting. In this noise model, weighting the union-find decoder increases the threshold from 0.380.38%0.38 to 0.620.62%0.62, compared to an increase from 0.650.65%0.65 to 0.720.72%0.72 when weighting a matching decoder. Further assuming quantum nondemolition measurements, weighted union-find decoding achieves a threshold of 0.760.76%0.76 compared to the 0.900.90%0.90 threshold when matching. We additionally provide comparisons of timing as well as low error rate behavior.
A fault-tolerant quantum computer must decode and correct errors faster than they appear. The faster errors can be corrected, the more time the computer can do useful work. The Union-Find (UF) decoder is promising with an average time complexity slightly higher thanO(d3O(d^{3}O(d3. We report a distributed version of the UF decoder that exploits parallel computing resources for further speedup. Using an FPGA-based implementation, we empirically show that this distributed UF decoder hasaaasublinear average time complexity with regard todddgivenO(d3O(d^{3}O(d3parallel computing resources. The decoding time per measurement round decreases asdddincreases, a first time for a quantum error decoder. The implementation employs a scalable architecture called Helios that organizes parallel computing resources into a hybrid tree-grid structure. We are able to implementdddup to 21 with a Xilinx VCU129 FPGA, for which an average decoding time is 11.5 ns per measurement round under phenomenological noise of 0.1 %, significantly faster than any existing decoder implementation. Since the decoding time per measurement round of Helios decreases with d, Helios can decode a surface code of arbitrarily largedddwithout a growing backlog.
In fault-tolerant quantum computing, soft outputs from real-time decoders play a crucial role in improving decoding accuracy, post-selecting magic states, and accelerating lattice surgery. A recent paper by Meister et al. [arXiv:2405.07433 (2024)] proposed an efficient method to evaluate soft outputs for cluster-based decoders, including the Union-Find (UF) decoder. However, in parallel computing environments, its computational complexity is comparable to or even surpasses that of the UF decoder itself, resulting in a substantial overhead. Furthermore, this method requires global information about the decoding graph, making it poorly suited for existing hardware implementations of the UF decoder on Field-Programmable Gate Arrays (FPGAs). In this paper, to alleviate these issues, we develop more efficient methods for evaluating high-quality soft outputs in cluster-based decoders by introducing several early-stopping techniques. Our central idea is that the precise value of a large soft output is often unnecessary in practice. Based on this insight, we introduce two types of novel soft-outputs: the bounded cluster gap and the extra-cluster gap. The former reduces the computational complexity of Meister's method by terminating the calculation at an early stage. Our numerical simulations show that this method achieves improved scaling with code distance ddd compared to the original proposal. The latter, the extra-cluster gap, quantifies decoder reliability by performing a small, additional growth of the clusters obtained by the decoder. This approach offers the significant advantage of enabling soft-output computation without modifying the existing architecture of FPGA-implemented UF decoders. These techniques offer lower computational complexity and higher hardware compatibility, laying a crucial foundation for future real-time decoders with soft outputs.