PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning for Syndrome Extraction

John Zhuoyang Ye, Aarav Pabla, Jens Palsberg

arXiv:2609.12020v1cs.LGquant-ph

TL;DR

Finding low-LER syndrome-extraction schedules is difficult because the search space is large and prior methods trade solution quality against scalability. FastSched combines reinforcement learning with importance sampling to search and evaluate schedules. It reports lower LER than AlphaSyndrome and PropHunt on average, including at surface-code distance 15.

  • Problem

    Schedule synthesis seeks low-LER implementations, but prior approaches trade solution quality against scalability.

    Source: §1 · pp. 1–2

  • Method

    FastSched uses reinforcement learning to search schedules and importance sampling to estimate their LER.

    Source: §1 · p. 2, §7 · p. 11

  • Results

    FastSched averages 25.9% lower LER than AlphaSyndrome and 71.7% than PropHunt; at d=15 it measures 3.62×10−9, an estimated 97.8% reduction versus AlphaSyndrome.

    Source: §7 · p. 11

  • Takeaways & Limitations

    The results support combining RL and importance sampling for syndrome-extraction scheduling when direct failure samples are scarce.

    Source: §7 · p. 11

    Finite-sample rewards can be biased by the nonlinear logarithm, and adaptive stopping adds another bias source; final schedules are therefore assessed independently with target-noise Monte Carlo.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

A key subtask of quantum error correction is to extract a syndrome that, if nontrivial, signals an error. The number of possible ways to extract a syndrome grows exponentially with the syndrome size, and these implementations vary greatly in fault tolerance, as measured by their logical error rates. This creates a natural search problem: find an implementation with a low logical error rate. Previous work solves this problem but sacrifices either solution quality or scalability. In this paper, we use reinforcement learning and importance sampling to outperform previous work at all scales. Compared with the state of the art automatic scheduling tools AlphaSyndrome and PropHunt, our tool reduces the logical error rate by 25.9\% and 71.7\% on average, respectively, culminating with a reduction of 97.8\% for a surface code with distance 15.

1 Introduction

Syndrome-extraction schedules have an enormous search space, and prior tools trade solution quality against scalability. FastSched combines reinforcement learning and importance sampling, reducing logical error rates against both state-of-the-art tools.

Syndrome Extraction

  • Choosing CNOT orders across checks yields a factorial number of schedules before timing restrictions or symmetries are considered.For the example code, the order space is approximately 3.1 × 10^24 combinations.Source: §1 · p. 1

State of the Art

  • Prior tools trade solution quality against scalability: AlphaSyndrome scales poorly to large distances, while PropHunt can return schedules with much higher LER.The schedule-synthesis goal is to find a schedule with low logical error rate.Source: §1 · pp. 1–2

Outline of Our Approach

  • FastSched’s RL agent chooses each check’s CNOT order based on earlier choices, learns from complete-circuit LER estimates, and selects one schedule.It evaluates many schedules with small sample budgets during training, then uses larger budgets to re-evaluate candidates before a final high-precision evaluation.Source: §1 · p. 2

Our Results

  • 25.9% and 71.7% average LER reductions versus AlphaSyndrome and PropHunt, respectively; at distance 15, FastSched achieves an estimated 97.8% reduction.The comparison uses matched code, noise model, and decoder for the distance study.Source: Figure 3 · p. 2, §1 · p. 2

Outline of Our Approach

  • Importance sampling amplifies fault probabilities so logical failures occur more often, then corrects for the changed sampling distribution to estimate LER.This targets the rare-event problem: most samples do not produce a logical failure.Source: §1 · p. 2

Our Contributions

  • The contributions include an RL schedule-synthesis formulation, an importance-sampling evaluator with increasing sample budgets, and a proof of unbiasedness under a fixed sampling budget.Source: §1 · p. 2

2 Background

