betaFeedback

WorksComputer Science

Beyond Blossom: Accelerating MWPM Decoding for Surface Codes With Local Predecoding and Architecture-Aware Optimizations

Abstract

Minimum-weight perfect matching (MWPM) is widely used to decode surface codes, but its computational cost increases with code distance. We present Beyond Blossom, a state-of-the-art CPU-based MWPM decoder for surface codes. It combines algorithmic optimization through local predecoding, architecture-aware optimization, and pipeline-wide parallelism to reduce matching workload and execution overhead while preserving MWPM optimality. Across rotated surface codes with distances 9-33 and circuit-level physical error rates of 0.05%-0.3%, on a single CPU core, Beyond Blossom achieves a 4.23×\times geometric-mean speedup and up to 5.58×\times speedup over Sparse Blossom in PyMatching. At distance 33 and a physical error rate of 0.1%, with 8 CPU cores, decoding a block of 33 measurement rounds takes 21.40 μμs on average, equivalent to 0.65 μμs per round.

Introduction

Quantum error correction (QEC) combines QEC codes with decoders [1, 2, 3]. QEC codes encode logical qubits into multiple physical qubits. A decoder is a classical algorithm that processes repeated stabilizer measurement outcomes, then determines an appropriate recovery operation. The surface code, a QEC code, is well suited to superconducting processors because its stabilizers can be measured using local interactions on a two-dimensional qubit array [4]. Recent superconducting experiments have demonstrated surface-code memories below threshold, where increasing the code distance reduces the logical error rate [5]. An eight-qubit stability experiment has also demonstrated FPGA decoding with feedback on superconducting hardware [6].

These advances place growing demands on classical decoding. Superconducting devices can generate a new round of measurement outcomes about every microsecond [5]. The decoder must therefore maintain an amortized decoding time below 1 μs\mu\mathrm{s} per measurement round to avoid a growing backlog. Logical operations that depend on the decoded result also require low feedback latency [6]–[8]. Efficient decoding is likewise important in simulations of fault-tolerant quantum circuits, where estimating low logical error rates through Monte Carlo sampling can require decoding millions of circuit samples.

In response, researchers have devoted considerable effort to developing accurate, low-latency surface-code decoders. A surface-code decoder takes a set of detection events as input. A detection event is a change in the measurement outcome of a stabilizer between consecutive rounds. Union-find decoding grows and merges clusters of detection events and offers an almost-linear worst-case runtime, but does not generally minimize the total correction weight [9]. Tensor-network methods approximate maximum-likelihood decoding by accounting for collections of equivalent errors, with higher accuracy generally requiring more computation [10]. Neural decoders can learn features of experimental noise that are difficult to capture in a simple model, but require suitable training data and sufficiently fast inference [11].

Minimum-weight perfect matching (MWPM) casts surface-code decoding as a graph matching problem and is widely used owing to its well-defined optimization objective and mature, efficient implementations [7], [8], [12], [13]. Among these implementations, Sparse Blossom [7], implemented in PyMatching 2 [12], performs the matching search directly on the sparse decoding graph. It avoids the all-to-all shortest-path searches used by some earlier implementations. Mikami and Yamasaki provide a rigorous theoretical framework for parallel sparse-blossom decoding, but their parallel implementation is slower in practice than single-threaded Sparse Blossom [14]. Fusion Blossom divides the decoding problem into smaller parts, solves them in parallel, and fuses the results into a global minimum-weight matching [13]. On FPGAs, Micro Blossom parallelizes dual updates while retaining the primal solver on

Introduction

Quantum error correction (QEC) combines QEC codes with decoders [1, 2, 3]. QEC codes encode logical qubits into multiple physical qubits. A decoder is a classical algorithm that processes repeated stabilizer measurement outcomes, then determines an appropriate recovery operation. The surface code, a QEC code, is well suited to superconducting processors because its stabilizers can be measured using local interactions on a two-dimensional qubit array [4]. Recent superconducting experiments have demonstrated surface-code memories below threshold, where increasing the code distance reduces the logical error rate [5]. An eight-qubit stability experiment has also demonstrated FPGA decoding with feedback on superconducting hardware [6].

These advances place growing demands on classical decoding. Superconducting devices can generate a new round of measurement outcomes about every microsecond [5]. The decoder must therefore maintain an amortized decoding time below 1 μs\mu\mathrm{s} per measurement round to avoid a growing backlog. Logical operations that depend on the decoded result also require low feedback latency [6]–[8]. Efficient decoding is likewise important in simulations of fault-tolerant quantum circuits, where estimating low logical error rates through Monte Carlo sampling can require decoding millions of circuit samples.

In response, researchers have devoted considerable effort to developing accurate, low-latency surface-code decoders. A surface-code decoder takes a set of detection events as input. A detection event is a change in the measurement outcome of a stabilizer between consecutive rounds. Union-find decoding grows and merges clusters of detection events and offers an almost-linear worst-case runtime, but does not generally minimize the total correction weight [9]. Tensor-network methods approximate maximum-likelihood decoding by accounting for collections of equivalent errors, with higher accuracy generally requiring more computation [10]. Neural decoders can learn features of experimental noise that are difficult to capture in a simple model, but require suitable training data and sufficiently fast inference [11].

Minimum-weight perfect matching (MWPM) casts surface-code decoding as a graph matching problem and is widely used owing to its well-defined optimization objective and mature, efficient implementations [7], [8], [12], [13]. Among these implementations, Sparse Blossom [7], implemented in PyMatching 2 [12], performs the matching search directly on the sparse decoding graph. It avoids the all-to-all shortest-path searches used by some earlier implementations. Mikami and Yamasaki provide a rigorous theoretical framework for parallel sparse-blossom decoding, but their parallel implementation is slower in practice than single-threaded Sparse Blossom [14]. Fusion Blossom divides the decoding problem into smaller parts, solves them in parallel, and fuses the results into a global minimum-weight matching [13]. On FPGAs, Micro Blossom parallelizes dual updates while retaining the primal solver on the CPU. It handles isolated local conflicts while preserving exact MWPM [8].

These advances suggest two directions for further CPU optimization. First, at low physical error rates, many detection events occur in adjacent pairs or next to a boundary, allowing local predecoding to reduce the workload passed to the full MWPM solver. However, heuristic prematching can increase the logical error rate [15, 16]. We therefore seek to exploit this locality while preserving MWPM optimality. Second, further gains may come from more efficient graph data access, single-instruction, multiple-data (SIMD) execution [17], and reduced overhead for thread coordination and state reinitialization.

