DART-Q : A Deadline-Driven Framework for Real-Time QLDPC Decoding

This paper introduces DART-Q, a deadline-driven framework for real-time QLDPC decoding that models decoding as an online scheduling problem to demonstrate how state organization, admission control, and service capacity critically determine decoder viability under strict timing and memory constraints.

The Gist

Imagine you are running a high-speed emergency dispatch center for a futuristic quantum city. Every second, sensors (the quantum processor) send out thousands of tiny "distress signals" (errors) that need to be fixed immediately. If the fix isn't sent back within a strict time limit, the whole city's power grid could fail.

This paper introduces DART-Q, a new way of thinking about how to manage this emergency dispatch center. Instead of just asking, "Can we solve the puzzle?" (which is what most researchers do), DART-Q asks, "Can we solve the puzzle on time, without our desks getting so cluttered that we can't move?"

Here is the breakdown of the paper's findings using simple analogies:

1. The Problem: The "Too Many Emails" Crisis

In the past, scientists built "decoders" (the dispatchers) that were great at solving puzzles but didn't care about the clock or the mess on their desks.

• The Reality: In a real quantum computer, errors arrive in a continuous stream. Sometimes, a puzzle is hard and takes a long time to solve. If the dispatcher gets stuck on one hard puzzle, the next 100 emails pile up.
• The Result: Even if the dispatcher is fast on average, a few slow puzzles can cause a "traffic jam." By the time the dispatcher finally sends a fix, it's too late. The deadline has passed, and the fix is useless.

2. The Solution: DART-Q (The Traffic Cop)

The authors created a simulation framework called DART-Q. Think of it as a traffic cop for the dispatch center. It doesn't just solve puzzles; it manages the flow of work using three main tools:

• Deadlines: Every job has a "drop dead" time. If you can't finish by then, it's a failure.
• Queuing: Jobs wait in line. The cop decides who goes next (usually the one with the closest deadline).
• Admission Control: If the line gets too long, the cop stops letting new people in. It's better to say "no" to a new job than to let the whole system collapse.

3. Key Findings (The "Aha!" Moments)

The paper tested this system under four different scenarios, revealing some surprising truths:

A. The "Desk Space" Rule (SRAM Fit)

Imagine the dispatcher has a small desk (on-chip memory) and a huge filing cabinet in the basement (off-chip memory).

• The Old Way: Some dispatchers kept every single piece of paper on their desk, even if it meant the desk was overflowing. When the desk was full, they had to run to the basement for every piece of paper, which was slow.
• The New Way: The authors found that if you organize your notes better (using "cached summaries" instead of raw data), you can fit 4 times more work on the small desk.
• The Impact: As long as everything fits on the desk, the system is lightning fast. Once it spills over into the basement, the system slows down drastically. Lesson: Organizing your workspace is more important than just having a faster brain.

B. The "Rescue Team" Trap (Tail Latency)

Sometimes, a job gets stuck. The system has a "Rescue Policy" to try and save these stuck jobs.

• The Trap: If you send the rescue team to every stuck job, they get overwhelmed and clog up the line. It's like calling an ambulance for every minor scrape; soon, no ambulances are left for real emergencies.
• The Fix: The rescue team should only be called for the most critical, rare cases. If they are called too often, they actually make the system slower and cause more missed deadlines. Lesson: Be picky about when you ask for help.

C. The "Don't Let the Line Grow" Rule (Overload)

What happens when too many errors arrive at once?

• The Mistake: Many people think, "If we just let more jobs into the line, we'll get more done."
• The Reality: The paper showed that if you relax the rule and let the line grow huge, you don't get more useful work done. Instead, you just create a massive backlog. The system ends up with 20 times more work waiting and 17 times slower response times, but the number of successfully fixed errors barely changes.
• Lesson: It's better to cut off the line early than to let it grow into a monster that takes forever to clear.

D. The "More Dispatchers" Solution (Capacity Scaling)

If the line is still too long even after cutting off new jobs, what do you do?

• The Fix: You need more dispatchers. The study showed that simply doubling the number of decoder engines (dispatchers) working together was a game-changer.
• The Result: Going from 1 dispatcher to 2 reduced the number of missed deadlines from 97% down to less than 1%.
• Lesson: When the system is truly overwhelmed, no amount of "tweaking" or "rescuing" will help. You just need more hands on deck.

Summary

The paper argues that building a real-time quantum error correction system isn't just about making the decoder smarter. It's about managing the flow.

To keep a quantum computer running smoothly, you must:

