PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulation of rare events in quantum error correction

Sergey Bravyi, Alexander Vargo

arXiv:1308.6270v3quant-ph

TL;DR

Estimating logical error probabilities for large-distance quantum codes is difficult because logical errors become extremely rare. This paper combines splitting and Bennett’s acceptance ratio to estimate surface-code logical error probabilities and their decay rates. Its numerical results show that low-p asymptotic formulas tend to underestimate finite-error-rate probabilities, and it proposes a more accurate fitting formula.

  • Problem

    Estimating logical error probabilities at large code distances is difficult because such errors become extremely unlikely, while the decay rate α is needed to assess code-distance overhead.

    Source: §I · p. 1

  • Method

    The algorithm combines splitting across a monotonic sequence of error rates with Bennett’s acceptance ratio to estimate logical error probabilities and α.

    Source: §I · pp. 1–2

  • Results

    Numerical results show that low-p asymptotic formulas tend to underestimate P_L at finite error rates, and the paper proposes a more accurate fitting formula.

    Source: §II · p. 3, §IX · p. 14

  • Takeaways & Limitations

    The proposed fitting formula offers a more accurate description of surface-code logical error probabilities than the low-p asymptotic formulas at finite error rates.

    Source: §IX · p. 14

    The low-p asymptotic estimate of α is a poor approximation at large and moderately small error rates, especially for path-like errors.

    Source: §II · p. 3

Abstract

from arXiv · show

We consider the problem of calculating the logical error probability for a stabilizer quantum code subject to random Pauli errors. To access the regime of large code distances where logical errors are extremely unlikely we adopt the splitting method widely used in Monte Carlo simulations of rare events and Bennett's acceptance ratio method for estimating the free energy difference between two canonical ensembles. To illustrate the power of these methods in the context of error correction, we calculate the logical error probability $P_L$ for the 2D surface code on a square lattice with a pair of holes for all code distances $d\le 20$ and all error rates $p$ below the fault-tolerance threshold. Our numerical results confirm the expected exponential decay $P_L\sim \exp{[-\alpha(p)d]}$ and provide a simple fitting formula for the decay rate $\alpha(p)$. Both noiseless and noisy syndrome readout circuits are considered.

I. INTRODUCTION

Estimating the decay rate α matters for determining code-distance overhead and comparing decoders, but rare logical errors make direct Monte Carlo ineffective in important regimes. The paper proposes combining splitting with Bennett’s acceptance ratio to estimate logical error probabilities and α for surface codes.

I. INTRODUCTION

  • The decay rate α determines the dominant large-distance contribution to P_L and helps estimate required code distance and compare decoders.Source: §I · p. 1
  • Direct Monte Carlo becomes impractical when physical error rates are small or code distances are large because logical errors are extremely unlikely.Source: §I · p. 1
  • Fault path counting can bound P_L through weighted self-avoiding walks, while Fowler’s variant computes P_L exactly at asymptotically small error rates but does not suit α at fixed p.For fixed d and p approaching zero, minimum-weight uncorrectable errors yield P_L = A_d p^(d/2).Source: §I · p. 1
  • Splitting and Bennett’s acceptance ratio estimate surface-code logical error probabilities and decay rates in regimes where logical errors are rare.The method estimates ratios across a sequence of error rates and combines them with an initial probability estimate.Source: §I · pp. 1–2

II. SUMMARY OF RESULTS

The section reports surface-code logical-error scaling with noiseless and noisy syndrome readout, compares fitted decay rates with low-error asymptotics, and outlines the estimation methods’ regimes and limits.

II. SUMMARY OF RESULTS

  • In the simulated two-defect geometry, code distance is d = 4r; logical loop-like and path-like errors are evaluated for both noiseless and noisy syndrome readout.For noisy readout, syndrome measurements are repeated d times.Source: §II · pp. 2–3
  • The low-p asymptotic estimate poorly approximates α(p) at large and moderately small error rates, especially for path-like errors.The section extends α(p) to rates nearer threshold by linear interpolation.Source: Figure 2 · p. 3, §II · p. 3
  • The heuristic fit refines exponential scaling by fitting low-degree x(p) and y(p) polynomials to reproduce the pre-exponential factor, with log(p) terms set by low-p scaling.The coefficients c, x_i, and y_i are listed in Table I.Source: §II · p. 3, Table I · p. 3
  • The low-p asymptotic formula significantly overestimates α for large and moderately small error rates with noisy syndrome readout.The plotted decay rates are computed using downward splitting.Source: Figure 3 · p. 3, §II · p. 4
  • Monte Carlo handles rates near threshold, splitting lower rates, and fault-path counting very small rates; noiseless estimates are cross-checked at p*, while noisy curves match derivatives there.The noisy-readout derivative match partially confirms splitting-method correctness.Source: Figure 4 · p. 4, §II · p. 4
  • Metropolis runtime restricts splitting to p≤p*≈pth/2, and noisy-readout simulations use p≤0.7% to avoid finite-size effects.The noisy threshold estimates cited are 0.75%–0.9%.Source: §II · p. 4

III. RARE EVENT SIMULATION

The splitting method estimates a rare-event probability by breaking it into ratios between distributions whose failure-conditioned samples overlap. Bennett’s acceptance ratio estimates those ratios, with an error bound when adjacent conditional distributions are sufficiently close.

III. RARE EVENT SIMULATION

  • Splitting computes the overall failure probability from the product of successive ratios πj+1(F)/πj(F), starting from a distribution where π1(F) is known.Each intermediate distribution must be efficiently evaluable, sampleable conditional on failure, and overlap non-negligibly with its neighbor.Source: §III · pp. 4–5
  • For noiseless readout, upward splitting estimates PL(p) below p*, while Monte Carlo estimates it above p*; their values agree at p*.The junction rates are 3% for path-like errors and 5% for loop-like errors.Source: Figure 5 · p. 5
  • For noisy readout, downward splitting estimates PL(p) below p*, while Monte Carlo estimates it above p*; their derivatives agree at p*.The junction rates are 0.3% for path-like errors and 0.5% for loop-like errors.Source: Figure 6 · p. 5
  • Bennett’s acceptance ratio estimates each adjacent failure-probability ratio from samples drawn conditional on failure.The method chooses an estimator parameter to minimize statistical error for a fixed sample count.Source: §III · pp. 5–6
  • When neighboring failure-conditioned distributions have total variation distance at most 1−δ, the method bounds the relative error of the overall estimate.The statistical errors may accumulate in a random-walk fashion because the ratios are computed independently.Source: §III · p. 6

IV. SURFACE CODES

The surface code encodes logical qubits in a stabilizer subspace of a lattice with defects. Error chains produce syndromes on decoding graphs, and recovery succeeds only when the residual error acts trivially on the encoded logical qubit.

IV. SURFACE CODES

  • The code space is the common +1 eigenspace of site and plaquette stabilizers, and its dimension is 2^b1, where b1 is the number of defects for open boundaries.The simulations consider single- and double-defect geometries.Source: §IV · p. 6
  • Decoding graphs map physical errors to syndromes: phase-flip errors create endpoint pairs, while boundary bit-flip errors create one syndrome and a hanging edge.For bit flips, the syndrome is (∂E)\T; for phase flips, T is empty.Source: §IV · p. 6
  • In simulations, geometry is set by defect size r, defect separation s, and boundary-buffer length b; choosing s = b = 4r guarantees code distance d = 4r.Source: Figure 7 · p. 7
  • Recovery must match the measured syndrome, and correction succeeds only if the combined recovery and error have even overlap with the logical chain.The logical chains are a loop around a defect and a path connecting defects (or a defect and the external boundary).Source: §IV · pp. 6–7

V. DECODING ALGORITHMS

The decoder chooses a most-likely error chain consistent with the observed syndrome by minimizing chain weight. With boundary vertices allowed to absorb unmatched syndromes, the optimization reduces to a non-perfect matching problem.

V. DECODING ALGORITHMS

  • For independent errors on graph edges, a recovery chain is chosen as the minimum-weight chain consistent with the syndrome.The edge weights encode the specified error rates.Source: §V · p. 7
  • With boundary vertices T, the decoder minimizes chains whose syndrome matches S outside T, allowing paths from syndrome vertices to T.This is Problem 2, the minimum-weight chain subject to (∂E)\T=S.Source: §V · pp. 7–8
  • Problem 2 reduces to non-perfect matching on syndrome vertices, pairing vertices or connecting them to T using weighted distances.The objective includes costs for paired vertices and unmatched vertices connected to T.Source: §V · p. 8
  • The reduction makes decoding a maximum-weight matching problem solvable in O(|S|^3), and edges with nonpositive weights can be safely removed.The authors report that this reduction had not previously been used in error correction.Source: §V · p. 8

VI. CORRECTABILITY

The section defines correctability both independently of a decoder and relative to the implemented decoder, then gives efficient tests for selected graph geometries. It also establishes that, in two surface-code geometries, uncorrectable chains can be connected through single-edge changes that remain uncorrectable.

Correctability and degeneracy

  • A degenerate syndrome can have minimum-weight recoveries of both parities, so logical error probability depends on how the decoder breaks ties.The simulations use decoder-specific correctability and therefore apply only to the particular minimum-weight decoder implemented in the paper.Source: §VI · pp. 8–9

Correctability tests

  • Correctability testing takes O(|V|^3) time for arbitrary decoding graphs when Γ is a cut, and for planar decoding graphs of maximum degree O(1) when Γ is a dual-graph path.Source: §VI · p. 9

Connectivity of uncorrectable chains

  • For a square lattice with one smooth defect, any two uncorrectable chains can be connected by adding or removing single edges while remaining uncorrectable.The proof transforms the chains through loops, contracting even loops and turning odd loops into the defect boundary.Source: §VI · p. 10
  • For a square lattice with two rough defects, any two uncorrectable chains likewise admit a single-edge path through uncorrectable chains.The proof reduces to loops and paths between the defects, then contracts loops and transforms paths into a fixed connecting path.Source: §VI · p. 10

VII. IMPLEMENTATION OF THE SPLITTING METHOD

The implementation estimates the probability of uncorrectable chains by splitting across a sequence of error distributions and sampling each conditional failure distribution with a Metropolis process. Its step sizes are heuristic, and mixing times are not known in practice.

Splitting setup

  • The failure event is the set of uncorrectable chains, whose probability gives the logical loop-like or path-like error probability.Membership is tested using the paper’s decoder-specific correctability definition and the relevant decoding problem.Source: §VII · p. 11

Splitting sequence

  • The splitting sequence changes the error rate in steps sized by 1/√w_j, where w_j estimates the typical number of edges in a sampled failure chain.The authors describe this heuristic choice as a tradeoff between statistical error and the number of splitting steps.Source: §VII · p. 11

Conditional sampling

  • A Metropolis step proposes toggling one edge and accepts the change according to the probability ratio, provided the resulting chain remains in the failure set.The resulting reversible Markov process has the conditional failure distribution as its steady distribution.Source: §VII · p. 11

Sampling accuracy

  • The sampling length is chosen using heuristic fluctuation and doubling checks because the Markov-process mixing time is unknown.The target relative error for the failure probability was about 50%, despite probabilities spanning almost 20 orders of magnitude; workloads ranged from 10^5 to 10^7 non-trivial flips.Source: §VII · p. 11

Implementation and scope

  • Recycling minimum-weight paths between neighboring Metropolis states speeds membership tests, since their syndromes differ at no more than two vertices.Loop-like errors are simulated in a single-defect geometry and path-like errors in a double-defect geometry; for the special decoding graphs, the paper proves ergodicity and correctness as the sampling length tends to infinity.Source: §VII · pp. 11–12

VIII. NOISY SYNDROME READOUT

For noisy syndrome readout, the paper maps circuit faults to a space-time decoding graph and assigns probabilities to its edges. It uses this representation for splitting simulations, while limiting the simulated defect sizes because of runtime and memory constraints.

Noise model

  • The circuit model includes noisy measurements, ancilla preparations, CNOT gates, and idle-qubit memory errors, with error rates specified for each operation type.A non-identity two-qubit Pauli follows a noisy CNOT with probability p/15 for each of the 15 non-identity operators.Source: §VIII · p. 12

Syndrome readout

  • The syndrome circuit measures site and plaquette stabilizers, using one ancilla and six rounds per stabilizer; readout repeats to collect data for correction.During data collection, the paper assumes defects are not added, changed, or annihilated.Source: §VIII · p. 12, Figure 9 · p. 12

Decoding graph

  • A decoding-graph edge represents a set of circuit faults that produce endpoint syndromes, and its prior is the probability of an odd number of those faults.The edge sets are disjoint; time-like and diagonal edges are described as the most and least noisy, respectively.Source: §VIII · pp. 12–13

Decoding and simulation

  • The decoder maps graph chains to accumulated 2D errors by projection, then tests correctability through the overlap with the relevant logical chain.The same splitting implementation is used with independent edge errors weighted by the edge priors.Source: §VIII · p. 13

Simulation scope and results

  • Simulations covered defect sizes r = 2, 3, 4, limited partly by Metropolis runtime and memory; combining splitting-method and Monte Carlo data computed fitting parameters for exponential logical-error scaling, with decay rate α(p).For double-defect geometry with r = 4, the minimum-weight-path lookup table on the decoding graph takes about 4GB of RAM.Source: §VIII · p. 13

IX. CONCLUSION AND OPEN PROBLEMS

The paper proposes an algorithm for estimating surface-code logical error probabilities at large code distances and moderately small error rates, and reports results for noiseless and noisy syndrome extraction. The results show that low-error-rate asymptotic formulas underestimate logical error probabilities at finite rates; the authors also outline extensions and unresolved theoretical questions.

IX. CONCLUSION AND OPEN PROBLEMS

  • The proposed algorithm estimates surface-code logical error probabilities at large code distances and moderately small error rates.Numerical results are reported for noiseless and noisy syndrome extraction.Source: §IX · pp. 13–14
  • Asymptotic formulas valid as p approaches 0 tend to underestimate P_L at finite error rates, motivating a more accurate fitting formula.Numerical results cover noiseless and noisy syndrome extraction.Source: §IX · p. 14
  • For large networks of defect tubes, the authors anticipate rough P_L estimates by dividing networks into tiles and summing the tiles’ logical error probabilities.The proposed tiles are isolated tube segments or parallel pairs; the paper says the techniques apply to each tile.Source: §IX · p. 14
  • Rigorous bounds on algorithm runtime and approximation error remain open and require upper bounds on the Metropolis subroutine’s mixing time.Source: §IX · p. 14
Loading 1308.6270v3…