Building on these investigations, we present Beyond Blossom2, an exact MWPM decoder that combines algorithmic optimization through predecoding, architecture-aware optimization, and pipeline-wide parallelism on modern CPUs. Together, these techniques accelerate both the blossom search and the surrounding decoding stages while preserving MWPM optimality. We provide both single-core and multi-core implementations of Beyond Blossom. Across rotated surface-code memory circuits with odd distances from 9 to 33 and circuit-level physical error rates of 0.05%, 0.1%, and 0.3%, the single-core configuration achieves a 4.23× geometric-mean speedup and up to 5.58× speedup over unmodified PyMatching 2.3.13, a prior state-of-the-art CPU MWPM decoder that supports only single-threaded decoding [7, 12]. Using eight physical CPU cores, Beyond Blossom achieves up to a 10.26× decoding speedup over single-threaded PyMatching. Our main contributions are:

  1. Degree-ordered one-hop predecoding. We introduce a predecoder that reduces global matching work while preserving MWPM optimality. It processes common local error patterns in degree order while maintaining dual feasibility, then transfers the resulting matching and dual state directly to the full solver.

  1. SIMD-enabled structured grid representation. We exploit the regular local connectivity of surface-code decoding graphs to introduce a structured grid representation. Its data layout improves cache locality, reduces pointer chasing and irregular memory accesses, and enables SIMD execution of key neighborhood computations in the dual phase.

  1. Pipeline-wide CPU parallelism for short blocks. We develop a parallel design for decoding blocks of dd measurement rounds in a distance-dd surface code. It combines parallel predecoding, connected-component parallelism, and overlapped state reset across thread groups.

Preliminaries

This section briefly introduces the background and notation needed to describe Beyond Blossom. We first review surface-code QEC, then introduce decoding graphs and the minimum-weight perfect matching (MWPM) formulation. Finally, we outline the alternating-tree operations and primal–dual framework of blossom-based decoders.

Surface-Code Quantum Error Correction

We consider the rotated surface code, which encodes one logical qubit using d2d^2 data qubits and d2−1d^2-1 ancilla qubits [18]. Here, the code distance dd is the minimum weight of a nontrivial logical Pauli operator. With ideal stabilizer measurements, a distance-dd code can correct any Pauli error affecting at most ⌊d−12⌋\left\lfloor\frac{d-1}{2}\right\rfloor data qubits [19].

The surface code detects errors through repeated measurements of local XX- and ZZ-type stabilizers on a two-dimensional lattice [4, 19, 20]. In the rotated layout illustrated in Figure 1(a), each stabilizer is a product of Pauli XX or ZZ operators acting on four neighboring data qubits in the interior or two at a boundary. Each stabilizer is measured using an ancilla qubit, which interacts with the corresponding data qubits through entangling gates and is then read out to yield a ±1\pm1 outcome. An odd number of XX errors on the data qubits of a ZZ-type stabilizer flips its measurement outcome, and ZZ errors affect XX-type stabilizers in the same way. In the illustrated example, an XX error on the highlighted data qubit flips the measurement outcomes obtained from the adjacent Z2Z_2 and Z3Z_3 stabilizer checks.

Figure 1. Rotated surface-code layout and 3D decoding graph. (a) A distance-3 code with 9 data qubits (white circles) and 8 ancilla qubits for measuring X-type (green) and Z-type (green) stabilizers. (b) The three-dimensional decoding graph for a distance-5 surface code, emphasizing the X-stabilizer subgraph; the Z-stabilizer subgraph is constructed analogously.

The logical error rate per measurement cycle, ϵd\epsilon_d, depends on both the code distance dd and the physical error rate pp. For odd dd, it approximately scales below threshold as [4]

ϵd∝(ppthr)(d+1)/2,\epsilon_d \propto\left(\frac{p}{p_{\mathrm{thr}}}\right)^{(d+1)/2},

where pthrp_{\mathrm{thr}} is the threshold for the chosen noise model and decoder. At a fixed p<pthrp < p_{\mathrm{thr}}, this scaling indicates that increasing dd reduces ϵd\epsilon_d exponentially, a trend also demonstrated experimentally [5].

Representative superconducting experiments have demonstrated surface-code memories at distances d=3,5,7d = 3, 5, 7 [5]. Practical quantum computations, however, can require larger code distances to keep the overall failure probability low over many logical operations. For example, resource estimates for quantum dynamics simulation, chemical energy estimation, and RSA-2048 factorization demand code distances ranging from d=9d = 9 to 33 at assumed physical error rates of p=10−4p = 10^{-4} and 10−310^{-3} [21]. These larger code distances increase the volume of stabilizer measurement data and hence the decoding workload, motivating decoder acceleration for practical fault-tolerant quantum computation.

Decoding Graph

Decoding aims to determine an appropriate recovery operation from the observed stabilizer measurement outcomes. In addition to the data-qubit errors described above, stabilizer measurements can themselves be faulty. We therefore decode measurement histories spanning dd rounds to correct up to ⌊(d−1)/2⌋\lfloor(d - 1)/2\rfloor data and measurement faults [19]. Under an independent-error model, we represent surface-code decoding using a three-dimensional decoding graph G=(V,E)G = (V, E), as shown in Figure 1(b). Each layer corresponds to one measurement round. Each non-boundary vertex is called a detector; the detector at (x,y,t)(x, y, t) corresponds to the stabilizer measurement at spatial location (x,y)(x, y) in round tt. Each edge represents a possible error mechanism, connecting either the two detectors it flips or a single detector to a virtual boundary. Within-layer edges represent data errors, while errors arising during measurement are represented by interlayer edges. For example, the black edge in Figure 1(b) represents a measurement error and connects two detectors associated with the same stabilizer.

A detector with a detection event is called a defect. The same set of defects can arise from different error configurations. In the t+1t + 1 layer of Figure 1(b), the solid red chain AA–BB–DD–FF flips the outcomes of internal detectors BB and DD twice each, producing defects only at AA and FF. These defects alone cannot distinguish between the error chains AA–BB–DD–FF and AA–CC–EE–FF, whose probabilities may differ. The objective of MWPM decoding is to identify the most probable set of error edges consistent with the observed defect set.

Assuming independent edge errors, a path γ\gamma has probability

P(γ)=∏e∈γpe∏e∈E∖γ(1−pe)∝∏e∈γpe1−pe.(1)P(\gamma) = \prod_{e \in\gamma} p_e \prod_{e \in E \setminus\gamma} (1-p_e) \propto\prod_{e \in\gamma} \frac{p_e}{1-p_e}. \tag*{(1)}

Each edge with error probability pep_e is assigned the weight we=ln⁡[(1−pe)/pe]w_e = \ln[(1-p_e)/p_e], making probability maximization equivalent to minimizing the total edge weight.

