Constraint-Optimal Driven Allocation for Scalable QEC Decoder Scheduling

Dongmin Kim, Jeonggeun Seo, and Youngsun Han, Yongtae Kim · 2025

Read Constraint-Optimal Driven Allocation for Scalable QEC Decoder Scheduling by Dongmin Kim, Jeonggeun Seo, and Youngsun Han, Yongtae Kim (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-2512-02539.txt.

Introduction

Dongmin Kim and co-authors tackle a bottleneck in fault tolerant quantum computing: too few decoders. Quantum error correction produces a stream of syndrome data that decoders have to read fast and well. In large systems, logical qubits far outnumber the decoders on hand, so scheduling becomes a core problem.

Their constraint optimal approach allocates decoder time where it helps most, under strict limits. Good allocation keeps errors from piling up while hardware stays scarce. As quantum machines grow, smart sharing of decoding power may matter as much as the decoders themselves for keeping computations reliable. More qubits will need this kind of smart time share if they are to work as one machine at all.

Catalog record

CREATORDongmin Kim, Jeonggeun Seo, and Youngsun Han, Yongtae Kim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02539

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constraint-Optimal Driven Allocation for Scalable QEC Decoder Scheduling Preprint: APS/123-QED Dongmin Kim, Jeonggeun Seo, and Youngsun Han, Yongtae Kim Abstract Fault-tolerant quantum computing (FTQC) requires fast and accurate decoding of Quantum Error Correction (QEC) syndromes. However, in large-scale systems, the number of available decoders is much smaller than the number of logical qubits, leading to a fundamental resource shortage. To address this limitation, Virtualized Quantum Decoder (VQD) architectures have been proposed to share a limited pool of decoders across multiple qubits. While the Minimize Longest Undecoded Sequence (MLS) heuristic has been introduced as an effective scheduling policy within the VQD framework, its locally greedy decision-making structure limits its ability to consider global circuit structure, causing inefficiencies in resource balancing and limited scalability. In this work, we propose Constraint-Optimal Driven Allocation (CODA), an optimization-based scheduling algorithm that leverages global circuit structure to minimize the longest undecoded sequence length. Across 19 benchmark circuits, CODA achieves an average 74% reduction in the longest undecoded sequence length. Crucially, while the theoretical search space scales exponentially with circuit size, CODA effectively bypasses this combinatorial explosion. Our evaluation confirms that the scheduling time scales linearly with the number of qubits, determined by physical resource constraints rather than the combinatorial search space, ensuring robust scalability for large-scale FTQC systems. These results demonstrate that CODA provides a global optimization-based, scalable scheduling solution that enables efficient decoder virtualization in large-scale FTQC systems. I Introduction Quantum computing has attracted significant attention from both academia and industry due to its potential to provide computational advantages in problems such as integer factorization 57 ; 21 , unstructured search 35 ; 6 , and complex quantum simulations 45 ; 30 . Recent advances in superconducting, trapped-ion, and photonic hardware platforms, along with increasingly sophisticated fabrication techniques, have enabled the execution of small to medium-scale quantum circuits 2 ; 9 ; 63 ; 25 ; 12 . However, due to the intrinsic fragility of quantum states, these systems remain fundamentally vulnerable to noise and errors, and are therefore referred to as belonging to the Noisy Intermediate-Scale Quantum (NISQ) era 52 ; 3 . To achieve practical quantum advantage, it is essential to scale beyond NISQ devices toward large-scale Fault-Tolerant Quantum Computing (FTQC) systems with thousands of high-fidelity qubits and deep circuit depths 27 ; 13 ; 42 . As FTQC systems scale, the increasing number of qubits and circuit depth amplify the impact of noise and hardware imperfections, leading to rapid error accumulation 28 ; 41 . Specifically, decoherence, gate infidelity, and crosstalk fundamentally limit the reliability and scalability of current quantum processors 55 ; 41 . To mitigate these issues, FTQC employs Quantum Error Correction (QEC), which encodes logical information into multiple physical qubits and continuously measures error syndromes to suppress logical error rates below a target threshold 34 ; 27 . The task of interpreting these error syndromes and determining appropriate correction operations is carried out by the QEC decoder. Depending on the underlying decoding algorithm, the QEC decoder serves as a critical component that directly affects the performance and stability of the entire FTQC system 27 ; 20 ; 14 ; 32 . In large-scale FTQC systems, decoders which is a critical component that determines error correction performance, pose a major scalability constraint on the expansion of large-scale quantum systems. This is because physical limitations in power, memory bandwidth, interconnect, and chip area make it practically infeasible to assign a dedicated decoder to each logical qubit 13 ; 17 ; 26 ; 22 . As a result, the number of available decoders is smaller than the number of logical qubits, leading to a structural resource imbalance that serves as a fundamental bottleneck in the scalability of FTQC systems. To address this imbalance, limited decoder resources inevitably be shared among multiple qubits over time. Prior work proposed an architectural approach based on Virtualized Quantum Decoder (VQD) architectures to overcome the imbalance problem 17 ; 14 ; 47 . VQD combines a small number of decoders into a shared pool and allows multiple logical qubits to use them in a time-multiplexed manner, thereby improving the efficiency of limited decoder resources usage. This concept is analogous to time-multiplexing in classical computing systems 43 . In addition to the VQD architecture, several scheduling algorithms have been proposed, including Most-Frequent Decoder (MFD), Round-Robin (RR), and Minimize Longest Undecoded Sequence (MLS) 17 . These algorithms are all based on local heuristics and therefore fail to anticipate future decoding demands required by the global circuit structure. Among them, MLS provides good short-term performance by prioritizing the qubits that have accumulated the longest backlog of undecoded syndromes (i.e., the longest undecoded sequence), but its reliance on local heuristics prevents it from considering global workload distribution and achieving an optimal solution. In addition, the extra computational overhead required for calculating priorities introduces scalability limitations that become increasingly exacerbated as circuit size grows. To overcome the limitations of existing scheduling algorithms, we propose Constraint-Optimal Driven Allocation (CODA), a global optimization-based decoder scheduling algorithm for FTQC systems. Specifically, the CODA minimizes the longest undecoded sequence length across all qubits by jointly considering global circuit structure, which captures the temporal and spatial distribution of decoder requests, and hardware resource constraints. This approach achieves shorter longest undecoded sequence lengths by balancing decoder resource usage, while ensuring better scalability compared to existing heuristic approaches. We integrate the CODA algorithm into an existing Python-based decoder scheduling simulator and evaluate it alongside RR and MLS under identical conditions. Across 19 benchmarks comprising representative quantum programs, CODA achieves a 74% reduction on average in the longest undecoded sequence length and demonstrates robust scalability by overcoming theoretical exponential complexity, ensuring practical scheduling times even at larger circuit scales. These results demonstrate that CODA goes beyond the performance limitations of existing heuristics and provides a scalable, global optimization-based scheduling solution under resource constraints, effectively enhancing the stability and scalability of FTQC systems. The main contributions of this paper are summarized as follows: • Mathematical modeling of scalable decoding: We analyze the computational hardness of the decoder scheduling problem and reformulate it into a sequence of feasibility decision problems to enable efficient solution finding. • CODA algorithm: We design a constraint optimization–based scheduling algorithm that incorporates resource and decoding priority constraints, and provides a scalable, global optimization-based scheduling solution. • Experimental validation: We demonstrate that CODA significantly reduces the longest undecoded sequence lengths compared to state-of-the-art heuristics while maintaining linear scalability with respect to circuit size. The rest of this paper is organized as follows. Section II reviews the background of FTQC, QEC decoding, the scalability challenges, and the motivation of this work. Section III presents the overall process of the CODA scheduler and describes its algorithm. Section IV describes the experimental setup and provides evaluation results compared with RR and MLS. Finally, Section V concludes the paper. Additional details and extended discussions are provided in the Appendix. II Background In this section, we provide the technical background on FTQC, specifically focusing on the critical role of QEC decoding. We then analyze the scalability constraints imposed by limited decoder resources in large-scale systems, identifying the fundamental bottlenecks that motivate our proposed constraint-optimal scheduling approach. II.1 FTQC and QEC Decoding Realizing large-scale

Read the complete text