Distance-Finding Algorithms for Quantum Codes and Circuits

1 Introduction

• Distance is the minimum number of physical errors required for an undetectable logical failure, providing a rigorous guarantee of error suppression.Protocol performance also depends on hardware-realistic noise and efficient decoding.Source: §1 · p. 2
• Fast upper bounds can filter unpromising quantum LDPC candidates, while tight lower bounds can build confidence before investing in circuits or decoder optimization.Circuit distance is upper-bounded by the distance of the code itself.Source: §1 · p. 2
• For a distance-11 colour code, a circuit memory experiment involves 43,298 error mechanisms, versus 91 for the code-distance calculation.The circuit example is an 11-round experiment using the superdense circuit; its detectors can each be triggered by up to 270 errors.Source: §1 · p. 2
• Distance-finding informs code and circuit design but does not replace full circuit-level simulations and, eventually, experimental demonstration.Those evaluations account for hardware-specific constraints, practical decoding, and fault-tolerant logic.Source: §1 · p. 3

2 Contribution of this Work

• Exact algorithms guarantee the distance on termination, whereas heuristic algorithms run faster but may provide only an upper or lower bound.The benchmark summarizes algorithm support across classical, CSS, and non-CSS codes, error models, probability, and parallelization in Table 1.Source: §2 · p. 3, Table 1 · p. 3
• The benchmark covers classical-code, quantum-code, and syndrome-extraction-circuit datasets, with recommended exact and heuristic methods listed in Tables 2 and 3.The tables identify recommendations by dataset, not a single method for all settings.Source: §2 · p. 3, Table 2 · p. 4, Table 3 · p. 4
• QDistEvol is significantly more accurate than other heuristic algorithms on the benchmark's quantum LDPC datasets.The contribution also adapts existing methods for classical codes, non-CSS quantum codes, and quantum circuits.Source: §2 · p. 4
• The codeDistance Python package provides algorithm wrappers and new implementations, along with the benchmark test data.It includes an open-source Brouwer-Zimmermann implementation that supports classical, CSS, and non-CSS codes.Source: §2 · p. 4

3.1 Distance of Classical Linear Codes

• A classical code's distance is the minimum weight of a nonzero codeword, with codewords formed from row combinations of its generator matrix.A full-rank k × n generator matrix encodes a length-k vector u as uG.Source: §3.1 · p. 5

3.2 Distance of Quantum Stabiliser Codes

• A stabilizer code's distance is the minimum weight of a Pauli string that commutes with every stabilizer generator but is not itself in the stabilizer group.Stabilizer measurements produce a syndrome; undetectable nontrivial logical operators change the logical state.Source: §3.2 · pp. 5–6

3.2.1 Two-Block (Symplectic) Representation of Stabiliser Codes

• The two-block symplectic representation maps Pauli operators to binary vectors (x|z), representing stabilizers and logical operators as rows of binary matrices.Pauli weight corresponds to the weight of x ∨ z.Source: §3.2.1 · p. 6

3.2.2 Three Block Representation Stabiliser Codes

• The three-block representation maps (x|z) to (x|z|x ⊕ z), allowing ordinary dot products to capture anticommutation and separate Pauli-error detection across blocks.Each row has twice the corresponding Pauli weight, and the representation can be mapped back to two-block form.Source: §3.2.2 · p. 7

3.2.3 Four-Block Representation of Stabiliser Codes

• The four-block representation preserves addition, has twice the Pauli weight, and can be converted into a [[4n, 2k, 2d]] CSS code for CSS-only distance methods.Appending [In|In|In|In] forces logicals to have even weight.Source: §3.2.3 · pp. 7–8

3.2.4 CSS Codes

• CSS codes separate X-only and Z-only stabilizer generators; when Z-distance is known to be lower, finding it suffices to determine minimum distance.For Z-distance calculations, HX can serve as the detector matrix and LX as the observable matrix; classical codes use H and a basis for its complementary subspace.Source: §3.2.4 · p. 8, §3.4 · p. 9

3.3 Distance of Quantum Circuits

• Circuit distance is the minimum weight of an error mechanism set in ker H but not ker L, and the circuit formulation generalizes the code-distance problems considered here.A circuit's detector error model supplies detector and observable matrices H and L; circuit experiments can involve many more error mechanisms than code checks.Source: §3.3 · pp. 8–9

3.5 Computational Complexity of Distance Finding