We reduce decoding to MWPM by constructing an auxiliary matching graph GM=(VM,EM)G_M = (V_M, E_M) [19, 22]. Here, VMV_M is the set of all defects, and EME_M connects every pair of defects u,vu,v. Each matching edge is weighted by their shortest-path distance in the decoding graph GG:

wuvM=dist⁡G(u,v).(2)w^M_{uv} = \operatorname{dist}_G(u,v). \tag*{(2)}

We then add virtual boundary vertices and edges so that defects can independently match to a boundary. MWPM pairs every vertex exactly once with minimum total edge weight, yielding a most probable error configuration consistent with the observed defect set. The matched pairs are then expanded into their corresponding paths in the decoding graph. Finally, these paths are combined modulo two to obtain the inferred error set.

Blossom-Based Decoders

Edmonds’ Blossom algorithm provides a polynomial-time solution to MWPM in general graphs [23, 24, 25]. The algorithm alternates between primal and dual updates. Primal updates modify the matching and alternating trees, while dual updates enable further search without violating the linear constraints. The blossom algorithm is guided by a primal–dual formulation on the graph GM=(VM,EM)G_M = (V_M, E_M). For each edge e∈EMe \in E_M, let xex_e denote its selection variable. Let δ(B)\delta(B) denote the edges in EME_M crossing between BB and VM∖BV_M \setminus B, with δ(v)=δ({v})\delta(v) = \delta(\{v\}), and O\mathcal{O} contain the odd-sized subsets of VMV_M with at least three vertices. The primal linear program is

min⁡x∑e∈EMwexes.t.∑e∈δ(v)xe=1,∀v∈VM,∑e∈δ(B)xe≥1,∀B∈O,xe≥0,∀e∈EM.(3)\begin{aligned} \min_x \quad& \sum_{e \in E_M} w_e x_e \\ \text{s.t.}\quad& \sum_{e \in\delta(v)} x_e = 1,\quad\forall v \in V_M, \\ & \sum_{e \in\delta(B)} x_e \ge1,\quad\forall B \in\mathcal{O}, \\ & x_e \ge0,\quad\forall e \in E_M. \tag*{(3)} \end{aligned}

The corresponding dual assigns unrestricted variables yvy_v to vertices and nonnegative variables yBy_B to odd sets:

max⁡y∑v∈VMyv+∑B∈OyBs.t.slack⁡(e)≥0,∀e∈EM,yB≥0,∀B∈O.(4)\begin{aligned} \max_y \quad& \sum_{v \in V_M} y_v + \sum_{B \in\mathcal{O}} y_B \\ \text{s.t.}\quad& \operatorname{slack}(e) \ge0,\quad\forall e \in E_M, \\ & y_B \ge0,\quad\forall B \in\mathcal{O}. \tag*{(4)} \end{aligned}

For an edge e=(u,v)e = (u,v), its slack is defined as

slack⁡(e)≡we−yu−yv−∑B∈Oe∈δ(B)yB.(5)\operatorname{slack}(e) \equiv w_e - y_u - y_v - \sum_{\substack{B \in\mathcal{O} \\ e \in\delta(B)}} y_B. \tag*{(5)}

We call an edge tight when slack⁡(e)=0\operatorname{slack}(e) = 0.

The algorithm starts with every vertex as an unmatched root labeled +. During execution, the algorithm maintains an alternating forest rooted at unmatched nodes. Paths from each root alternate between unmatched and matched edges. Nodes at even and odd depths are labeled + (outer) and − (inner), respectively. Each node represents either an original vertex or a contracted blossom. Nodes outside the alternating forest are frozen; their dual variables remain unchanged during the dual phase.

With the dual variables fixed, the primal search uses only tight edges and performs four operations: GROW, AUGMENT, SHRINK, and EXPAND. GROW follows a tight edge from an outer node to an unlabeled matched node outside the forest, adding that node as inner and its matched partner as outer (Figure 2(a)–(Figure 2b)). AUGMENT applies when a tight edge joins outer nodes in different trees, yielding an augmenting path between their unmatched roots. Flipping matched and unmatched edges along this path increases the matching size by one (Figure 2(c)–(Figure 2d)). SHRINK applies when a tight edge joins two outer nodes in the same tree, closing an odd cycle called a blossom. The algorithm contracts this cycle into a pseudo-node with a new dual variable initially set to zero (Figure 2(e)–(Figure 2f)). EXPAND is triggered when the dual variable yBy_B of an inner blossom BB reaches zero. The blossom is expanded into its constituent nodes, and the affected alternating-tree path is reconstructed without changing the matching (Figure 2(g)–(Figure 2h)). The primal phase therefore involves complex updates to matching and alternating-tree structures.

Figure 2. Key steps of the blossom algorithm for MWPM. Dashed edges indicate edges that became tight during the immediately preceding dual update. (a)–(b) Alternating-tree growth. (c)–(d) Augmentation yields one additional matched pair. (e)–(f) Blossom contraction into a pseudo-node. (g)–(h) Blossom expansion.

When no further primal operation is available, the algorithm performs a dual update. Under the fixed-δ\delta strategy, all active trees take the same step: outer-node duals increase by δ\delta, inner-node duals decrease by δ\delta, and variables inside contracted blossoms remain fixed. The step ends at the earliest eligible event across all active trees: an edge becomes tight or an inner blossom’s dual reaches zero. A global priority queue orders candidate events by their scheduled times, finding the earliest event. The primal search then resumes at the triggering edge or blossom. Primal operations may switch nodes among +, −, and frozen states or modify the blossom structure. Any new valid event candidates produced by these changes are added to the priority queue [25]. The algorithm terminates when the priority queue is empty, at which point the complementary slackness conditions guarantee that the resulting matching is an MWPM [25].

Although only defects require pairing in QEC decoding, the Sparse Blossom algorithm searches directly on the decoding graph GG using graph-fill regions (hereafter referred to as regions) [7]. Each defect uu initially seeds a region that grows along weighted edges under the control of its radius yuy_u, potentially reaching nondefect detectors. The radius yuy_u is the dual variable associated with defect uu. When two regions collide, the relevant dual contributions equal the weight of the corresponding pairing edge, making it tight. At a region’s frontier, growth adds ordinary detectors and shrinkage releases them. These ownership changes and region collisions are handled as events in a global priority queue. This implements the Blossom search through region growth, shrinkage, and collision detection, without first computing all pairwise shortest-path distances or constructing the complete matching graph GMG_M.

Proposed Method

MWPM decoding performance depends on both the matching workload and the efficiency of its CPU implementation. At low physical error rates, sparse local errors and the regular structure of surface-code graphs offer opportunities to improve both. Beyond Blossom therefore combines algorithmic optimization through predecoding (Section III-A), architecture-aware optimization (Section III-B), and pipeline-wide parallelism (Section III-C) to reduce decoding time while preserving MWPM optimality.

