betaFeedback

WorksPhysics and Astronomy

Evolving Decoding Algorithms for Quantum Error Correction

Abstract

Quantum computation entails robustness engineering: a noisy quantum state is measured continuously, and a classical algorithm (the decoder) must infer corrections that reliably remove the noise, fast enough to keep up. We write several published belief-propagation (BP) decoders for quantum low-density parity-check (qLDPC) codes in a Domain-Specific Language (DSL), and search over it with grammatical evolution. Written in the language, the published decoders show their parameters in plain view, allowing us to re-parameterise BP+OSD (ordered statistics decoding) and BP+LSD (localized statistics decoding) decoders with damping, before any search, making each 17.1–41.0×\times faster at a higher error rate, and BP+OSD-0 about 103 faster than the ldpc package's version tuned on the [[72,12,6]] bivariate-bicycle code. Evolution over the language finds decoders that improve the time-error front. One makes 23% fewer logical errors than BP+OSD-0 with damping at 0.64×\times its time, and decoders evolved from random code are more accurate than ldpc's tuned BP+OSD-0 at 1/31 of its time or less. Frozen at one operating point, the two fastest evolved decoders generalize well across noise levels, code sizes and round counts, staying at the time-error front. Ultimately, we demonstrate that capturing expert knowledge within a DSL creates a powerful intermediate layer—one that effectively bridges human intuition and machine-driven optimization to unlock highly efficient quantum error correction.

Introduction

A quantum computer is a machine whose very state is in constant noisy decay, and whose scalability rests critically on recovery mechanisms of quantum error correction (QEC) (for an accessible introduction, see [25]). In QEC, measurements detect which errors have occurred; a classical algorithmic decoder infers which corrections to apply. The better the decoder, the more robust the system is.

A quantum state encodes data that cannot be inspected directly: observation is a destructive process; monitoring is therefore indirect, relying on repeated measurements of parity checks on ancilla qubits. Noise causes these checks to trigger, and the resulting pattern is called a syndrome. The decoder’s job, given a stream of syndromes, is to infer appropriate corrections in real time, round after round. This presents two distinct engineering challenges. First, computational intractability [12]: every practical decoder must be a heuristic balancing accuracy with real-time performance. Second, degeneracy: distinct errors may produce the same syndrome and require equally valid corrections. This symmetry stalls message-passing inference [23], requiring the decoder to algorithmically break such ties.

To overcome the limitations of human-designed heuristics, we carry out an evolutionary search for decoder algorithms. The substrate of evolution is a Domain-Specific Language (DSL): a small vocabulary of typed operations in which the published decoders of one family—belief propagation (BP, recognizable to the ML community as a graph-based message-passing algorithm for probabilistic graphical models) plus a tie-breaking post-processor—are short programs (§2, App. A). The DSL plays two roles: it defines the space of algorithms explored by the search, and simultaneously becomes the lexicon recording all such algorithms found: it is a common layer that human experts can understand, and computers can explore mechanically. Regardless of the manner in which the code is produced or found—by evolution, by human researchers, or by language models—it is a tangible artefact useful to two audiences: humans can read and compare it against other algorithms; computers can parse and execute it, measuring its effectiveness. The DSL is thus not a convenience but the decisive expert-knowledge input: domain knowledge enters through the representation; the search itself stays generic. Prior evolutionary work tunes weights inside a fixed Belief Propagation with Ordered Statistics Decoding decoder (BP+OSD) [14]; ours writes the algorithm.

The paper makes two contributions. Contribution 1 (methodological): writing the state of the art in a language exposes what its implementations hide. By expressing BP+OSD and BP with Localized Statistics Decoding (BP+LSD) as compositions of named and typed steps, their parameters are brought into plain view. Simply re-parameterising them with damping made them significantly faster, at a higher error rate, even before any search is applied (§3). Contribution 2 (algorithmic): We discover evolved decoders that break the Pareto front of speed versus accuracy—running faster than the reference decoder while producing fewer errors—including some evolved entirely from random code (§3). Every evolved decoder reported here was produced by grammatical evolution alone. There is no language model in the variation loop. These results provide a counterexample to the view that genetic programming [13] is ineffective on real algorithm-discovery problems [21], as well as to the prevailing narrative in recent LLM-driven program discovery [27, 20] that classical variation is the weak link.

Experiment setup

We focus on the [[72,12,6]][[72, 12, 6]] bivariate-bicycle code [3] under circuit-level noise (physical error rate p=0.004p = 0.004, six rounds, ZZ basis)—a configuration we designate as the exam-point—with the error model extracted by the Python library Stim [9]. A syndrome acts as the input feature vector, and one shot represents a single inference pass. A shot is decoded correctly when all twelve encoded bits are recovered, making the logical error rate (LER)—the fraction of failed shots—our primary classification error metric.

We designed the DSL by reading the published BP+ family of decoders (the panel) and factoring them into reusable operations, each an algorithmic step used by at least one of the published decoders: 38 typed operations in eight groups, with enumerated tags for rules, schedules and orderings, and a constant prior drawn from the published operating points (Appendix A). An evolved decoder is an ordinary typed function solve(state) → state, called once per shot; its control flow is written by evolution itself. Panel and search are one family by construction, so neural, matching-based and tensor-network decoders lie outside both (Appendix C).

def solve_bp_osd_cs(state):
    state = run_bp(state, BP_ITERS, BpRule.MIN_SUM, BP_ALPHA, 0.0,
                   Schedule.PARALLEL, BP_GAMMA)
    if bp_converged(state):
        return state

    ranking = rank_faults(state, RankKey.POSTERIOR, Order.ASCENDING)
    state = most_reliable_basis(state, ranking)
    state = solve_on_basis(state)
    state = keep_candidates(state)
    state = enumerate_patterns(state, OSD_CS_WEIGHT, OSD_CS_TOP, Scope.GLOBAL)
    state = select_best(state, SelectKey.PRIOR_WEIGHT)
    return state

Listing 1: BP+OSD-CS as written in the DSL (our damped variant).

