Source-linked AI summary
Pipelined correlated minimum weight perfect matching of the surface code
Alexandru Paler, Austin G. Fowler
TL;DR
Correlated surface-code matching previously required repeated full-decoder runs to reweight the graph. This paper uses a staged pipeline with parallelizable reweighting and pre-matching, followed by full matching. Simulations support feasibility across three surface-code variants, with reported logical-error results practically unchanged from the earlier method.
Problem
Earlier correlated matching required multiple full-decoder runs and recomputation after reweighting, creating significant computational overhead.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
The correlated analysis is decoder agnostic, and graph reweighting is described as highly hardware compatible.
Source: §4 · p. 5The analysis assumes depolarizing noise, and uses w=-ln p as an approximation stated sufficient for usual p values.
Source: §2.1 · p. 2, §2 · p. 2
Abstract
from arXiv · showhide
We describe a pipeline approach to decoding the surface code using minimum weight perfect matching, including taking into account correlations between detection events. An independent no-communication parallelizable processing stage reweights the graph according to likely correlations, followed by another no-communication parallelizable stage for high confidence matching. A later general stage finishes the matching. This is a simplification of previous correlated matching techniques which required a complex interaction between general matching and re-weighting the graph. Despite this simplification, which gives correlated matching a better chance of achieving real-time processing, we find the logical error rate practically unchanged. We validate the new algorithm on the fully fault-tolerant toric, unrotated, and rotated surface codes, all with standard depolarizing noise. We expect these techniques to be applicable to a wide range of other decoders.
1 Introduction
Real-time, accurate surface-code decoding remains an open problem, and earlier correlated matching required repeated full-decoder runs after graph reweighting. The paper proposes a pipeline to reduce that overhead while retaining decoding performance.
1 Introduction
- Repeated full-decoder runs after correlation-based graph reweighting incurred significant overhead, with each reweighting costing O(d^6 log(d)).Reweighting erased partial matchings, requiring the entire matching to be recomputed from scratch [14] [20].Source: §1 · p. 1
- The proposed pipeline replaces repeated full decoding for reweighting with an O(d^2) pre-matching decoder and then performs matching on the reweighted graph.Its stages are pre-matching for reweighting, optional pre-matching on the reweighted graph, and a usual decoder using the pre-matched outputs and reweighted graph.Source: §1 · p. 1
- The work describes extracting circuit correlations and using round-by-round detection events to reweight the graph and partially match events.The introduction says the algorithm then proceeds without further graph reweighting [14] [17].Source: §1 · pp. 1–2
2 Methods
The methods represent likely errors as weighted detection-graph edges and use correlation analysis and parallel pre-matching to reweight the graph and produce partial matchings for a later decoder.
2 Methods
- The method performs correlated reweighting and initial partial matching round by round, without backtracking or revision and without sacrificing logical error rate.Edge weights are chosen so the most probable error corresponds to a minimum-weight matching; the work uses w=-ln p as an approximation stated sufficient for usual p values.Source: §2 · p. 2
2.1 Correlated pre-analysis of the surface code
- Gate errors are catalogued by their detection-event coordinates, then grouped as single events, pairs, or 2+ events to build the correlation representation.For 2+ events, errors are decomposed into basis edges and recorded with their decompositions for later correlated analysis.Source: §2.1 · pp. 2–3
- Edge probabilities are approximated by grouping associated errors by gate and estimating the probability of exactly one independent error, avoiding inaccurate sums that can exceed 1.The resulting edge probability combines the base probability and correlated probability as pf=pe+pc.Source: §2.1 · p. 3
2.2 Correlated reweighting and pre-matching
- Parallel pre-matching selects each event’s lowest-weight neighbor, breaks ties by canonical edge order, and pairs events only when their choices are mutual.The illustrated graph uses vertical, horizontal, and diagonal edge weights of 4, 6, and 8, respectively.Source: §2.2 · p. 3, Figure 2 · p. 3
- A virtual pre-matching associates nearby edges with correlated probabilities, approximates pf=pe+pc, and converts that probability to a new weight with w=-ln pf.Further pre-matching rounds are optional; the retained partial matches and reweighted graph can be passed to a general matching algorithm or another decoder.Source: §2.2 · pp. 3–4
3 Results
The results compare correlated and uncorrelated decoding for toric, unrotated, and rotated surface codes under standard depolarizing noise. For the unrotated simulations, results are indistinguishable from those reported in [14].
Simulation setup
- Simulations compare toric, unrotated, and rotated surface codes with and without correlated graph reweighting, using standard equal-duration 8-step CNOT-based circuits and equal-probability depolarizing noise.Initialization and measurement, single-qubit gates, and CNOT gates receive the stated standard depolarizing errors.Source: §3 · p. 4
Toric surface code
- For the toric code, high-distance data curves at high gate error rates are steeper than the p^2–p^5 asymptotic lines, indicating stronger logical-error suppression in that regime.Figure 4 compares uncorrelated pink and correlated black curves for distances 3–9.Source: Figure 4 · p. 4
Unrotated and rotated surface codes
- The unrotated and rotated code figures each compare correlated and uncorrelated simulations across distances 3–9.Figure 5 uses red and blue curves for the unrotated code; Figure 6 uses green and orange curves for the rotated code.Source: Figure 5 · p. 4, Figure 6 · p. 4
4 Conclusion
The conclusion presents a no-communication, parallelizable pipeline for processing surface-code detection events. Simulations on toric, unrotated, and rotated codes support its feasibility.
4 Conclusion
- The method processes streaming detection events through parallelizable stages requiring no communication, as a step toward real-time surface-code decoding.The pipeline stages are reweighting, pre-matching, and full-matching; the first two use a novel correlated-error analysis.Source: §4 · p. 5
- The correlated analysis is decoder agnostic, and graph reweighting is described as highly hardware compatible.The conclusion envisions dedicated hardware producing a reweighted graph, with optional partial matching, for another decoder.Source: §4 · p. 5
- Simulations on toric, rotated, and unrotated surface codes support pipeline feasibility; extending the results to other decoder types is future work.Source: §4 · p. 5
A Appendix: Pre-matching
Pre-matching is a fast, best-effort procedure that uses local information to identify potential matches and determine which graph edges should be reweighted. It initializes vertex states and processes detection events using their neighborhood-edge weights.
A Appendix: Pre-matching
- Pre-matching is a fast, best-effort procedure that informs later pipeline stages but is not guaranteed to have a threshold or work as a standalone full error-correction decoder.It is used to compute which graph edges should be reweighted.Source: A Appendix: Pre-matching · p. 6
- The procedure initializes detection-graph vertices to ZP, then updates their states using the weights of neighboring edges.It uses the neighboring vertex connected by a minimum-weight edge.Source: A Appendix: Pre-matching · p. 6
- Detection events have coordinates (t,i,j), and the algorithm processes them in temporal order, with later events having higher t.The temporal ordering affects how states are assigned and transformed.Source: A Appendix: Pre-matching · p. 6
- With sorted edge lists, pre-matching has total complexity O(d2), since detection-event count scales quadratically with code distance d.Without sorted edges, selecting a minimum-weight edge requires iterating through the edge list.Source: A Appendix: Pre-matching · p. 6
- Figure 7 depicts events processed by time, row, and column, their weighted detection graph, and the graph after time layers are removed from view.In the example, only A and C have edges to the patch boundary.Source: Figure 7 · p. 6
A.1 Pre-matching condition (PMC)
The pre-match condition (PMC) determines directed pre-matches between detection events, which become full pre-matches when both directions hold. Its strict form ensures valid minimum-weight matchings, while its relaxed form permits more pre-matches without that guarantee.
A.1 Pre-matching condition (PMC)
- PMC checks are processed in increasing time, then increasing i-coordinate, then increasing j-coordinate.The pre-match order shown in Figure 8 is A, B, C.Source: §A.1 · p. 7, Figure 8 · p. 7
- A full pre-match A↔B requires both directed conditions, A→B and A←B, reflecting the temporal ordering of the events.A→B checks from the earlier event toward the future; A←B checks from the later event toward the earlier one.Source: §A.1 · p. 7
- A strict PMC sets A→B only when B is A’s sole low-weight neighbor, ensuring pre-matched events are valid minimum-weight matchings.The relaxed PMC allows more pre-matches but does not guarantee they form minimum-weight matches.Source: §A.1 · p. 7
- When a future event B satisfies A→B, B becomes HP and stores a reference to A; if the reverse condition points back to A, B changes to FP.The transition rules depend on which event is being processed in the temporal order.Source: §A.1 · p. 7, Table 1 · p. 7
A.2 Vertex state updates
Vertex-state updates handle past and future neighbors differently while ensuring that processed events end in either ZP or FP. Boundary connections can automatically make an event FP, and state-transition checks support correctness in parallel processing.
A.2 Vertex state updates
- A ZP event that can connect to the boundary is automatically changed to FP, after which processing advances to the next event.The boundary case is handled before the other state-transition procedure.Source: §A.2 · p. 7
- Figure 9 illustrates a boundary-connected A becoming FP, followed by C resetting to ZP when its lowest-weight option is excluded by A’s FP state.The figure’s example uses a=5 and b=4.Source: Figure 9 · p. 8
- For a past neighbor B, an HP event A becomes FP if its backward reference points to B; otherwise A resets to ZP.If B is already FP, a reference from A to B is an error; otherwise A resets to ZP.Source: §A.2 · p. 8
- For a future neighbor B, two ZP events make B HP with a reference to A; if both are HP, both reset to ZP.Other future-neighbor cases include resetting A or B when the required PMC direction or reference is not fulfilled.Source: §A.2 · p. 8
- Before processing, only ZP and HP are valid; afterward, only ZP and FP are valid, and inconsistent states raise an error.The rules provide checks for concurrent access in multi-threaded or distributed stream processing.Source: §A.2 · p. 8
A.3 Pre-matching with the boundary
Pre-matching generally avoids boundary matches because a locally lowest-weight boundary choice may not minimize the global weight sum. A boundary match is still allowed under a neighborhood-state condition.
A.3 Pre-matching with the boundary
- Pre-matching aims to pair detection events and avoid boundary matches, since a locally lowest-weight boundary choice may not be best for the global weight sum.The authors state that this is generally the case, not an absolute rule.Source: §A.3 · pp. 8–9
- A boundary match is allowed when the processed event has no neighboring detection event in state FP or HP.The paper assumes this choice will not produce a low-weight global matching when two neighboring events could both connect to the boundary.Source: §A.3 · p. 9
- The authors note that boundary-near events are proportionally more common at small code distances, while their heuristic is intended to yield more realistic-looking matches at larger distances.They frame decoding performance at large distances as the priority.Source: §A.3 · p. 9