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

CCS Concepts: • Computer systems organization → Quantum computing.

Keywords: Fault-Tolerant Quantum Computing; Quantum Error Correction; Quantum Computer Architecture; Quantum Memory Hierarchy; Yoked Surface Codes

ACM Reference Format: Gunagya Singh Mamak, Suhas Vittal, Kabir Dubey, Kaitlin N. Smith, and Moinuddin K. Qureshi. 2027. Trident: Efficient Load Verification for Yoked Surface Codes using a Three-Level Memory Hierarchy. In Proceedings of the 32nd ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 (ASPLOS ’27), April 11–15, 2027, Heraklion, Greece. ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/3845814.3850031

Introduction

Quantum computing provides exponential speedups for important applications, but the error rates required to execute these applications are typically $10^{-9}$ or less [17, 21, 30, 33]. Quantum Error Correction (QEC) is the most promising method of reaching such low error rates [5] [34]. QEC codes encode a large number of unreliable physical qubits into a code block containing few logical qubits. Throughout program execution, the parity checks of the QEC code are periodically measured to identify errors in the code block. The error correction capabilities of a QEC code can be increased in two ways. First, by increasing the code distance ($d$) by adding more qubits. Second, by code concatenation, which uses the logical qubits of one QEC code (inner code) as the data qubits of another QEC code (outer code).

In this paper, we study Fault-Tolerant Quantum Computers (FTQCs) which use the surface code for error correction [7] [22, 37]. Fault-tolerant computation involving the surface code is highly optimized [9] [11, 15, 18, 26, 27]. Unfortunately, the surface code’s encoding rate is poor, requiring nearly 1000 physical qubits per logical qubit in practice for $d=25$ codes. Recent work has proposed Yoked Surface Codes (YSCs) to mitigate the overhead of surface codes [14]. Figure 1(a) shows an overview of YSCs. YSCs concatenate the surface This work is licensed under a Creative Commons Attribution 4.0 International License.

Image not extracted

ASPLOS ’27, Heraklion, Greece

© 2027 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-3012-2/2027/04

https://doi.org/10.1145/3845814.3850031 code with high-rate quantum codes to reduce the physical qubit footprint. The parity checks of the high-rate quantum code, or yokes, protect the surface code qubits within the YSC. YSCs have two variants, 1D and 2D, which are 1.8× and 4.5× more efficient than a normal surface code, respectively. Given the storage efficiency of 2D YSCs, modern FTQC studies advocate the use of 2D YSCs instead of 1D YSCs [3] [12, 20].

While 2D YSCs have better storage efficiency than the normal surface code, they cannot both perform logical operations and measure yokes concurrently. Furthermore, stalling yoke measurements to execute logical operations on the YSC would increase the probability of a logical error. Therefore, modern FTQCs use a two-level exclusive memory hierarchy. The compute subsystem of the hierarchy uses a few (normal) surface codes to execute logical operations, whereas the memory subsystem uses the 2D YSC blocks to store the idle program qubits in a storage-efficient manner. Because the design devotes most of the physical qubits to the memory subsystem, the overall storage efficiency of the two-level hierarchy remains close to that of the 2D YSC.

Accessing the Yoked Surface Code Memory: Throughout program execution, the FTQC will move program qubits between the two subsystems using load and store operations. Loads and stores involve interacting with the constituent surface qubits within a 2D YSC block. These interactions consume the routing channel within the 2D YSC block which is normally used to measure the yokes of the block. At any given time, the channel can be used to measure yokes or serve memory accesses, but not both concurrently [14].

Unfortunately, this limitation means that neither loads nor stores are fault-tolerant [13]. During a memory access, the surface codes constituting a 2D YSC are unprotected by its yokes. These surface codes may incur logical errors that compromise the outcome of the load or store instruction. Hence, a loaded or stored program qubit is in an unverified state, and the FTQC cannot execute any logical operations until the retrieved logical qubit is verified.

The Verification Bottleneck of 2D YSCs: Resolving the state of the program qubit is called verification and requires the FTQC to measure all yokes of the 2D YSC block. For a 2D YSC block, verification incurs significant latency overheads. For a store, this verification latency is off the critical path as compute instructions do not depend on stores. In contrast, compute instructions are often dependent on the load. So, until load verification completes, the FTQC must stall. Figure 1(b) describes the operation of a load instruction, including retrieval (moving from the memory system to the compute system) and verification (ensuring that the retrieved qubit is free of error). While the retrieval of the program qubit only lasts eight cycles, verification lasts 178 cycles. If we could eliminate all verification-induced stalls (ideal), we would speed up execution by 5.7×, on average.

Verification latency scales with the number of yokes in a 2D YSC as all yokes must be measured to verify a load. A 194-entry 2D YSC, for example, has 62 yokes which take 178 cycles to measure. In contrast, 1D YSCs only have two yokes, and these yokes can be interleaved with a memory access. Hence, the entire load operation, retrieval and verification, takes eight cycles, and the exposed latency of verification is zero. Unfortunately, while replacing all 2D YSC blocks with 1D YSC blocks would reduce load latency, the physical qubit footprint of the memory subsystem would increase by 2.5×. The goal of this paper is to reduce the verification latency of 2D YSCs while retaining their storage efficiency.

A Case for a Three-Level Memory Hierarchy: We propose Trident, which expands the two-level memory hierarchy into a three-level memory hierarchy by including an intermediate memory tier consisting of a small 1D YSC (e.g., with eight entries). An overview of Trident is shown in Figure 1(c). We refer to the compute subsystem, 1D YSC memory, and 2D YSC memory of Trident as the L0, L1, and L2, respectively. Our insight is that if a majority of loads in Trident access the L1 instead of the L2, then we can obtain a significantly reduced load verification latency, on average.

Demand-Driven Hierarchy: We first study Trident-D, which operates as a demand-driven hierarchy where the L1 operates as a cache. While this cache can be operated at runtime using the popular LRU replacement policy, we observe that quantum programs have deterministic access patterns already known at compile-time, so we can obtain optimal (OPT) replacement. Trident-D implements the L1 as a compiler-managed cache. When a program qubit is to be stored into the L1, Trident-D must allocate space for the incoming program qubit. So, Trident-D evicts the qubit whose next load is farthest into the memory access stream and places the evicted qubit into the L2 tier.

Prefetch-Driven Hierarchy: The performance of a cache is limited by the temporal locality of the memory access stream. Ideally, we want a solution whose speedups are not limited by the access pattern of the program. To this end, we study Trident-P which operates as a prefetch-driven hierarchy. For each load in the quantum program, Trident-P checks if the target program qubit resides in the L1 or L2. If it resides in the L2, Trident-P will prefetch the program qubit into the L1, well in advance of the intended use. To allocate space for this qubit, Trident-P will evict the oldest resident of the L1.

Our studies find that Trident-D and Trident-P provide speedups of 2.8× and 4.2× relative to the baseline two-level memory hierarchy. Trident increases the physical qubit footprint of memory storage by only 4.9% on average.

Overall, this paper makes the following contributions:

1. To the best of our knowledge, this is the first paper to study the performance impact of verification for 2D YSC.

2. We propose Trident, which expands the FTQC’s two-level memory hierarchy into a three-level hierarchy which uses a single 1D YSC as an intermediate memory tier (L1).