Degree-Ordered One-Hop Predecoding

At low physical error rates, many common errors produce adjacent defect pairs or defects that can be matched directly to a boundary [8, 15]. These patterns occupy small local neighborhoods and often admit simple matching relationships. Under an independent local fault model, two distinct faults occur within a fixed-size neighborhood with probability O(p2)O(p^2), providing substantial opportunities for local processing.

Nevertheless, a full MWPM solver maintains general-purpose search and scheduling structures even for these simple patterns. Sparse Blossom [7], for example, advances growing regions uniformly along a shared timeline and processes events through a global priority queue. Events from spatially distant regions therefore share the same ordering mechanism. State changes can also invalidate queued events: after AA and BB match at time 2 in Figure 3(a), a previously scheduled growth event for BB must be revalidated when dequeued. Alternating-tree maintenance, event-time calculations, queue operations, and validity checks collectively increase the cost of resolving local pairs.

Figure 3. Event-driven MWPM decoding in Sparse Blossom and degree-ordered one-hop predecoding. (a) Sparse Blossom schedules region events through a shared priority queue and discards stale events when dequeued. (b) Beyond Blossom’s one-hop predecoder processes defects in increasing order of candidate degree, bounds radius growth using the slack of all incident edges, and accepts tight-edge matches. If all defects are matched, the optimal solution is returned immediately. Otherwise, the partial matching and dual state initialize the full MWPM solver.

We therefore introduce a degree-ordered one-hop predecoder that quickly matches most defects through simple local operations, constructing a matching and a feasible dual state before invoking the MWPM solver when needed. Figure 3(b) illustrates the algorithm.

The one-hop restriction defines the scope of local processing.

  1. Direct matching. We match an unmatched defect to another unmatched defect or a boundary along a tight edge, then freeze the matched defects’ radii.

  2. Growth limited by a neighbor. When an edge to a nondefect detector or a matched defect becomes tight, the source cannot grow further.

These rules yield two structural simplifications:

  1. Flat dual state. Because the predecoder neither extends alternating trees nor contracts blossoms, each defect retains its own dual radius without a blossom hierarchy. We therefore store radii in a flat array and check edge tightness directly from the two endpoint radii and the edge weight.

  2. Sequential growth without a global event queue. Radii only increase or remain frozen, so the predecoder has no