Syndrome extraction uses checks and ancillas to measure stabilizers, while gate order and timing determine how faults propagate. The background defines schedules, logical-error evaluation, and the learning and decoding concepts used in the paper.

Syndrome-Extraction Schedules

  • For overlapping X and Z checks, placing all X-check CNOTs before all Z-check CNOTs preserves their joint measurement.The checks use separate ancillas.Source: §2 · p. 3

From an Ancilla Fault to a Logical Failure

  • An ancilla fault can propagate through later CNOTs into a correlated hook error, and an aligned surface-code schedule can admit a logical error from two circuit faults.The two-fault example combines a hook with a boundary-check fault to form a logical operator.Source: §2 · p. 3
  • Circuit fault distance counts the minimum faults for an undetectable logical operation, but schedules with equal fault distance can still have different LERs.LER depends on the probabilities of fault patterns that cause decoder failure, not only the minimum fault count.Source: §2 · p. 3

Syndrome-Extraction Schedules

  • A schedule assigns CNOTs to time steps and chooses an order within each check; the unrestricted order space is the product of check factorials.For the distance-five rotated surface code, the cited order count is approximately 3.1 × 10^24.Source: §2 · pp. 3–4

Logical Error Rate and Circuit Evaluation

  • LER sums logical failure probabilities in separate X- and Z-memory experiments; decoding uses MWPM or BP-OSD, which supports faults affecting more than two detectors.Source: §2 · p. 4

Reinforcement Learning and PPO

  • In PPO-based RL, a policy chooses actions, a critic predicts future reward, and generalized advantage estimation assigns credit across a trajectory.PPO uses clipped updates to discourage large changes in action probabilities.Source: §2 · p. 4

Logical Error Rate and Circuit Evaluation

  • Direct Monte Carlo requires approximately N ≈ 1/(p_L ε^2) shots for relative standard error ε, making estimation increasingly expensive as failures become rare.Source: §2 · p. 4

3 Our Reinforcement Learning Approach

FastSched treats syndrome-extraction scheduling as sequential CNOT-order decisions, using circuit LER to train a policy and select one fixed schedule. Its workflow includes candidate re-evaluation and optional local improvement after training.

3.1 Markov Decision Process Formulation

  • The actor chooses each check’s CNOT order in sequence, forming a complete schedule whose terminal reward is its LER.The state records the partial schedule and code structure; a fixed action table caps the orders considered for larger checks.Source: §3.1 · pp. 4–5

3.2 Objective and Reward

  • The reward combines logarithmic LER with an exploration bonus for less-used gate orders, while code, noise, memory duration, and decoder stay fixed during search.Final schedule selection ranks candidates by LER rather than the exploration bonus.Source: §3.2 · p. 5

3.3 Learning Algorithm

  • Training collects schedules, evaluates their LERs, and updates the actor and critic with PPO; coordinated auxiliary candidates also enter the saved pool.GAE carries the terminal reward backward through the stored trajectory, and PPO clipping limits credited gains from large action-probability changes.Source: §3.3 · pp. 5–6

3.4 Post-Training Selection

  • After training, FastSched merges and deduplicates candidate pools, re-evaluates a shortlist with fresh samples and larger budgets, then optionally tests local order changes.Local improvement accepts a change when its estimated LER improvement exceeds one combined standard error; the selected schedule is independently assessed afterward.Source: §3.4 · p. 6

4 Schedule Evaluation

FastSched uses importance sampling to make logical failures more observable during schedule evaluation, while correcting samples to estimate LER under the target noise model. It allocates evaluation effort adaptively, then independently assesses selected schedules because adaptive stopping can bias estimates.

4 Schedule Evaluation

  • Direct Monte Carlo becomes costly as failures grow rare; importance sampling amplifies fault probabilities and corrects for the changed sampling distribution to obtain more informative LER estimates with fewer shots.The evaluator weights failed samples by the likelihood ratio P/Q and supplies the resulting estimate as the reward signal for PPO.Source: §4 · p. 6, §4.1 · p. 7