3. We propose Trident-D and Trident-P as demand-driven (L1 as cache) and prefetch-driven (L1 as prefetch buffer) hierarchies, respectively. They provide speedups of 2.8× and 4.2×, respectively, over a two-level hierarchy.

Background

Surface Codes

The surface code is a quantum error correcting code that encodes $2(d+1)^2$ physical qubits into a single, distance $d$ logical qubit [3] [12, 20]. $d^2$ of these physical qubits are data qubits that encode the logical state of the surface code. The remaining qubits are known as parity qubits. During program execution, the data qubits will inevitably accumulate errors which modify the logical state of the surface code. Detecting these errors requires periodically performing syndrome extraction, which involves executing a physical circuit that entangles the data qubits with the parity qubits. Then, the parity qubits are measured to obtain a syndrome that is analyzed by a classical decoder to identify changes to the logical state. Any changes manifest as X or Z flips on the logical state and are tracked in software.

Note that the syndrome extraction circuitry is also error-prone, and so the decoder cannot reliably identify changes to the logical state using only a single syndrome. Instead, the decoder must analyze $d$ consecutive rounds of syndromes to accurately filter time-like errors introduced by readout or CX gates. Thus, $d$ syndrome extraction rounds constitute an error correction cycle of the surface code.

Fault-Tolerant Quantum Computation

Fault-Tolerant Quantum Computers (FTQCs) use quantum error correction to protect program information from errors that occur during program execution. The surface code is a common choice for fault-tolerant quantum computation given that surface code computation is highly optimized [9] [11, 15, 18, 26, 27]. Surface code logical operations are implemented using the lattice surgery framework. Lattice surgery involves manipulating the boundaries of surface code logical qubits to measure Pauli-product operators, such as ZZ, between two logical qubits. Measuring a Pauli-product operator involves measuring the parity checks connecting the boundaries of two logical qubits for an entire error correction cycle. At the end of the error correction cycle, the decoder analyzes the $d$ rounds of syndrome data to resolve the measurement outcome. Logical operations, such as CX gates, involve one or more Pauli-product measurements [9]. The reliable execution of a logical operation on a logical qubit is contingent on the entire syndrome history of that qubit being available. Otherwise, the FTQC must stall until the history is available (see Appendix § 11).

Yoked Surface Codes

The primary limitation of the surface code is its poor encoding rate, which reduces quadratically with the code distance ($d$). For low logical error rates (i.e., $10^{-15}$), a surface code logical qubit will require around $d=25$ which consumes 1.3k physical qubits. To address this, recent works have proposed Yoked Surface Codes (YSCs) [14], which concatenate the surface code with high-rate quantum codes with low code distance. The parity checks of the outer codes, or the yokes, protect the inner surface code logical qubits. The effective distance of YSC ($d_{\mathrm{eff}}$) scales with the product of the inner surface code distance ($d_{\mathrm{in}}$) and the outer code distance.

There are two variants of YSCs: 1D and 2D. Figure 2(a) presents an overview of both. 1D YSCs concatenate $d_{\mathrm{in}}=15$ surface codes with an $[[n,n-2,2]]$ quantum code and are 1.8× more efficient than normal surface codes. They have two yokes, one X and one Z, measured across all $n$ surface code qubits, much like a checksum. 2D YSCs concatenate $d_{\mathrm{in}}=11$ surface codes with an $[[n^2,n^2-4n+2,4]]$ quantum code and are 4.5× more efficient than normal surface codes. The $n^2$ surface code qubits are organized into an $n \times n$ grid, and each yoke spans one or two rows/columns of the grid.

Image not extracted

Two-Level Memory Hierarchy using 2D YSCs

Modern surface code FTQCs use YSCs as a large, high-density memory for storing idle program qubits during program execution [3] [12, 20]. Figure 2(b) presents a high-level overview of modern FTQC architectures that use a two-level memory hierarchy. The compute subsystem contains a few surface code logical qubits which execute logical operations such as $CX$ or $T$ gates. The memory subsystem uses one or more 2D YSCs for storage. Note that due to the no cloning theorem, the memory hierarchy is exclusive. So, a program qubit can reside at only one level in the memory hierarchy.

Loading from a Yoked Surface Code Memory

Throughout program execution, the FTQC will execute load and store instructions to move program qubits between the compute and memory subsystems. As the implementations of loads and stores are similar, we focus on loads for brevity.

In a YSC memory, a load has two parts: retrieval and verification. Accessing a YSC memory is much like accessing the DRAM-based memory system in traditional processors that use error-correcting codes (ECC) to correct data loaded from memory. In traditional systems, verification, where ECC is leveraged to detect or correct errors on the loaded data, incurs negligible overhead. Retrieval dominates load time. In contrast, in a YSC memory, we find that verification constitutes the majority of the load latency. Below, we discuss the technical details of retrieval and verification in YSCs.

Load Retrieval

In general, load retrieval from a YSC-encoded qubit $q_A$ into a surface code qubit $q_B$ (prepared in the $|+\rangle$ state) involves a logical-level state teleportation performed in two steps [6] [14]. First, the FTQC measures the joint $ZZ$ operator between $q_A$ and $q_B$ using lattice surgery. Then, $q_A$ is destroyed by measuring it in the $X$ basis. $q_B$ is left in the original state of $q_A$. The two steps of load retrieval are complicated by the YSC encoding of $q_A$. The $X$ and $Z$ logical operators of $q_A$ span multiple surface code patches within the YSC. Measuring the joint $ZZ$ operator therefore requires lattice surgery involving $q_B$ and all patches supporting the logical $Z$ operator of $q_A$. Similarly, measuring $q_A$ in the $X$ basis requires lattice surgery involving all patches supporting its logical $X$ operator, as measuring these patches transversally would destroy the entire memory, not just $q_A$.

Load Verification

During load retrieval, a YSC cannot measure its yokes since the routing space is used for lattice surgery operations. If any of the surface code qubits involved in these lattice surgery operations incur logical errors, then the outcome of the load is erroneous. Thus, loading from a YSC memory is not fault-tolerant [13]. Recovering from any errors encountered during the load operation requires the FTQC to measure all yokes of the YSC after the load has finished. We refer to this process as verification.

Until the load is verified, the syndrome history of the loaded program qubit is incomplete. Consequently, if a lattice surgery operation were to be executed using the loaded program qubit, the decoder would be unable to accurately resolve the operation’s outcome. Hence, the FTQC cannot execute any gates using the loaded program qubit until verification completes the qubit’s syndrome history.

1D YSC: Retrieval and Verification

As the 1D YSC has only two yokes, retrieval and verification steps can be interleaved. Figure 3 shows the complete load procedure of a program qubit within the 1D YSC into a surface code qubit qLD initialized in the $|+\rangle$ state. The first retrieval step measures the joint $ZZ$ operator between qLD and the target program qubit. As the program qubit is encoded using a 1D YSC, qLD performs $ZZ$ measurements with each surface code qubit constituting the program qubit’s $Z$ operator. Then, the first verification step measures the $Z$ yoke of the 1D YSC. As retrieval and verification both must access the $X$ operators of the 1D YSC’s surface code qubits, the boundaries of each surface code qubit are “rotated”, which takes four cycles in total. Next, the second retrieval step measures the $X$ operator of the program qubit. This destroys the program qubit, leaving qLD in the program qubit’s original state. The second verification step measures the $X$ yoke of the 1D YSC. Hence, for a 1D YSC, a full load operation takes eight cycles.