shrinking (−-) nodes. In a general blossom solver, an edge e=(u,v)e=(u,v) between a growing (++) node uu in tree TT and a shrinking node vv in another tree T′T' imposes the cross-tree constraint δT−δT′≤slack⁡(e)\delta_T-\delta_{T'}\leq\operatorname{slack}(e), where δT\delta_T and δT′\delta_{T'} denote the dual increments of the two trees [25]. This class of constraints is absent from predecoding. We can therefore update nodes sequentially by different amounts, bounding each update by the current incident-edge constraints to preserve dual feasibility. This permits a direct traversal of the defects without equal-rate advancement, event-time prediction, or a global priority queue.

Degree ordering determines the processing sequence. Let S⊆VS\subseteq V denote the input defect set in the decoding graph GG, excluding virtual boundaries. We define the candidate degree of defect uu as k(u)=∣N(u)∩S∣+b(u)k(u)=|N(u)\cap S|+b(u), where N(u)N(u) contains its ordinary neighboring nodes and b(u)b(u) counts its valid boundary candidates. A single stable bucket sort orders defects by increasing candidate degree. For each defect uu, let ru≥0r_u\geq0 denote its dual radius, corresponding to yuy_u in the absence of blossom contributions. All radii are initialized to zero. For each unmatched source uu, we update its radius as

ru←min⁡v:(u,v)∈E(wuv−rv)(6)r_u\gets\min_{v:(u,v)\in E}(w_{uv}-r_v) \tag*{(6)}

where wuvw_{uv} is the weight of edge (u,v)(u,v) in GG. The minimum includes all incident edges. We take rv=0r_v=0 for nondefect nodes and virtual boundaries. We then examine unmatched defect neighbors. If ru+rv=wuvr_u+r_v=w_{uv}, the edge is tight and the pair is immediately matched. Otherwise, we attempt to grow vv using (6) and accept the pair if the edge becomes tight. If no defect match is found, we check for a tight boundary edge. If the source remains unmatched, we retain its radius and proceed to the next source.

These updates preserve ru+rv≤wuvr_u+r_v\leq w_{uv}. Summing these constraints along paths gives a feasible dual solution on GMG_M, with all blossom dual variables zero. Once every defect is matched exactly once through tight edges, complementary slackness guarantees optimality [25], allowing immediate return. Otherwise, we consistently import the radii and matching relationships into the full MWPM solver. Only unmatched defects become initial alternating-tree roots and initiate scheduling. The full MWPM solver can undo and revise prematches as it completes the matching.

The effectiveness of one-hop predecoding on surface codes also follows from the structure of the edge weights. For a decoding-graph edge e∈Ee\in E dominated by first-order faults, its error probability satisfies pe=aep+O(p2)p_e=a_ep+O(p^2), where ae>0a_e>0 is a coefficient independent of pp. Using the edge-weight definition above, as p→0p\to0, we=ln⁡[(1−pe)/pe]=ln⁡(1/p)−ln⁡ae+O(p)w_e=\ln[(1-p_e)/p_e]=\ln(1/p)-\ln a_e+O(p). Such edge weights differ by ln⁡(1/p)\ln(1/p), with differences primarily determined by their local coefficients. Consider an unprocessed adjacent defect pair u,vu,v with no other neighboring defects. Let μu\mu_u and μv\mu_v denote the minimum incident-edge weights at the respective endpoints, including edges to nondefect nodes and boundaries. If uu is processed first, its radius reaches μu\mu_u. The pair becomes tight when vv supplies the remaining radius wuv−μuw_{uv}-\mu_u, which is feasible exactly when

μu+μv≥wuv.(7)\mu_u+\mu_v\geq w_{uv}. \tag*{(7)}

When the target edge and the neighboring edges limiting both endpoints are dominated by first-order faults, μu+μv−wuv=\mu_u+\mu_v-w_{uv}= ln(1/p)(1/p) + O(1)O(1). This condition holds at sufficiently low error rates, allowing sequential radius updates to match the isolated pair.

Degree ordering further exploits the asymmetry of these updates. When local edge weights are similar, the source processed first typically acquires a large radius, while its partner supplies only a small remainder. The larger source radius restricts the growth available to its other defect neighbors. Prioritizing sources with fewer candidates therefore reduces the number of other defects directly affected by each large update. For example, in Figure 3(b), matching (B,C)(B,C) first leaves AA and DD unmatched during predecoding, whereas processing the degree-one sources AA and DD first yields (A,B)(A,B) and (C,D)(C,D). A single static ordering preserves more opportunities for subsequent matching at low preparation cost.

For the fixed-size neighborhoods of the surface-code graph, bucket sorting and one-hop growth and matching require O(∣S∣)O(|S|) total work. Fully covered inputs terminate immediately, while the remaining inputs enter the full solver with fewer unmatched roots, reducing computational work while preserving MWPM optimality.

SIMD-Enabled Structured Grid Representation

The blossom algorithm alternates between primal and dual phases, which exhibit distinct computational characteristics. The primal phase maintains the alternating forest and matching structures through tree growth, augmentation, and blossom contraction and expansion. These operations involve extensive data-dependent branching and serially dependent pointer accesses. Their execution efficiency therefore relies heavily on CPU branch prediction and out-of-order execution, while offering limited scope for software transformations based on regular computation and batched parallel execution. In contrast, the dual phase, which is a major computational hotspot [8], exhibits a more regular computational structure. It repeatedly evaluates edge slack to determine admissible dual-variable updates and identify the next edge to become tight. For a given dual state, candidate edges can be evaluated independently, followed by a minimum reduction to determine the next update. This repeated local computation provides opportunities for data-layout optimization, instruction-level parallelism, and SIMD vectorization.

The local stabilizer checks and repeated measurements of surface codes provide a natural three-dimensional spacetime representation for their decoding graphs. Under local circuit-level noise, each fault can trigger detection events only within a bounded spacetime neighborhood, allowing graph edges to be described by a finite set of relative displacements. As illustrated in Figure 4, we apply an affine transformation to detector coordinates and embed each independently decoded X/Z component of the rotated surface code in a regular three-dimensional lattice. The spatial, temporal, and diagonal spacetime edges induced by circuit-level noise are then represented by a twelve-direction stencil specific to each component. This representation encodes adjacency through fixed lattice offsets [26]. For lattice coordinates (x,y,t)(x,y,t), let (Δxk,Δyk,Δtk)(\Delta x_k,\Delta y_k,\Delta t_k) denote the displacement in direction k∈{0,…,11}k \in\{0,\ldots,11\}. The linear site index and neighbor offset are

Figure 4. Structured lattice embedding of a surface-code decoding graph. A twelve-direction stencil represents local connectivity, allowing neighbors of site cc to be addressed as c+δkc+\delta_k.

c=x+Nx(y+Nyt),δk=Δxk+NxΔyk+NxNyΔtk,(8)c = x + N_x(y + N_y t), \\ \delta_k = \Delta x_k + N_x \Delta y_k + N_xN_y\Delta t_k, \tag*{(8)}

where NxN_x and NyN_y denote the lattice extents along the two spatial dimensions. For an existing edge in direction kk, its neighbor is located at index c+δkc+\delta_k. The fixed directions and offsets also permit full unrolling of the neighbor scan, allowing the compiler to interleave address calculations and candidate evaluations across neighbors to exploit instruction-level parallelism.

Building on this addressing scheme, we organize data according to the access requirements of neighbor scanning. To reduce cache pollution and improve cache-line utilization, we compactly store the edge weights, each occupied detector’s top-level region identifier, and radius-related state repeatedly accessed during candidate evaluation. Information for event maintenance, logical-observable tracking, and path recovery is stored separately. This hot–cold separation concentrates the scan’s accesses on the required state and reduces the unrelated data fetched with each cache line.

The structured layout further enables SIMD vectorization across neighbor candidates. Each vector lane processes a different neighboring direction of the same source node, sharing the source state while independently evaluating a candidate event time. However, a scalar scan follows conditional branches based on edge presence, region ownership, and growth state, and different neighbors may satisfy different conditions. To express these differences within a uniform SIMD instruction stream, we replace per-neighbor conditional control flow with

mask operations and organize the scan into arithmetic and eligibility paths. The arithmetic path evaluates candidate times in parallel. At the current dual time, let rur_u and rvkr_{v_k} denote the local effective radii at source site uu and its neighbor vkv_k, and let wk=wuvkw_k = w_{uv_k} denote their edge weight. We set hk=1h_k = 1 when both endpoints are growing and hk=0h_k = 0 otherwise. The mask mkm_k selects existing edges with a positive combined growth rate, excluding edges internal to the same top-level region. Candidate time increments are

ΔT^k=wk−ru−rvk1+hk,ΔTmin⁡=min⁡0≤k<12select⁡(mk,ΔT^k,+∞).(9)\begin{aligned} \widehat{\Delta T}_k &= \frac{w_k-r_u-r_{v_k}}{1+h_k},\\ \Delta T_{\min} &= \min_{0\leq k<12}\operatorname{select}(m_k,\widehat{\Delta T}_k,+\infty). \tag*{(9)} \end{aligned}

For eligible candidates, the numerator is the remaining slack and the denominator is its closing rate. Applying the validity mask before reduction replaces invalid candidates with infinity, eliminating per-neighbor conditional branches within each batch. Although uniform evaluation includes some candidates that scalar branches would discard early, it permits multiple neighbors to be evaluated in parallel. We use 256-bit AVX-512VL to evaluate four 64-bit candidates per batch, covering all twelve directions in three batches. The benefit of four-way parallel evaluation outweighs the additional computation on invalid candidates.

Pipeline-Wide CPU Parallelism for Short Decoding Blocks

The central challenge in thread-level MWPM parallelization on the decoding graph is to partition the graph while preserving dual feasibility across partition boundaries during independent execution. Fusion Blossom [13] constrains local growth using temporary partition boundaries, then fuses the local matching states and resumes joint solving. Clustering-based approaches [14] instead preprocess the defect set to identify clusters of defects that can be processed independently during the current parallel stage. For short decoding blocks, limited computation is available to amortize these preparation and coordination costs, which can offset the time savings from parallel execution. Predecoding further reduces the remaining MWPM workload. We therefore retain sequential MWPM within each component and organize pipeline-wide CPU parallelism around independent components, state cleanup, and local predecoding.

First, the independently decoded X/ZX/Z connected components can be solved concurrently before their outputs are combined. We identify connected components using a disjoint-set data structure during decoder construction and assign each component a separate thread group and event priority queue, allowing independent event streams to advance concurrently. As decoding time decreases, reset operations—including restoring decoding-graph state and clearing defect and region state from the preceding shot—also become a significant cost. We overlap this work through double buffering: once the current result has been extracted and copied out, its workspace is reset while the next input is decoded in the other workspace. Figure 5 illustrates the overall thread organization and execution timeline.

Figure 5. Pipeline-wide CPU parallelism for short decoding blocks. Separate thread groups decode independent components concurrently. Within each component, two threads predecode disjoint temporal interiors, then synchronize before one thread processes the deferred conflict-band sources and, if needed, continues with MWPM. Two alternating workspaces overlap reset of the previous shot with decoding the next.

Building on this organization, we further parallelize predecoding within each component. In our tests, predecoding accounts for a substantial fraction of total decoding time, making it an important target for further acceleration. Compared with the dynamically evolving MWPM search, predecoding accesses a fixed neighborhood, allowing dependencies between concurrent operations to be determined from the local structure of the decoding graph.

Local operations, however, are not inherently independent. A predecoding operation can update one-hop neighbors, while candidate evaluation may read state up to two hops away. Operations with overlapping neighborhoods can therefore introduce read–write conflicts. Using the structured lattice, we partition each component along the measurement-time dimension and retain a three-layer conflict band around the partition boundary, as illustrated in Figure 5. Each stencil edge spans at most one measurement round. Deferring operations originating in this band therefore prevents either interior task from modifying state accessed by the other. Two threads first process their respective interiors concurrently, after which operations originating in the conflict band are executed sequentially. The matching and radius states produced by the partitions then jointly initialize MWPM on the complete component, which continues the search to complete the remaining matching.

Experimental Evaluation

We evaluate Beyond Blossom primarily on an Intel Xeon server, examining exact MWPM correctness (Section IV-B), amortized decoding time (Section IV-C), the contributions of algorithmic and architecture-aware optimizations and parallel execution (Section IV-D), and the mechanisms behind the speedup (Section IV-E). We further evaluate portability to the Arm-based Apple M4 Pro and its ability to meet real-time decoding requirements (Section IV-F).

Experimental Setup

We use rotated surface codes with d∈{9,13,17,21,25,29,33}d \in\{9, 13, 17, 21, 25, 29, 33\}, with each decoding block containing dd measurement rounds. Physical error rates are p∈{0.05%,0.1%,0.3}p \in\{0.05\%, 0.1\%, 0.3\}, yielding 21 settings. These distances cover larger code sizes relevant to resource estimates for fault-tolerant quantum computation [21], while the error rates span workloads ranging from sparse local errors to higher defect densities. We generate rotated surface-code memory-X circuits using Stim [27] under circuit-level noise. The after-Clifford depolarization, before-round data depolarization, before-measurement flip, and after-reset flip probabilities are all set to pp. Each input contains defect data from both the XX- and ZZ-check components.

Our experiments use a dual-socket Intel Xeon Gold 6230R server with 52 physical cores and a 14-core Apple M4 Pro. Both builds use C++20 and -O3, with GCC 12.2.0 on Xeon and Apple Clang 21.0.0 on M4 Pro. The Xeon and M4 Pro builds use AVX-512VL/AVX2 and NEON instructions, respectively.

Correctness

Beyond Blossom returns exactly the same total matching weight as PyMatching for every tested input. These results agree with our optimality analysis in Section III-A and validate Beyond Blossom’s exact MWPM decoding.

Comparison with Open-Source Decoders

We compare Beyond Blossom with PyMatching 2.3.1 [7], Parity Blossom, Fusion Blossom [13] from fusion-blossom 0.2.13, and two Union-Find implementations, UnionFind [28] and the union-find implementation in the ldpc library 2.4.1 (LDPC-UF). PyMatching is invoked through its native C++ interface, avoiding Python call overhead. All baselines use one physical core except Fusion Blossom, which is restricted to four physical cores. Timing includes per-shot preparation, decoding, output extraction, and state reset. Setup, warm-up, I/O, and validation are excluded.

Figure 6 shows that Beyond Blossom achieves the lowest amortized decoding time among the evaluated implementations across all 21 settings. Its largest speedups over PyMatching are 9.38×, 10.26×, and 7.33× at the three respective error rates. Even the Union-Find implementations, which typically trade decoding accuracy for simpler computation, are slower in these settings. Beyond Blossom thus achieves the best performance among the evaluated CPU implementations while preserving the exact MWPM objective.

Figure 6. Amortized decoding time versus code distance for the compared decoders at three physical error rates, with dd measurement rounds. Filled markers denote 10610^6 shots. Open markers denote 10410^4 shots, used when this setting would require prohibitively long runtimes.

The Beyond Blossom curve uses the most suitable configuration for each setting, employing one to eight physical cores. Small workloads typically favor single-threaded predecoding, whereas larger blocks benefit further from the Pipeline-Wide CPU Parallelism for Short Decoding Blocks described in Section III-C. The following ablation explains this transition.

Incremental Ablation

Figure 7 evaluates our optimizations incrementally against the state-of-the-art single-threaded PyMatching baseline. We first introduce the structured grid and SIMD computation (Section III-B), followed by degree-ordered predecoding (Section III-A), while retaining single-core execution. We then enable component parallelism, tail-processing optimizations with overlapped reset, and intra-component predecoding parallelism (Section III-C), using two, four, and eight physical cores, respectively. All speedups shown in Figure 7 are measured relative to PyMatching; differences between adjacent configurations show the incremental benefit of each optimization.

Figure 7. Incremental ablation of Beyond Blossom across code distances and physical error rates. Each cell reports amortized decoding time and speedup relative to PyMatching. PyMatching, the structured SIMD backend, and predecoding use one physical core. The successive parallel configurations use two, four, and eight physical cores.

For this ablation, all six variants process the same 10610^{6} independent shots per setting. We report amortized decoding time per shot after warm-up.

a) Architecture-aware optimizations: The structured representation and SIMD dual-phase computation provide larger benefits as the workload increases. Fixed-offset access to compact state reduces pointer chasing and improves cache-line utilization during neighborhood scans. At d=33d = 33, p=0.3%p = 0.3\%, the corresponding L2/L3 miss rates decreased from 60.212%/0.094% for PyMatching to 26.988%/0.017% for Beyond Blossom. At the same setting, the decoding time decreases from 954.41 μ\mus to 684.38 μ\mus, yielding a 1.39× speedup.

