Do Not Let CNOTs Overwhelm the Decoder: Scheduling Transversal Gates for Fast FTQC

AI summary

Overview

Research area: Fault-tolerant quantum computing (FTQC) — specifically the interaction between quantum instruction scheduling (transversal CNOT gates on surface codes) and the classical real-time decoding pipeline.

Technical level: Advanced. The paper assumes familiarity with surface codes, syndrome extraction, detector error models, and matching-based decoding. The prose here explains the ideas in plainer terms, but the underlying subject is specialized.

Scope: This paper proposes PACE, a decoder-aware framework that schedules transversal CNOT (TCNOT) gates as densely as a classical decoder can sustain, using three decoder-side techniques to reduce decoding cost.

What This Paper Is About

Transversal CNOT gates can cut the number of syndrome-extraction rounds between logical operations in the surface code from O(d) to O(1), which is attractive for platforms with long-range connectivity such as neutral-atom arrays. But dense TCNOT scheduling makes the classical decoding problem much harder: errors become correlated across multiple surface-code patches, decoding windows grow, and the detector error model of each window depends on the schedule, so it cannot all be precompiled. The paper's goal is to schedule TCNOTs as aggressively as possible while keeping the classical decoder within its latency and memory limits.

Key Contributions

1. Identification of three decoder-side bottlenecks caused by aggressive TCNOT scheduling: (i) correlated-unmatchable decoding cost, (ii) the growing diversity of DEM patterns, and (iii) decoding volume growth.

2. Three decoder-side mitigation techniques:

   • Hybrid Window Decoding — assigns a matchable decoder (e.g., PyMatching) to windows whose DEM is graphlike and an unmatchable decoder (e.g., BP-LSD) only where hyperedges actually appear, with a "window-wise correction" step that converts either decoder's estimate into a common logical Pauli-frame update and residual detection-event state.
   • DEM Stitch — a template-based just-in-time DEM compiler that precompiles recurring local circuit blocks (initialization, measurement, idle, logical Clifford operations including TCNOT) offline and stitches them online via index remapping, logical-observable propagation, and resolution of "temporal ports."
   • Sub-window Parallel Decoding (SPD) — decomposes a large decoding window into smaller variable-height sub-windows using a short-edge/long-edge event graph, then assigns parallel decoding layers by graph coloring of a conflict graph.

3. A decoder-aware TCNOT scheduler that searches a bounded family of spacing policies (every p-th inter-TCNOT gap on each logical-qubit timeline is forced to be d rounds apart, others use dependency-minimum spacing), greedily builds an earliest-start schedule for each, and keeps the shortest candidate whose every window satisfies the decoder feasibility constraints.

4. A generic decoder feasibility model expressing DEM-preparation latency, decoder working memory, and decoding latency as power-law functions of a "decoding volume" V = q·w/W, then specialized into three per-window constraints (Eq. 4) that PACE enforces.

Main Findings

• TCNOTs dominate the instruction stream: across the benchmark circuits in the paper's Table 2, TCNOTs account for 40–55% of all primitive quantum instructions, because S and T gates are implemented by magic-state teleportation, which itself introduces TCNOTs.

• Most windows do not actually need a slow decoder: many decoding windows in TCNOT-containing workloads remain graphlike, so a matchable decoder suffices — the key observation motivating Hybrid Window Decoding.

• DEM compilation is far slower than syndrome extraction: DEM construction with Stim takes tens to hundreds of milliseconds, versus a typical syndrome-extraction period of about 1 ms on neutral-atom platforms.

• Exhaustive DEM precompilation is infeasible: a window spanning O(d) syndrome-extraction rounds contains O(d) candidate TCNOT slots at O(1)-round intervals, so the number of distinct window-level DEMs grows exponentially with code distance d, and each DEM has a non-negligible memory footprint.

• Aggressive scheduling inflates the decoding volume: TCNOTs propagate errors across patches, so a single physical fault can flip more than two detectors, creating hyperedges and a non-graphlike DEM; multiple TCNOTs inside one window enlarge the region that must be decoded jointly, potentially exceeding decoder memory and real-time throughput.

• The conservative baseline gives up speed: separating consecutive TCNOTs by d syndrome-extraction rounds (as in Sahay et al.) bounds decoding volume but sacrifices much of the quantum-side speedup; in PACE's policy family this corresponds to p = 1, while p → ∞ gives the dependency-limited ASAP schedule.

• Evaluation results: the paper states that Section 6 and 7 present decoder evaluations, DEM-construction experiments, and benchmark circuits showing reduced quantum execution time under decoder constraints. The specific quantitative results from those sections are not present in the content available here and are therefore not reported in this summary.

Methodology in Plain English

The authors start by observing that the classical decoder, not the quantum hardware, becomes the limiting factor once you pack transversal CNOTs tightly together. They break that limit into three concrete costs — correlated (hard-to-decode) errors, the need to build a fresh error model for each window, and sheer decoding volume — and then attack each one separately.

To cut correlated-error cost, they check each decoding window individually: if it happens to be graphlike, a fast matcher is used; only genuinely non-graphlike windows go to a heavier correlated decoder. They add a bookkeeping step so that mixing decoder types across windows does not break the sliding-window chain.

To cut error-model construction cost, they precompute reusable pieces of error model offline (one per small repeating circuit block) and assemble window-level models at runtime by remapping indices and connecting the pieces, rather than compiling each window from the full circuit.

To cut volume, they split an oversized window into smaller sub-windows wherever two TCNOTs on the same logical qubit are separated by at least d syndrome-extraction rounds (which is what the d-round buffer requirement permits), group events that must stay together, and then color a conflict graph so non-conflicting sub-windows decode simultaneously.

Finally, they wrap these techniques in a scheduler: they restrict themselves to a simple, parameterized family of TCNOT spacing policies, build the earliest possible schedule for each, and accept the first (densest) one for which every window passes the latency and memory constraints, with a DSatur-based heuristic to minimize the critical-path decoding latency of the colored layers.

Why This Matters

The paper reframes TCNOT-based FTQC as a co-design problem: quantum-side speedup is only real if the classical decoder can keep up in real time. It gives a concrete accounting of where the decoding cost comes from and shows that schedule choice, decoder assignment, error-model compilation, and window partitioning are all coupled.

Real-world applications (as directions this kind of work enables):

• Neutral-atom quantum computers, which are explicitly named as the motivating platform because TCNOTs need long-range connectivity.
• Real-time decoding hardware/software stacks for fault-tolerant machines, where latency and memory budgets are hard engineering constraints.
• Compiler and scheduler tooling for FTQC, which must currently assume d-round spacing between TCNOTs.
• Error-model tooling (the DEM Stitch idea of reusable local templates) for fast circuit-level noise modeling.

Industry relevance: the results bear directly on whether a quantum vendor's decoding budget forces them to slow down their logical clock. The paper also flags that current decoding systems may be insufficient for TCNOT-based FTQC, which is a signal for decoder developers about what to optimize.

Future Directions

• Decoder hardware/algorithm development: the paper states its evaluation "reveal[s] the limitations of current decoding systems for TCNOT-based FTQC and highlighting directions for future decoder development," but does not enumerate those directions in the available content.
• Faster just-in-time DEM compilation: DEM Stitch reduces the constant factor, but compilation latency remains a first-order constraint; further reduction is an obvious lever.
• Richer scheduling search: PACE deliberately restricts itself to a bounded family of spacing policies rather than jointly optimizing all inter-TCNOT spacings, which the authors note is combinatorial.
• Beyond the assumed instruction set: the authors state that the proposal is not limited to the specific instruction set (TCNOT for CNOT, patch rotation for H, magic-state teleportation for S/T) and applies to any FTQC architecture supporting transversal CNOTs — testing this claim on other architectures is open.

Target Audience

Researchers and engineers working on fault-tolerant quantum computing architecture, real-time decoders, and FTQC compilation/scheduling — especially those targeting neutral-atom or other long-range-connectivity platforms. It is also relevant to decoder developers (matching-based and correlated/hypergraph decoders) who want to know what workloads will stress their systems. Readers without a background in surface codes and detector error models will find the details dense, though the high-level argument about decoder capacity limiting quantum speedup is accessible.

Authors’ abstract

Transversal CNOT (TCNOT) gates can accelerate fault-tolerant quantum computation (FTQC) in the surface code by reducing the number of syndrome extraction rounds required between logical operations from $O(d)$ to $O(1)$. This is particularly attractive for quantum platforms with long-range connectivity, such as neutral atoms. However, dense TCNOT schedules substantially increase the classical decoding workload. TCNOTs propagate errors across multiple surface-code patches, enlarging the spatiotemporal region that must be decoded jointly. Consequently, denser TCNOT schedules increase decoding latency and memory requirements and potentially exceed available decoder capacity. Moreover, because the detector error model (DEM) of each decoding window depends on the TCNOT schedule, exhaustively precomputing all possible window-level DEMs is infeasible, requiring just-in-time (JIT) DEM compilation. Thus, the practical benefit of TCNOT gates is limited not only by quantum hardware performance but also by classical decoding and DEM-compilation capacity. We introduce PACE, a decoder-aware scheduling framework for TCNOT-based FTQC. PACE first mitigates the decoder-side costs of aggressive TCNOT scheduling through three complementary techniques. Hybrid Window Decoding assigns different decoders for each decoding window according to its DEM structure. DEM Stitch generates schedule-specific window-level DEMs just in time by assembling reusable precompiled fragments. Sub-window Parallel Decoding decomposes large windows into smaller sub-windows with graph-coloring formulation. Building on these techniques, PACE then performs decoder-aware scheduling to maximize TCNOT concurrency within the available decoder resources. Our evaluation shows the trade-off between quantum acceleration and classical decoding cost, revealing the limitations of current decoding systems for TCNOT-based FTQC.