Image not extracted

2D YSC: Retrieval and Verification

Appendix C discusses the specific lattice surgery operations required to implement load retrieval within 2D YSCs. Retrieval takes eight computation cycles. However, retrieval occupies the routing space required for yoke measurements, so the retrieved qubit remains unverified.

For verification, yokes across all rows and columns are measured through a long sequence of lattice surgery operations. Specifically, measuring all yokes in 2D YSCs with width $w$ and inner surface-code distance $d_{\mathrm{in}}$ requires $25d_{\mathrm{in}}w + 4d_{\mathrm{in}}$ rounds of syndrome-extraction [14]. For example, 2D YSCs with outer code $[[256, 194, 4]]$ ($w = 16$) and inner distance $d_{\mathrm{in}} = 11$ take 4444 rounds of syndrome-extraction for verification. For this code, one computation cycle comprises $d_{\mathrm{eff}} = 25$ rounds, so verification takes $4444/25 \approx178$ cycles. Thus, following retrieval, a loaded program qubit must wait 178 cycles for its load to be verified.

Motivation and Goal

Modern FTQCs that use the surface code use 2D YSCs within the memory subsystem of their two-level memory hierarchy. While the load retrieval latency of 2D YSCs is rather short (eight cycles), their load verification latency is lengthy (178 cycles). Figure 2(c) shows that if all loads were to have zero verification latency, we would get a 5.7× speedup.

The simplest solution would be replacing all 2D YSCs with 1D YSCs, as 1D YSCs effectively have zero additional verification latency. However, 1D YSCs are less storage efficient than 2D YSCs, so this solution is undesirable. The goal of this work is to design an FTQC memory hierarchy that achieves the low verification latency of 1D YSCs while retaining the storage benefits of 2D YSCs. We discuss our methodology before presenting our solution.

Methodology

Compilation

Our compiler takes benchmark programs provided as QASM files and translates them into Clifford+$RZ$ operations. We synthesize $RZ$ gates into a sequence of Clifford+$T$ gates using Gridsynth [31]. These syntheses are further optimized using gate coalescing [41]. Finally, our compiler inserts load/store instructions to move program qubits between the compute and memory subsystems of the FTQC in a manner similar to prior works such as HeTQC, HeT, LSQCA, and qSIEVE [23, 35, 38].

Simulation

We use the compiled binaries generated by our compiler to drive a cycle-level simulator that simulates program execution on an FTQC. Our simulator models the compute subsystem, memory subsystem, and magic state production in detail, including routing space contention in the compute and memory subsystems. In particular, we allow at most one memory operation to execute at any time, so all loads and stores are serialized. Table 1 shows the simulation configuration used in our evaluations which models a three-level memory hierarchy whose intermediate memory tier contains a single 1D YSC with capacity eight. Note that the baseline system, whose memory subsystem only contains 2D YSCs, does not contain this intermediate memory tier. This simulation configuration reflects an FTQC operating in the teraquop regime, which corresponds to a logical error rate per syndrome extraction round of $10^{-15}$.

Compute Subsystem
Capacity (Logical Qubits)	4
Distance	$d = 25$
Physical Qubits per Logical Qubit	2028 (incl. Routing)
Logical Error Rate	$d \times10^{-15}$
L1 Memory (1D Yoked Surface Code) – not in baseline
Surface Code Count	10
Capacity (Logical Qubits)	8
Inner Surface Code Distance	$d = 15$
Retrieval Latency	8 cycles
Verification Latency	0 cycles
Physical Qubits per Logical Qubit	1100 (incl. Routing)
L2 Memory (2D Yoked Surface Codes)
Surface Code Count	256
Capacity (Logical Qubits)	194
Inner Surface Code Distance	$d = 11$
Retrieval Latency	8 cycles
Verification Latency	178 cycles
Physical Qubits per Logical Qubit	454 (incl. Routing)
Magic State Production
Physical Qubit Footprint	47.8K
$d = 3$ Cultivation Units [15]	62
15 : 1 Distillation Units [27]	6
Magic State Infidelity	$10^{-12}$

Evaluated Workloads

We perform our evaluations using ten diverse, large-scale benchmarks that represent promising applications for FTQCs. Table 2 summarizes the characteristics of these benchmarks, namely their qubit counts, instruction counts, percentage of $T$ gates (T%), and percentage of memory accesses (M%) in the compiled binary, and speedup of an idealized system with zero-cycle verification. Our workload suite contains three types of applications: block-encoding (Qubitization) [16, 28], Trotterization [36], and algorithmic benchmarks such as Shor’s [33] or Grover’s [17]. We use Hamiltonians from HamLib [32] to construct each block-encoding and Trotterization benchmark. For each Hamiltonian, we denote the block-encoding benchmarks with a “q” suffix and the Trotterization benchmarks with a “t” suffix. For each benchmark, we simulate the first 100M instructions and measure performance using Instructions per Cycle (IPC).

Workload	Qubits	Inst.	T%	M%	Ideal Speedup
bose_hubbard_q	2228	204M	75.0%	6.7%	5.96×
chromium_q_prep	167	471M	76.4%	4.7%	6.58×
ethylene_q_prep	289	1.3B	79.4%	3.1%	5.67×
chromium_q_sel	167	292M	20.1%	33.0%	12.5×
ethylene_q_sel	289	436M	21.4%	24.4%	12.4×
bose_hubbard_t	2188	161M	93.1%	1.3%	3.21×
chromium_t	121	340M	75.2%	7.5%	7.42×
ethylene_t	241	320M	88.7%	2.3%	3.89×
shor_rsa24	111	174M	86.6%	1.7%	4.12×
grover_3sat	1710	295M	91.2%	1.7%	2.83×

Within a block encoding benchmark, there are two prominent subroutines: PREPARE and SELECT. Both subroutines exhibit very different program behavior. While PREPARE is $RZ$-heavy and thus compute intensive, SELECT is highly memory intensive. Thus, we evaluate the PREPARE and SELECT subroutines separately, and they are denoted by the “prep” and “sel” suffixes, respectively. The only exception to this rule is for the Bose-Hubbard benchmark. The benchmark is so short that both PREPARE and SELECT appear in the first 100M instructions of the benchmark.

Application Fidelity Estimation

We compute application fidelity by estimating the fidelity of the compute and memory subsystems separately. As we evaluate a subset of a program (100M instructions), we scale statistics output by our simulator, such as the number of cycles, to the total number of instructions in the program.

Compute Subsystem Fidelity

3.4.1 Compute Subsystem Fidelity. The fidelity of the compute subsystem relies on the following: (1) the number of compute subsystem cycles ($C$), (2) the capacity of the compute subsystem ($N$), (3) the per-cycle error rate of the surface code ($e_C$), (4) the number of $T$ gates in the program ($T$), and (5) $T$ infidelity ($e_T$). $N$, $e_C$, and $e_T$ are shown in Table 1, whereas $C$ and $T$ are calculated after simulation. Equation (1) shows how these variables determine the fidelity of the compute subsystem [19].