At d=9d = 9, p=0.05%p = 0.05\%, decoding time instead increases slightly, from 1.202 μ\mus to 1.286 μ\mus. The structured SIMD backend introduces input-organization, vector-packing, masking, and minimum-reduction costs. Vectorized scans also evaluate some candidates that scalar branches can discard early. For very small workloads, these costs can outweigh the benefits of regular memory access and parallel arithmetic.

b) Degree-ordered predecoding: Adding predecoding substantially reduces decoding time across all 21 settings, providing approximately 2.49–5.19× additional speedup over the preceding configuration. Resolving defects locally reduces the work entering the full MWPM search. This optimization is particularly effective at low error rates, where local error patterns are prevalent.

c) Pipeline-wide CPU parallelism: Independent X/ZX/Z components provide an opportunity for parallel execution, but exploiting it requires enough work to offset coordination costs. At p=0.1%p = 0.1\%, component parallelism increases decoding time from 1.831 μ\mus to 2.798 μ\mus for d=13d = 13, but reduces it from 46.568 μ\mus to 32.371 μ\mus for d=33d = 33, yielding a 1.44× speedup. As the error rate increases, component parallelism becomes beneficial at smaller code distances.

This crossover reflects the per-input costs of task dispatch, synchronization, and result merging. Small decoding blocks already have short sequential execution times, making these costs difficult to amortize. Serial input organization and unequal X/ZX/Z workloads further limit scaling: synchronization waits for the slower component, so practical speedups generally remain below 2×.

