PaperlayerView exact revision on arXiv

Source-linked AI summary

Decoding algorithms for surface codes

Antonio deMarti iOlius, Patricio Fuentes, Román Orús, Pedro M. Crespo, Josu Etxezarreta Martinez

arXiv:2307.14989v6quant-ph

TL;DR

Quantum noise threatens reliable quantum computation, and decoding must estimate errors quickly enough to support correction. This review surveys and compares surface-code decoders and software; it identifies trade-offs among decoder performance and complexity, including a 50% threshold for the XZZX code. Some approaches also have scope limits, such as neural decoders’ training costs or MaxSAT’s restricted noise assumptions.

  • Problem

    Quantum noise and faulty syndrome measurements complicate error correction, while decoders must estimate errors without delaying correction.

    Source: §1 · p. 2, §5.1.4 · p. 17

  • Method

    The review describes and compares surface-code decoding algorithms by performance and complexity, and surveys available methods and software.

    Source: §1 · p. 3

  • Results

    The discussion identifies MWPM as a strong rotated-planar candidate for high threshold and almost linear expected complexity, while the XZZX code reaches a 50% threshold.

    Source: §6 · pp. 43, 46

  • Takeaways & Limitations

    Decoder choice involves balancing speed against consideration of more error configurations, and expected complexity offers an average-runtime benchmark alongside worst-case complexity.

    Source: §6 · p. 45

    Neural-network training cost may scale exponentially with code distance, and most NN decoders have been tested only for distances d < 10.

    Source: §5.5.3 · p. 39

Abstract

from arXiv · show

Quantum technologies have the potential to solve certain computationally hard problems with polynomial or super-polynomial speedups when compared to classical methods. Unfortunately, the unstable nature of quantum information makes it prone to errors. For this reason, quantum error correction is an invaluable tool to make quantum information reliable and enable the ultimate goal of fault-tolerant quantum computing. Surface codes currently stand as the most promising candidates to build near term error corrected qubits given their two-dimensional architecture, the requirement of only local operations, and high tolerance to quantum noise. Decoding algorithms are an integral component of any error correction scheme, as they are tasked with producing accurate estimates of the errors that affect quantum information, so that they can subsequently be corrected. A critical aspect of decoding algorithms is their speed, since the quantum state will suffer additional errors with the passage of time. This poses a connundrum, where decoding performance is improved at the expense of complexity and viceversa. In this review, a thorough discussion of state-of-the-art decoding algorithms for surface codes is provided. The target audience of this work are both readers with an introductory understanding of the field as well as those seeking to further their knowledge of the decoding paradigm of surface codes. We describe the core principles of these decoding methods as well as existing variants that show promise for improved results. In addition, both the decoding performance, in terms of error correction capability, and decoding complexity, are compared. A review of the existing software tools regarding surface codes decoding is also provided.

1 Introduction

Quantum noise makes reliable quantum computation depend on error correction, but decoding must balance accuracy against speed. This review introduces surface-code decoding methods, compares their performance and complexity, and surveys available software.

1 Introduction

  • Quantum noise arises from imperfect operations and unavoidable environmental interactions, making quantum errors a central obstacle to practical computing.The paper distinguishes engineering imperfections from decoherence.Source: §1 · p. 2
  • Decoding infers errors from syndrome measurements, but degeneracy makes optimal decoding #P-complete and creates a trade-off between accuracy and decoding time.Decoders must act quickly enough to correct the state before further errors or decoherence.Source: §1 · p. 3
  • Surface codes suit near-term quantum processors through two-dimensional layouts, local syndrome measurements, and high tolerance to quantum noise.The review notes their relevance to platforms with restricted qubit connectivity.Source: §1 · p. 3
  • The review explains MWPM, UF, BP, and TN decoders, compares performance under depolarizing and biased noise with computational complexity, and surveys other methods and software.Its scope includes simulations and a comparison of rotated planar code decoders.Source: §1 · p. 3

2 Background

The background introduces quantum noise and error correction, then develops stabilizer-code and syndrome concepts needed to frame surface-code decoding. It distinguishes most-likely-error decoding from the optimal coset-based rule and their complexity costs.

2 Background

  • Quantum error correction protects logical information using physical qubits, while error mitigation instead estimates observables from noisy circuits.The paper cites a logical error probability on the order of 10^-14–10^-15 as a requirement for fault-tolerant Shor’s algorithm.Source: §2 · p. 4, §2.1 · p. 4

2.1 Stabilizer Codes

  • Stabilizer codes encode k logical qubits into n physical qubits using an abelian subgroup of Pauli operators, and code distance relates to the maximum error weight correctable.Checks are measured indirectly to obtain a syndrome that records each error’s commutation relationship with the checks.Source: §2.1 · pp. 4–5
  • Degenerate errors can share a syndrome and act equivalently on the encoded state, so decoding may succeed with an error from the same degenerate coset.An estimate outside the correct error or its degenerate coset induces a non-trivial logical action and fails correction.Source: §2.1 · p. 5

2.2 The decoding problem

  • QMLD selects the most likely error matching the syndrome and reduces to minimum-weight decoding under i.i.d. noise, whereas DQMLD selects the most likely compatible coset.DQMLD is optimal for stabilizer codes but is #P-complete; QMLD is NP-complete and less computationally expensive.Source: §2.2 · pp. 5–6

3 The surface Codes

The section introduces planar and rotated surface-code layouts, their local check structure, and the logical errors that motivate code-distance and threshold considerations. It explains how syndromes arise and why performance depends on both code distance and noise model.

3 The surface Codes

  • The planar code removes toric-code periodic boundaries to encode one logical qubit, while the rotated planar code reduces the physical-qubit count to d^2.The tutorial focuses on rotated planar codes with a square lattice and CSS structure, while noting that its decoding methods apply to other surface codes.Source: §3 · p. 6

3.1 Stabilizer and check structure

  • CSS surface codes use X-checks to detect X-errors and Z-checks to detect Z-errors, with local check operators arranged to commute.Adjacent checks commute either by sharing the same operator type or by anticommuting on two shared data qubits.Source: §3.1 · pp. 6–7
  • Odd numbers of susceptible data-qubit errors trigger a check measurement, while even numbers can cancel and remain undetected by that check.The check circuits use measurement qubits coupled to adjacent data qubits.Source: §3.1 · p. 7

3.2 Types of errors and code threshold

  • Logical errors are boundary-spanning chains with trivial syndrome that act nontrivially on the codespace; multiplying by stabilizers can change their physical path without changing their action.Increasing code distance raises the minimum weight of a logical error, but improves performance only below the noise-model-dependent threshold.Source: §3.2 · pp. 8–9

4 Noise models

The section surveys noise sources and the models used to represent them in quantum error correction, from decoherence to operational errors and erasures. It explains how twirling and multi-qubit assumptions make noise models tractable for code analysis.

4 Noise models

  • The review distinguishes code-capacity, phenomenological, and circuit-level noise models, while noting that coherent, non-Markovian, and correlated errors are often neglected.It focuses on active error correction, where errors are detected and corrected rather than passively suppressed.Source: §4 · p. 9

4.1 Decoherence

  • Decoherence includes energy relaxation, pure dephasing, and thermal excitation, which describe different ways the environment affects a qubit.The section describes Markovian noisy evolution using quantum channels, represented by Kraus operators.Source: §4.1 · pp. 9–10

4.2 Twirled quantum channels

  • Twirling replaces general channels with Pauli channels that can be simulated classically; Pauli and Clifford twirls yield biased and depolarizing models, respectively.A code correctable for the twirled channel is also correctable for the original channel.Source: §4.2 · pp. 10–11

4.3 Noise models for multiple qubits

  • The multi-qubit models assume independent errors, distinguishing identically distributed noise from per-qubit error probabilities that vary across the system.The text cautions that independence is not universal and notes that nearest-neighbor correlations may be considered.Source: §4.3 · p. 11

4.4 SPAM and gate errors

  • SPAM errors affect preparation and measurement, while gate errors are modeled by applying depolarizing channels after single- and two-qubit operations.The section also allows biased circuit-level noise by replacing those depolarizing channels with Pauli channels.Source: §4.4 · pp. 11–12

4.5 Erasure errors

  • Erasure errors mark a known qubit location as lost, allowing its reinitialization; leakage and physical loss are identified as mechanisms that can produce erasures.The text distinguishes erasure from deletion, in which the qubit is effectively removed from the system.Source: §4.5 · p. 12

5 Decoders for surface codes

Decoding estimates the error from measured syndrome data so that a recovery operation can be applied. The section surveys surface-code decoders and their variants, emphasizing the trade-off between correction performance and computational complexity.

5 Decoders for surface codes

  • A decoder infers an error from the measured syndrome, and its estimate determines the recovery operation applied to the qubits.The effectiveness of decoding is critical to quantum error correction.Source: §5 · p. 12
  • Decoder accuracy and computational complexity trade off, while decoding must be fast enough to limit additional errors during inference.The code threshold depends on the decoder used.Source: §5 · pp. 12–13
  • The review compares minimum-weight perfect matching, Union-Find, belief propagation, and tensor-network or matrix-product-state decoders, alongside variants and other algorithms.It also surveys public software implementations.Source: §5 · p. 13

5.1 The Minimum Weight Perfect Matching Decoder

MWPM decodes X- and Z-check syndromes through separate minimum-weight matchings, with implementations and modifications addressing speed and noise-model fit. Its performance depends on the noise model, and measurement errors require space-time decoding.

5.1 The Minimum Weight Perfect Matching Decoder

  • MWPM builds separate X- and Z-check graphs and chooses the minimum-weight perfect matching to estimate an error consistent with the measured syndrome.It uses virtual checks at boundaries and maps matched paths back to data-qubit errors.Source: §5.1 · pp. 13–14

5.1.1 Complexity

  • The expected MWPM runtime is roughly O(N^2), while sparse blossom has observed O(N^1.32) complexity and Fusion Blossom has O(N) complexity.Sparse blossom is faster single-threaded, whereas Fusion Blossom can be faster with enough cores.Source: §5.1.1 · p. 15

5.1.3 Modifications and re-weighting for specific noise models

  • Reweighting can adapt MWPM to nonuniform qubit error probabilities or pass information between X and Z subgraphs to account for correlations in Y errors.The standard decoder assumes equal qubit probabilities and decodes the two subgraphs independently.Source: §5.1.3 · p. 16

5.1.2 Performance and threshold

  • MWPM has higher logical error probabilities and a lower threshold under biased noise than under depolarizing noise, because independent decoding can leave the denser Z-subgraph less accurately matched.The physical error probability is fixed in the comparison; increasing bias further lowers the threshold.Source: §5.1.2 · p. 16, Figure 8 · p. 17

5.1.4 Measurement errors

  • Measurement errors can cause logical errors in single-round decoding; repeated measurements produce a space-time graph that accounts for them, though thresholds remain below the perfect-measurement case.The text notes that distance-d codes usually record d measurement rounds, increasing graph size and decoding complexity.Source: §5.1.4 · p. 17

5.2 Union-Find decoder

The Union-Find decoder transforms syndrome decoding under Pauli noise into erasure decoding through syndrome validation and peeling, with near-linear complexity. Its lower thresholds than MWPM for the biases considered are balanced against low complexity and support for erasure errors.

5.2 Union-Find decoder

  • UF turns Pauli-noise decoding into erasure decoding through syndrome validation followed by peeling, with decoding complexity O(nα(n)).Here α is the inverse Ackermann function and is at most 3 for practical purposes.Source: §5.2 · pp. 17–18

5.2.1 Syndrome validation

  • Odd-parity checks grow as clusters that merge and update parity; growth stops when a cluster becomes even, reaches a virtual qubit, or merges with a cluster frozen at a virtual qubit.The validation uses separate graphs for X-checks and Z-checks.Source: §5.2.1 · p. 18

5.2.2 Erasure decoder

  • Peeling selects a spanning tree for each cluster and removes leaves toward a root, recording an edge as a decoded error when its leaf is a non-trivial check.A cluster spanning between open boundaries is split into two spanning trees; trivial-check leaves are removed without recording a matching.Source: §5.2.2 · pp. 18–19

5.2.3 Performance and threshold

  • UF achieves smaller code thresholds than MWPM for all considered biases; peeling can miss links between the closest non-trivial syndrome elements.The comparison is for the rotated planar code under depolarizing noise; the text attributes the performance decrease to these non-optimal choices.Source: §5.2.3 · p. 19, Figure 11 · p. 20, Table 2 · p. 20

5.2.4 Measurement errors

  • Measurement errors are handled by running validation and peeling on a space-time graph, whose added complexity motivates truncated UF methods to retain speed without losing too much decoding success.Reweighting methods for these space-time graphs are also discussed.Source: §5.2.4 · pp. 20–21
  • UF also handles mixtures of Pauli and erasure errors, and its cluster-growth process has inspired methods to reduce MWPM complexity.Its use for QLDPC decoding has been studied, but the complexity problem in that setting remains unaddressed.Source: §5.2.4 · p. 21

5.3 Belief Propagation

This section surveys belief-propagation decoding for quantum codes, including its message-passing approach and BP-OSD postprocessing. It covers complexity and threshold tradeoffs, decoding measurement and circuit-level noise, and belief-matching and single-shot BPOSD proposals.

5.3 Belief Propagation

  • BP exchanges messages on a Tanner graph to approximate variable-node marginal probabilities; it is exact on trees and a heuristic on loopy code graphs, especially when loops are large.For error-correction codes, BP is the paper’s term for the message-passing algorithm also known as the Sum-Product Algorithm.Source: §5.3 · pp. 21–22

5.3.1 BP: Specifics

  • For CSS codes, BP runs simultaneous classical decoders on the X- and Z-error parity-check matrices to estimate qubit-wise most likely errors, which need not equal the global QMLD optimum [118].The decoder iteratively exchanges variable- and check-node messages, updates beliefs, and stops when the estimated syndrome matches the measured syndrome or the iteration limit is reached.Source: §5.3.1 · pp. 22–23

5.3.2 Aftermath of neglecting DQMLD

  • Rotated planar codes exhibit no threshold under BP decoding because degeneracy-induced split beliefs become more prevalent as code size grows.This symmetric degeneracy error phenomenon arises when many similarly weighted operators produce broad qubit-wise marginals despite a sharply peaked logical-coset probability; Figure 13 illustrates logical error probability under depolarizing noise.Source: §5.3.2 · p. 24, Figure 13 · p. 24

5.3.3 Enhanced Belief Propagation: Quantum Ordered Statistics Decoding

  • BP-OSD combines BP with qOSD post-processing, using BP soft outputs to select a least-reliable independent-column basis and break split-belief symmetries.The unique solution from the selected full-rank submatrix matches the syndrome; ordering bits by their final BP likelihoods guides the basis choice.Source: §5.3.3 · p. 25
  • OSD-0 reorders parity-check columns by [OG] ranking, selects the first n−k = rank(H) linearly independent columns as the least-reliable set, solves the syndrome equation there, and maps the solution back to original bit order.OSD-w considers nonzero assignments to complementary bits to seek lower-weight solutions, using a greedy combination-sweep strategy because testing all configurations is intractable beyond small n.Source: §5.3.3 · p. 26

5.3.4 OSD Complexity

  • BP has complexity O(nj), OSD-0 is at most O(n^3), and exhaustive OSD-w is O(n^3 + n^2w); OSD-0 captures most qOSD gains and may be the only real-time option.Combination sweep is approximately O(w^αn^3); stabilizer inactivation has worst-case O(n^2logn) and achieved a higher threshold for generalized bicycle codes [132].Source: §5.3.4 · p. 27

5.3.5 Performance and threshold

  • BPOSD-0 gives BP a 0.139 probability threshold under depolarizing data-qubit noise, while higher orders can expand the threshold at greater complexity and Z-noise bias can impair decoding.BP alone has no probability threshold; the denser Z-check subgraph under Z-noise bias is described as more prone to failure.Source: §5.3.5 · p. 28, Figure 15 · p. 28

5.3.6 Measurement errors

  • Belief-matching uses sum-product belief-propagation soft outputs to set MWPM graph weights; for circuit-level noise, it achieved a 0.94% threshold, comparable to belief-find’s 0.937% [65].Its circuit-level Tanner graph incorporates surface-code measurement circuits and requires O(d) measurement rounds.Source: §5.3.6 · p. 28
  • Soft syndrome information feeds uncertainty in noisy measurements into BP, but the cited QLDPC study considered SPAM errors only [134]; soft-information MWPM and UF decoders improved thresholds under circuit-level noise.Circuit-level BPOSD can instead use a parity-check matrix whose columns encode single error mechanisms, but the larger matrix must be inverted [111] [123].Source: §5.3.6 · pp. 28–29
  • Single-shot BPOSD jointly decodes data errors and noisy syndrome measurements for the 4D toric code, with better thresholds than multiple-measurement and cellular-automaton alternatives under phenomenological noise.The study did not consider full circuit-level noise; single-shot decoding avoids the usual O(d) measurement rounds.Source: §5.3.6 · p. 29

5.4 The Tensor Network decoder

Tensor-network decoding approximates degenerate maximum-likelihood decoding by contracting code tensors, with bond-dimension truncation controlling the approximation. For the rotated planar code, it reports a 0.185 threshold at χ = 16, alongside substantial complexity costs.

5.4 The Tensor Network decoder

  • The decoder seeks an error matching the observed syndrome, then selects the most probable logical coset; it is also called MLD, a label that obscures its degenerate-decoder character.The recovered operation combines the syndrome-matching error with the selected logical operator.Source: §5.4 · p. 29

5.4.1 Introduction to TNs

  • The decoder represents the code as a tensor network, contracts columns, and truncates growing bond dimensions to obtain an approximate result with defined polynomial runtime.QR decomposition and SVD are used for truncation; without it, bond dimensions grow exponentially during contraction.Source: §5.4.1 · p. 30, Figure 17 · p. 30

5.4.2 TN decoding for the planar code

  • For planar codes, contracting the network sums products of error probabilities over stabilizer combinations to estimate error-class probabilities, with χ controlling the approximation.The most probable logical coset is selected using these probabilities.Source: §5.4.2 · pp. 30–31

5.4.3 TN decoding for the rotated planar code

  • For rotated planar codes, stabilizer nodes are split and contracted with adjacent data-qubit nodes to form a PEPS that can be decoded with the tensor-network method.The decoding process builds an error matching the syndrome, computes probabilities for four logical cosets, and recovers using the most probable one.Source: §5.4.3 · p. 32

5.4.4 Performance and threshold

  • Tensor-network decoding also suffers significantly under biased noise; studies have explored improving performance and convergence with lower χ.The cited table reports threshold values across bias settings, but the supplied passages do not state those values.Source: §5.4.4 · pp. 32–33, Table 4 · p. 33
  • 0.185 is the tensor-network decoder’s highest code threshold among methods considered, under depolarizing noise at bond dimension χ = 16.Figure 22 shows logical error probability versus physical error probability for the rotated planar code.Source: §5.4.4 · p. 32, Figure 22 · p. 33

5.4.5 Complexity

  • The decoder’s truncation cost is O(nχ^3) and dominates its complexity; χ must grow exponentially with code distance, and the method is many orders of magnitude slower than experimental MWPM implementations.The authors identify this runtime as a constraint on possible real-time use.Source: §5.4.5 · p. 33

5.4.6 Measurement errors

  • With measurement errors, decoding requires space-time syndrome extraction represented as a tensor network, and the added complexity accompanies the best performance in Google’s experimental rotated code.The cited approach constructs a Tanner graph, rewrites it as a tensor network, and planarizes and contracts it under truncation.Source: §5.4.6 · p. 33

5.5 Other decoders

This section surveys decoders beyond MWPM, UF, BPOSD, and TN, including methods for code families such as toric and color codes, and describes their mechanisms, reported capabilities, and limitations. It also presents a LightsOut-based MaxSAT decoder for color codes, noting its strong bit-flip threshold and limited demonstrated scope.

5.5.1 Cellular-automaton decoder

  • The cellular-automaton decoder uses local probabilistic charge motion guided by an auxiliary electrostatic field; colliding non-trivial cells are matched and the process ends when all checks are trivial.The auxiliary automaton evolves the field, and its field velocity must grow logarithmically with the auxiliary matrix size to establish meaningful fields.Source: §5.5.1 · pp. 34–35
  • Cellular-automaton decoders report an 8.2% threshold for 2D toric codes and 15.5% for cubic toric codes with the sweep rule; MWPM reaches 10.31% for 2D toric codes.The cited noise model is primarily i.i.d. phase-flip noise. The 2D and 3D cellular automata require log5(d) and log3(d) updates, respectively, while the sweep decoder has O(d) runtime.Source: §5.5.1 · p. 35
  • Cellular-automaton decoders are described as single-shot: they can handle measurement errors in one decoding round.Other decoders typically address noisy syndromes with d measurement rounds and a space-time graph.Source: §5.5.1 · p. 35

5.5.2 Renormalization group decoder

  • RG decoding approximates the toric code as overlapping concatenated blocks, passes soft logical-error information between layers, and uses belief propagation to reconcile shared-qubit probabilities.Small open-boundary toric-code blocks can be decoded by brute force; proposed extensions include color, cubic, qudit, and four-dimensional toric codes, while rotated planar-code use has not been investigated.Source: §5.5.2 · p. 36
  • BP+RG reaches a 16.5% threshold, versus 7.8% for standard RG and 15.5% for MWPM under depolarizing noise.The review notes that BP+RG exceeds MWPM alone but not the tensor-network decoder’s 17%–18.5% threshold; it also incurs BP complexity. Standard RG has O(d) complexity with complete parallelization and O(d2 log d) serially, and faulty measurements require d rounds.Source: §5.5.2 · pp. 36–37

5.5.3 Neural-network decoders

  • Neural-network decoding classifies the logical Pauli among I, X, Y, and Z after removing the syndrome-producing pure error; its recovery matches the syndrome but is not guaranteed minimum-weight.The method requires training, and training cost may scale exponentially with code distance; the review notes that most NN decoders have been tested only at d < 10, while NN+UF for toric codes was tested up to d = 255.Source: §5.5.3 · pp. 37–39
  • The original neural-network decoder performs similarly to MWPM on rotated planar codes at d ∈ {3, 5, 7}; deep neural networks improve the threshold at higher complexity, while reinforcement learning has almost linear complexity but a worse threshold.For circuit-level noise, the NN decoder matches MWPM, but requires approximately d measurement rounds and training specific to the noise model.Source: §5.5.3 · pp. 38–39

5.5.4 MaxSAT decoder

  • The MaxSAT decoder applies a LightsOut analogy to color-code decoding under bit-flip noise, mapping data qubits to switches and the syndrome to the initial light configuration.Source: §5.5.4 · p. 39
  • The decoder maps color-code decoding to LightsOut and formulates the minimum switch set matching the syndrome as a MaxSAT problem.The formulation uses satisfiability constraints to match the syndrome and soft constraints to minimize the error weight.Source: §5.5.4 · pp. 39–40
  • The MaxSAT color-code decoder reaches a 10.1% threshold for bit-flip noise, near MPS/TN’s 10.9% and above MWPM’s ≈9%, UF’s 8%, and RG’s 7.8%.Its runtime is slower than MWPM, UF, and RG but faster than TN; the NP-hard decoder runs faster at lower physical error rates.Source: §5.5.4 · p. 40
  • The approach is limited to bit-flip noise, assumes the LightsOut analogy, and has not considered faulty measurements; its operation under circuit noise is unclear.Generalizations to other noise structures, including depolarizing noise, and other topological codes are proposed as future work.Source: §5.5.4 · p. 40

5.6 Software Packages

The review surveys open-source tools for simulating surface-code decoders and shows which packages support which decoder families. It also describes tools for generating circuit-level noise samples.

Software Packages

  • Stim rapidly samples circuit-level noise, while Plaquette combines Stim with several decoder packages for integrated testing.Stim is reported to sample d = 100 surface-code circuits at about 1,000 shots per second in approximately 15 seconds.Source: §5.6 · p. 40
  • Pymatching is described as the quickest popular serial MWPM implementation; Fusion Blossom enables parallel decoding and can surpass it with enough nodes.Plaquette incorporates both packages, alongside QECSIM, which also simulates MWPM.Source: §5.6 · p. 40
  • Qsurface implements standard and node-suspension UF decoders, while Plaquette includes another UF implementation; the LDPC package provides BPOSD for QLDPC codes.Qsurface authors claim the modified UF decoder improves threshold while maintaining complexity; BPOSD surface-code simulations require the code's parity-check matrix.Source: §5.6 · pp. 40, 42
  • QECSIM supports a tunable-truncation tensor-network decoder, and SweepContractor implements a tensor-network decoder based on the sweep-line algorithm.Source: §5.6 · p. 42
  • Sweep-Decoder-Boundaries implements the sweep-rule cellular automaton with circuit-level noise; LocalToricDecoder implements Toom’s rule, while other discussed variants lack located packages.Source: §5.6 · p. 42
  • The reviewed repositories also cover neural-network decoders for toric, rotated planar, and color codes, a MaxSAT decoder, and an RG implementation reported as unmaintained.The MaxSAT decoder is included in QECC, a broader QEC tool described as being in early development; Figure 32 maps decoder families to supporting packages.Source: Figure 32 · p. 41, §5.6 · p. 42

6 Discussion

The discussion compares decoder accuracy and complexity while emphasizing that hardware noise and decoding delay shape real-time choices. It concludes that the best decoder for an experimental surface code remains an open question.

Decoder trade-offs

  • MWPM is presented as a strong rotated-planar candidate, UF as fast, BPOSD as suited to general QLDPC codes, and TN as highest-threshold but most complex.The review says TN explicitly targets maximum-likelihood decoding; its bond dimension limits practical computation, and decoder trade-offs are illustrated in Figure 33.Source: §6 · pp. 43–44, Figure 33 · p. 43

Experimental implementations

  • Reported experiments used a single syndrome-measurement round and post-processing rather than real-time decoding, despite demonstrating decreasing experiment error with code distance.The described transversal-CNOT Bell-pair experiment used rotated planar codes at distances 3, 5, and 7 and jointly decoded the two logical qubits.Source: §6 · p. 44

Runtime and circuit-level noise

  • Decoding delay risks additional errors before recovery, while faster algorithms and sliding-window schemes aim to reduce runtime without sacrificing accuracy.The review notes that expected runtime can better reflect frequent sub-threshold error patterns than worst-case complexity; circuit-level decoding and its measurement rounds add further runtime costs.Source: §6 · pp. 44–45
  • Circuit-level noise introduces measurement errors and typically requires O(d) measurement rounds, increasing runtime while lowering thresholds relative to data-qubit-only noise.The review reports that thresholds usually decrease by about an order of magnitude, making hardware requirements more stringent.Source: §6 · p. 45

Noise-tailored codes

  • Noise tailoring includes rectangular codes that increase Z-distance at the cost of more data qubits, and Clifford-deformed codes that better accommodate Z-biased noise.The XY code uses X- and Y-checks; the XZZX code uses mixed X/Z checks, and its structure lowers logical phase-flip probability under highly Z-biased noise.Source: §6 · pp. 45–46
  • At infinite Z-bias, XZZX becomes disjoint repetition codes and reaches a 50% threshold while significantly reducing required qubits.The code's single set of Z physical operators yields logical operators whose stabilizer products include X, Y, and Z operators, lowering logical phase-flip probability under highly Z-biased noise.Source: §6 · p. 46, Figure 35 · p. 47

Noise-aware decoding

  • Independent X/Z decoding misses Y-error correlations; sequential probability updates can account for them, while correlated and time-varying noise motivate further decoder tailoring.The probability update can be applied once or recursively and can be combined with the XY code; the review notes that independent error distributions may not describe real processors.Source: §6 · pp. 46–47

Conclusion

  • Decoder selection remains open because accuracy, speed, hardware noise, and the rate of further error accumulation vary across experimental platforms.Source: §6 · pp. 44, 47

A The backlog problem and why QEC requires real-time decoding

Real-time decoding matters when useful computations require T-gates: during magic-state injection, syndrome information must be decoded to decide whether to apply an S-gate. If syndrome data is generated faster than the decoder processes it, backlog can exponentially slow computation as T-gate depth grows.

A The backlog problem and why QEC requires real-time decoding

  • When rgen/rproc=f>1, a small initial syndrome backlog leads to exponential slowdown as T-gate depth grows.The decoder must process syndrome data fast enough to keep magic-state injections from being delayed by an exponentially increasing amount of time.Source: A The backlog problem and why QEC… · p. 56
  • During magic-state injection, decoding syndrome data before the S-gate decision is needed to determine whether that gate should be applied.Ignoring the Clifford correction can let the resulting error propagate into a more complicated error that corrupts computation.Source: A The backlog problem and why QEC… · p. 56
  • Clifford-only circuits can record syndrome history and post-process errors, allowing a quantum memory without real-time decoding.The need for timely decoding changes when useful computations involving T-gates and magic-state injection are considered.Source: A The backlog problem and why QEC… · p. 56

B Multiple-round decoding for measurement errors

Noisy measurements require decoding methods to account for errors in syndrome data, commonly by using multiple syndrome-extraction rounds to represent errors across space and time. Circuit-level noise increases graph size and connectivity, and faulty measurements lower code thresholds relative to data-qubit noise.

B Multiple-round decoding for measurement errors

  • Data-qubit-only decoding assumes noiseless check measurements, but circuit-level gate and SPAM errors can produce incorrect syndromes that lead to logical errors.A common response is to repeat syndrome extraction and connect checks across time; cellular-automaton decoders are an exception that may use single-shot decoding.Source: B Multiple-round decoding for… · p. 57
  • For MWPM and UF, space edges represent data-qubit Pauli errors, while time edges represent faulty measurements that require no code recovery.The potential matching shown in FIG. 37 contains two time edges and one space edge.Source: B Multiple-round decoding for… · p. 57
  • In repeated rounds, a detector event is a change in a check’s measurement outcome between consecutive measurement instances.The resulting decoding graph represents errors across space and time; FIG. 37 illustrates three rounds, with changed outcomes marking non-trivial syndrome elements.Source: B Multiple-round decoding for… · pp. 57–58, Figure 37 · p. 57
  • The circuit-level Tanner graph relates possible Pauli errors from a noisy CNOT to the detector events they trigger.The stabilizing circuit’s CNOT order can be scheduled in four steps, and indistinguishable errors that trigger the same measurement qubits are treated as equal events under combined probabilities.Source: B Multiple-round decoding for… · pp. 57–58, Figure 38 · p. 58
  • For circuit-level noise, BP on Tanner graphs built from stabilizer-circuit errors can aid decoders such as MWPM, UF, and BPOSD.The illustrated graph covers a CNOT error; considering the whole rotated-code circuit requires including the distinct CNOT-error Tanner graphs.Source: B Multiple-round decoding for… · p. 58
  • For a rotated distance-d code, multiple syndrome rounds yield d(d^2−1) checks, while circuit-level noise with faulty measurements lowers code thresholds relative to data-qubit noise.The larger decoding graph has more nodes and connectivity; measurement errors are a significant challenge for successful surface-code implementation.Source: B Multiple-round decoding for… · pp. 58–59

C QECC numerical simulations

The simulations evaluate MWPM, UF, BPOSD, and tensor-network decoders on rotated planar codes of several distances using logical error rate as the performance measure. They omit SPAM and gate errors and use a run-count rule of thumb for estimating that rate.

C QECC numerical simulations

  • The simulations compare MWPM, UF, BPOSD, and tensor-network decoders on d×d rotated planar codes with d∈{3,5,7,9,11}.Monte Carlo simulations were used to obtain performance curves and code thresholds.Source: C QECC numerical simulations · p. 59
  • The reported performance measure is PL, the probability of a logical error after recovery, and the simulations omit SPAM and gate errors.Each run samples an N-qubit Pauli error, calculates its syndrome, decodes it, and checks for a logical error using the channel error.Source: C QECC numerical simulations · p. 59
  • The decoder implementations use QECSIM for MWPM and tensor networks, Joschka Roffe’s LDPC implementation for BPOSD, and a custom UF implementation.The UF implementation is based on Delfosse and Nickerson.Source: C QECC numerical simulations · p. 59
  • Under independent observed error events, the run-count rule of thumb gives an approximate 95% confidence interval of (0.8 PL̂, 1.25 PL̂).PL̂ is the empirically estimated logical error rate.Source: C QECC numerical simulations · p. 59

Related papers

Loading 2307.14989v6…