4.2 Importance-Sampling Estimator

  • The fixed-budget estimator weights failures sampled under an amplified distribution to estimate target-noise LER, with unbiasedness requiring the amplified distribution to cover every target-supported pattern.The decoder remains fixed for the target distribution while sampling probabilities change.Source: §4.2 · p. 7

4.3 Choosing the Amplification Factor

  • Three pilot runs calibrate the amplification factor to balance failure frequency, weight variance, and decoding cost, after which the median choice stays fixed throughout search.Source: §4.3 · p. 7

4.4 Allocating Shots per Schedule

  • Evaluations stop when the effective failure count reaches its target or the per-circuit shot cap is reached; targets rise from 30 during training to 200 and then 500 for narrowing candidate pools.The effective count accounts for unequal importance weights, and local improvement spends larger budgets on promising changes and small estimated improvements.Source: §4.4 · pp. 7–8
  • Fixed-budget variance falls as 1/N, but adaptive stopping can bias estimates, so the selected schedule receives an independent target-noise assessment.Source: §4.2 · p. 7, §4.4 · p. 8

5 Evaluation

The evaluation compares FastSched with prior scheduling tools across effectiveness, scalability, and ablations. It reports lower average LERs than both baselines and examines performance as code distance grows and physical noise falls.

5.1 Experimental Setup

  • The evaluation assesses released AlphaSyndrome and PropHunt circuits under the Brisbane noise model, with comparisons matched by code, noise, decoder, and memory duration.It uses Stim and code-appropriate decoders, and reports the two memory protocols separately.Source: §5.1 · p. 8

5.2 RQ1: Schedule Effectiveness

  • 25.9% versus AlphaSyndrome and 71.7% versus PropHunt are the average LER reductions reported across benchmark circuits.The averages weight circuits equally.Source: Table 1 · p. 8, §5.2 · p. 8
  • The same ancilla fault produced a logical failure in one Steane schedule but a harmless stabilizer after decoding in the delivered schedule.The example illustrates how gate ordering changes fault propagation.Source: §5.2 · p. 9, Figure 9 · p. 9
  • All eleven AlphaSyndrome point estimates improved, by up to 49.4%; confidence bounds established lower LER in seven PropHunt comparisons.Those seven PropHunt comparisons had estimated reductions of 58.2%–98.9%; the LP39 point reduction was 24.0% with an interval including no improvement.Source: §5.2 · p. 9

5.3 RQ2: Scalability Study

  • Importance sampling used 48.3%, 52.8%, 64.1%, and 40.3% fewer total training shots across four circuits spanning 7–45 data qubits.Final-LER intervals overlapped in all four cases, and the comparison measures sampling cost rather than matched uncertainty or wall-clock speedup.Source: §5.3 · p. 9, Figure 10 · p. 10
  • FastSched has confirmed lower LER than AlphaSyndrome at every tested distance from d=3 through d=15, with a 97.8% point reduction at d=15.The comparison uses rotated surface codes, one noisy Brisbane round, ideal boundaries, and MWPM.Source: §5.3 · p. 9, Figure 11 · p. 10

5.4 RQ3: Ablation Study

  • 66.0% lower mean normalized LER came from candidate re-evaluation, the largest measured ablation effect; larger shortlists gave 64.4% and importance-sampled feedback 8.1%.The full method averaged 13.0% above released baseline LERs in this short-budget study.Source: §5.4 · p. 10

5.3 RQ2: Scalability Study

  • At surface-code distance 5, the AlphaSyndrome-to-FastSched LER ratio reached 236.6× at 1/16 noise strength and 391.3× at 1/32.The corresponding FastSched LERs were 7.81 × 10^-8 and 1.17 × 10^-8, with wide bounds reflecting five and three observed failures.Source: §5.3 · p. 10, Figure 12 · p. 11

6 Related Work

Prior work addresses fault propagation through circuit design and automatic schedule synthesis, while rare-event methods target the cost of estimating logical failures. FastSched combines policy learning with importance-weighted evaluation at the target noise level.

Fault-tolerant circuit design

  • Surface-code schedules use the connection between gate ordering, hook faults, and fault distance to preserve code distance.Prior strategies orient hooks diagonally, interleave X and Z checks, or address hook errors through decoder design.Source: §6 · p. 11

Automatic circuit synthesis

  • AlphaSyndrome searches ordering and parallelism with MCTS guided by decoded LER, whereas PropHunt uses MaxSAT to find and resolve decoding ambiguities.FastSched instead learns a policy that constructs schedules one check at a time.Source: §6 · p. 11

Rare-event evaluation

  • Prior rare-event evaluators use splitting, stratified fault injection with extrapolation, or counts of minimum-weight failing configurations.FastSched uses importance weights so rewards reflect target-noise LER when failures are sampled under amplified noise.Source: §6 · p. 11

Learning with rare events

  • FastSched separates schedule learning from calibration of the noise-amplification factor, allowing learning from LER feedback at target noise.Prior work also applies rare-event sampling to learning through oversampling or adaptive sampling distributions.Source: §6 · p. 11

7 Conclusion

FastSched combines reinforcement learning with amplified-noise feedback and importance sampling for syndrome-extraction scheduling. It reports lower average LERs than both scheduling baselines and a measured LER of 3.62×10^-9 at surface-code distance 15.

Conclusion

  • FastSched reports average LER reductions of 25.9% versus AlphaSyndrome and 71.7% versus PropHunt, and a measured LER of 3.62×10^-9 at d=15 with an estimated 97.8% reduction versus AlphaSyndrome.The distance-15 comparison used matched 30-minute search limits.Source: §7 · p. 11
  • Noise amplification makes logical failures more frequent for learning, while importance weights convert samples into LER estimates at the target noise level.The agent explores combinations of gate orders and learns which choices yield lower LER.Source: §7 · p. 11
  • The results support combining reinforcement learning and importance sampling for syndrome-extraction scheduling when direct failure samples are scarce.Source: §7 · p. 11

8 Artifact

The paper provides an anonymous artifact with its code, experimental results, and reproduction instructions. Supplementary material documents scheduling details needed to reproduce the search.

8 Artifact

  • The anonymous artifact contains the code, experimental results, and instructions for reproducing the reported results.Source: §8 · p. 11
  • The authors state that a large language model assisted with manuscript text and experiment scripts, while they produced and verified all results.Source: §8 · p. 11

A Supplementary Scheduling Details

  • The supplementary scheduling material records action tables, PPO details, exploration settings, and post-training selection procedures.These details are provided to support search reproduction.Source: A Supplementary Scheduling Details · p. 14

A.1 Training Implementation Details

Training maps circuit-level LER feedback to gate-order decisions through PPO, while auxiliary shared-index exploration probes coordinated orders across checks.

A.1 Training Implementation Details

  • Training ends when preset batch, elapsed-time, or configured shot limits are reached; evaluation overhead is reduced by reusing circuits and decoder workers and deduplicating BP-OSD syndromes.The standard AlphaSyndrome comparison allows 80 batches per run with 30 candidate evaluations per batch.Source: §A.1 · p. 14
  • Action tables include every permutation for checks with at most 32 orders; larger checks use capped 32-entry tables built from rotations, reversals, and random permutations.A fixed seed makes the tables identical across PPO runs, and local improvement can add further permutations.Source: §A.1 · p. 14
  • The network uses two shared fully connected layers of 128 tanh neurons, with an actor head for masked action probabilities and a critic head for state-value predictions.The actor scores the maximum action-table size and masks invalid entries before sampling.Source: §A.1 · p. 14
  • PPO propagates the final circuit reward back through gate-order decisions, using prediction errors and a backward recursion to favor actions associated with better outcomes.Clipping the policy objective limits the incentive for large updates while allowing several updates from one collected batch.Source: §A.1 · p. 14