3.4.2 Memory Subsystem Fidelity. The fidelity of the memory subsystem is determined by the error rates of its YSCs. The measurement of all yokes in a YSC completes one yoke cycle. The logical error probability of a yoke cycle depends on the following: (1) the distance of the constituent surface code patches ($d_{\mathrm{in}}$), (2) the number of surface code patches ($n$), and (3) the number of syndrome extraction rounds that elapse during the yoke cycle ($r$). The logical error probabilities of a 1D YSC and a 2D YSC yoke cycle are given by Equation (2) [14].

The dependence on $r$ reflects the need to measure yokes periodically to prevent errors from accumulating on the constituent surface codes of a YSC. During simulation, we allow $r$ to vary between different yoke cycles according to the memory access pattern of the program. To bound $r$, we allow a 2D YSC to serve memory accesses for at most 100 consecutive cycles. It also begins measuring its yokes after 14 consecutive cycles without a memory access. In contrast, a 1D YSC can interleave yoke measurements with memory accesses. We therefore check its yokes on every memory access or after 50 consecutive idle cycles. Consequently, a high memory-access rate delays yoke measurements and increases the logical error probability for a 2D YSC, but not that of a 1D YSC.

Since the duration of a yoke cycle may vary during execution, so may its logical error probability. Let $e_y$ denote the error probability of the $y^{\mathrm{th}}$ yoke cycle, calculated using its realized value of $r$. Then, the total fidelity of a YSC that completes $Y$ yoke cycles during execution is calculated using Equation (3). Equation (4) accumulates the fidelity across all $B$ YSC blocks in the memory subsystem.

Overall Fidelity

3.4.3 Overall Fidelity. Assuming independent errors, the overall application fidelity is the product of compute system fidelity and memory system fidelity.

Trident: Towards a Three-Level Hierarchy

To achieve low verification latency overheads while maintaining the high density of 2D YSC, we propose Trident. Trident is based on the observation that the effective verification latency for 1D YSC is zero as the verification procedure can be interleaved with the retrieval of the logical qubit. However, using 1D YSCs as a memory in place of 2D YSCs is undesirable as 2D YSCs are much more storage efficient than 1D YSCs (4.5× better than surface code vs 1.8×). Hence, we must devote most of the physical qubits to the 2D YSC memory for getting high density.

The main insight in Trident is to augment the two-level memory hierarchy with an intermediate memory tier consisting of 1D YSC memory. If a majority of loads are from the 1D YSC memory (L1) rather than the 2D YSC memory (L2), then the average load verification latency will be much less than 178 cycles. Trident expands the traditional two-level memory hierarchy into a three-level memory hierarchy. Trident uses a single, 8-entry 1D YSC block in the L1 memory, which consumes 8.8k physical qubits total, including routing space. The effectiveness of Trident depends on the hit rate of the L1 tier, so it is important to manage the L1 space intelligently. We propose two variants of Trident. The first, Trident-D, manages the L1 as a cache in a demand-driven manner. The second, Trident-P, manages the L1 as a prefetch buffer in a prefetch-driven manner. In this section, we first discuss the load operation in Trident and then discuss the design details and effectiveness of Trident-D.

Trident: Design and Operation

Figure 4 shows an overview of Trident. Due to the no-cloning theorem, a quantum memory hierarchy must be exclusive: each program qubit can only occupy a single memory location in the memory hierarchy. Consequently, there is an aspect of “conservation" when performing memory accesses. A load, for example, clears a location in the L1 or L2 memories and occupies a location in the L0 (compute subsystem). However, as the L0 will be full, space must be allocated for the loaded program qubit. Thus, each load, regardless of the source memory location, must have a corresponding store.

Image not extracted

Trident provides two load semantics for moving data throughout the three-level memory hierarchy. Figure 4(a) shows how Trident handles a load to the L1 memory. As shown, when qubit B is loaded into the L0, Trident removes some qubit A from the L0 to allocate space for B. Subsequently, Trident stores A into the memory location vacated by B in the L1. Figure 4(b) shows how Trident manages a load from the L2 memory. When qubit C is loaded into the L0, Trident removes a qubit A from the L0. If Trident elects to store A into the L1, Trident must evict some qubit B residing within the L1. Then, Trident stores A into the location left vacant by B in the L1 and stores B into the location left vacant by C in

the L2. Alternatively, Trident may store the removed qubit from L0 directly into the L2.

There are more options for data movement than exposed by Trident. However, in our studies, additional load semantics beyond the two described above provided negligible benefit. So, we did not include them.

Trident-D: Design

Trident provides a framework for operating a three-level memory hierarchy on surface code FTQCs. However, Trident does not specify the specific decisions that should be taken during a load, such as which qubit to store to a lower memory tier. To this end, we propose Trident-D (Demand-Driven Trident) which operates the three-level memory hierarchy as a demand-driven hierarchy. A high-level overview of Trident-D is shown in Figure 6.

Image not extracted

Program qubits that are accessed more frequently are preferentially stored in the L1 memory, whereas infrequently accessed program qubits are stored in the L2 memory. In other words, Trident-D operates the L1 as a cache for the L2.

Trident-D is a compile-time solution that modifies a program already compiled to a two-level memory hierarchy, which we obtain by using the algorithms proposed in prior works [23, 35, 38]. Trident-D adds additional instructions to the input program to manage the L1 memory. Trident-D can use either LRU or Belady’s optimal replacement policy (OPT). We discuss both implementations of Trident-D.

Trident-D with LRU

Trident-D reads the program and tracks the contents of the L1 memory. When a program qubit is stored from the L0 and into the L1, Trident-D records the time at which this qubit was stored. This timestamp will be used later for eviction decisions. Each load in the initial quantum program will either target a program qubit currently within the L1 or within the L2. If the load accesses the L1 (cache hit), then Trident-D does not change the program as the load and its corresponding store obey the first load semantic. However, if the load accesses the L2 (cache miss), then Trident-D must identify which qubit in the L1 to evict and store to the L2 as per the second load semantic. Trident-D with LRU evicts the oldest qubit in the L1¹.

4.2.2 Trident-D with OPT. While OPT replacement is not practical for hardware-managed caches, in our case, we have a compiler managed cache, which has knowledge of future accesses to each qubit. Trident-D with OPT functions similarly to Trident-D with LRU. The only difference is that to implement OPT, we must record when each qubit is accessed.

To accomplish this, we read the input program and record the DAG layer of each load as a timestamp. The program is not modified in this first read. Then, Trident-D re-reads the entire program with the intent to modify it. For an L2 load, Trident-D with OPT uses the pre-recorded timestamps from its first read of the program to identify the L1 program qubit whose next load is farthest into the future. The evicted qubit is then stored into the L2 as per the second load semantic.

Trident-D: Results

Figure 5 (top) shows the speedups of Trident-D with LRU, Trident-D with OPT, and an idealized two-level hierarchy with zero verification latency. As shown, Trident-D with LRU, Trident-D with OPT, and the idealized FTQC achieve speedups of 2.3×, 2.8×, and 5.7×, respectively. The speedup of Trident-D with OPT is slightly larger than Trident-D with LRU, which is expected as LRU is an approximation of OPT.

