Can logical error rates be predicted without Monte Carlo sampling?

Monte Carlo cost explodes with distance and levels

Estimating a logical error rate (LER) by Monte Carlo sampling needs O(p^−⌈d/2⌉/ε²) samples at physical error rate p, code distance d and relative error ε. That scaling is already punishing at large d and low p, and it becomes worse for concatenated codes, whose distance grows as d^ℓ with the number of levels ℓ.

The paper quantifies the practical consequence: at p = 10^−3, Monte Carlo sampling would need more than 10^12 shots for 113 of the 148 cases the authors compare. Each Monte Carlo run also returns the LER at only a single p, so a new p requires a new run.

The fail fast method reduces cost by sampling the failures of each weight separately, but the paper states it only works for unconcatenated codes and does not model the soft information that levels of a concatenated code pass to each other. That gap is what the new predictor targets.

The predictor needs stabilizers and minimum-weight logical operators

The predictor takes as input the stabilizers, the minimum-weight logical operators, and, for odd d, the logical operators of weight d + 1 of a code. From these it computes, without sampling, the leading monomial c·p^o of the LER when that rate is expressed as a polynomial in p.

The computation runs at every level of concatenation, in time polynomial in the code parameters and linear in ℓ for fixed budgets. The paper proves the prediction is exact for any unconcatenated stabilizer code, for every logical observable and arbitrary per-qubit error rates, whenever no budget is exhausted.

For concatenated codes the authors construct a recursive approach that computes the leading monomial exactly in exponential time; the predictor approximates this recursion. The approximation is what makes the runtime polynomial in d and in the number of minimum-weight logical operators.

At small p the decoder only compares leading orders

The mechanism rests on how the soft tree decoder behaves at small p. The decoder compares the leading orders of the likelihoods of the logical classes, so whether it fails on an error configuration depends only on the gaps between these orders.

The predictor counts each failing error configuration at the intersection of the minimum-weight logical operators containing it, then uses a recursion that computes the distribution of these gaps at each level from the distribution at the level below. Budgets placed on that recursion keep the predictor polynomial.

This is why a single leading monomial can stand in for a full LER curve: it gives the LER at every sufficiently small p from one run, rather than one run per p.

Predictions match exact enumeration to within 0.1% at level 1

The authors validate against three baselines: Monte Carlo sampling with a tree decoder (with 95% confidence intervals), exact enumeration of errors under a joint-marginal maximum-likelihood decoder, and, at level 1, fail fast. The latter two are feasible only for small codes and distances.

At level 1 the prediction agrees with exact enumeration to within 0.1% at p = 3.2×10^−4, validating the exactness theorem. Above level 1, the prediction agrees to within 0.2% for the iceberg code up to level 3, and for the toric code at level 2 the predicted leading coefficient equals the exact one.

The paper also reports a contrast with a sampling-based baseline: fail fast with BP-OSD estimates LERs up to 2.5×10^9 times higher than the prediction at p = 10^−3, because BP-OSD fails on some error configurations of weight below d/2.

Only two budgets materially change the predicted LER

The predictor depends on a set of budgets. Varying each one around its default for six concatenated codes at their deepest level, plus surface codes with d = 9 and d = 11 at level 1, shows that four budgets — B_cellratio, B_class, B_configweight and B_truthconv — never change the predicted LER.

Lowering B_gap or B_likelihood below its default does change the result, by up to 34% at half the default B_gap and by up to nine orders of magnitude at B_gap = 2. Above their defaults, neither changes the LER by more than 3%, while B_likelihood multiplies runtime by up to 12 at 16 times its default.

At default budgets every prediction is within 3% of its value at the largest budget tested, except the surface code with d = 4 at level 2, whose LER is 15% higher at the default B_work and stops changing from twice the default on. The authors therefore set B_work = 4.8×10^7 above level 1.

The best code depends on the noise bias

Using the predictor, the authors evaluate and compare 37 code configurations under four noise biases in 48 core-hours. The comparison groups codes by effective distance D = d^ℓ and reports the predicted LER of the first logical qubit at p = 10^−3 under code-capacity noise.

The headline observation is that the choice of best code depends on the noise bias. The same runs also give the predicted LER at every p, whereas Monte Carlo must be rerun for each p.

The predictor also supports a practical search: pick the code with the lowest LER that still meets a desired property such as a minimum encoding rate e* or a minimum number of logical qubits k*. For example, at p = 10^−3 and a target LER of 10^−12, the surface code with d = 11 needs the fewest physical qubits, 121, but for e* = 0.2, GALA reaches the target with 132 physical qubits for 30 logical qubits.

Exactness holds only while no budget is exhausted

The exactness guarantee is conditional. The prediction is exact for any unconcatenated stabilizer code, for every logical observable and arbitrary per-qubit error rates, whenever no budget is exhausted. For concatenated codes the exact recursion is exponential; the deployed predictor approximates it.

A second boundary concerns the logical operators used as input. A missing logical operator causes the predictor to miss some error configurations on which the actual decoder fails, so if every budget is large enough, the computed leading coefficient of the total LER at level 1 is a lower bound on the true one. This may not hold for the LER of any particular logical observable θ, since a missing logical operator may also cause the predictor to miss a competing class that does not flip θ.

For high-rate codes the search finds between 7% and 95% of the minimum-weight logical operators by the Chao1 estimate. When the estimated chance that another call returns an already-found logical operator is at least 0.94 — the gross code and the Mitten code with d = 10 — the authors scale the predicted leading coefficient by the ratio of the estimated size of the operator set to the number found; for other high-rate codes they report the prediction from the operators found, since the estimate is not confident enough.

Compare codes at matched effective distance and stated bias

The most decision-relevant output of this paper is not a single LER number but a comparison protocol. Because the predictor groups codes by effective distance D = d^ℓ and reports the LER of the first logical qubit at a stated p and noise bias, a reader comparing candidates should match on D, on p, and on the bias before reading off a winner.

The paper's own ranking shows why: the best code among the contenders at the same effective distance changes with the noise bias, so a ranking produced under depolarizing noise does not transfer to X-, Y- or Z-biased noise. The bias scenario used in the comparison sets one Pauli at probability 0.8p while each of the other two occurs with probability 0.1p.

The practical threshold the paper highlights is the target LER. At p = 10^−3 and a target of 10^−12, the surface code with d = 11 needs the fewest physical qubits at 121, but once a minimum encoding rate of e* = 0.2 is imposed, GALA reaches the same target with 132 physical qubits for 30 logical qubits. The binding constraint is therefore the combination of target LER, physical-qubit budget and required encoding rate, not any one of them alone.

Sources used in this answer