Trident: Efficient Load Verification for Yoked Surface Codes using a Three-Level Memory Hierarchy

AI summary

Overview

Research area: Fault-tolerant quantum computing (FTQC) architecture — specifically quantum error correction, yoked surface codes, and memory-hierarchy design.

Technical level: Advanced. The paper assumes familiarity with the surface code, lattice surgery, syndrome extraction, code concatenation, and classical cache/prefetch concepts.

Scope (1 sentence): The paper quantifies the load-verification bottleneck of 2D yoked surface code memory and proposes Trident, a three-level memory hierarchy that inserts a small 1D yoked surface code tier to cut verification latency while preserving storage density.

What This Paper Is About

Fault-tolerant quantum computers store idle program qubits in 2D yoked surface codes (YSCs) because these are 4.5× denser than plain surface codes. However, loading a qubit out of a 2D YSC is not fault-tolerant: the routing channel used for the load cannot simultaneously measure the block's yokes, so the fetched qubit stays unverified until all yokes are measured, which takes 178 cycles versus only 8 cycles for the retrieval itself. The paper's goal is to reduce this verification latency without giving up the storage efficiency of 2D YSCs.

Key Contributions

1. The first study of the performance impact of load verification latency in 2D yoked surface code memories, showing that eliminating verification entirely would yield a 5.7× geomean speedup.
2. Trident, a three-level memory hierarchy that adds a small intermediate tier (L1) built from a single 1D YSC — an 8-entry block using 10 surface codes and 8.8k physical qubits including routing — between the compute subsystem (L0) and the 2D YSC memory (L2).
3. Trident-D, a demand-driven variant that runs the L1 as a compiler-managed cache, evaluated with both LRU replacement and Belady's optimal (OPT) replacement.
4. Trident-P, a prefetch-driven variant that moves qubits from L2 into L1 ahead of their next load, with a victim-selection rule (evict the oldest stored resident) chosen to maximize the time between prefetch and load.

Main Findings

• Verification dominates load latency: In a 2D YSC, retrieval takes 8 cycles while verification takes 178 cycles; for a 194-entry 2D YSC with 62 yokes, verification requires 4444 syndrome-extraction rounds, and at d_eff = 25 rounds per cycle this is 4444/25 ≈ 178 cycles.
• Ideal-case ceiling: An FTQC with zero verification latency achieves a 5.7× geomean speedup over the baseline two-level hierarchy.
• 1D YSCs have effectively zero exposed verification latency: With only two yokes, yoke measurement interleaves with retrieval so a full load takes 8 cycles. Replacing all 2D YSCs with 1D YSCs would, however, increase the memory subsystem's physical qubit footprint by 2.5×.
• Trident-D results: 2.3× speedup with LRU and 2.8× with OPT, against L1 hit rates of 66.7% (LRU) and 78.7% (OPT).
• Trident-P results: 4.2× speedup, versus 2.8× for Trident-D, reported as the headline result alongside the demand-driven variant.
• Cost: Trident increases the physical qubit cost of memory storage by only 4.9% on average.
• Where demand-driven caching falls short: On memory-intensive, low-temporal-locality workloads such as chromium_q_sel, both LRU and OPT leave a large gap to the ideal system, which motivates the prefetch-driven design.
• Prefetch verification is deadline-driven: An L1 load following a prefetch incurs 178 − (t_load − t_prefetch) cycles of residual verification overhead, and zero if the gap exceeds 178 cycles.
• Wide spread in ideal speedups: From 2.83× (grover_3sat) to 12.5× (chromium_q_sel), tracking memory-access intensity (1.3% to 33.0% of instructions).

Methodology in Plain English

The authors build a compiler-and-simulator toolchain rather than running on quantum hardware. Their compiler takes benchmark programs in QASM, converts them to Clifford+RZ, synthesizes RZ gates into Clifford+T sequences with Gridsynth, applies gate coalescing, and then inserts load/store instructions that move program qubits between the compute subsystem and memory, following the approach of prior work (HetEC, LSQCA, qSIEVE).

A cycle-level simulator then executes the compiled binaries, modeling the compute subsystem, the memory subsystem, magic state production, and routing-space contention. Memory operations are serialized — at most one load or store runs at a time — and the configuration models a teraquop-regime machine with a per-syndrome-round logical error rate of 10^-15.