Published comparators use the authors’ own packages at their tuned settings where available: ldpc’s BP+OSD-0 and BP+OSD-CS [26, 22, 8], and Relay-BP [19]. For Ambiguity Clustering (BP+AC) [29], which lacks an open-source implementation, we use our DSL implementation of its published stages, certified against an independent re-implementation (Appendix § 7).

Times in the body are clean wall-clock milliseconds per shot on a benchmark workstation (Apple M3 Ultra, single process, idle), with ratios against the reference decoder of § 3 unless another is named.

The engine is MAP-Elites [18, 24] utilizing a 1-dimensional behavioral characterization (computational cost) with one cell per cost bin, which forces the quality-diversity engine to act as an explicit Pareto-front discoverer. Parents are drawn by tournaments of three over the cells, each generation 64 programs scored on a 1 024-shot training draw. To efficiently navigate the fitness landscape, we apply an importance sampling technique: the draw over-samples the hard instances where plain BP fails and reweights each by its inverse sampling probability. This focuses the selection gradient on informative edge cases while keeping the objective function unbiased. Selection ranks on accuracy plus a weighted cost term limited by per-shot budgets (Appendix § 8).

The campaign ran twelve runs: two founder arms (seeded with eighteen published compositions, or random code) times two cost axes (the work proxy, or wall-clock calibrated per worker) times three replicates, each run for 80 generations (1.1–2.6 h on 120 actors); the winner of each run first appeared between generations 14 and 76. The evolved decoders are named C01 to C15: the champion each run selected on the validation split (C01 to C12; C01 and C02 duplicate C03 and C09 and are not reported separately), and three further validation finalists from the archive (C13 to C15; App. § 8).

Three dataset splits were generated: train (drives selection), validation (screening and candidate naming) and final.

The final split is uniform, unweighted, and strictly read once, exclusively for subjects named in advance, against dominance bars pre-registered before the campaign ran (Appendix § 8). Comparisons are paired on common shots and adjudicated by McNemar tests [17, 5].

In the literature, qLDPC decoders are already compared on accuracy and time together, matched to BP+OSD’s accuracy and then timed [29, 11] or faster and more accurate at once [31]. Recent benchmarking names the criterion: a decoder is on the Pareto frontier when none is both faster and more accurate [16]. We adopt it as the standard for a discovered recovery mechanism: Pareto competitiveness against the published standard and not record-setting accuracy. Improving robustness (accuracy) competes for the compute budget (cost) of the recovery loop, which in a fault-tolerant stack is a hard real-time constraint. Pressure on the trade-off is what keeps discovered mechanisms deployable rather than merely accurate.

Results

Contribution 1: writing the state of the art in a language exposes damping. Writing the BP-plus-post-processor family in the DSL puts every parameter of every published decoder in one place, and one of them, the damping of the BP front end [19], is a knob the ldpc package does not expose and cannot be tuned.

In loopy graphical models, standard BP often oscillates and fails to converge; damping acts as a momentum term that stabilizes message passing. The ability to modify this parameter makes the computationally inexpensive—but normally unstable—flooding min-sum schedule viable. Tuning it results in a decoder comparable to ldpc’s BP+OSD-0: while it incurs a higher LER (0.04392 to 0.05454), it runs in roughly 1/103 of the time, effectively leveraging the speed-for-accuracy tradeoff inherent to this representation. We call this tuned decoder P2-d and make it the cost reference (1.0×\times) for everything that follows, chosen because it is the fastest decoder in its family. Table 1 isolates the parameter effect across the decoders in ldpc by running both versions in the DSL’s engine. Every damped member is faster, by 17.1×\times to 41.0×\times, and every damped member is less accurate.

familyms per shotspeed-upLER, pub. → dampedzz
pub.damped
BP+OSD-0365.088.9141.0×0.04355 → 0.05525+25.8
BP+LSD-0364.2416.2522.4×0.05080 → 0.07241+42.7
BP+LSD-μ\mu364.1716.2622.4×0.05048 → 0.07206+42.7
BP+OSD-CS372.3521.7117.1×0.03841 → 0.04224+9.2

Table 1. Contribution 1: each decoder published in the ldpc library, at its published settings and damped, both run in the DSL’s engine. Time is clean ms per shot, one single-threaded process; LER is on the final split; zz is McNemar, positive when the published member is right more often. Settings and the timing protocol are in Appendix § 11.

Contribution 2: evolved decoders that break the Pareto front. Sixteen finalists were drawn from the four experimental arms. Four of these (C03, C07, C08, C09) met the stretch bar: not Pareto-dominated by any panel member, more accurate than the reference, and cheaper than it by at least the 1.4×\times margin.

Of these, C03 makes 23% fewer errors than the reference at 0.64× its time (z=+31.8z = +31.8, at the exam-point of Figure 1). Measured against ldpc’s tuned BP+OSD-0 instead, the same decoder runs at 1/160 of its time with 4.8% fewer errors (z=+5.0z = +5.0).

Logical error rate against clean time per shot

Figure 1. Logical error rate against clean time per shot (log scale) at the benchmark’s exam-point (n=72n = 72, p=0.004p = 0.004, six rounds; 200 000 shots); down and left is better. C12 (LER 0.1538) lies outside the frame; hollow marks missed the primary bar. The dashed line is the time–error front computed from the drawn rows: C09, C03, C04, C10, BP+AC, Relay-BP at stop 5 and at stop 9.

Figure 1 draws every benchmarked row; the front computed from them runs C09, C03, C04, C10, BP+AC, Relay-BP at stop 5 and at stop 9, so the four fastest decoders on it are evolved. Ambiguity Clustering and Relay-BP reach lower error rates, at about six and thirty-four times C03’s time (z=+10.2z = +10.2 for Relay-BP over BP+AC). Relay-BP at its tuned point is more accurate than every evolved decoder in this paper —at stop 9 it errs on 0.02795 of shots at 270.6 ms.

The seeded winners are descendants of Ambiguity Clustering that keep its shape and differ in the settings: C03 and C09 run BP+AC’s own stages with min-sum BP in place of product-sum (Appendix § 6), C07 and C08 add a degeneracy cut (a published op) before BP+AC’s search, and at the accurate end C14 retunes BP+AC’s constants to beat published BP+AC on the final split (0.03206 vs. 0.03435, z=+9.4z = +9.4) at 0.80× its time (Listing 3; Table 7).

subjectarmLERproxytimezz vs P2-dzz vs P10bar
C13seeded, wall-clock0.030202.9refusedprimary (proxy)
C14seeded, proxy0.032062.42.145+54.7+9.4primary
C15seeded, proxy0.035721.11.011+46.6−4.1primary
C10random, wall-clock0.040362.72.389+35.9−22.0primary
C04random, proxy0.040652.01.882+35.8−20.6primary
C08seeded, wall-clock0.041590.570.534+33.1−19.6stretch
C03seeded, proxy0.041730.580.565+33.4−19.6stretch
C09seeded, wall-clock0.043150.540.537+30.8−22.5stretch
C07seeded, wall-clock0.046940.460.456+23.3−31.9stretch
C06random, proxy0.055841.00.995−1.7−49.4primary
C11random, wall-clock0.066192.41.955−22.2−66.0—
C05random, proxy0.066262.41.887−22.4−66.1—
C12random, wall-clock0.15511.81.658−126.9−146.7—
P5 Relay-BP (our port)panel0.0285640.035.57
P10 BP+AC, as publishedpanel0.034353.02.67
P3 BP+OSD-CS, 1dpc’s pointpanel0.0384126.0
P2 BP+OSD-0, 1dpc’s pointpanel0.0435525.1
P2-d (the reference)panel0.055251.01.00

Table 7. The slate on the 200 000 shots of split s20261004, sorted by LER. Proxy and time are in P2-d units (time on one pinned core); zz is McNemar, positive when the subject is right more often than the named panel member (P2-d the reference, P10 Ambiguity Clustering as published). Two further finalists make the same decisions as C10 and C06 on every shot and are not repeated.

From random code, evolution re-found BP+OSD-0 and tuned its BP stage (damped parallel product-sum), reaching the front past ldpc’s tuned BP+OSD-0: C10 makes 25% fewer errors than the reference (z=+33.6z = +33.6) and is more accurate than ldpc’s tuned BP+OSD-0 (z=+8.9z = +8.9) at 1/31 of its time, and C04 is more accurate (z=+6.9z = +6.9) at 1/44. Both are Pareto- dominated past ldpc’s BP+OSD-0 and never past BP+AC, which at about C10’s time has the lower error rate (z=−18.9z = -18.9 for C10).

Frozen at their exam-point, C03 and C09 are on the time–error front at all twenty-two benchmark points, with C03 strictly dominating the reference—making fewer errors in less time—at every point and beating published BP+AC at n=90n = 90, 108, 144 (Figure 2). Over the benchmarked rows, BP+AC is on the front at seventeen points, Relay-BP at sixteen (stop 9) and ten (stop 5), C04 at thirteen and C10 at eleven, and the reference at none. At n=144n = 144, C03 makes 310 errors in 24 500 shots at 29.9 ms, against BP+AC’s 431 at 211.6 ms, Relay-BP’s 448 at 2 553 ms (stop 5) and the reference’s 816 at 79.3 ms. The fronts compare point estimates, and shot counts vary by point (Appendix § 10), so the counts are not significance statements.

Figure 2. Logical error rate with every decoder frozen at its exam-point settings, against physical error rate at n=72n = 72 (left), code length at p=0.004p = 0.004 (centre) and syndrome rounds at n=72n = 72, p=0.004p = 0.004 (right), with Wilson 95% intervals. A filled mark is on the time–error front at that point over every benchmarked row, and a hollow one is off it; C03 is filled at every point. Shot counts run from 10 216 500 (p=0.001p = 0.001) down to 3 500 (p=0.006p = 0.006) and 6 500 (18 rounds); at n=288n = 288, ldpc’s BP+OSD-CS was decoded on 4 000 of the point’s 40 000 shots. The error-rate axis is logarithmic on the left and centre panels and linear on the right.

Conclusion

This work shows that evolutionary search can discover efficient recovery mechanisms for quantum error correction, provided the domain expertise is encoded into a Domain-Specific Language (DSL).

The methodological contribution came before any search: writing the published decoders in a language put their parameters in plain view, and re-parameterising BP+OSD with damping ran it 41.0× faster within the same engine—and at about a hundredth of the packaged time—at a higher error rate, a trade exposed by the representation.

The algorithmic contribution is driven by the search itself. Operating from both seeded and purely random code, grammatical evolution discovered decoders that are faster than the reference while producing fewer errors. Crucially, the fastest of these evolved decoders hold the fast end of the time-error front and remain there—even when frozen—across a twenty-two-point benchmark spanning various noise levels, code sizes, and rounds. Ambiguity Clustering and Relay-BP remain more accurate, at several times their cost.

Ultimately, the transferable lesson of this work lies in the representation, not in the optimizer. A Domain-Specific Language serves as a common layer whose programs are natively readable by people, executable by machines, and discoverable by evolution. We expect this framework to outlast our specific search, directly challenging the assumption that classical variation is obsolete. The true bottleneck in automated algorithmic discovery is not a lack of sophisticated generative models, but the absence of tangible, auditable environments; when domain knowledge is properly embedded into the substrate, evolution alone is enough to move the fast end of the state of the art.

The DSL

The language is thirty-eight typed operations in eight groups, plus enumerated tags (BP rule, message schedule, orderings, ranking keys, scopes, sectors) and a constant prior. It was designed by reading the published BP+ family algorithms and factoring them into reusable steps; each operation (named and typed) is an algorithmic step used by at least one of the reference decoders in the published literature.

Table 2 lists the DSL vocabulary. Every operation is executed natively by a Rust engine on which an evolved program runs unchanged, and each benchmarked champion was also ported to a standalone native decoder, certified against the evolved program on the 200 000 shots of the exam-point with zero differing predictions.