• Exact distance-finding is NP-complete for arbitrary classical binary linear and quantum stabilizer codes, while naive codeword or error enumeration has exponential complexity.Implementation choices, including representation and language, can also affect runtime and memory use.Source: §3.5 · pp. 9–10

4 Distance-Finding Algorithms

• The review groups methods into codeword enumeration, error enumeration with checks for codewords or nontrivial logicals, and SAT or mixed-integer programming.Codewords include generator-row combinations, nontrivial logical Pauli operators, or combinations of observable and detector matrices.Source: §4 · p. 10
• One method class enumerates codewords formed from combinations of generator-matrix rows or related logical and matrix vectors.The listed vectors include nontrivial logical Pauli operators and combinations of observable and detector matrices.Source: §4 · p. 10
• Another method class enumerates errors and checks whether they represent codewords or nontrivial logicals.Source: §4 · p. 10

4.1 Desiderata and Characteristics of Distance-Finding Algorithms

• For screening many code or circuit candidates, heuristic methods can quickly give a distance upper bound while using relatively little memory and processing time.For one code where exactness matters, longer calculations may be acceptable, and early termination should ideally return upper and lower bounds.Source: §4.1 · p. 10
• Methods should ideally apply to classical, CSS, non-CSS, and circuit problems, and accommodate differing error models such as biased Pauli errors.For differing error probabilities, the desired output is the highest-probability error.Source: §4.1 · pp. 10–11
• Some methods are probabilistic and can improve confidence through repeated iterations, whereas deterministic methods return the same outcome regardless of iteration count.Source: §4.1 · p. 11

4.2.4 Evolutionary Algorithms

• QDistEvol uses evolutionary search and, for many code families, is more accurate than QDistRnd with a modest runtime increase.It evaluates permutations using a continuous fitness tuple comprising minimum weight and average weight of non-trivial codewords in a kernel basis.Source: §4.2 · p. 11, §4.2.4 · p. 18

4.2.1 Exhaustive Codeword Methods

• Classical exhaustive search finds distance by enumerating 2^k codewords, while Gray codes reduce generation to one generator-row addition per step.For quantum codes, the naive approach enumerates non-trivial logical operators; the quantum MacWilliams identity can reduce the calculation to O(2^(n-k)) by enumerating the check span instead.Source: §4.2.1 · p. 11

4.2.2 Brouwer-Zimmermann Algorithm

• Brouwer–Zimmermann enumeration tracks upper and lower distance bounds and can be faster than exhaustive codeword methods while returning the exact distance when the bounds converge.The paper’s BZDistMW implementation uses Gray codes and supports two-, three-, or four-block representations of non-CSS codes; it has competitive runtime versus Magma and Qubitserf for CSS codes.Source: §4.2.2 · pp. 12, 13, 15

4.2.3 Random Information Set/QDistRnd Algorithm

• QDistRnd randomly permutes columns to find low-weight codewords or logicals, providing an upper bound on distance rather than certifying the minimum.Its GAP methodology estimates failure probability from how often the lowest-weight codewords are encountered; the described GAP and C versions calculate distance only, though the algorithm can be modified for arbitrary error probabilities.Source: §4.2.3 · pp. 15–17

4.2.4 Evolutionary Algorithms

• QDistEvol starts from random column permutations and selects parents across generations, using a continuous fitness function to distinguish candidate solutions.Its fitness combines the minimum weight with the average weight of non-trivial codewords in a kernel basis.Source: §4.2.4 · p. 18
• QDistEvol selects the best μ permutations as parents and generates offspring by random transpositions; restricting swaps to pivots and non-pivots improved accuracy in benchmarking.The method uses mutation without the cross operation used by the algorithm in [43].Source: §4.2.4 · p. 18
• Over 250 trials, setting pMut=15 gave QDistEvol a success rate above 60% per trial, while swapPivot=TRUE raised success from 12% to 28% under default settings.The success criterion was returning distance 34 for the 756-qubit bivariate bicycle code; each trial used 10,000 RREF calculations.Source: §4.2.4 · p. 18, Figure 2 · p. 19
• For the 756-qubit code, increasing QDistEvol to 1,000 generations raised success to around 50%, while five offspring gave the best offspring-count result, peaking at 37%.QDistRndMW returned distance 34 in 2 of 100 runs, a 2% base success rate.Source: §4.2.4 · p. 18, Figure 2 · p. 19