A.2 Coordinated Exploration

  • Shared-index exploration applies one table index across checks with the same Pauli type and weight, directly testing coordinated gate-order patterns.In a standard 30-candidate batch, 22 candidates come from the actor and eight from auxiliary exploration; PPO updates use the actor-generated trajectories.Source: §A.2 · p. 14

A.3 Post-Training Selection

Post-training selection re-evaluates promising schedules, optionally improves them through local changes, and uses calibrated importance sampling with uncertainty checks; final assessment uses fresh target-noise samples.

A.3 Post-Training Selection

  • The compiler re-evaluates a shortlist with fresh samples, retains the best candidates, and optionally refines starting schedules through one-check changes before fixing the lowest-estimated-LER output.Local trials reschedule the full circuit; local searches stop at preset limits or when no untested changes remain.Source: §A.3 · p. 15
  • Local changes are accepted when their estimated LER improvement exceeds a one-standard-error margin; close comparisons receive more samples, and accepted schedules are re-evaluated with fresh samples.The margin is a search heuristic; independent assessment, not the heuristic, supplies evidence for reported LER comparisons.Source: §A.3 · p. 15

A.4 Amplification Calibration

  • Amplification calibration tests candidate factors on random schedules, screens for at least eight effective failures, and selects the retained setting with the smallest work–variance score.The median of three pilot selections is held fixed during PPO, candidate re-evaluation, and local improvement in the default pipeline.Source: §A.4 · p. 16

A.5 Weighted Uncertainty for Local Selection

  • Weighted LER estimates provide the uncertainty measure for local selection, but adaptive stopping based on observed failures can introduce bias.Final assessment therefore uses independent target-noise Monte Carlo samples.Source: §A.5 · p. 16

B.1 Independent Assessment

  • Independent assessment uses fresh target-noise samples and confidence intervals to quantify sampling uncertainty in the fixed schedules' whole-window LER comparisons.For adaptively stopped earlier cases, the nominal two-standard-error intervals have approximate coverage; unresolved comparisons leave the LER ordering uncertain.Source: §B.1 · pp. 16–17

B.2 Surface-Code Distance Study

FastSched has confirmed lower LER than AlphaSyndrome at every tested surface-code distance through 15, with a 97.8% point reduction at distance 15. These comparisons concern selected circuits, not variation across independent search seeds.

B.2 Surface-Code Distance Study

  • 97.8% lower measured LER at d=15, with FastSched confirmed below AlphaSyndrome at all seven tested distances from d=3 through d=15.The distance study uses rotated surface codes, one noisy Brisbane round, ideal boundaries, and MWPM; the d=15 comparison has limited precision on the reduction magnitude.Source: §B.2 · p. 17
  • At d=9, FastSched's LER is 1.586 × 10^-7, 99.4% below AlphaSyndrome's point estimate; simultaneous bounds support at least 98.3% lower LER.At d=11, the LER is 4.840 × 10^-9, a 99.9% point reduction, with bounds supporting at least 98.9% lower LER.Source: §B.2 · p. 17
  • At d=13, FastSched's LER is 2.624 × 10^-8 versus AlphaSyndrome's 4.86 × 10^-7, a 94.6% point reduction with at least 56.3% lower LER under simultaneous 95% bounds.At d=15, their LERs are 3.623 × 10^-9 and 1.678 × 10^-7, respectively; the simultaneous ratio bound confirms the direction but has limited precision on the advantage's magnitude.Source: §B.2 · p. 17
  • The comparisons describe selected circuits rather than variation across independent search seeds.Each distance has one search seed, and the amplification factor was retuned after the initial study.Source: §B.2 · p. 17

B.3 Decreasing Physical Noise