Tail-processing optimizations and reset overlap further reduce decoding time in 17 settings. As decoding approaches microsecond timescales, state maintenance accounts for an appreciable fraction of execution time. Overlapping cleanup of the previous input with decoding of the next reduces its exposed cost.

Finally, intra-component predecoding parallelism provides additional gains for larger workloads. At d=33d = 33, p=0.3%p = 0.3\%, decoding time decreases from 156.040 μ\mus to 130.151 μ\mus, reaching a cumulative 7.33× speedup over PyMatching. Smaller workloads can regress because of partitioning, synchronization, and sequential conflict-band processing.

Among the evaluated open-source CPU decoders, Beyond Blossom is the only implementation whose parallel execution surpasses the state-of-the-art single-threaded PyMatching baseline on short dd-round decoding blocks. Its additional gains over our optimized sequential configuration demonstrate the effectiveness of directing parallelism toward local predecoding and pipeline operations.

Understanding the Speedup

To isolate the effect of predecoding, we compare no predecoding, simple predecoding, and degree-ordered predecoding in Beyond Blossom, with all other settings fixed. The simple baseline omits degree ordering and uses equal-rate growth, with each endpoint contributing half the edge weight to a direct match. Our method orders defects by candidate degree and allocates growth according to the current dual constraints (Section III-A).

tbl:I reports complete decoding time, the mean number of defects left unmatched after predecoding, and the fraction of defects matched during predecoding. At p=0.3%p = 0.3\%, degree-ordered predecoding matches approximately 94.79%–95.18% of the initial defects. For d=33d = 33, the mean number of unmatched defects decreases from 1929.86 to 100.45, substantially reducing the number of unmatched roots entering the full solver. Complete decoding time, including predecoding when enabled, decreases from 382.49 μ\mus without predecoding to 156.51 μ\mus with degree-ordered predecoding.

ddNoneSimpleDegree-ordered
98.314.724.00
1318.7911.409.10
1741.9425.1918.80
2181.3748.9335.72
25143.4686.6562.43
29236.33141.97101.11
33382.49223.65156.51
ddNoneSimpleDegree-ordered
934.932.52 (92.79%)1.68 (95.18%)
13110.638.44 (92.37%)5.43 (95.09%)
17253.7320.04 (92.10%)12.69 (95.00%)
21485.7239.23 (91.92%)24.64 (94.93%)
25828.0467.93 (91.80%)42.45 (94.87%)
291302.48108.12 (91.70%)67.37 (94.83%)
331929.86161.61 (91.63%)100.45 (94.79%)

Table 1. Serial predecoding at p=0.3%p = 0.3\% with dd measurement rounds. (a) Amortized decoding time (μ\mus/shot). (b) Mean unmatched defects/shot (matched %).

Arm Portability and Processing Throughput

We evaluate Beyond Blossom on an Apple M4 Pro using the same workloads, selecting a suitable parallelization strategy for each combination of code distance dd and physical error rate pp. Each setting uses 10610^6 saved independent inputs; reported times are the median of three complete-batch mean times per shot. Beyond Blossom accelerates decoding across all 21 settings, with maximum speedups over PyMatching of 6.36×\times, 6.41×\times, and 5.02×\times at p=0.05%p = 0.05\%, 0.1%, and 0.3%, respectively.

To assess processing capacity, we divide the reported block decoding time by its dd measurement rounds. Figure 8 compares the resulting time per round with a 1 μ\mus measurement cycle, representative of the interval between measurement rounds in superconducting quantum processors [5]. Beyond Blossom meets this processing budget for every tested distance from d=9d = 9 to d=33d = 33 at both p=0.05%p = 0.05\% and p=0.1%p = 0.1\%. PyMatching reaches d=29d = 29 and d=21d = 21, respectively. At p=0.3%p = 0.3\%, Beyond Blossom extends the supported range to d=21d = 21, compared with d=9d = 9 for PyMatching. Overall, Beyond Blossom meets the budget in 18 of the 21 settings, compared with 11 for PyMatching.

Figure 8. Decoding time per measurement round on Apple M4 Pro (logarithmic yy-axis). The horizontal line marks 1 μ\mus/round.

On the M4 Pro, Beyond Blossom achieves lower amortized decoding time than on Xeon. The faster platform therefore allows the decoder to keep pace with the 1 μ\mus measurement cycle over a wider range of workloads.

Conclusion

We presented Beyond Blossom, a CPU-based MWPM decoder for surface codes. It combines degree-ordered local predecoding with structured graph storage, SIMD computation, and parallel execution to reduce decoding time while preserving MWPM optimality. On an x86 CPU, it achieves a 4.23×\times geometric-mean speedup on a single core and up to a 10.26×\times speedup with eight cores over single-threaded PyMatching. Results on Arm also demonstrate portability. Future work will focus on streaming decoding, GPU acceleration for batched workloads, and integration with quantum control systems to evaluate end-to-end feedback latency.

References

  1. [1]P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Physical Review A, vol. 52, no. 4, pp. R2493–R2496, 1995. [Online]. Available: https://doi.org/10.1103/PhysRevA.52.R2493
  2. [2]A. M. Steane, “Error correcting codes in quantum theory,” Physical Review Letters, vol. 77, no. 5, pp. 793–797, 1996. [Online]. Available: https://doi.org/10.1103/PhysRevLett.77.793
  3. [3]B. M. Terhal, “Quantum error correction for quantum memories,” Reviews of Modern Physics, vol. 87, no. 2, pp. 307–346, 2015. [Online]. Available: https://doi.org/10.1103/RevModPhys.87.307
  4. [4]A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” Physical Review A, vol. 86, p. 032324, 2012. [Online]. Available: https://doi.org/10.1103/PhysRevA.86.032324
  5. [5]Google Quantum AI and Collaborators, “Quantum error correction below the surface code threshold,” Nature, vol. 638, pp. 920–926, 2025. [Online]. Available: https://doi.org/10.1038/s41586-024-08449-9
  6. [6]L. Caune, L. Skoric, N. S. Blunt, A. Ruban, J. McDaniel, J. A. Valery, A. D. Patterson, A. V. Gramolin, J. Majaniemi, K. M. Barnes, T. Bialas, O. Buġdaycı, O. Crawford, G. P. Gehér, H. Krovi, E. Matekole, C. Topal, S. Poletto, M. Bryant, K. Snyder, N. I. Gillespie, G. Jones, K. Johar, E. T. Campbell, and A. D. Hill, “Demonstrating real-time and low-latency quantum error correction with superconducting qubits,” Nature Communications, vol. 17, p. 7383, 2026. [Online]. Available: https://doi.org/10.1038/s41467-026-73331-6
  7. [7]O. Higgott and C. Gidney, “Sparse Blossom: correcting a million errors per core second with minimum-weight matching,” Quantum, vol. 9, p. 1600, 2025. [Online]. Available: https://doi.org/10.22331/q-2025-01-20-1600
  8. [8]Y. Wu, N. Liyanage, and L. Zhong, “Micro Blossom: Accelerated minimum-weight perfect matching decoding for quantum error correction,” in Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ser. ASPLOS ’25. Association for Computing Machinery, 2025, pp. 639–654. [Online]. Available: https://doi.org/10.1145/3676641.3716005
  9. [9]N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum, vol. 5, p. 595, 2021. [Online]. Available: https://doi.org/10.22331/q-2021-12-02-595
  10. [10]S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code,” Physical Review A, vol. 90, p. 032326, 2014. [Online]. Available: https://doi.org/10.1103/PhysRevA.90.032326
  11. [11]J. Bausch, A. W. Senior, F. J. H. Heras, T. Edlich, A. Davies, M. Newman, C. Jones, K. Satzinger, M. Y. Niu, S. Blackwell, G. Holland, D. Kafri, J. Atalaya, C. Gidney, D. Hassabis, S. Boixo, H. Neven, and P. Kohli, “Learning high-accuracy error decoding for quantum processors,” Nature, vol. 635, pp. 834–840, 2024. [Online]. Available: https://doi.org/10.1038/s41586-024-08148-8
  12. [12]O. Higgott, “PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching,” ACM Transactions on Quantum Computing, vol. 3, no. 3, pp. 1–16, 2022, article 16. [Online]. Available: https://doi.org/10.1145/3505637
  13. [13]Y. Wu and L. Zhong, “Fusion Blossom: Fast MWPM decoders for QEC,” in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2023, pp. 928–938. [Online]. Available: https://doi.org/10.1109/QCE57702.2023.00107
  14. [14]R. Mikami and H. Yamasaki, “Sparse-Blossom decoding in o(1) time,” arXiv:2609.12262 [quant-ph], 2026. [Online]. Available: https://arxiv.org/abs/2609.12262
  15. [15]S. C. Smith, B. J. Brown, and S. D. Bartlett, “Local predecoder to reduce the bandwidth and latency of quantum error correction,” Physical Review Applied, vol. 19, no. 3, p. 034050, 2023. [Online]. Available: https://doi.org/10.1103/PhysRevApplied.19.034050
  16. [16]N. Alavisamani, S. Vittal, R. Ayanzadeh, P. Das, and M. Qureshi, “Promatch: Extending the reach of real-time quantum error correction with adaptive predecoding,” in Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ser. ASPLOS ’24. Association for Computing Machinery, 2024, pp. 818–833. [Online]. Available: https://doi.org/10.1145/3620666.3651339
  17. [17]M. J. Flynn, “Some computer organizations and their effectiveness,” IEEE Transactions on Computers, vol. C-21, no. 9, pp. 948–960, 1972. [Online]. Available: https://doi.org/10.1109/TC.1972.5009071
  18. [18]D. Horsman, A. G. Fowler, S. Devitt, and R. Van Meter, “Surface code quantum computing by lattice surgery,” New Journal of Physics, vol. 14, no. 12, p. 123011, 2012. [Online]. Available: https://doi.org/10.1088/1367-2630/14/12/123011
  19. [19]E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” Journal of Mathematical Physics, vol. 43, no. 9, pp. 4452–4505, 2002. [Online]. Available: https://doi.org/10.1063/1.1499754
  20. [20]A. Y. Kitaev, “Fault-tolerant quantum computation by anyons,” Annals of Physics, vol. 303, pp. 2–30, 2003.DOI
  21. [21]M. E. Berryman, P. Murali, M. Troyer, K. M. Svore, T. Hoefler, V. Kliuchnikov, G. H. Low, M. Soeken, A. Sundaram, and A. Vashchillo, “Assessing requirements to scale to practical quantum advantage,” arXiv:2211.07629 [quant-ph], 2022. [Online]. Available: https://arxiv.org/abs/2211.07629
  22. [22]C. Wang, J. Harrington, and J. Preskill, “Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory,” Annals of Physics, vol. 303, no. 1, pp. 31–58, 2003. [Online]. Available: https://doi.org/10.1016/S0003-4916(02)00019-2
  23. [23]J. Edmonds, “Paths, trees, and flowers,” Canadian Journal of Mathematics, vol. 17, pp. 449–467, 1965. [Online]. Available: https://doi.org/10.4153/CJM-1965-045-4
  24. [24]———, “Maximum matching and a polyhedron with 0,1-vertices,” Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, vol. 69B, no. 1–2, pp. 125–130, 1965. [Online]. Available: https://doi.org/10.6028/jres.069B.013
  25. [25]V. Kolmogorov, “Blossom V: a new implementation of a minimum cost perfect matching algorithm,” Mathematical Programming Computation, vol. 1, no. 1, pp. 43–67, 2009. [Online]. Available: https://doi.org/10.1007/s12532-009-0002-8
  26. [26]K. Datta, S. Kamil, S. Williams, L. Oliker, J. Shalf, and K. Yelick, “Optimization and performance modeling of stencil computations on modern microprocessors,” SIAM Review, vol. 51, no. 1, pp. 129–159, 2009. [Online]. Available: https://doi.org/10.1137/070693199
  27. [27]C. Gidney, “Stim: a fast stabilizer circuit simulator,” Quantum, vol. 5, p. 497, 2021.DOI
  28. [28]C.-Y. Park and K. Meinerz, “Open-source c++ implementation of the union-find decoder,” https://github.com/chaeeyunpark/UnionFind, 2020.

Paper details

vlnc:W_abwx4644
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents