PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved decoding of circuit noise and fragile boundaries of tailored surface codes

Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, Earl T. Campbell

arXiv:2203.04948v5quant-ph

TL;DR

Fast surface-code decoders can miss important noise information, while more accurate approaches may be impractical. This paper combines belief propagation with graph-based decoders to use the full circuit-level noise model. The decoders raise the reported surface-code threshold from 0.82% to 0.94%, and belief-matching was the only efficient decoder in a cited experiment to observe logical error suppression.

  • Problem

    Fast decoders can discard circuit-level noise information, while high-accuracy alternatives can have exponentially scaling runtimes and be impractical for modest codes.

    Source: §I · p. 2

  • Method

    Belief-matching and belief-find use belief propagation to exploit the full circuit-level noise model, then decode reweighted graphs with MWPM or weighted union-find.

    Source: §I · p. 2, §V · p. 10

  • Results

    The surface-code threshold is 0.94% with belief-matching and belief-find, compared with 0.82% for MWPM.

    Source: §I · p. 2

  • Takeaways & Limitations

    In the cited Google QEC experiment, belief-matching was the only efficient decoder accurate enough to observe logical error suppression.

    Source: §I · p. 2

    The boundary-improvement analysis considers only a few failure mechanisms; other mechanisms, entropy, and circuit-level simulations remain needed to quantify potential gains.

    Source: Appendix G · p. 20

Abstract

from arXiv · show

Realizing the full potential of quantum computation requires quantum error correction (QEC), with most recent breakthrough demonstrations of QEC using the surface code. QEC codes use multiple noisy physical qubits to encode information in fewer logical qubits, enabling the identification of errors through a decoding process. This process increases the logical fidelity (or accuracy) making the computation more reliable. However, most fast (efficient runtime) decoders neglect important noise characteristics, thereby reducing their accuracy. In this work, we introduce decoders that are both fast and accurate, and can be used with a wide class of QEC codes including the surface code. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. Using the surface code threshold as a performance metric, we observe a threshold at 0.94\% error probability for our decoders, outperforming the 0.82\% threshold for a standard minimum-weight perfect matching decoder. We also tested our belief-matching decoders in a theoretical case study of codes tailored to a biased noise model. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code. Surprisingly, in the well-below threshold regime, the rectangular surface code becomes more resource-efficient than the tailored surface code, due to a previously unnoticed phenomenon that we call "fragile boundaries". Our decoders outperform all other fast decoders in terms of threshold and accuracy, enabling better results in current quantum error correction experiments and opening up new areas for theoretical case studies.

I. INTRODUCTION

The paper combines belief propagation with graph-based decoders to use more circuit-noise information while retaining computational efficiency. It reports improved surface-code thresholds and identifies fragile boundaries that change which code is more resource-efficient under biased noise.

I. INTRODUCTION

  • Fast MWPM and union-find decoders ignore important noise mechanisms such as Y errors that correlate X and Z decoding, whereas high-accuracy alternatives can have exponentially scaling runtimes.The paper frames its contribution as addressing this accuracy–speed trade-off.Source: §I · pp. 1–2
  • Belief propagation uses circuit-level noise information, but can fail to converge; combining it with MWPM or weighted union-find is intended to ensure convergence while improving accuracy.The resulting decoders are called belief-matching and belief-find, respectively.Source: §I · p. 2
  • The surface-code threshold rises from 0.82% with MWPM to 0.94% with belief-matching and belief-find.The authors also report that belief-find has an almost-linear worst-case running time.Source: §I · p. 2
  • The decoders apply to codes supported by MWPM, and the biased-noise case study compares square and rectangular CSS codes with XY codes.The study optimizes physical resources for a target logical failure rate under a square-lattice constraint.Source: §I · p. 2
  • For biased circuit-level noise, the XY code reaches a 0.841(6)% CNOT infidelity threshold versus MWPM’s 0.498(2)%; below around 0.4%, rectangular CSS codes use fewer qubits than XY codes.The reported threshold is a 1.69× relative improvement over MWPM.Source: §I · p. 2
  • XY fragile boundaries allow spatial failures with O(√n) Z errors plus one X or Y error, while temporal Z strings can occur even at infinite bias.The authors connect temporal-boundary vulnerability to measuring only half the code stabilizers during logical measurement; such boundaries also arise in lattice surgery.Source: §I · p. 2

II. PRELIMINARIES

The preliminaries define stabilizer-code errors, syndromes, and circuit-level noise. The decoding discussion explains why graph-based decoders omit correlated errors and introduces belief propagation with matching or union-find as a way to use more of the noise model.

II. PRELIMINARIES

  • A stabilizer code stores information in a joint eigenspace; a decoder uses the measured syndrome and noise model to predict an error, succeeding when the residual error is a stabilizer.For CSS surface codes, stabilizer generators are X-type or Z-type and are geometrically local.Source: §II · p. 3
  • Circuit-level noise includes faults in syndrome-extraction gates and measurements, so stabilizer measurements are repeated O(d) times and detector outcomes form the decoder’s syndrome.A detector is a combination of circuit measurement outcomes that is deterministic without noise.Source: §II · pp. 3–4

III. DECODING CIRCUIT-LEVEL NOISE

  • MWPM and union-find represent graphlike errors as matching-graph edges, but Y errors flip four stabilizers and induce X/Z correlations that those decoders cannot represent.The same issue applies to circuit-level noise, where the matching graph includes time as a third dimension.Source: §III · p. 4
  • Earlier approaches addressed hyperedges with trade-offs: tensor-network decoding is computationally costly and assumes perfect measurements, while prior belief-propagation work did not address noisy syndrome-extraction gates.The cited XY tailored decoder’s suitability for general circuit-level noise was unclear.Source: §III · p. 4
  • Belief propagation estimates error-mechanism marginals to reweight X and Z matching graphs, which are then decoded by MWPM for belief-matching or weighted union-find for belief-find.The illustrated pipeline assumes perfect syndrome measurements for simplicity, although the decoders can handle more complex circuit-level models.Source: §III · pp. 4–5, Figure 3 · p. 5

A. Belief-matching and belief-find

Belief-matching and belief-find use belief propagation to incorporate the full circuit-level error model before decoding with a matching-graph algorithm. For depolarizing noise, both improve on MWPM’s threshold, while belief-find has almost-linear worst-case runtime.

A. Belief-matching and belief-find

  • Belief propagation estimates posterior error probabilities using the full error model, including hyperedges, then reweights matching-graph edges for MWPM or weighted union-find decoding.BP alone is only an approximation and has no threshold in this setting.Source: A. Belief-matching and belief-find · p. 5
  • Belief-find has almost-linear worst-case runtime and decoding performance almost identical to belief-matching, whose worst-case runtime is dominated by MWPM.Belief-matching’s expected runtime is approximately linear below threshold when using sparse blossom; BP remains computationally intensive but highly parallelisable.Source: A. Belief-matching and belief-find · p. 6

B. ML decoding with tensor networks

  • The circuit-level ML benchmark models fault locations as probability tensors and uses approximate tensor-network contraction to reduce the cost of maximum-likelihood decoding.Exact contraction is computationally expensive; approximation allows complexity to be lowered while maintaining controllable accuracy.Source: B. ML decoding with tensor networks · p. 6

C. Performance of belief-matching and belief-find for depolarizing noise

IV. TAILORING CODES TO BIASED NOISE

The section compares surface-code variants for biased circuit-level noise and identifies failure mechanisms that limit the XY code’s apparent protection against Z errors. These fragile errors occur at spatial and temporal boundaries, including during logical operations and lattice surgery.

IV. TAILORING CODES TO BIASED NOISE

  • For biased-noise code selection, the study compares square-lattice XY codes with CSS codes whose aspect ratio is optimized to reduce below-threshold qubit overhead.The XY code is treated on a square lattice because its aspect ratio sets X and Y distances, which should be equal when X and Y errors are equiprobable.Source: §IV · p. 7

A. Fragility of the XY surface code

  • The XY code’s high tolerance to Z errors at infinite bias can vanish at finite bias or at spatial or temporal boundaries.The section identifies boundary failure mechanisms requiring only O(√n) Z errors during logical state preparation and measurement.Source: §IV · p. 8, A. Fragility of the XY surface code · p. 8
  • At finite bias, spatial-boundary logical errors can combine one X or Y error with O(√n) Z errors, and are expected to dominate at low physical error rates and high bias.The mechanism arises from open boundary conditions; because it occurs on all four boundaries, a square aspect ratio is expected to be optimal when X and Y error probabilities are similar.Source: A. Fragility of the XY surface code · p. 8
  • Temporal boundaries also permit undetectable O(√n) Z-type logical errors during logical measurement, where only half the stabilizers are measured.The same fragility affects logical state preparation and measurement, including the corresponding operations in the Y basis.Source: A. Fragility of the XY surface code · pp. 8–9
  • During lattice-surgery merge and split operations, fragile boundary errors can act as logical idling errors, while measurement-error strings can corrupt the multi-qubit Pauli measurement.The space-time diagram depicts string-like fault patterns during preparation, merge, and split operations.Source: Figure 6 · p. 8, A. Fragility of the XY surface code · p. 9

B. Below-threshold scaling of the XY surface code

Below threshold, the XY code’s boundary-related string-like failure mechanisms limit its expected scaling advantage at infinite bias. Numerical results for η = 100 show decay with a √n exponent rather than the hoped-for n exponent.

B. Below-threshold scaling of the XY surface code

  • Temporal-boundary errors are equivalent to dominant square-CSS failure mechanisms, while the XY code’s vulnerable string-like mechanisms can be split into two operators that cannot both be correctable.The passage uses this split to explain why one of the operators can cause logical failure.Source: B. Below-threshold scaling of the XY… · p. 9
  • In practical regimes, string-like failures are expected to dominate over weight-n Z-type logical errors, which decay as O(p^(n/2)).With constant bias η, there is always a code size above which string-like errors dominate.Source: B. Below-threshold scaling of the XY… · p. 9
  • For η = 100, simulations show logical failure decay of O(p^(√n/2)/√η), rather than the hoped-for O(p^(n/2)) scaling at infinite bias without SPAM errors.The simulations include entropic contributions to the logical error rate.Source: B. Below-threshold scaling of the XY… · p. 9

C. Decoder performance for biased noise

For η = 100 biased circuit-level noise, belief-matching raises the XY surface-code threshold relative to MWPM. A separate L = 5 comparison finds lower logical error than MWPM at a representative physical error rate, while remaining above the ML decoder.

C. Decoder performance for biased noise

  • At p = 0.27%, belief-matching’s logical error rate is around 7.8× lower than MWPM’s and 2.8× higher than the circuit-level ML decoder’s.This comparison uses an L = 5 XY code for L rounds with η = 100.Source: C. Decoder performance for biased noise · p. 9
  • 0.841(6)% CNOT infidelity is the belief-matching threshold for the XY code, versus 0.498(2)% for MWPM, a 1.69× relative improvement.Figure 9 plots threshold curves for the two decoders at η = 100.Source: Figure 9 · p. 10, C. Decoder performance for biased noise · p. 10
  • Figure 10 estimates qubit overhead versus CNOT infidelity for XY and square or rectangular CSS codes at η = 100, targeting a logical error rate of 10^-12.The estimates use fitted ansätze; stepped lines restrict lattice sizes to odd integers, while smooth lines interpolate over positive real sizes.Source: Figure 10 · p. 10

D. Resource requirements of tailored surface codes

The resource comparison favors the XY surface code over the square CSS code, but optimized rectangular CSS codes can use fewer qubits well below threshold. The conclusion also identifies fragile boundary errors as a concern for XY-code performance under biased noise.

D. Resource requirements of tailored surface codes

  • At a CNOT infidelity of 10^-3, the XY code requires 1057 physical qubits per logical qubit versus 1921 for the square CSS code, while rectangular CSS requires 681.The comparison targets a logical error rate of 10^-12; the rectangular aspect ratio is optimized so X and Z logical error rates are approximately equal.Source: D. Resource requirements of tailored… · p. 10
  • The XY code retains a higher threshold and improves on square-aspect-ratio CSS, but optimizing CSS aspect ratio can be crucial to exploiting bias below threshold.The authors do not expect aspect-ratio changes to improve XY-code performance because its identified failure mechanisms can occur horizontally and vertically.Source: D. Resource requirements of tailored… · p. 10

V. CONCLUSION

  • Belief-matching and belief-find use the full circuit-level noise model and improve accuracy over standard MWPM for circuit-level noise.Belief-matching also outperformed MWPM and correlated MWPM for experimental noise; belief-find has almost-linear worst-case runtime and similar accuracy to belief-matching.Source: §V · pp. 10–11
  • Fragile boundary errors comprise O(√n) Z errors and O(1) X or Y errors, and will likely dominate weight-n Z-type logical errors in most realistic settings.They can occur at temporal boundaries or, at finite bias, spatial boundaries.Source: §V · p. 11
  • The biased-noise study compares XY codes with CSS codes whose lattice dimensions can be tailored to the bias, while other biased-noise proposals such as XZZX were not considered.The authors describe XZZX as a promising candidate with high thresholds under biased noise.Source: §V · p. 11

Appendix A: BP review

The appendix reviews belief propagation and defines a circuit-level Tanner graph for representing error mechanisms and detectors. The decoders use BP estimates to reweight a matching graph, then apply MWPM or weighted union-find when BP does not converge.

Appendix A: BP review

  • Belief propagation passes messages between check and variable nodes using prior bit-flip probabilities and syndrome information to approximate marginal bit-flip probabilities.The appendix describes horizontal check-to-variable and vertical variable-to-check steps, with local applications of Bayes’ rule.Source: Appendix A · p. 14
  • BP marginals cannot distinguish equiprobable quantum-decoding solutions that differ by stabilizers, motivating post-processing such as ordered statistics decoding.The appendix notes that OSD has been used to decode hypergraph product codes.Source: Appendix A · p. 14

Appendix B: The circuit-level Tanner graph

  • The circuit-level Tanner graph represents detectors as check nodes and circuit error mechanisms as variable nodes, connected when an error flips a detector.The construction approximates disjoint error probabilities as independent mechanisms, which is correct to leading order in p and considered a good approximation at the studied physical error rates.Source: Appendix B · p. 14

Appendix C: The belief-matching and belief-find decoders

  • Because BP alone has no surface-code threshold, the decoders use BP posteriors to set matching-graph edge weights, approximating hyperedges with existing edges.The edge weights are negative logarithms of adjusted probabilities; the appendix specifies a unique decomposition for each hyperedge.Source: Appendix C · p. 15
  • Belief-matching uses MWPM to find a minimum-weight syndrome-consistent edge set, while belief-find uses weighted union-find for a low-weight solution with almost-linear worst-case runtime.The stated worst-case runtimes are O(N^3 log(N)) for MWPM and O(Nα(N)) for weighted union-find.Source: Appendix C · p. 15
  • Weighted union-find implementation refinements significantly improve decoding performance without changing asymptotic running time.The refinements include growing smaller odd clusters first and fusing clusters when an edge becomes fully grown.Source: Appendix C · p. 15

Appendix D: Noise model used in numerical simulations

The simulations use a biased circuit-level noise model and make specified choices for gate schedules and state preparation and measurement. The appendix also describes boundary and bulk failure mechanisms that can affect lattice surgery.

Appendix D: Noise model used in numerical simulations

  • The simulations use biased circuit-level noise parameterized by p and η, with specified Pauli, preparation, and measurement error probabilities.CNOT infidelity p_CX is used to compare thresholds; p equals CNOT infidelity only when η = 1.Source: Appendix D · pp. 15–16
  • The simulations assume native CY gates and, except for the SPAM analysis, perfect state preparation and measurement to isolate fragile spatial boundary errors.The authors describe these choices as optimistic assumptions for XY-code simulations.Source: Appendix D · p. 16

Appendix E: Fragility of lattice surgery

  • Preparing |+⟩ qubits before a lattice-surgery merge creates a temporal boundary where a Z error can go undetected and cause logical failure.The preparation slice is analogous to temporal-boundary errors during logical state preparation.Source: Appendix E · p. 16
  • Lattice-surgery failures can also arise from bulk-spanning strings of measurement faults that terminate at temporal boundaries.With d_m repeated measurements, the described event requires d_m consecutive measurement faults and can yield an incorrect logical Pauli measurement.Source: Appendix E · p. 16
  • The bulk error mechanism has more possible paths than boundary errors, while suppressing it with more measurement rounds makes computation slower.The passage notes that a standard choice is d_m = √n, and that d_m = n can suppress these errors at a significant speed cost.Source: Appendix E · p. 16

Appendix F: Additional numerical results for tailored surface codes

The analysis compares noisy and perfect state preparation and measurement (SPAM) for XY and square CSS surface codes. The SPAM-related logical-error ratio responds differently to bias in the two codes.

1. Impact of state preparation and measurement errors

  • The comparison uses an L = 7 XY code with L rounds of noisy syndrome extraction and evaluates both noisy and perfect SPAM.The same analysis is carried out for the square CSS code, with decoding using MWPM.Source: §1 · pp. 16–17
  • The SPAM-related logical-error ratio increases significantly with bias for the XY code, but remains small and approximately constant for the square CSS code.The authors say this is consistent with Z^⊗L errors during SPAM being more probable than fragile spatial boundary errors.Source: §1 · p. 17
  • The SPAM-related ratio also depends on lattice size and the number of rounds, and is expected to decrease as rounds increase.Source: §1 · p. 17

2. Below threshold scaling of the XY surface code

The XY surface code’s below-threshold logical-error data are fit with a scaling ansatz. The fit parameters are used to estimate qubit overhead at a target logical error rate.

2. Below threshold scaling of the XY surface code

  • The schedule’s bulk symmetry makes the logical X error rate almost identical to the logical Y error rate.The authors report that this was numerically verified.Source: §2 · p. 17
  • The XY logical Y error data fit an ansatz with a_tailored = 0.0419(6) and b_tailored = 24.76(7).The data are shown for belief-matching at η = 100.Source: §2 · p. 17, Figure 14 · p. 18
  • The fitted ansatz enables an estimate of the XY code’s qubit overhead for a target logical error rate of 10^-12.Source: §2 · p. 18

3. Below threshold scaling of the rectangular CSS surface code

The rectangular CSS surface code is analyzed below threshold using data across code distances. The fitted scaling ansätze provide optimal aspect ratios for a target logical failure rate.

3. Below threshold scaling of the rectangular CSS surface code

  • For η = 100, the fitted parameters are a_x = 0.1015(9), b_x = 42.30(7), a_z = 0.0527(9), and b_z = 1.69(1).The fits use a larger dataset than the subset plotted for the rectangular CSS code.Source: Figure 15 · p. 18, §3 · p. 18
  • The plotted scaling fixes the X distance at 7, varies the Z distance, and uses max(d_X, d_Z) syndrome-measurement rounds.Source: Figure 15 · p. 18, §3 · p. 18
  • The optimal aspect ratios equalize X and Z logical failure rates for a target logical failure rate of 10^-12.The ratios were used to estimate the CSS code’s qubit overhead in the main text.Source: Figure 16 · p. 18, §3 · p. 18

Appendix G: Mitigating fragile errors

Deforming the XY surface code’s spatial boundaries partially mitigates fragile boundary errors, but trades off performance at infinite Z bias. The deformed code’s Z distance remains linear in the number of qubits, with a size-dependent limiting fraction.

Appendix G: Mitigating fragile errors

  • Boundary deformation applies H or A := HSH to qubits in boundary stabilizers, requiring more X and Y errors for logical X or Y operators.The authors describe this as partially mitigating fragile spatial boundaries; temporal boundaries during SPAM and lattice surgery remain open.Source: Appendix G · p. 19
  • For all odd L < 100, the authors computed Z-type logical operators and stabilizers; their periodic structure explains the large-L distance fractions.The structures for L = 15, 17, and 19 generalize to L > 6 because they repeat with period 6.Source: Appendix G · pp. 19–20, Figure 19 · p. 20
  • 5/9 and 1/3 are the large-L limits of dZ/n when L mod 6 is 1 or 5, and 3, respectively.The deformed boundaries reduce dZ from n to 5n/9 or n/3 at infinite bias.Source: Appendix G · pp. 19–20, Figure 18 · p. 19
  • At infinite Z bias, deformation impairs performance, while the authors expect substantial improvement for noise with even very large finite bias.They attribute the tradeoff to the deformed code admitting pure Z-type errors with fewer than n errors.Source: Appendix G · pp. 19–20
  • The analysis considers only selected failure mechanisms; entropic contributions, other mechanisms, and circuit-level simulations are needed to quantify the potential improvement.The authors specifically caution that these analyses are crucial to better understand and quantify the improvement.Source: Appendix G · p. 20

Related papers

Loading 2203.04948v5…