groupnoperations
A prepare9init_llrs, scale_llrs, sparsify_dem, permute_problem, mask_columns, boost_priors_from_syndrome, use_check_basis, inactivate_check, cut_degenerate_supports
B engine5run_bp, bp_converged, reseed_priors_from_posteriors, rank_by_oscillation, valid_candidates
C ranking5rank_faults, most_reliable_basis, decimate, decimate_and_continue, rank_checks
D clusters7seed_clusters_from_syndrome, grow_clusters, syndrome_guided_reduce, reduce_marked_rows, enrich_blocks, clusters_valid, build_forest
E solvers3solve_on_basis, incremental_eliminate, forced_logical
F local search2enumerate_patterns, vote_logical_classes
G control5keep_candidate, select_best, branch_frontier, advance_frontier, prune_frontier
H assembly2assemble_cluster_solutions, map_back

Table 2. The 38 operations, by group. Every published panel member is expressible as a short composition; Appendix B prints three decoders in this vocabulary.

Three design rules at the core: first, typed enumerations instead of numbers wherever the literature has a discrete choice (rule, schedule, ordering), so that mutation moves among meaningful alternatives; second, the constant prior is the literature’s own operating points—BP iteration caps, damping factors, sweep depths and masking fractions are the values the papers use—and every tuned panel parameter is reachable as a listed constant, a fairness rule enforced by test; third, exclusions are stated, not silent: one catalogue operation (a per-shot linear-programming engine) is deliberately absent on per-shot cost grounds. The DSL vocabulary spans the family, and variation respects the types: mutation and crossover only ever substitute type-compatible subtrees and constants, so every offspring parses and runs by construction, with no syntactic-repair step.

Two evolved decoders in full, with Ambiguity Clustering for contrast

The audit that reads an evolved program has three clauses, scored by an automated audit against every panel member: structural (the canonical call multiset differs), behavioural (shot-for-shot predictions differ after ablation) and discordance (at least one decision differs).

A simple ablation removes whole top-level statements only, so a live statement carrying dead wrappers keeps them and the structural clause counts each; we therefore also prune below the statement—delete a statement at any depth, unwrap a call to its argument, flatten a constant branch—keeping an edit only when every prediction stays identical to the evolved program’s, and confirm each pruned form on 32 768 validation shots. Table 3 gives the verdict for the seven decoders this paper names.

decoderarmcallsnearestdist.verdict
evolvedpruned
C03seeded, work proxy54P10 (BP+AC)0retuning of BP+AC (min-sum inside BP+AC)
C09seeded, wall-clock44P10 (BP+AC)0retuning of BP+AC (min-sum inside BP+AC)
C07seeded, wall-clock249P10 (BP+AC)5recomposition: BP+AC + cut + frontier/reseed stage (panel ops)
C08seeded, wall-clock176P10 (BP+AC)1recomposition: BP+AC + P12’s degeneracy cut; mostly retuning
C14seeded, work proxy84P10 (BP+AC)0retuning of BP+AC
C04unseeded, work proxy155P3 (tool) / P2 (pruned)2recomposition of published stages (P4’s decimation + P2’s OSD-0); functionally P2 retuned
C10unseeded, wall-clock335P2 (BP+OSD-0)0retuning of P2

Table 3. What the evolved decoders are, after pruning: calls in the program as evolved and after pruning, the nearest panel member and the call-multiset distance to it after pruning, and the verdict. Every pruned form is prediction-identical to its evolved program on 32 768 validation shots; “unseeded” is the random-code arm.

def solve(state):
    state = run_bp(state, 9, BpRule.MIN_SUM, 0.7710300216438394,
                   0.003077120912963548, Schedule.PARALLEL,
                   0.3106797689580642)
    state = reduce_marked_rows(state, True)
    state = enrich_blocks(state, 0.04118582037119639, True)
    state = enumerate_patterns(state, 1, 4000, Scope.BLOCK_VOTE)
    return state

Listing 2: C03, the fast end, pruned. Ambiguity Clustering’s own stages—BP, elimination on the marked rows, enrichment of each cluster’s block, a per-cluster search—with min-sum BP in place of product-sum, a narrower enrichment and a weight-1 search, in four calls. BP+AC’s early exit after BP is gone: it changes no decision of C03’s on 32 768 shots. Every operation is one of the thirty-eight in Appendix § 5, and the whole function is called once per shot.

Table 4 says where the speed comes from. Putting product-sum BP back into either decoder roughly doubles its time and buys back part of the accuracy; restoring BP+AC’s enrichment width or its search weight costs time and does not help, and BP+AC’s early exit after BP, which C09 dropped, changes no decision. Substituting min-sum for product-sum BP inside BP+AC’s cluster post-processor is the mechanism that unlocks the fast end of the front.

change put backC03 LERC03 msC03 ×\timesC03 zzC09 LERC09 msC09 ×\timesC09 zz
none, as evolved0.041355.571.00.044155.431.0
product-sum BP0.0368010.71.9+3.80.0407510.11.9+3.0
enrichment κ=0.1\kappa= 0.10.041756.111.1−0.80.045356.301.2−3.8
search weight 20.041655.671.0−0.3—
early exit after BP—0.044155.400.990.0
all three at once0.0366011.22.0+4.0—
BP+AC as published0.0347531.35.6+5.6
P2-d, the reference0.055758.901.6−11.2

Table 4. Where the speed comes from: C03 and C09 with one of BP+AC’s settings put back at a time, on 20 000 shots of split s20260904, timed on the benchmark workstation. ×\times is time over the evolved decoder’s and zz is McNemar against it (positive: the variant is more accurate). The last two rows are BP+AC as published and the reference on the same shots, against C03.

def solve(state):
    state = run_bp(state, 31, BpRule.PRODUCT_SUM, 0.625, 0.0,
                   Schedule.PARALLEL, 0.4123303093240179)
    state = reduce_marked_rows(state, True)
    state = enrich_blocks(state, 0.03269060068025888, True)
    state = enumerate_patterns(state, 2, 4000, Scope.BLOCK_VOTE)
    return state

