Certifying quantum code and circuit distances at scale

The paper in detail

A detector error model lists each fault mechanism as a column of a detector matrix \(\mathbf D\) and an observable matrix \(\mathbf O\). The circuit distance is the least weight of a fault vector \(\mathbf e\) with \(\mathbf D\mathbf e=\mathbf0\) and \(\mathbf O\mathbf e\ne\mathbf0\); for a CSS code the code distance is the same problem with check and logical matrices. Because one ancilla fault spreads to several data qubits (a hook error), circuit distance can be smaller than code distance, and overestimating it by two overestimates the exponent of \(p\) in the low-noise logical error rate by one.

The authors evaluate the distance with three exact algorithms whose costs depend on different features. A dense dynamic program sweeps the columns, keeping the minimum weight for each boundary syndrome; its cost is set by the cut rank, not the distance. A weight-truncated version keeps only light partial solutions and joins forward and backward sweeps. A weight-bounded search branches on faults that flip an unsatisfied detector, pruned by a covering bound from a dual linear program and completed by table lookup. A cost model schedules them.

Reductions make circuits tractable. Keeping one memory basis is exact when checked; summing each check's detectors over rounds gives a small problem whose distance is a lower bound for any number of identical rounds. Minimum solutions of that collapsed problem are then lifted back to circuit fault sets of the same weight, which certifies the distance, and every reported error is replayed in Stim. The overestimates in the audit come from circuits with heavy checks and new schedules, where minimum fault sets combine hook errors from several checks, combinations that randomised searches rarely find.

For the gross code the certified one-cycle distance is 10, as assumed, and 428 schedules reach 11, though none reaches 12. For logical measurements, the SSIP merged codes keep distance 12 only when the gauge qubits introduced by merging are fixed; with them unfixed the dressed distance falls as low as 2. GPU parallelism, tree-shaped decompositions and sharper pruning bounds are left as ways to reach the remaining wide instances.

Transferable methods

1. Min-plus dynamic programming on the syndrome trellis

   Two partial fault assignments that produce the same syndrome on the columns seen so far have exactly the same completions, so only the lighter one matters. Storing one minimum weight per reachable syndrome turns an exponential search over fault sets into a sweep whose size depends on how many syndromes can cross each cut.

   Impose one logical row at a time: with \(\mathbf M^{(a)}\) the detector matrix extended by row \(a\) of \(\mathbf O\) and target \(\mathbf t=(\mathbf0,1)\), \[d=\min_a Z_{\mathbf M^{(a)}}(\mathbf t),\qquad Z_{\mathbf M}(\mathbf t)=\min\{|\mathbf e|:\mathbf M\mathbf e=\mathbf t\}=\lim_{\beta\to\infty}-\tfrac1\beta\log\!\sum_{\mathbf M\mathbf e=\mathbf t}e^{-\beta|\mathbf e|}.\] The update over column \(\mathbf m_j\) is \(T_j(\mathbf s)=\min\{T_{j-1}(\mathbf s),\,T_{j-1}(\mathbf s+\mathbf m_j)+1\}\), and only syndromes in an affine space of dimension \(w_j=\operatorname{rank}\mathbf M_{\le j}+\operatorname{rank}\mathbf M_{>j}-\operatorname{rank}\mathbf M\) can still be completed, so the table has at most \(2^{w_j}\) entries.

   Editorial check: for the Steane code (Hamming checks, logical \(\bar X=X^{\otimes7}\)) the sweep returns distance 3, matching brute force, with cut ranks \(0,1,2,2,3,2,1,0\). For a circuit ordered in time, where each fault touches detectors of a bounded number of consecutive rounds, the width is bounded independently of the number of rounds.

   How to reuse it

   Any minimum-weight solution of a sparse linear system over \(\mathbb F_2\), such as classical LDPC minimum distance or syndrome decoding in code-based cryptography, can be computed by the same min-plus trellis, with cost governed by the cut rank of a good column order rather than by the answer.

2. Relax, then lift: certified lower bounds that meet explicit errors

   A heuristic search finds a logical error, which only bounds the distance from above. A certificate needs a matching lower bound. Projecting the constraints onto fewer rows can only remove constraints, so its minimum is a lower bound, and it is much smaller; if one of its minimum solutions corresponds to a real circuit fault set of the same weight, the two bounds meet.

   For any binary matrix \(\mathbf T\), every solution of \(\mathbf M\mathbf e=\mathbf0,\ \mathbf R\mathbf e\ne\mathbf0\) also solves \(\mathbf T\mathbf M\mathbf e=\mathbf0\), so \[\Delta(\mathbf T\mathbf M,\mathbf R)\le\Delta(\mathbf M,\mathbf R).\] Time collapse takes \(\mathbf T\) to add each check's detectors over all rounds; after equal columns are merged, the collapsed problem has one row per check and does not grow with the number of rounds. If no collapsed solution of weight at most \(W\) lifts to a circuit fault set of that weight, the circuit distance exceeds \(W\), since every circuit fault set collapses to one of them.

   Editorial remark: this is the circuit analogue of bounding a code's distance by that of a code with fewer checks. For IBM's two-gross circuit the lower bound rises until it meets a weight-16 fault set, replayed in Stim, below the published upper bound of 18; since \(\lceil 16/2\rceil=8\), every decoder fails on some configuration of eight faults.

   How to reuse it

   Pair every heuristic minimum with a relaxation that can only lower the optimum: aggregating constraints, dropping rounds or projecting syndromes. When an explicit solution meets the relaxed bound, the value is certified; when it does not, report the interval.

Source: Methods (distance problems, Dense Rank DP, weight-bounded search, reductions and lifting). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. Distances become verified quantities rather than estimates, and in several published proposals the leading exponent of the logical error rate changes. IBM's architecture study assumed 18 for the two-gross code; some eight-fault configurations already cause failure. The same tools score all 8,496 uniform depth-seven schedules of five bivariate bicycle codes exactly, certify logical-measurement constructions, and certify chips with dead checks one at a time, raising the estimated usable share of gross-code blocks at 99.98% junction yield from 53% (perfect blocks only) to 94% with an improved schedule.

Limitations. Problems that are both wide and of large distance remain expensive: for IBM's \([\![756,16,34]\!]\) circuit only a lower bound of 15 is certified, and the largest Cornucopia circuit is left at an interval of 12 to 16. The audit covers instances the authors could reconstruct, under the papers' own noise models; circuit distance alone does not set the rate at a given noise level, which also depends on the number of low-weight fault sets. Lifting and the time-collapsed bound are proved for repeated identical rounds.

Description based on the full arXiv HTML of v1, read 2026-11-08: the main text (Results, Discussion) and Methods. The Supplementary proofs (Sections 3–5) and per-instance audit tables were not checked. The min-plus recursion and cut-rank formula were checked on the Steane code against brute force. The paper's mentions of LLMs refer to audited codes found by LLM-guided search, not to the authors' work.