Image not extracted

While the speedups from both versions of Trident-D are substantial, there still remains a significant performance gap between Trident-D and an idealized system. Figure 5 (bottom) further shows the L1 hit rates, or proportion of loads that access the L1 memory, for Trident-D with LRU and Trident-D with OPT. Trident-D with LRU has a hit rate of 66.7% and Trident-D with OPT has a hit rate of 78.7%. For workloads like chromium_q_sel, both versions of Trident-D do not have high hit rates, and so there is a significant gap in performance between Trident-D and ideal. As we cannot do better than OPT in terms of cache hit rate, we must look towards an alternative implementation of Trident.

Trident-P: Trident with Prefetching

Trident-D provides limited benefit on memory-intensive workloads with low temporal locality. Improving performance on these workloads requires moving toward a version of Trident whose performance is independent of the workload’s temporal locality pattern. To this end, we propose Trident-P (Prefetch-Driven Trident) which operates the memory hierarchy as a prefetch-driven hierarchy. Figure 7 presents how Trident-P reduces verification latency. While a demand-driven hierarchy (Trident-D) installs the most frequently accessed program qubits in the L1, a prefetch-driven hierarchy moves program qubits in the L2 into the L1 before their next load. We refer to this as a prefetch.

Image not extracted

Like Trident-D, Trident-P is also a compile-time solution that modifies a program already compiled to a two-level memory hierarchy. During compilation, Trident-P tracks the contents of the L1. Qubits can only enter the L1 if they are either (1) stored from the L0, or (2) prefetched from the L2. Trident-P does not modify loads that access the L1 memory as such loads have no verification latency. Thus, Trident-P focuses specifically on issuing prefetches to avoid L2 loads. The remainder of this section discusses the technical details of prefetching and design of Trident-P.

Prefetch Verification Overheads

Prefetching a program qubit from the L2 requires verification. However, loading the program qubit from the L1 after the prefetch does not incur any additional verification overhead. Thus, an L1 load incurs some verification overhead dependent on when the prefetch executes relative to the load. If $t_{\mathrm{load}} - t_{\mathrm{prefetch}}$ is larger than the L2 verification latency (178 cycles), then the L1 load incurs no additional verification overhead as the L2 will verify the prefetch before the load occurs. Otherwise, the L1 load will have a verification overhead of $178 - (t_{\mathrm{load}} - t_{\mathrm{prefetch}})$ cycles.

Trident-P: Orchestrating Prefetches

Trident-P has two goals: eliminate L2 loads via prefetching, and ensure that the verification overhead of these prefetches is as low as possible. When Trident-P encounters an L2 load, Trident-P attempts to insert a prefetch instruction that installs the target program qubit into the L1. To install the target qubit into the L1, Trident-P must first allocate space by evicting a qubit currently residing within the L1.

There are only two ways a program qubit can enter the L1: (1) it was stored from the L0, or (2) it was prefetched from the L2. We refer to the latter as inflight prefetches. Trident-P will never evict an inflight prefetch as doing so degrades performance, so it must choose a victim to evict among the qubits stored from the L0. However, the choice of victim can greatly affect the timeliness of a prefetch. Figure 7(b) presents how Trident-P selects which qubit to evict. Suppose an eviction candidate was installed in the L1 at time $t_{\mathrm{store}}$. Then, $t_{\mathrm{prefetch}} > t_{\mathrm{store}}$ as the prefetch can only begin after the eviction candidate is stored into the L1. In order to maximize the difference between $t_{\mathrm{load}}$ and $t_{\mathrm{prefetch}}$, Trident-P chooses the eviction candidate with the smallest $t_{\mathrm{store}}$, or the oldest eviction candidate. This is equivalent to FIFO eviction.

Once Trident-P selects a program qubit to evict, it will generate a prefetch instruction which installs the target qubit into the L1 and installs the evicted qubit into the L2. Trident-P inserts the prefetch directly after the instruction that stored the victim qubit into the L1. This ensures that the prefetch occurs as early as possible. Trident-P may also not have any program qubit to evict, which occurs if the L1 is saturated with inflight prefetches. Then, Trident-P does not insert a prefetch and leaves the qubit to be loaded from L2. We note that this is incredibly rare as the L1 can buffer up to eight inflight prefetches, and in our evaluations, Trident-P rarely fails to generate a prefetch.

Results

Impact on Instruction Throughput

Figure 8 (top) compares the speedups of Trident-D, Trident-P, and the idealized system over the baseline system with a two-level memory hierarchy. Trident-D, Trident-P, and the idealized system provide average speedups of $2.8 \times$, $4.2 \times$, and $5.7 \times$, respectively. Trident-P outperforms Trident-D across all workloads. The greatest gap between Trident-P and Trident-D is for memory-intensive workloads such as chromium_q_sel that exhibit poor temporal locality and thrash Trident-D’s cache. There is a significant gap between Trident-P and ideal for these memory-intensive workloads.

Image not extracted

Figure 8 (bottom) shows the average load verification latency for Trident-D and Trident-P (baseline verification latency is 178 cycles). Trident-D and Trident-P reduce the mean verification latency to 41.3 and 14.3 cycles, respectively. Trident’s reduction in verification latency also reduces verification-related stalls, as shown in Figure 9. Trident-D and Trident-P reduce load verification stalls from 64% of cycles to 30% and 20%, respectively.

Image not extracted

Trident-P: Prefetch Coverage and Timeliness

Figure 10 shows that Trident-P’s lower latency is driven by prefetches. For benchmarks such as chromium_q_prep and ethylene_t, Trident-D achieves high L1 hit rates, leaving few L2 loads for Trident-P to prefetch. On the other hand, benchmarks such as chromium_q_sel and chromium_t have lower L1 hit rates and therefore more L2 loads, enabling Trident-P to achieve higher prefetch coverage. Across benchmarks, Trident-P prefetches 32.5% of loads on average.

Image not extracted

Further, Figure 11 provides evidence that these prefetches are timely. Trident-P fully hides verification latency for 91.0% of loads and partially hides it for another 9.0%, improving over Trident-D’s hit rate of 78.7% (Figure 5). Verification latency remains fully exposed for fewer than 0.01% of loads, indicating that Trident-P almost always issues prefetches early enough to hide at least part of the verification.

Image not extracted

Sensitivity to L1 Memory Capacity

Figure 12 compares the performance of Trident-D and Trident-P for L1 memory capacities of 4, 8 (default), 16, and 24. As shown, Trident-D provides speedups of $2.1 \times$, $2.8 \times$, $3.8 \times$, and $4.3 \times$, respectively. Trident-P provides speedups of $3.1 \times$, $4.2 \times$, $4.9 \times$, and $5.5 \times$, respectively. The performance of Trident-D and Trident-P improves almost linearly as the L1’s capacity increases. Furthermore, Trident-P at a smaller capacity (i.e., 8) outperforms Trident-D at the next largest capacity (i.e., 16). Thus, Trident-P requires a lower physical qubit footprint to achieve a comparable speedup to Trident-D.

Image not extracted

Sensitivity: Compute Capacity Size