def solve_ambiguity_clustering(state):  # BP+AC as published, for contrast
    state = run_bp(state, 45, BpRule.PRODUCT_SUM, 0.625, 0.0,
                   Schedule.PARALLEL, 0.3)
    if bp_converged(state):
        return state
    state = reduce_marked_rows(state, True)
    state = enrich_blocks(state, 0.1, True)
    state = enumerate_patterns(state, 2, 4000, Scope.BLOCK_VOTE)
    return state

Listing 3: C14, pruned, above Ambiguity Clustering as published. The same four stages with three constants moved: 31 parallel product-sum sweeps against BP+AC’s 45, damping γ=0.412\gamma= 0.412 against 0.3 and enrichment κ=0.0327\kappa= 0.0327 against 0.1; BP+AC’s early exit is inert …

The panel

Table 5 names the panel’s rows and how each was certified. The published members are certified per shot against ldpc [26] (BP+OSD-0, BP+OSD-CS, BP+LSD) and against the Relay-BP package (Relay-BP, at the authors’ tuned point); Ambiguity Clustering, which has no open-source implementation, is certified against an independent re-implementation of its published stages and against the Ambiguity Clustering paper’s own reported point. Rows without an oracle are our variants or regime rows, and are labelled as such. The damped front ends have no package oracle and are certified against a float64 damping referee. P13 is structurally void at this operating point, and the primary bar counts dominance over the other members only.