To compare designs fairly, the authors also estimate application fidelity, multiplying a compute-subsystem term (based on cycle count, capacity, per-cycle surface code error rate, and T-gate count/infidelity) by a memory-subsystem term accumulated over yoke cycles, where each yoke cycle's error probability depends on the surface code distance, the number of patches, and how many syndrome-extraction rounds elapsed. A 2D YSC is allowed to serve memory accesses for at most 100 consecutive cycles and begins yoke measurement after 14 consecutive cycles without a memory access; a 1D YSC checks yokes on every memory access or after 50 consecutive idle cycles. Ten benchmarks are simulated for their first 100M instructions and scored with instructions per cycle (IPC).

Why This Matters

Impact on research: The paper reframes memory access in FTQCs as an ECC-like problem where — unlike classical DRAM, where verification is nearly free and retrieval dominates — verification is the dominant cost. It also shows that a modest architectural addition (a single small 1D YSC block) captures most of the available benefit at a 4.9% qubit-cost increase, and it opens a compiler/architecture co-design space (cache replacement, prefetch scheduling) that did not previously exist for yoked surface code memories.

Real-world applications (as represented by the evaluated benchmarks):

• Quantum chemistry and materials simulation via block-encoding (qubitization) and Trotterization of Hamiltonians drawn from HamLib, including chromium and ethylene systems and the Bose-Hubbard model.
• Cryptanalysis, represented by shor_rsa24 (factoring an RSA-24 instance).
• Combinatorial search, represented by grover_3sat (Grover's algorithm on 3-SAT).
• Other Hamiltonian simulation workloads where SELECT subroutines are memory-intensive (up to 33.0% memory accesses in chromium_q_sel).

Industry relevance: Directly relevant to groups designing fault-tolerant quantum processors and their control/compilation stacks, since the results argue that memory tiering and prefetch scheduling belong in the compiler and microarchitecture, not just in the error-correcting code. The 4.9% footprint overhead and 2.8×–4.2× speedups are the kind of trade-off that shapes qubit budgets for machine builders.

Future Directions

• Combining demand-driven caching and prefetching into a single hybrid policy, since Trident-D wins on locality and Trident-P wins on memory-intensive streams.
• Exploring L1 capacity beyond the single 8-entry 1D YSC block evaluated here, and how multiple 1D blocks or a partitioned L1 would change hit rates and footprint.
• Carrying the three-level idea to other concatenated or high-rate code families beyond 1D and 2D yoked surface codes.
• Better prefetch scheduling and victim selection under runtime (rather than compile-time) information, and extending the analysis to the store path and to non-serialized memory systems, since this study serializes all memory operations.

Target Audience

Quantum architecture and compilation researchers, graduate students working on fault-tolerant quantum computing and quantum error correction, and hardware/software engineers at quantum computing companies who are designing memory hierarchies, instruction set abstractions, and compilers for surface-code machines. Readers without background in the surface code, lattice surgery, and classical cache design will find the paper steep.

Authors’ abstract

Fault-Tolerant Quantum Computers (FTQCs) commonly use the surface code to encode program qubits as error-corrected logical qubits. Unfortunately, the surface code has a poor encoding rate, so recent work has proposed Yoked Surface Codes (YSCs), which concatenate the surface code with a high-rate quantum code. The surface code qubits in YSCs are protected by the checks, or yokes, of the high-rate code. YSCs have 1D and 2D variants, which are $1.8\times$ and $4.5\times$ more efficient than the surface code, respectively. Modern FTQC architectures use a two-level hierarchy: surface codes perform logical operations (compute) while 2D YSCs store idle program qubits (memory). To load a qubit from memory, the FTQC first performs retrieval, which logically moves a program qubit from a 2D YSC into a surface code (8 cycles). However, retrieval is not fault-tolerant, so the FTQC must verify the load by measuring all the yokes of the 2D YSC (178 cycles). As verification dominates memory access latency, eliminating it can provide a speedup of $5.7\times$. Our goal is to reduce the verification overhead of 2D YSCs while retaining their storage efficiency. We exploit the fact that 1D YSCs, though less storage-efficient, incur negligible verification latency. We propose Trident, which expands the two-level hierarchy into a three-level hierarchy by adding a small intermediate level containing a 1D YSC (L1). If most loads hit L1 rather than L2 (2D YSC tier), it can significantly reduce verification overhead. We present two variants: Trident-D (demand-driven) and Trident-P (prefetch-driven), which achieve speedups of $2.8\times$ and $4.2\times$, respectively, while increasing the physical qubit cost of memory by only 4.9%.