Across the decreasing-noise study, measured LER advantages favor FastSched in the reported comparisons, with the LP39 advantage increasing at each displayed halving of noise strength. The evidence is based on best observed schedules from one or two attempts per setting, with some validation outcomes unresolved.

B.3 Decreasing Physical Noise

  • 236.6× at 1/16 and 391.3× at 1/32 are the AlphaSyndrome/FastSched LER ratios for surface d=5 using PyMatching.The wide uncertainty bounds reflect the small numbers of observed failures.Source: §B.3 · p. 17
  • 2.90×, 3.15×, and 7.59× are the LP39 AlphaSyndrome/FastSched LER ratios at strengths 1/2, 1/4, and 1/8; the measured advantage increases at each displayed halving.At 1/16 the ratio is 15.6×, and the single-run comparison gives 18.0× at 1/32.Source: §B.3 · p. 17
  • For RQT54, the reported lowest-LER ratios are 1.82× at 1/2, 3.23× at 1/4, 3.87× at 1/8, 4.54× at 1/16, and 18.2× at 1/32.The 1/8 and 1/16 comparisons have separated simultaneous bounds.Source: §B.3 · pp. 17–18
  • The reported comparisons show best observed schedules from one or two runs per setting, so they do not estimate typical optimizer performance across independent searches.More independent search seeds would be needed to estimate that performance and establish how the advantage changes with noise.Source: §B.3 · p. 18
  • The noise ladder scales Brisbane error probabilities while preserving their ratio and fault locations; searches use two attempts per method and a 450-second ceiling, with fixed-shot direct-MC assessments.The displayed extension includes RQT54 strengths from 1/2 through 1/32 and LP39 at 1/16 and 1/32.Source: §B.3 · pp. 18–19
  • In the separate RQT54 validation, all four saved schedules pass both importance-sampling checks, while direct controls establish the LER ordering but cannot certify FastSched's rare-event rate below 10^-8.The second FastSched seed's cross-factor discrepancy is 2.97 combined standard errors, within the registered three-standard-error criterion.Source: §B.3 · pp. 18–19

B.4 Component and Local-Improvement Studies

In the component and local-improvement studies, local improvement accounted for 21.0% of the measured final advantage, while ablations identified three components with measurable benefits. The studies also found that, at the short training budget, the full method remained above the released baseline on average.

Component comparisons

  • The component study compared ten training and later-stage changes across eight circuits, using four seeds and matched sampling budgets for the training variants.It comprised 160 searches, with independent fixed-shot assessment of final outputs.Source: §B.4 · p. 19
  • Candidate re-evaluation reduced mean normalized LER by 66.0%, retaining more candidates by 64.4%, and importance-sampled training feedback by 8.1%.These percentages compare the full method with the corresponding ablated variants; normalized LER divides output LER by the released baseline LER.Source: §B.4 · p. 19
  • At the short training budget, the full method averaged 13.0% above the released baseline LER, and effects for the other seven components remained unresolved across seeds.Measurement and seed-bootstrap analyses favored the three components above, with component effects overlapping and interpreted separately.Source: §B.4 · p. 19

Contribution of local improvement

  • Local improvement raised the mean baseline reduction from 33.7790% to 42.7320%; its additional 8.9531 percentage points accounted for 21.0% of the final advantage.The approximate simultaneous 95% measurement interval for the local-improvement share was [18.5, 23.4]%, with searched schedules held fixed.Source: §B.4 · p. 19, Figure B.1 · p. 20
  • The 19-circuit local-search estimates were 70.9% for AlphaSyndrome cases and −0.4% for PropHunt cases; the extra PropHunt pass had an unresolved effect.The suites used different search budgets: up to five rounds from two starts for AlphaSyndrome cases, and one added round with at most 256 neighbors for PropHunt cases.Source: §B.4 · pp. 19–20
Loading 2609.12020v1…