4.2.5 Syndrome Decoder Method

• The syndrome-decoder method samples a logical operator, decodes a syndrome that anticommutes with it, and uses the correction as a non-trivial logical; it applies to circuits, non-CSS codes, and classical binary linear codes.Its accuracy and processing time depend on the decoder; heuristic decoders can give inaccurate estimates, while exact decoders can take a long time.Source: §4.2.5 · pp. 19, 21
• On the [[48, 5, 10]] code, BP-OSD found distance 10 in 0 of 100 trials without sampling changes, 50% with DEM permutations, and 100% with permutations plus random stabilisers.Adding random stabilisers alone did not change the success rate.Source: §4.2.5 · p. 21

4.3 Enumeration of Errors

• Exhaustive error enumeration raises a lower bound by checking errors in increasing weight, but is practical only for low-distance and/or small-block codes.For CSS codes its complexity is O((ne/d)^d); the non-CSS version enumerates Pauli strings.Source: §4.3 · pp. 21–22

4.3.1 Matching Bipartition

• Matching bipartition combines two half-weight errors with matching syndromes but opposite commutation with a logical, reducing CSS complexity to O((2ne/d)^(d/2)).The MeetMiddleMW implementation supports classical, CSS, and non-CSS codes without a maximum code-size limit.Source: §4.3.1 · p. 22

4.3.2 Connected Cluster Algorithm

• Connected cluster searches low-weight errors breadth-first along Tanner graphs, with complexity O([2(m −1)]^d) for check-matrix row weight m.Three-block representation ran faster than four-block representation on the codeTables best-known-distance dataset; breadth-first search can grow rapidly before finding distance.Source: §4.3.2 · p. 23

4.3.3 Stim Undetectable Error Algorithm

• Stim-based searches truncate exploration to save memory and time; GEStim is exact when every error flips at most two detectors, and otherwise these methods provide only an upper bound.CCStim is intended for colour codes where each error can flip up to three detectors.Source: §4.3.3 · pp. 24–25

4.4 Solver-Based Methods

• Exact solver-based methods certify a global optimum, unlike heuristic methods that cannot guarantee the exact distance.Source: §4.4 · p. 25

4.4.1 Mixed Integer Linear Programming

• MILP minimizes error weight subject to stabilizer parity and nontrivial logical anti-commutation constraints, using integer slack variables to encode modular arithmetic.Non-CSS formulations use detector and logical-observable matrices; Gurobi’s two-block representation ran faster than the three-block representation.Source: §4.4.1 · pp. 25–26

4.4.2 MaxSAT Solvers

• MaxSAT minimizes error weight through soft clauses penalizing errors and hard clauses enforcing stabilizer and logical parity constraints.Stim can generate WCNF encodings for circuits, supporting more complex noise models.Source: §4.4.2 · pp. 26–27

5 Algorithm Benchmarks

• Benchmarking covered classical code, quantum code, and quantum-circuit families on a single 40-core cluster node with 8GB of memory per core.Source: §5 · p. 27, §5.1 · p. 27

5.1 Benchmarking Methodology

• Exact methods were capped at eight hours, with processing time and overall success rate measured on reduced code selections when datasets included many long-running cases.Partial results were used where available; success rate counted completed cases and cases whose partial results gave the lowest distance.Source: §5.1 · p. 27
• Heuristic success rate counted cases returning the known or benchmark-lowest distance, while processing time per successful trial estimated expected time to find it.Probabilistic methods used up to 10,000 trials and each code or circuit had a 48-hour runtime limit; results also included aggregate tables and scaling charts.Source: §5.1 · pp. 27–28

5.2.1 GF(2) Linear Codes from codetables.de

• On codetables.de GF(2) codes, QDistRnd, QDistEvol, and BP-OSD found the correct distance in every instance, while C QDistRnd had the lowest overall runtime.Magma completed all codes up to n = 128 and had the lowest average processing time per trial among exact methods.Source: §5.2.1 · p. 28, Table 4 · p. 28, Table 5 · p. 29
• Magma Brouwer-Zimmermann performed best among exact methods on larger codetables.de codes, but not necessarily below length 60.The figure plots time per successful trial for exact methods by code length.Source: §5.2.1 · p. 28, Figure 3 · p. 29
• For codes longer than about 60 bits, QDistEvol had better time per successful trial than QDistRnd and retained close to 40% success on the largest codes.For codes over 100 bits, success rates for other methods were close to zero.Source: §5.2.1 · p. 29, Figure 3 · p. 29