Increasing the capacity of the compute subsystem (L0) reduces the number of memory accesses required to execute a quantum program and thus reduces memory-related overheads. Hence, we study how Trident-D and Trident-P scale to FTQCs with larger compute subsystems. Figure 13 compares Trident-D and Trident-P for compute subsystem capacities of 4 (default), 8, 12, and 16. The reported speedups for each capacity are normalized to the baseline with the same capacity. Trident-D provides speedups of 2.8×, 2.4×, 2.5×, and 2.3×, respectively. Trident-P provides speedups of 4.2×, 3.4×, 3.4×, and 3.1×, respectively. Trident-D and Trident-P provide speedups even when memory-related overheads reduce, demonstrating that they will scale to FTQC systems with larger compute subsystems.

Image not extracted

Sensitivity: 2D Block Size

In this paper, we assume that each 2D YSC in the L2 memory uses an outer code of $[[256, 194, 4]]$ as this is typically used in prior works [3] [12, 20]. Depending on the number of program qubits in a quantum program, a larger outer code may be more desirable as the storage density of a yoked surface code increase with the size of its outer code. However, a larger outer code inherently has more yoke vertices, so its verification latency is longer. Equation (6) shows how the verification latency scales with the size of the outer code. As shown, increasing the number of surface code qubits within a YSC, or the block size of the YSC, by $4\times$ increases verification latency by $2\times$.

Table 3 shows the speedups of Trident-D, Trident-P, and ideal (no verification latency) for five different outer codes. The five outer codes have 64, 144, 256, 400, and 576 constituent surface code qubits which are encoded into 34, 98, 194, 322, and 482 logical qubits, respectively. Trident-D provides speedups of 3.7×, 3.1×, 2.8×, 2.6×, and 2.4×, respectively. Trident-P provides speedups of 4.6×, 4.3×, 4.2×, 4.0×, and 3.8×, respectively. An idealized memory with no verification latency has a speedup of 5.7× regardless of block size. The speedups of Trident-D and Trident-P decrease for larger block sizes. This is expected as a larger verification latency is harder to mitigate using the L1 memory. However, the speedups of Trident-D and Trident-P both remain significant even for the largest outer code evaluated.

Block Size	Capacity	V.L.	Trident-D	Trident-P	Ideal
64	34	90	3.7×	4.6×	5.7×
144	98	134	3.1×	4.3×	5.7×
256	194*	178	2.8×	4.2×	5.7×
400	322	222	2.6×	4.0×	5.7×
576	482	266	2.4×	3.8×	5.7×

Impact on Application Fidelity

Application fidelity is largely determined by the memory-errors incurred during program execution. Since Trident reduces the cycles required to execute a program, it improves fidelity over the baseline. As shown in Table 4, application fidelity tracks program speedup: it is lowest for the baseline at 92.9%, higher for Trident-D at 97.4%, and highest for Trident-P at 98.1%. Note that the idealized system achieves 100% application fidelity for every benchmark.

Benchmark	Baseline	Trident-D	Trident-P
bose_hubbard_q	90.2%	97.7%	98.1%
chromium_q_prep	97.5%	99.6%	99.6%
ethylene_q_prep	90.4%	97.9%	98.3%
chromium_q_sel	85.8%	89.9%	93.5%
ethylene_q_sel	75.9%	94.1%	95.3%
bose_hubbard_t	97.0%	99.0%	99.1%
chromium_t	97.2%	98.2%	98.3%
ethylene_t	98.5%	99.6%	99.7%
shor_rsa24	99.6%	99.8%	99.9%
grover_3sat	96.8%	98.2%	98.8%
Average	92.9%	97.4%	98.1%

Impact on Physical Qubit Footprint

In terms of physical qubit footprint, the baseline two-level memory hierarchy uses the fewest physical qubits but also has the worst performance. On the other end of the spectrum, the idealized two-level memory hierarchy has the best performance but requires the most physical qubits as it only uses 1D YSCs within its memory subsystem.

Table 5 shows the increase in physical qubit footprint of Trident and the idealized FTQC relative to the baseline. In our analysis, we consider the physical qubit footprint of program qubits and associated routing space in the compute and memory subsystems (excluding magic state factories). Furthermore, while we evaluated the PREPARE and SELECT subroutines for chromium_q and ethylene_q separately, we report a single value here for the entire workload to avoid inflating our results. As shown, Trident has a 4.9% higher physical qubit footprint relative to the baseline. In contrast, the idealized FTQC has a 52.8% higher physical qubit footprint. Thus, Trident achieves 73.7% of the performance of the idealized FTQC while requiring far fewer physical qubits to implement.

Benchmark	Qubits	Trident	Ideal (1D YSC)
bose_hubbard_q	2228	+0.8%	+92.7%
chromium_q	167	+9.1%	+66.1%
ethylene_q	289	+4.8%	+47.0%
bose_hubbard_t	2188	+0.8%	+89.2%
chromium_t	121	+9.2%	+22.1%
ethylene_t	241	+4.8%	+23.0%
shor_rsa24	111	+9.1%	+12.9%
grover_3sat	1710	+1.1%	+96.8%
gmean		+4.9%	+52.8%

Trident can further reduce its physical qubit overhead by reusing an existing 1D YSC block as L1 (Appendix § 13).

Related Work

Yoked Surface Codes

Yoked surface codes (YSCs) were introduced by Gidney et al. as components of a surface-code memory hierarchy compatible with planar superconducting hardware [14]. Since then, YSCs have primarily appeared in resource-estimation studies for large scale applications including 256-bit elliptic-curve discrete logarithm, RSA-2048 factoring, and optimal polynomial intersection [3] [12, 20]. These works treat YSCs as dense storage for a large number of qubits that are idle during computation, helping reduce the required hardware for such applications to under one million physical qubits. However, these studies do not examine how YSCs behave during execution: when data should be moved, whether the memory accesses are fault-tolerant, or how post-load verification latency impacts instruction throughput. Indeed, the problem of load verification was raised by Gidney recently [13], but recent works studying the yoked surface code have not accounted for the impact of load verification latency.

Trident complements existing research on yoked surface codes by demonstrating that the high load verification latency of the 2D yoked surface codes can be overcome by expanding the traditional two-level memory hierarchy into a three-level memory hierarchy with an intermediate memory tier containing a single 1D YSC block. We propose two methods of managing the three-level memory hierarchy: Trident-D (demand-driven) and Trident-P (prefetch-driven).

Quantum Memory Hierarchies

A growing body of work studies segregated compute–memory organizations for fault-tolerant quantum computing, but under different code and hardware modalities. LSQCA [23] uses surface codes in both the compute and memory subsystem. Unlike the compute subsystem, which has ample routing space in their studies, the memory subsystem has very limited routing space, resulting in high memory access latency. LSQCA studies how memory management techniques can exploit temporal and spatial locality to improve the average access latency to the memory subsystem. HetEC [35] studies FTQCs with a surface code compute subsystem and a memory subsystem composed of Bivariate Bicycle codes [4] [43]. HetEC finds that an FTQC with a surface code compute subsystem and QLDPC-based memory subsystem provides comparable performance to FTQCs that exclusively use the surface code while using far fewer physical qubits. qSIEVE [38] studies the same architecture for neutral atom systems. qSIEVE also examines data movement challenges and optimizes the syndrome extraction schedule for Bivariate Bicycle codes on neutral atom systems.

