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

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)

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

Takuya Kasamura, Junichiro Kadomoto, Hidetsugu Irie

Published Nov 10, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/iccd65941.2025.00121

Related papers

Design of a Quantum Error Correction Decoder Exploiting Temporal Parallelism

Leo Itoh, Takuya Kasamura, Hidetsugu Irie +1 more

In the pursuit of fault-tolerant quantum computing, low-latency quantum error correction (QEC) is essential to prevent rapid error accumulation within the syndrome measurement cycle. In this work, we propose a microarchitecture that implements the sandwich decoding method using the Union-Find algorithm by exploiting temporal parallelism, and we present an ASIC implementation. Through logic synthesis and simulation, we show that the proposed decoder achieves an average latency reduction of 35% at code distance d = 21 compared with a conventional batch Union-Find decoder, while maintaining a comparable logical error threshold of approximately 1.5% under phenomenological noise.

quant-pharXiv:2607.27930•Jul 31, 2026•0 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

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

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. Using Xilinx's cycle-accurate simulator, we present cycle-accurate decoding time for$d$up to 15, with the phenomenological noise model with$p=0.1\%$. We are able to implement$d$up to 7 with a Xilinx ZC106 FPGA, for which an average decoding time is 120 ns per measurement round. 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 Symposium on Field-Programmable Custom Computing Machines (FCCM)•May 1, 2023•14 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

Coset Ensemble Decoder for Quantum Error Correction with Algorithm-Hardware Co-Design

Shuang Liang, Jubo Xu, Giulio Bassanino +8 more

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.

cs.ARCross-listedarXiv:2606.11076•Jun 10, 2026•0 citations
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.
In the pursuit of fault-tolerant quantum computing, low-latency quantum error correction (QEC) is essential to prevent rapid error accumulation within the syndrome measurement cycle. In this work, we propose a microarchitecture that implements the sandwich decoding method using the Union-Find algorithm by exploiting temporal parallelism, and we present an ASIC implementation. Through logic synthesis and simulation, we show that the proposed decoder achieves an average latency reduction of 35% at code distance d = 21 compared with a conventional batch Union-Find decoder, while maintaining a comparable logical error threshold of approximately 1.5% under phenomenological noise.
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.
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.
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(d3)O(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 has a sublinear average time complexity with regard toddd, givenO(d3)O(d^{3})O(d3)parallel 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. Using Xilinx's cycle-accurate simulator, we present cycle-accurate decoding time fordddup to 15, with the phenomenological noise model withp=0.1%p=0.1\%p=0.1%. We are able to implementdddup to 7 with a Xilinx ZC106 FPGA, for which an average decoding time is 120 ns per measurement round. Since the decoding time per measurement round of Helios decreases withddd, Helios can decode a surface code of arbitrarily largedddwithout a growing backlog.
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.
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.