5.2 Classical Codes

• The classical lifted product benchmark comprised 19 codes with lengths from 5 to 475 bits; the codetables.de set comprised 121 best-known-distance binary linear codes with 5 to 128 bits.Exact-method comparisons for codetables.de were limited to codes with up to 100 qubits because of long processing times.Source: §5.2.1 · p. 28, §5.2.2 · p. 29

5.2.2 Classical Lifted Product Codes

• For classical lifted product codes, QDistEvol found the lowest distance in every case and had the lowest time per successful trial; exact methods completed at most 9 of 19 codes within eight hours.MIP-SCIP and Magma partial results found the lowest distance in all cases, while Gurobi and SAT partial results were less accurate.Source: §5.2.2 · pp. 29–30, Table 7 · p. 30, Table 6 · p. 30

5.3.1 Non-CSS Quantum Codes: codetables.de

• Block encoding and heuristic parameter choices materially affected non-CSS results: QDistEvol benchmarking used two blocks with regroupPerm and swapPivot enabled, while tuned QDistRnd success was around 47%.For exact methods, three-block encoding improved Brouwer-Zimmermann and m4riCC runtime, while two-block encoding performed better for Gurobi.Source: §5.3.1 · p. 31, Figure 5 · p. 31, Figure 6 · p. 32
• For non-CSS codetables.de codes, Magma had the lowest time per successful trial for medium-to-large codes, while QDistEvol outperformed QDistRnd above n > 30 but success rates approached zero for the largest codes.The random information set methods performed well but did not find the correct minimum distance in every case; BP-OSD was slower and less accurate, and Stim methods returned results for only some codes.Source: §5.3.1 · p. 32, Table 8 · p. 32, Figure 7 · p. 33

5.3.2 Two-Dimensional Hyperbolic Surface and Colour CSS Codes

• For hyperbolic surface codes, m4riCC had the lowest time per successful trial among exact methods, and all heuristic methods achieved close to perfect accuracy.Stim methods had the lowest total heuristic runtime, while random information set and BP-OSD methods had lower time per successful trial.Source: §5.3.2 · p. 33, Table 10 · p. 33, Table 11 · p. 34
• On hyperbolic surface codes, Stim graphlike error, colour-code, and undetectable-error methods all had 100% success, while BP-OSD was competitive for larger codes through lower execution time.The text attributes BP-OSD's larger-code suitability to very sparse check matrices, while its success rate was below QDistEvol and QDistRnd.Source: §5.3.2 · pp. 33–35, Figure 9 · p. 35
• For hyperbolic colour codes, only m4riCC completed every code within eight hours; Stim colour-code search performed well, whereas Stim graphlike error did not complete successfully.Most exact methods were slower than for surface codes, attributed to the colour codes' higher-degree Tanner graphs.Source: §5.3.2 · p. 34, Table 12 · p. 34, Table 13 · p. 35

5.4 Quantum Lifted Product Codes

• For quantum lifted product codes, QDistEvol found the lowest distance in every case and had substantially lower time per successful trial than other heuristic methods; exact methods completed at most 6 codes.The family contained 19 codes with 34 to 3230 qubits, and Gurobi partial results were accurate for all codes.Source: §5.4 · pp. 35–36, Table 14 · p. 36, Table 15 · p. 36

5.4.1 Bivariate Bicycle Codes

• For bivariate bicycle codes, QDistEvol found the lowest distance in 13 of 20 cases, compared with 8 of 20 for both QDistRnd and BP-OSD; exact methods completed at most 5 codes.The lowest distances in this family were not known with certainty, so the benchmark used the lowest distance observed in its trials.Source: §5.4.1 · pp. 36–37, Table 16 · p. 37, Table 17 · p. 37

5.4.2 Quantum Tanner Codes

• For quantum Tanner codes, QDistEvol found the lowest distance for 8 of 22 codes and had the highest heuristic success rate; among exact methods, Magma had the most accurate partial results.Exact methods completed at most 5 codes within eight hours; m4riCC was fastest per successful trial on smaller codes, while SAT and MIP were faster on larger ones.Source: §5.4.2 · p. 38, Table 19 · p. 38, Table 18 · p. 38

5.5 Syndrome Extraction Circuits

• Filtering detector error models reduced their size and improved every benchmarked distance-finding algorithm on superdense colour circuits.The filter selects detectors of the desired Pauli basis and retains errors supported by those detectors; the benchmark limited probabilistic methods to 1,000 trials on unfiltered models and used 10,000 on filtered models.Source: §5.5 · pp. 38–39, Table 20 · p. 41, Table 21 · p. 41

5.5.1 Surface Code Circuits

• For rotated surface circuits, both MIP methods found correct distances throughout, while all heuristics also found correct distances; SAT returned no result for 3 of 5 circuits.m4riCC completed 4 of 5 circuits within 8 hours; Stim graphlike error had the lowest overall heuristic processing time.Source: §5.5.1 · p. 40, Table 22 · p. 41, Table 23 · p. 42

5.5.2 Colour Code Circuits

• For midout colour circuits, Gurobi, CLISAT, and m4riCC completed every exact run within 8 hours, with m4riCC fastest; heuristics agreed on the lowest distances.QDistRnd and QDistEvol had the lowest heuristic time per successful trial; their success rates fell sharply as circuits grew, while QDistEvol was faster than QDistRnd at 60 qubits or more.Source: §5.5.2 · pp. 40–42, Table 24 · p. 42, Table 25 · p. 43
• Superdense colour circuits showed a similar pattern, but BP-OSD success stayed near 100% on large circuits.For the colour-circuit benchmarks, Stim Graphlike Error performed well despite not performing well for colour-code code-capacity distance.Source: §5.5.2 · pp. 41–42, Table 26 · p. 43, Table 27 · p. 43

5.5.3 Bivariate Bicycle Code Circuits

• Exact methods produced estimates for few bivariate bicycle circuits; Gurobi found the lowest distance in 4 of 7, but finished within 8 hours only on the smallest.Among heuristics, m4riRW completed 10,000 trials for all seven circuits and was accurate on the first four, but overestimated the last three.Source: §5.5.3 · pp. 42–44, Table 28 · p. 44, Table 29 · p. 44
• For bivariate bicycle circuits, only m4riRW completed 10,000 trials on all seven; BP-OSD, QDistRndMW, and QDistEvol each finished on only three or four.UEStim returned a result only for the smallest circuit, unlike its performance on other circuit families.Source: §5.5.3 · pp. 43–44, Table 29 · p. 44

Exact methods

• MIP methods gave good all-round performance across many codes, with Gurobi generally faster than MIP-SCIP and MIP methods generally outperforming SAT in time and accuracy.After early termination, MIP-SCIP sometimes produced more accurate results than Gurobi.Source: §6 · p. 45
• m4riCC performed well for LDPC codes with low-degree Tanner graphs and also for some quantum circuit families.The paper summarizes recommended exact algorithms by dataset in Table 30.Source: §6 · p. 45, Table 30 · p. 46

Heuristic methods

• Random information-set algorithms were effective for general code families, while QDistEvol was more accurate on the benchmark's high-rate LDPC codes.The authors note that QDistEvol may benefit from refinement and a C implementation using asymptotically optimal Gaussian elimination.Source: §6 · p. 45
• BP-OSD did not clearly outperform random information-set algorithms on any dataset, although it had better time per successful trial on larger hyperbolic surface and colour-code datasets.The authors suggest a faster BP-OSD implementation might make it more competitive.Source: §6 · p. 45
• Stim Undetectable Error methods performed well on codes and circuits with low-degree Tanner graphs, complementing m4riCC.The paper presents dataset-specific heuristic recommendations in Table 31.Source: §6 · p. 45, Table 31 · p. 46

Conclusions

• Distance-finding informs code and circuit exploration, but full circuit-level simulations and eventual experiments are still needed to account for hardware constraints, practical decoding, and fault-tolerant logic.Source: §6 · p. 45

• WCNF weights distinguish soft from hard clauses; the solver must satisfy all hard constraints and prioritize satisfying as many soft constraints as possible.Source: A SAT Solver Model Construction · pp. 51–52
• For a CSS code's Z-distance model, the construction takes the X-check matrix and X-logical basis and outputs a WCNF file.Source: A SAT Solver Model Construction · p. 51
• Each error mechanism contributes a soft clause to minimize its weight, while parity and logical requirements are encoded as hard constraints.The row-constraint construction uses clauses to encode parity relationships.Source: A SAT Solver Model Construction · pp. 51–52