YSCs introduce unique challenges not present in QLDPC-based memory systems because they are concatenated codes whereas high-rate QLDPC codes are implemented directly using physical qubits. Consequently, the problem of load verification is unique to YSCs. To the best of our knowledge, no similar problem exists for QLDPC-based memory systems. As this paper studies the problem of reducing load verification overheads in a YSC memory system, prior works like LSQCA, HetEC, and qSIEVE are orthogonal to this paper.

Memory Systems Using QLDPC Codes

Load/store architectures using high-rate QLDPC codes as a memory initially came out of Cohen et al.’s work on code surgery [6]. Following this work, HetEC and qSIEVE study FTQCs whose memory subsystem uses Bivariate Bicycle (BB) codes [35, 38]. Tour de Gross is a proposal from IBM that performs computation entirely using BB codes [43]. The Pinnacle architecture from Iceberg Quantum proposes using QLDPC codes for computation and memory [42].

While these architectures can be implemented on any hardware substrate, there is great uncertainty about the viability of implementing high-rate QLDPC codes like BB codes on superconducting quantum processors [10, 40]. High-rate QLDPC codes require dense and non-planar connectivity, which is hard to implement using superconducting qubits because of crosstalk and frequency collisions [25, 29, 39]. In contrast, yoked surface codes do not require any hardware changes as they build upon the surface code which has been demonstrated several times on real systems [1, 2] [24]. Thus, there is less uncertainty about whether yoked surface codes can be realized on real systems.

Conclusion

Recent work has proposed Yoked Surface Codes (YSCs) to reduce the physical qubit footprint of surface codes by concatenating the surface code with a high-rate quantum code.

YSCs have 1D and 2D variants, which are 1.8× and 4.5× more efficient than the surface code, respectively. As the 2D YSC has superior storage efficiency compared to the 1D YSC, modern Fault-Tolerant Quantum Computer (FTQC) architectures have evolved to use a two-level memory hierarchy where surface codes perform logical operations and 2D YSCs store idle program qubits. Loading from the 2D YSC first requires retrieval which moves a program qubit out of the 2D YSC memory and into a surface code qubit. However, retrieval is not fault-tolerant, so the FTQC must verify that the program qubit was loaded correctly. Verification dominates memory access latency, and eliminating it entirely would make the FTQC 5.7× faster. To this end, we propose Trident which is a three-level memory hierarchy with an intermediate 1D YSC memory tier. Our insight is that 1D YSCs have zero verification latency. We propose two versions of Trident which operate the memory hierarchy differently: Trident-D (Demand-Driven Hierarchy) and Trident-P (Prefetch-Driven Hierarchy). Trident-D and Trident-P provide speedups of 2.8× and 4.2× over the baseline. Both versions of Trident only require 4.9% additional physical qubits to implement.

Acknowledgements

K.D. and K.N.S. were supported by Google’s Research Scholar Program.

Artifact Appendix

Abstract

Our artifact is Quicksilver, a software package for compiling and simulating quantum programs on architectures with separate compute and memory subsystems. Quicksilver compiles quantum programs into a binary instruction format and simulates their execution in detail. It implements the memory compilation passes for Trident-D and Trident-P and models the runtime behavior of YSC memory. We also provide the benchmark programs used in our evaluations.

The artifact supports reproduction of all quantitative results in the paper: Figure 2(c), Figure 5, Figure 8, Figure 9, Figure 10, Figure 11, Figure 12, Figure 13, and Table 3, Table 4, Table 5. We provide a single Python script to run the experiments and generate plots in an iPython notebook.

Artifact check-list (meta-information)

• Program: Benchmark programs are available at 10.5281/zenodo.22931705.

• Compilation: CMake, C++23.

• Transformations: A two-pass memory scheduler inserts loads and stores in the first pass, and movement between L1 and L2 in the second pass.

• Hardware: A CPU host, (Optional) compute cluster.

• Metrics: Program throughput, hit rate, logical error rate.

• Output: Plots and tables corresponding to the paper’s quantitative results. Expected results are included.

• Experiments: A Python script automates evaluation.

• How much disk space is required (approximately)?: At most 50 GB.

• How much time is needed to prepare workflow (approximately)?: 30 minutes.

• How much time is needed to complete experiments (approximately)?: One day on a compute cluster.

• Publicly available?: Yes

• Code licenses (if publicly available)?: MIT

• Data licenses (if publicly available)?: MIT

• Archived (provide DOI)?: 10.5281/zenodo.22933092

How to access

Clone the Quicksilver Github repository and switch to the asplos2027 branch. Download the benchmark binaries from Zenodo and place the files in benchmarks/bin/.

Dependencies

Software dependencies

The build requires CMake 3.20.3 or newer, and a C++23 compiler (e.g. GCC 13). The experiment scripts require Python 3.10 or newer. Plot generation requires Matplotlib 3.7 and a Jupyter environment, such as JupyterLab. The Python dependencies are listed in requirements-artifact.txt.

Data sets

We provide compressed binaries for all benchmark programs on Zenodo. These binaries are generated from QASM descriptions of representative portions of quantum programs. The programs are first compiled to Clifford+$R_Z$, after which Gridsynth decomposes the $R_Z$ rotations into Clifford+$T$ sequences. The resulting binaries contain the program’s computational instructions.

Installation and Testing

Installation

After cloning the repository and downloading the benchmarks, run the following commands from the repository root to install dependencies and build the executables. For more details, refer to the repository README.

$ python3 -m venv venv
$ source venv/bin/activate
$ python3 -m pip install -r \
    requirements-artifact.txt
$ cmake -S . -B build \
    -DCMAKE_BUILD_TYPE=Release \
    -DCOMPILER_BINARY_GENERATION=OFF
$ cmake --build build --target \
    qs_memory_scheduler_yoked_simulator -j2

Basic Testing

To validate the installation, compile and simulate the first 100 instructions of base_hubbard_q:

$ python3 run_artifact.py --instructions 100 \
    --benchmarks base_hubbard_q --plots

Verify that outputs are written to results/smoke_100/.

Evaluation

Experiment workflow

The experiment runner executes two phases:

1. Compilation: The input binaries undergo two memory compilation passes. The first pass inserts loads and stores between the compute and memory subsystems according to the specified compute capacity. The output binary is added to firstpass under benchmarks/bin. The second pass augments outputs of firstpass by adding movement between L1 and L2 according to a cache (Trident-D) or prefetch (Trident-P) strategy, and writes output binaries to secondpass.

2. Simulation: The simulator models cycle-level execution of the compiled binaries using gate latencies, instruction dependencies, and resource availability. It uses the firstpass binaries to evaluate the baseline and idealized systems, and the secondpass binaries to evaluate Trident-D and Trident-P. Each simulation records its metrics in a log file under build.

Evaluation and expected results

To reproduce the results of the paper, run:

python3 run_artifact.py --plots

The script compiles all benchmarks and simulates the first 100 million instructions for each configuration. It sweeps over values of L1 capacity, compute capacity, and L2 block size to reproduce the sensitivity studies.

All results can be found by examining their respective cells in the iPython notebook results/paper_plots.ipynb. Generated plots and data should roughly match reported results, with some possible variance due to randomness.

Experiment customization

A.6.3 Experiment customization. Compilation and simulation parameters, including those varied in the sensitivity studies, are specified through command-line arguments. To evaluate other configurations, modify the arguments in the commands printed by run_artifact.py. Settings that control YSC memory behavior (e.g. maximum idle time, frequency of yoke checks) can be changed in the source code and require rebuilding the executables.

Methodology

Submission, reviewing and badging methodology:

• https://www.acm.org/publications/policies/artifact-review-badging

• http://cTuning.org/ae/submission-20201122.html

• http://cTuning.org/ae/reviewing-20201122.html

Syndrome History Criticality

Reliably executing a logical operation on a logical qubit requires the FTQC to have the entire syndrome history of that qubit. If the FTQC were to execute the operation incorrectly, then a Pauli correction (i.e., $X$) must be applied to the qubit. If this Pauli correction commutes through the next logical operation, then the FTQC can perform the current logical operation without having resolved the syndrome history of the qubit. Then, the syndrome history can be resolved later, and the Pauli correction can be applied upon resolution. However, resolving the syndrome history becomes critical when the potential Pauli correction cannot be passed through the next logical operation. This situation arises in $RZ$ and $CCX$ gates where $T$ gates prevent $X$ corrections from passing through. Thus, when the FTQC encounters a $T$ gate, it must stall until the syndrome history of the logical qubit is resolved.

This is relevant to load verification in YSCs as the syndrome history of the loaded program qubit is incomplete until verification completes. While the loaded program qubit can execute Clifford gates like $H$ or $CX$ before verification completes, it cannot execute $T$ gates. We model this aspect of load verification in our evaluations. In practice, program qubits quickly encounter a $T$ gate after being loaded, so verification latency cannot be hidden.

2D YSC: Operations for Load Retrieval

Figure 14 illustrates the sequence of operations required to load a logical qubit $q_A$ from 2D YSC into a surface code qubit $q_{LD}$. In a 2D YSC, both the $X$ and $Z$ operators of a logical qubit are distributed across four surface code patches.

Image not extracted

Panels 1–3 implement the first retrieval step. This step measures the joint $Z$ parity between $q_{LD}$ and the four surface code patches supporting the logical $Z$ operator of $q_A$, highlighted in blue. Due to limited routing space in 2D YSCs, this measurement must be split across two lattice surgery operations. In panel 1, $q_{LD}$ is initialized to $\lvert+\rangle$, and lattice surgery measures the joint $Z$ parity between an ancilla and two of the four $Z$-supporting patches of $q_A$. To retain the same protection as the YSC memory, this lattice surgery must be carried out in an ancilla region with width and height equal to the effective code distance ($d_{\mathrm{eff}}$) of the YSC, and its intermediate parity checks must be measured for $d_{\mathrm{eff}}$ syndrome extraction rounds. Throughout this paper, we treat $d_{\mathrm{eff}}$ syndrome extraction rounds as one cycle. In panel 2, the routing space is moved adjacent to the remaining two $Z$-supporting patches using sliding operations, which require $2d_{\mathrm{eff}}$ rounds, or 2 cycles [8]. Panel 3 then completes the ZZ retrieval by measuring the joint $Z$ parity of $q_{LD}$ with the remaining two patches and the ancilla, which takes 1 cycle.

Panels 4–6 implement the second retrieval step, which measures $q_A$ in the $X$ basis. This is done by measuring the joint $X$ parity of the four patches supporting the logical $X$ operator of $q_A$, highlighted in pink. Like before, this is done with two lattice surgery operations. An ancilla patch is initialized in $\lvert0\rangle$ in panel 4 and is finally measured in the $Z$ basis at the end of panel 6. At that point, the state of $q_A$ is loaded to $q_{LD}$. The full load retrieval sequence takes eight cycles.

Unlike a load retrieval from 1D YSC, this retrieval does not immediately verify the loaded state. Verification requires the yokes of the 2D YSC to be measured following the retrieval.

Fragmentation Study: 1D YSC Overheads

In this section, we describe how 1D YSCs can reduce fragmentation inherent in 2D YSC memory, and halve the additional physical qubit cost of Trident on average. The discrete capacities of 2D YSC blocks can require memory overprovisioning, leading to internal fragmentation. For example, ethylene_t stores 237 qubits in memory. Using standard $[[256, 194, 4]]$ 2D YSCs requires two such blocks, although the second holds only 43 qubits. A smaller second block could save space, but the smallest block that accommodates these remaining qubits is $[[144, 98, 4]]$, since the block width must be a multiple of four. Thus, storing solely with 2D YSC blocks is inefficient. In contrast, 1D YSCs support any even capacity. The minimum-cost configuration therefore combines two 2D YSC blocks, $[[256, 194, 4]]$ and $[[64, 34, 4]]$, with one $[[12, 10, 2]]$ 1D YSC block. Here, including a 1D YSC minimizes the physical qubit footprint even without considering Trident’s performance benefits. Trident can use this block as L1 at no additional physical qubit cost.

To quantify this benefit, we implement a memory configuration optimizer that minimizes the physical qubit footprint for a target memory capacity. The optimizer first enumerates all supported 1D and 2D YSC block sizes and precomputes the minimum physical qubit cost for each block capacity. It then uses dynamic programming to select the lowest-cost combination of blocks that meets or exceeds the target capacity. To determine Trident’s overhead, we repeat the optimization with the constraint that the configuration include a 1D YSC block whose capacity is at least the desired L1 buffer size.

Table 6 reports the optimal memory configurations and additional physical qubits required by Trident. For four of the eight benchmarks, the optimal configuration contains only 2D YSC blocks; provisioning an eight-entry L1 for Trident requires 8.8k additional physical qubits. The other four configurations already include a 1D YSC block with at least eight entries. Trident can manage this existing block as L1, incurring no additional storage overhead.

Benchmark	Optimal Memory Configuration	Trident Overhead (physical qubits)
bose_hubbard_q	2D: 11 × $[[256, 194, 4]]$, 1 × $[[144, 98, 4]]$	+8800
chromium_q	2D: 1 × $[[256, 194, 4]]$	+8800
ethylene_q	2D: 1 × $[[256, 194, 4]]$, 1 × $[[144, 98, 4]]$	+8800
bose_hubbard_t	2D: 11 × $[[256, 194, 4]]$, 1 × $[[64, 34, 4]]$; 1D: $[[18, 16, 2]]$	0
chromium_t	2D: 1 × $[[144, 98, 4]]$; 1D: $[[22, 20, 2]]$	0
ethylene_t	2D: 1 × $[[256, 194, 4]]$, 1 × $[[64, 34, 4]]$; 1D: $[[12, 10, 2]]$	0
shor	2D: 1 × $[[144, 98, 4]]$; 1D: $[[12, 10, 2]]$	0
grover	2D: 9 × $[[256, 194, 4]]$	+8800

To evaluate beyond our benchmark suite, we sweep target memory capacities from 100 to 2500 logical qubits. Across this range, requiring an eight-entry 1D YSC for Trident adds an average of 4.4k physical qubits, half the block’s nominal cost of 8.8k physical qubits. Thus, after accounting for fragmentation, Trident requires no additional physical qubits in the best case, 4.4k on average, and 8.8k in the worst case.