1. Organize your memory so everything fits on the fast "desk."
2. Be strict about who gets into the line (don't let it get too long).
3. Be selective about when you use rescue policies (don't overuse them).
4. Add more workers if the load is too heavy for one team.

DART-Q is the tool that helps engineers figure out exactly when to do these things before they build the actual hardware.

Technical Summary

Technical Summary: DART-Q Framework for Real-Time QLDPC Decoding

Problem Statement
Fault-tolerant quantum computing relies on Quantum Error Correction (QEC) to preserve logical information, requiring classical decoders to operate within the fault-tolerant control loop. For Quantum Low-Density Parity-Check (QLDPC) codes, practical deployment depends not only on correction performance but also on the ability to decode under strict timing deadlines, finite on-chip memory, and time-varying workloads. Existing decoder research primarily focuses on correction performance, asymptotic complexity, or average runtime. These metrics fail to capture service-level failure modes in real-time settings, such as deadline misses, backlog growth, and long latency tails caused by hard instances or memory pressure. When decoding enters the feedback path, low latency becomes an operational requirement alongside correction quality; a late correction is effectively unavailable at the required control boundary.

Methodology: The DART-Q Framework
The authors present DART-Q, a discrete-event simulation framework designed to analyze real-time QLDPC decoding as a deadline-driven online service. Rather than modeling specific hardware cycles, DART-Q isolates the operational transitions and policy tradeoffs that shape timely decoding.

• Service Abstraction: The framework models windowed QLDPC decoding as a stream of jobs. Syndrome data is partitioned into fixed-duration windows, forming primary decode jobs ($J_i$) with arrival times ($a_i$), service requirements ($S_i$), and absolute deadlines ($d_i = a_i + \Delta$).
• Queueing and Scheduling: Jobs enter a queue managed by a non-preemptive Earliest Deadline First (EDF) scheduler. The system employs admission control with a backlog cap ($B_{max}$) to drop jobs when the queue is full, explicitly modeling the tradeoff between drops and deadline misses.
• Cost Models: DART-Q utilizes configurable cost models to map decoder characteristics to service time:
  • Traffic Model (TM): Quantifies memory traffic based on decoder state organization (e.g., edge-centric vs. cached summaries) and on-chip SRAM budget. It defines a "SRAM-fit boundary" where exceeding on-chip capacity forces off-chip accesses, increasing latency.
  • Workload Model (WM): Introduces variability in compute time based on syndrome weight or detector-event patterns.
  • Composite Hardware Model (CHM): Combines compute and memory components (using SUM or MAX rules) to determine total service time.
• Rescue Policies: The framework supports bounded auxiliary "rescue" jobs triggered by specific conditions (e.g., backlog thresholds, slack thresholds) to study limited recovery mechanisms under overload.

Key Contributions

1. Systems Framework: DART-Q provides a comparative analysis tool for real-time QLDPC decoding under finite memory and time-varying loads, treating decoding as a service with explicit metrics for misses, drops, and tail latency.
2. Service Abstraction: It casts decoding as a deadline-driven online service with arrivals, deadlines, queueing, and non-preemptive EDF scheduling, making deadline misses and queue growth explicit measures of viability.
3. Regime Analysis: The framework evaluates four specific regimes:
   • SRAM-Fit Transition: Analyzing how state organization affects memory footprint and the transition from on-chip to off-chip memory access.
   • Tail-Latency: Studying bounded mitigation policies (cutoffs and rescue) under heavy-tailed service variability.
   • Overload (QoS): Examining the tradeoff between admission control (backlog caps) and deadline misses.
   • Capacity Scaling: Investigating the impact of pooling multiple decoder instances.

Key Results

• State Organization: Switching from an edge-centric state organization to a cached-summary organization shifts the SRAM-fit boundary by a factor of 4× (e.g., from 2048 B to 512 B for BB72). This allows the decoder to fit entirely on-chip at smaller memory budgets, collapsing off-chip traffic and reducing service time.
• Tail Latency and Rescue: Under overload, rescue policies are highly sensitive to trigger selectivity. A "Cutoff only" policy yielded a MissRate of 48.44%. Adding a rescue policy triggered by backlog (18.49% trigger rate) increased MissRate to 57.30%. However, policies triggered by slack or cutoff-hit (activating ~98% of the time) degraded performance significantly, acting as persistent extra queue load rather than targeted recovery.
• Overload and Admission Control: Relaxing the backlog cap under bursty overload (increasing from 10 to 320 jobs) reduced the DropRate from 35.92% to 0%, but increased the MissRate from 95.85% to 97.64%. This resulted in a 20.1× increase in queued work and a 17.6× worsening of p99 latency (from 220 µs to 3.861 ms) with negligible gain in Goodput.
• Capacity Scaling: Doubling the decoder capacity (from 1 to 2 instances) in an overloaded regime reduced the MissRate from 97.64% to 0.98% and improved p99 latency from 3.861 ms to 100 µs. This indicates that at capacity-limited operating points, adding service capacity is far more effective than tuning admission or rescue policies.

Significance and Claims
The paper argues that the viability of real-time QLDPC decoders is governed not merely by correction performance or average runtime, but by state organization, rescue selectivity, admission control, and pooled service capacity.

The authors claim that DART-Q successfully exposes the "regime changes" that determine decoder viability. Specifically:

• Memory Fit: Decoder organization directly dictates the SRAM-fit boundary, which is a primary driver of timing variability.
• Policy Sensitivity: Bounded rescue mechanisms are only effective when triggers remain selective; indiscriminate rescue degrades performance.
• Capacity Limits: Under true overload, admission control shapes the type of failure (drops vs. misses) but cannot restore timely service. Only increasing service capacity (pooling) can recover viability in capacity-limited regimes.

The work supports a shift toward a "service view" of QLDPC decoding, where queueing, deadlines, and shared-resource limits are treated as first-order design constraints. The authors position DART-Q as a methodology for identifying these critical regime changes, with hardware realization (e.g., FPGA) suggested as a natural next step for validation.