What the panel does not contain. The DSL factors the BP-plus-post-processor family and the panel is drawn from it, so three decoder families are absent by construction rather than by selection: neural decoders such as AlphaQubit [1], which learn a decoding policy rather than compose one and are reported on surface-code data; minimum-weight perfect matching [10], which is not defined on a bivariate-bicycle code’s hyperedge error model without a further reduction; and tensor-network maximum-likelihood decoding [2], whose per-shot cost sits far outside the real-time budget this campaign selects under. They bound the claim rather than weaken it: every comparison in this paper is against the family a [[72,12,6]][[72, 12, 6]] decoder is built from today, and no claim here is a claim about the decoder literature as a whole. One neighbour is worth naming separately, since it is the closest methodological one: Kwak et al. [ [14] fit trainable per-message BP weights—the neural-BP parameterisation of Liu and Poulin [ [15], fitted without gradients—by differential evolution, and pair them with OSD. Their decoder is inside this family—it is a BP+OSD—but its weight vector has no counterpart in our constant space, whose BP engine carries scalar normalisation, offset and memory constants only, so it is not a panel row we could implement faithfully. The contrast is the one this paper is about: evolution over the parameters of a fixed algorithm, against evolution over the algorithm. We did not run it as a comparator.

Evaluation protocol details

Splits and the two exam-points. Each dataset has three splits: train (drives selection), validation (champion naming and the held-out readings) and final. The adjudication reads the final split s20261004 (payload 0c07de8e383fe98d), which this campaign never read; Table 1 is read there too. The benchmark’s exam-point is split s20260904 (payload e49376e681002aba), where Figures 1 and 2 and the ablation are read.

The enriched training pool. At this operating point most uniformly drawn shots are decoded by plain BP alone and so carry no signal about the post-processing under selection. Training shots are therefore drawn from two strata—the pool on which plain BP fails, and the remainder—and each draw is weighted by its inverse sampling probability, so selection concentrates on discriminating shots while every reported accuracy remains an unbiased estimate for the uniform distribution. The final and benchmark splits are uniform and unweighted.

Budgets. Selection ranks on accuracy plus a cost term of weight W∗=0.0071W^{*} = 0.0071, the weight at which P2-d and Ambiguity Clustering rank equal, chosen on a sweep over held-out validation shots before the reported runs. Four per-shot budgets bound what one shot may spend, and one cap bounds what an evaluation may spend on average (Table 6). An operation called with its budget spent does nothing, and the shot is decoded from the state the program has reached by then; an evaluation past the work cap scores as a failure. Column operations and the cap are twice the costliest seed’s measured usage on the hard shots the training pool concentrates on; the candidate budget truncates two seeds’ enumeration at no measured cost to their accuracy (no discordant shot for one, McNemar p=1.0p = 1.0 for the other); sweeps and operation calls are kept wider than that rule’s 734 and 88, so that evolved multi-round BP is not truncated.

Table 6: The campaign’s budget set (n1.m5b). Work is in the proxy of Appendix E, relative to the reference P2-d’s.

budgetlimitbounds
BP sweeps2 000 per shotmessage-passing sweeps, summed over every BP call
operation calls256 per shotcalls of any DSL operation; the budget of last resort for generated loops
candidates10 100 per shotcandidate corrections enumerated and tested
column operations982 256 per shotGF(2) column operations spent in elimination (OSD, LSD)
work cap60× P2-dmean priced work per shot over one evaluation

Table 6.

Table 5: The panel and its certification. “Oracle” is the independent implementation each row was checked against, and “result” what the check found on the shots stated. Rows marked “—” have no oracle: they are our variants, regime rows, or rows not carried.

memberoracleresult
iddecoderreference
P1BP[23]ldpc BpDecoder; the damping refereeserial: equal on every shot (1 024 x 6 points); flooding: 955-1 020 / 1 024 decisions equal, failures inside McNemar; float64 referee = ldpc on 4 096 / 4 096
P2BP+OSD-0 at ldpc’s tuned point[22]ldpc BpOsdDecodercorrections 1 024 / 1 024 and 1 023 / 1 024; failures equal
P2-ddamped (the reference)the damping referee; the undamped kernel via P1decisions equal the referee’s on every shot at 10 iterations
P3BP+OSD-CS[22, 8]ldpc BpOsdDecoder(osd_cs)corrections 1 024 / 1 024 at all four points; failures equal
P3-oursour OSD-CS sweepnoneour variant
P4BPGD, as published[30]noneregime row: a code-capacity method with no circuit-level claim
P5Relay-BP, our port[19]relay-bp 0.2.2, given the crate’s own strengthskernel per shot to ten iterations; leg machinery identical on every shot any stage converges (4 x 1 024); full decoder agrees with relay-bp’s float32 as often as its float64 does, failures inside McNemar
P6BP+SI-lite[6]noneour variant
P7BP+LSD-0[11]ldpc BpLsdDecoder(LSD_0)predictions 1 024 / 1 024 at both p behind the serial BP; no invalid correction
P7-ddampedthe damping referee; P7’s damped front end as P1damped front end as P1
P8BP+LSD-μ\mu[11]ldpc LSD_CS 1 and 10 (nearest)failures 50 / 49 and 0 / 0 (McNemar p = 1.0)
P8-ddampedas P7-ddamped front end as P1
P9BP+OTF[deMarti iOlius et al., 2026]nonethe published forest on the raw error model
P10BP+AC, as published[29]an independent re-implementation; the Ambiguity Clustering paper’s Table 1predictions equal on 16 384 / 16 384 at four settings and both p; the Ambiguity Clustering paper’s Table 1 point at 0.787x (0.768-0.807) on 524 288 fresh shots, within 25 % at 95 %
P10-oursBP+AC, our variantnoneour variant
P11BP+BS[31]—not carried
P12BP+DC[28]noneone cut per generator, BP restarted once
P13BP+CA[7]—structurally void here

Table 5.

Paired adjudication. All decoders decode the same shots (common random numbers), so comparisons are paired: McNemar’s test on the discordant counts bb (we succeed, they fail) and cc (the reverse), z=(b−c)/b+cz = (b-c)/\sqrt{b+c}. Dominance requires the test in both directions, so that low power cannot be read as parity. The oracles named above are configured independently of our own settings, not handed ours.

The bars and the verdicts. Primary: Pareto-dominated by no panel member at its best known settings, and strictly dominating at least one. Stretch: more accurate than the reference P2-d at a cost lower by the margin of 1.4×1.4\times. Reach: the accuracy of BP+OSD-CS at that cost. A cost verdict must hold on both rulers, the work proxy and pinned-core time (Appendix § 9). Overall, thirteen subjects met primary on the proxy and twelve on time, four met stretch on both (C03, C07, C08, C09), and zero met reach. Each decoder runs at its own budgets (the campaign’s for the subjects, the published settings for the panel), and the reference saturates none of them.

The slate. Table 7 is the slate as read. In all, sixteen subjects were frozen in writing before the read: the champion each run pinned, and the top-ranking archive finalists from the validation split; the table lists every one but one seeded finalist that we do not report, and the verdict counts above include it. C13, a seeded finalist, is the most accurate subject (LER 0.03020 at 2.9× P2-d’s proxy cost), but it raised an error on 42 of its timing shots, so its time ruler was refused and it meets primary on the proxy only; it is not reported in the body.

Time units. Time on this split is in P2-d units on one pinned core of an Intel Xeon Platinum 8581C, under two calibrations of one CPU model: the subjects under the campaign’s own (P2-d at 14 946 μ\mus per shot, drift 0.94%), and the panel rows under the earlier read’s (13 618 μ\mus), in which the campaign’s P2-d reads 1.016. So a subject’s time over a panel row’s, such as C14’s 0.80× BP+AC’s, spans the two calibrations. P5 here is our DSL port of Relay-BP at the authors’ tuned point (LER 0.02856 at 35.57 P2-d units), not the authors’ package; the body’s Relay-BP rows are the package, timed on the benchmark workstation.

Table 7: The slate on the 200 000 shots of split s20261004, sorted by LER. Proxy and time are in P2-d units (time on one pinned core); zz is McNemar, positive when the subject is right more often than the named panel member (P2-d the reference, P10 Ambiguity Clustering as published). Two further finalists make the same decisions as C10 and C06 on every shot and are not repeated.

The cost model

Selection ranked on a work proxy: a non-negative least-squares fit of per-shot wall time on one pinned core onto seven deterministic counters, frozen once fitted, in units of the reference P2-d’s mean (12 924.58 weighted units per shot). Table 8 gives the counters and their frozen weights; a min-sum edge update costs 0.52 of a product-sum one. Over 252 programs the fit’s 95th-percentile relative error is 11.8% in the fit and 21.2% held out (R2=0.998R^2 = 0.998), and its rank agreement with measured time is Kendall τ=0.973\tau= 0.973 (Spearman 0.998) on the fitting machine and τ=0.935\tau= 0.935 (Spearman 0.992) on the benchmark workstation. A cost gap counts only past a margin of 1.4×, set above the floor of 1.31× that the fit’s own error can resolve.

counterweight
BP edge updates, min-sum1.00
BP edge updates, product-sum1.91
GF(2) elimination words0.28
candidate-enumeration words2.25
ranking and scan elements0.30
DSL operation calls0.00
interpreter ticks0.00

Table 8. The work proxy’s counters and frozen weights, in units of one min-sum BP edge update.

Two rulers. Every adjudicated cost verdict is stated twice, in the proxy and in time on one pinned core, and must hold on both. On every timed subject the two agree within a factor of 1.01–1.26, and zero proxy verdicts were refused by the time ruler. Figure 3 is Figure 1’s companion on the proxy ruler, on the adjudication split. The body quotes neither ruler: its times are clean ms per shot on the benchmark workstation, where the proxy’s rank agreement with measured time is the τ=0.935\tau= 0.935 above.

Logical error rate against frozen work proxy

Figure 3. Figure 1 on the proxy ruler: logical error rate against the frozen work proxy in P2-d units (log scale), on the 200 000 shots of split s20261004. The ldpc-named rows here are our DSL compositions at ldpc’s tuned point, and Relay-BP at stop 9 is our DSL port, not the authors’ package. Two finalists that duplicate C10 and C06 shot for shot are not drawn; C12 lies outside the frame. The front computed from the drawn rows is C07, C09, C08, C15, C14 and Relay-BP at stop 9 (our port).

The wall-clock arm. The wall-clock arm selected on measured time, calibrated per worker against P2-d: each run records 120 calibrations, one per actor, and at 2 CPUs per actor a calibration probe measured a median drift of 0.9 %. The run summaries record those calibrations, but they cannot show that each actor re-calibrated during the run.

The twenty-two benchmark points

The benchmark grid holds twenty-two points: physical error rates p=0.001p = 0.001 to 0.006 at n=72n = 72, code lengths n=90,108,144,288n = 90, 108, 144, 288 at p=0.004p = 0.004, and syndrome rounds 7 to 18 at n=72n = 72, p=0.004p = 0.004, each a circuit-level memory experiment in the ZZ basis. Every decoder keeps its exam-point settings at every point, because retuning one row per point would oblige us to retune every row, and the evolved rows, selected at one point, would gain the most from it. Each point has its own shot count, from 10 216 500 at p=0.001p = 0.001 to 3 500, and times are clean ms per shot on the benchmark workstation except the ldpc rows, timed on a second workstation of the same model and calibrated to the first. Table 9 counts the points at which each row is on the time–error front. At p=0.001p = 0.001, C03 makes 760 errors at 2.30 ms and C08 633 at 3.83 ms, against BP+AC’s 718 at 7.23 ms, Relay-BP’s 915 at 22.7 ms (stop 5) and the reference’s 996 at 3.22 ms, on 10 216 500 shots. A clean pass of the Relay-BP package on the first 20 000 shots of the adjudication split (s20261004) reads 172.8 ms per shot at stop 5 and 272.0 at stop 9, 19.7× and 31.0× P2-d’s 8.77 ms in the same session, consistent with the grid’s 190.0 and 270.6 ms at the exam-point.

rowpointsrowpoints
C0322BP+AC17
C0922Relay-BP, stop 916
C0413Relay-BP, stop 510
C1011ldpc BP+OSD-CS1
C081ldpc BP+OSD-00
C05, C06, C07, C11, C120P2-d (the reference)0

Table 9. Points, of 22, at which each row is on the time–error front over every benchmarked row. Fronts compare point estimates.

Contribution 1 in detail: the damping knob and the damping pairs

What the factor of a hundred contains. On the 200 000 shots of the benchmark’s exam-point (s20260904), ldpc’s BP+OSD-0 at its tuned setting (product-sum BP, serial schedule) takes 903.75 ms per shot and errs on 0.04392 of shots. The same algorithm in the DSL with its BP stage re-parameterised —min-sum, flooding, damped— takes 8.82 ms, about 1/103 of the time, and errs on 0.05454 (z=+23.6z = +23.6 for the package). That factor compares a package with the DSL, so it contains the difference between ldpc’s C++ and our Rust engine as well as the parameter.

The parameter on its own. It is measured at the panel’s front end: undamped flooding min-sum limit-cycles on this code, and on validation shots at equal iterations it errs on 47.66% of shots against 5.15% damped —9.3× fewer errors at 1.04× the BP edge updates. ldpc reproduces the failure when given these settings undamped (47.4% at 96.0 ms per shot); its own stabiliser is the serial product-sum schedule, which is the expensive one. So “damping” names the re-parameterisation that damping makes possible: the rule (product-sum to min-sum), the schedule (serial to flooding) and the damping itself, and for BP+OSD-0 the iteration count.

The pairs of Table 1. Published front end: product-sum, serial, 30 it., undamped; OSD-0; damped front end: min-sum 0.625, flooding, 10 it., damping 0.3; OSD-0 (min-sum 0.625, flooding, 30 it., damping 0.3; LSD-0 to validity for the LSD pairs). Our sweep: as P2-d; sweep weight ≤2\le2 over the top 100 free columns; P3-d: as P2-d; OSD-CS order 60 (P3’s back end). Time is clean ms per shot on the benchmark workstation (Apple M3 Ultra, one single-thread processor; 256 timed shots a row after 32 of burn-in; P2-d unit 8 909.5 to 8 920.0 μ\mus per shot, drift 0.12%), and the LER is read on the 200 000 shots of split s20261004. Every damped member is faster, by 17.1× to 41.0×, and every damped member is less accurate, its LER 1.10–1.43× the published member’s (zz from +9.2 to +42.7 for the published member). The speed is not fewer BP updates: the damped LSD members perform more edge updates per shot than the published ones and are still faster, because an edge of serial product-sum costs far more than an edge of flooding min-sum. For BP+OSD-CS there are two damped variants: our own combination sweep, which also changes the back end, and its twin P3-d, the table’s row, which keeps ldpc’s OSD-CS and changes only the front end; the twin isolates the front end like the other three pairs, and it dominates our sweep, faster by 3.4× at a lower LER.

The search-engine evidence

The decision to utilize a quality-diversity engine is grounded in a controlled, pre-campaign evaluation on this specific decoder problem. To isolate the impact of the search loop, we compared MAP-Elites against an otherwise identical generational engine, initializing both arms with a bit-identical generation zero.

Early Discovery (20 Generations): At a constrained budget of twenty generations, the unseeded arm under MAP-Elites achieved a markedly higher held-out accuracy than the generational baseline.

Long-term Convergence (80 Generations): We then extended this to an eighty-generation budget using a matched three-replicate control. At this scale, the performance margin narrowed, as the generational arm discovered its best solutions late in the run. A held-out rescore of the winners maintained the directional advantage of MAP-Elites, but the difference was not statistically resolved at only three replicates per arm.

The definitive claim supported by this control is that quality-diversity search finds strong decoders earlier; whether it finds strictly better ones at a full compute budget remains an open question. The main results presented in Section 3 do not depend on this claim.

References

  1. [1]Johannes Bausch, Andrew W. Senior, Francisco J. H. Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuehzen Niu, Sam Blackwell, George Holland, Dvir Dafni, Juan Atalaya, Craig Gidney, Demis Hassabis, Sergio Boixo, Hartmut Neven, and Pushmeet Kohli. Learning high-accuracy error decoding for quantum processors. Nature, 635 (8040):834–840, 2024. doi: 10.1038/s41586-024-08148-8.DOI
  2. [2]Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum likelihood decoding in the surface code. Physical Review A, 90(3):032326, 2014. doi: 10.1103/PhysRevA.90.032326.DOI
  3. [3]Sergey Bravyi, Andrew W. Cross, Jay M. Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J. Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature, 627:778–782, 2024.DOI
  4. [5]Thomas G. Dietterich. Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10(7):1895–1923, 1998.pubmed.ncbi.nlm.nih.gov/9744903
  5. [6]Julien du Crest, Mehdi Mhalla, and Valentin Savin. Stabilizer inactivation for message-passing decoding of quantum LDPC codes. In IEEE Information Theory Workshop, ITW 2022, Mumbai, India, November 1-9, 2022, pages 488–493. IEEE, 2022. doi: 10.1109/ITW54588.2022.9965902. URL https://doi.org/10.1109/ITW54588.2022.9965902.
  6. [7]Julien du Crest, Francisco Garcia-Herrero, Mehdi Mhalla, Valentin Savin, and Javier Valls. Check-Agnosia based post-processor for message-passing decoding of quantum LDPC codes. Quantum, 8(1334):1334, May 2024.DOI
  7. [8]Marc P. C. Fossorier and Shu Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Transactions on Information Theory, 41(5):1379–1396, 1995.
  8. [9]Craig Gidney. Stim: a fast stabilizer circuit simulator. Quantum, 5:497, 2021.DOI
  9. [10]Oscar Higgott and Craig Gidney. Sparse blossom: correcting a million errors per core second with minimum-weight matching. Quantum, 9:1600, 2025.DOI
  10. [11]Timo Hillmann, Lucas Berent, Armanda O Quintavalle, Jens Eisert, Robert Wille, and Joschka Roffe. Localized statistics decoding for quantum low-density parity-check codes. Nat. Commun., 16(1):8214, September 2025.DOI
  11. [12]Pavithran Iyer and David Poulin. Hardness of decoding quantum stabilizer codes. IEEE Transactions on Information Theory, 61(9), 2015.arxiv.org/abs/1310.3235
  12. [13]John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
  13. [14]Hee-Youl Kwak, Seong-Joon Park, Hyunwoo Jung, Jeongseok Ha, and Jae-Won Kim. Evolutionary BP+OSD decoding for low-latency quantum error correction, 2025. arXiv:25l2.18273.arxiv.org/abs/2512.18273
  14. [15]Ye-Hua Liu and David Poulin. Neural belief-propagation decoders for quantum error-correcting codes. Phys. Rev. Lett., 122(20):200501, May 2019.DOI
  15. [16]Shay J. Manor, Leila S. Erhili, and Yassine Jebbouri. A sim-to-real study of surface-code decoder benchmarking, 2026. arXiv:2609.04557.arxiv.org/abs/2609.04557
  16. [17]Quinn McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12(2):153–157, 1947.pubmed.ncbi.nlm.nih.gov/20254758
  17. [18]Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. CoRR, abs/1504.04909, 2015. URL http://arxiv.org/abs/1504.04909.
  18. [19]Tristan Müller, Thomas Alexander, Michael E. Beverland, Markus Bühler, Blake R. Johnson, Thilo Maurer, and Drew Vandeth. Improved belief propagation is sufficient for real-time decoding of quantum memory. 2025. URL https://arxiv.org/abs/2506.01779.
  19. [20]Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J R Ruiz, Abbas Mehrabian, M Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, June 2025.arxiv.org/abs/2506.13131
  20. [21]Michael O’Neill, Leonardo Vanneschi, Steven Gustafson, and Wolfgang Banzhaf. Open issues in genetic programming. Genetic Programming and Evolvable Machines, 11(3–4):339–363, September 2010. ISSN 1389-2576. doi: 10.1007/s10710-010-9113-2. URL https://doi.org/10.1007/s10710-010-9113-2.
  21. [22]Pavel Panteleev and Gleb Kalachev. Degenerate quantum LDPC codes with good finite length performance. Quantum, 5:585, 2021.DOI
  22. [23]David Poulin and Yeojin Chung. On the iterative decoding of sparse quantum codes. Quantum Information and Computation, 8(10):987–1000, 2008.arxiv.org/abs/0801.1241
  23. [24]Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, Volume 3 - 2016, 2016. ISSN 2296-9144. doi: 10.3389/frobt.2016.00040. URL https://www.frontiersin.org/journals/robotics-and-ai/articles/10.3389/frobt.2016.00040.DOI
  24. [25]J Geschka Roffe. Quantum error correction: an introductory guide. Contemporary Physics, 60(3):226–245, 2019.DOI
  25. [26]J Geschka Roffe, David R. White, Simon Burton, and Earl Campbell. Decoding across the quantum low-density parity-check code landscape. Physical Review Research, 2:043423, 2020.DOI
  26. [27]Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco J R Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, January 2024.
  27. [28]Kento Tsubouchi, Hayata Yamasaki, and Shiro Tamiya. Degeneracy cutting: A local and efficient post-processing for belief propagation decoding of quantum low-density parity-check codes. arXiv preprint arXiv:2510.08695, October 2025.arxiv.org/abs/2510.08695
  28. [29]Stasiu Wolanski and Ben Barber. Introducing ambiguity clustering: An accurate and efficient decoder for qldpc codes. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 02, pages 402–403, 2024. doi: 10.1109/QCE60285.2024.10326.DOI
  29. [30]Hanwen Yao, Waleed Abu Laban, Christian Häger, Alexandre Graell i Amat, and Henry D. Pfister. Belief propagation decoding of quantum ldpc codes with guided decimation. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 2478–2483, 2024. doi: 10.1109/ISIT57864.2024.10619083.DOI
  30. [31]Min Ye, Dave Wecker, and Nicolas Delfosse. Beam search decoder for quantum low-density parity-check codes. PRX quantum, 7(3), July 2026.DOI

Paper details

vlnc:W_fdkpfyd9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents