PaperlayerView exact revision on arXiv

Source-linked AI summary

Ancestor Lifting of Quasi-Cyclic Additive Codes and Certified Quantum Codes

Liangdong Lu, Ran Xu, Ruipan Yang, Qiang Fu

arXiv:2610.36700v1cs.ITmath.ITquant-ph

TL;DR

Improving quantum-code distances requires searching large spaces and certifying exact minimum distances, since explicit logical operators alone give only upper bounds. This paper studies additive 1-generator quasi-cyclic codes, develops ancestor-lifting structure, and combines it with exact computational certification. It reports twenty-one record-breaking codes across twenty table entries and thirty-four further propagated improvements.

  • Problem

    Improving Grassl-table quantum-code distances is difficult because small-length searches are well explored, large-length exact computation is expensive, and explicit logical operators alone give only upper bounds.

    Source: §I · p. 1

  • Method

    The paper develops ancestor lifting and quasi-cyclic family structure, then certifies distances through ISD screening, exact Brouwer–Zimmermann computation on the additive dual, and independent witness verification.

    Source: §I · p. 2

  • Results

    Twenty-one certified record-breaking codes improve twenty table entries, and propagation improves thirty-four further entries.

    Source: §I · p. 2, §X · p. 15

  • Takeaways & Limitations

    The divisor-lattice lift bound often explains the dominant distance scale, although strict deviations occur in several certified examples.

    Source: §X · p. 15

    Further candidates are reported at evidence level only, rather than as certified exact-distance results.

    Source: §X · p. 15

Abstract

from arXiv · show

Additive codes over $\Ffour$ that are self-orthogonal under the trace inner product correspond to binary quantum stabilizer codes. We study 1-generator $(1,2)$-quasi-cyclic (QC) additive codes and their exact quantum distances. For composite lengths $n=\ell m$, an ancestor-lifting theorem transports dual words of the folded ancestor to the length-$n$ code. A two-layer decomposition for $\ell=2$ and a CRT splitting for odd $\ell$ yield dimension laws and explain equality, escape, and mixed-branch behavior in the certified examples. A palindromic criterion ensures symplectic self-orthogonality, while reversal pairing and a symplectic Gram rank formula describe broader construction families. Exact distances are established by information-set decoding screening, Brouwer--Zimmermann computation on the additive dual, and independent witness verification. We certify twenty-one record-breaking binary quantum codes across twenty entries of Grassl's code table, with twenty-eight certified members in total. Propagation improves thirty-four further entries, and explicit constructions are supplied for three table-tying GV entries marked Code Missing Construction. Six additional candidates are reported only with rigorous upper bounds and heuristic screening evidence. The results connect divisor-lattice structure in additive quasi-cyclic codes with reproducible certification of exact quantum distances.

I. INTRODUCTION

The paper develops additive 1-generator quasi-cyclic constructions and exact-distance certification to address both the search and proof challenges in improving quantum-code records. Its introduction connects a palindromic self-orthogonal family and divisor-lattice lifting to certified code results.

II. PRELIMINARIES

  • Quantum stabilizer codes are represented as additive F4 codes self-orthogonal under the trace inner product, and a (1, 2)-QC code is generated by cyclic closure in R.The paper uses R = F2[x]/(x^n − 1) and compares best-known distances with Grassl’s table [2].Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • For n = ℓm, ancestor lifting transports dual words from a folded ancestor, while two layers for ℓ = 2 and CRT splitting for odd ℓ yield distance laws.The divisor-lattice analysis accounts for equality, deviations, and mixed-branch behavior in certified examples.Source: §I · p. 2
  • A three-stage certification pipeline combines ISD screening, exact Brouwer–Zimmermann computation on the additive dual, and independently re-verified witnesses.It records CPU time and supplies scripts, logs, and witnesses for reproducibility.Source: §I · p. 2

III. THE PALINDROMIC QUASI-CYCLIC FAMILY

  • Palindromic multipliers force the defect symbol to vanish, making the resulting (1, 2)-QC additive code symplectically self-orthogonal at every length.The paper also describes reversal pairing and symplectic Gram-rank constraints for broader construction families.Source: §I · p. 2, §III · p. 3

I. INTRODUCTION

  • Twenty-one certified record-breaking codes improve twenty entries, with nineteen entries gaining one and the [[60, 13]]2 entry gaining two.The paper also reports thirty-four propagated improvements and explicit constructions for three table-tying GV entries marked Code Missing Construction.Source: §I · p. 2

III. THE PALINDROMIC QUASI-CYCLIC FAMILY

  • A palindromic-multiplier code is reversible exactly when its gcd-exact g is self-reciprocal up to a shift; otherwise it pairs with a distinct reversal twin.The paper verifies [[80, 7, 16]]2 as reversible and [[73, 10, 15]]2 and [[56, 9, 12]]2 as non-reversible.Source: §III · p. 3

A. Duality structure of 1-generator QC codes

The dual of a 1-generator QC code has structured cyclic components, with separate descriptions for odd lengths and for repeated-factor components at even lengths. These structures yield dimension formulas and constraints on the form of low-weight dual words.

A. Duality structure of 1-generator QC codes

  • For odd n, the pure-X and pure-Z dual sections are cyclic annihilator codes whose defining sets are complements of the corresponding generator root sets.The BCH bound applies to each section; if both defining sets contain consecutive runs of length at least dQ, every minimum-weight logical operator is mixed.Source: A. Duality structure of 1-generator QC… · p. 3
  • The dual has dimension n + deg ˜g and can be described using a unit-ratio graph code together with a pure-X annihilator.For [[73, 10, 15]]2, minimizing over the annihilator correction is essential: the certified weight-15 witness has X-part weight 11 after correction, versus 37 for the canonical representative.Source: A. Duality structure of 1-generator QC… · p. 4
  • At even lengths n = 2^s n′, CRT components describe the dual as graph or single-coordinate sections, with local dimension (2s + α_j) deg f_j.Summing component dimensions gives Σ min(α_j, β_j) deg f_j = n + deg gcd(a, b, x^n−1).Source: A. Duality structure of 1-generator QC… · p. 4
  • Unequal component valuations force one section of every dual word into a nilpotent ideal, as seen in the [[80, 7, 16]]2 and [[56, 9, 12]]2 profiles.The paper identifies this as a local counterpart to the two-layer analysis of Section IV.Source: A. Duality structure of 1-generator QC… · p. 4
  • The order-based diagonal bound is degenerate for every c of order t > 1, while root-balance is not automatic for the certified [[91, 15, 17]]2 and [[93, 15, 17]]2 codes.The paper states that exact distances are established by direct computation, not by that order-based bound.Source: A. Duality structure of 1-generator QC… · pp. 4–5
  • For the root-balanced [[73, 10, 15]]2 code, both single-component sections have minimum weight 28, above dQ = 15, so its certified witness is mixed.In this example, certifying dQ reduces to computing the symplectic distance of the unit-ratio graph code over S.Source: A. Duality structure of 1-generator QC… · p. 5

IV. ANCESTOR LIFTING

For composite lengths, ancestor lifting transports dual words from a folded code to the full-length code, with weight scaled by the quotient. The even- and odd-quotient decompositions yield distance laws that distinguish lift, escape, and mixed branches.

Ancestor lifting

  • d(C⊥ts) ≤ ℓ·d(C⊥ts_m), and a minimum-weight ancestor logical operator gives a quantum-distance bound when its lift lies outside C.The lift repeats ancestor blocks, preserves dual membership, and scales symplectic weight by ℓ.Source: §IV · p. 5

Two-layer decomposition

  • For ℓ=2, dual words split into a folded ancestor word and a second-block word constrained by Ψ(z)=Ru.Admissible second-block choices form an affine coset; the weight is swt(z) + swt(u + z), and consistency is linear in u.Source: §IV · pp. 5–6

Distance branches

  • The ℓ=2 distance law distinguishes lift-saturated, coexisting, and escaping edges; escape occurs when the coset branch falls below 2d(C⊥ts_m).The non-stabilizer condition applies to the reconstructed word u + ez, not to u and z separately.Source: §IV · p. 6

Certified examples

  • For σ(g)=0, the reported examples show no strict escape and satisfy d(C⊥ts) = 2d(C⊥ts_m), while squareful examples exhibit varied deviations.The authors state the forward implication as a conjecture; reported squareful cases include one- and four-unit deviations below lift bounds.Source: §IV · p. 6

Odd-ℓ CRT splitting

  • For odd ℓ, the CRT splits the trace-symplectic dual into independent fold and eS components, with dim C⊥ts = dim C⊥ts_m + dim K_eS.The ζ = 0 branch is the lift branch, with weight ℓ·swt(u).Source: §IV · p. 6

Certified examples

  • For [[93, 15, 17]]2, the ℓ=3 fold has dual dimension 36 and the complementary component dimension 72; its weight-17 logical reconstructs through the three-block formula.For [[91, 15, 17]]2, the length-13 fold's minimum-weight ancestor lifts into C, so the certified distance 17 comes from the mixed branch.Source: §IV · pp. 6–7

A. Lift-anchored construction

The two-layer analysis becomes a construction method by prescribing a fold and solving for a second layer. Lift-anchored codes are self-orthogonal exactly when their layer corrections satisfy a linear consistency equation; the resulting candidates can inherit ancestor distance bounds, while exact certification may require further computation.

A. Lift-anchored construction

  • Prescribing the fold and solving for the second layer turns the two-layer analysis into a construction method.A length-2m code is lift-anchored when its fold is the specified self-orthogonal anchor.Source: A. Lift-anchored construction · p. 7
  • The second layer preserves self-orthogonality exactly when its correction terms satisfy Tb(u) + Ta(w) = q, giving an affine solution space when q lies in im Ta + im Tb.The solution-space dimension is 2m − rank(Ta | Tb); when q = 0, the condition is homogeneous and the anchored codes form a linear space.Source: A. Lift-anchored construction · p. 7
  • The [[124, 17]] entry produced seven screened survivors, including a candidate with a weight-20 witness matching the table value, but exact certification requires further Brouwer–Zimmermann computation.Across five target lengths, 56 of 210 lift-anchored candidates were screened and 55 met Grassl thresholds.Source: A. Lift-anchored construction · p. 7
  • Seven certified codes serve as anchors for 210 lift-anchored candidates at lengths 112, 124, 146, 156, and 160, with candidates inheriting dQ ≤ 2d(anchor).The reported ancestor structure uses dQ(m), except for the self-dual length-13 fold of [[91, 15, 17]]2, where it uses d(C⊥ts_13).Source: A. Lift-anchored construction · p. 7, Table II · p. 8
  • A minimum-weight ancestor word can fail to be a logical operator after lifting if its lift lies in C, as for the self-dual length-13 fold of [[91, 15, 17]]2.That fold’s weight-28 lift lies in C; the section also reports coexisting lifted and primitive weight-14 logicals for [[78, 13, 14]]2.Source: A. Lift-anchored construction · p. 7

B. Structural explanation of the low-weight cluster in the n = 153 ISD census

The n = 153 ISD census separates into a low best-found cluster explained by periodic ancestor lifts and a high cluster without an identified exploitable fold. The ancestor sieve checks whether lifted logicals or divisibility witnesses already exclude a target before candidates proceed to ISD/BZ certification.

B. Structural explanation of the low-weight cluster in the n = 153 ISD census

  • At n = 153, 30 random family members split into 12 low-cluster members with best-found values 9–18 and 18 high-cluster members with values 31–35; the high cluster remains uncertified.All 12 low-cluster members had explicit lifted witnesses, while exact distances in the high cluster remain certification tasks.Source: B. Structural explanation of the… · p. 8
  • The low cluster has a divisor-lattice explanation: examined witnesses were exact period-9, period-17, or period-51 repetitions.The witnesses came from pure-X lifts of weights 9 or 17, (1,1)-type lifts of weight 17, and lifts of small m = 51 ancestor distances.Source: B. Structural explanation of the… · p. 8
  • The ancestor sieve rejects a candidate when a verified lifted logical or divisibility witness has weight at most the target; otherwise it passes the candidate to ISD/BZ without a conclusion.It checks folded ancestors across proper divisors before the later screening and exact-certification steps.Source: B. Structural explanation of the… · p. 9

V. RANK AND DEGREE STRUCTURE OF THE DEFECT SYMBOL

The defect symbol determines the symplectic Gram rank through its gcd with x^n − 1, while its reciprocal structure constrains achievable gcd degrees. A linear-algebra construction can also produce ingredients with a prescribed defect divisor.

V. RANK AND DEGREE STRUCTURE OF THE DEFECT SYMBOL

  • The symplectic Gram rank is r = n − deg gcd(P, x^n − 1), and rank zero holds exactly when P vanishes identically.The Gram matrix of cyclic shifts is circulant with symbol P.Source: §V · p. 9
  • For odd n, achievable gcd degrees lie among 1 plus subset sums of self-reciprocal block degrees, matching all computed cases, though equality remains conjectural in general.Complete enumeration at n = 5, 7, 9 and directed search at n = 15, 21 attained the stated sets.Source: §V · p. 9
  • For fixed b and target self-reciprocal divisor h_r, admissible multiples a = gf1 form a linear subspace with dimension at least (n − deg g) − deg h_r.The admissible set is the kernel of the map a ↦ Tb(a) mod h_r.Source: §V · p. 9
  • In the n = 21, r = 2 experiment, prescribed-defect construction succeeded in all 20 trials, versus 0 successes in 400 uniform random trials.When the dimension bound is positive, the method constructs the admissible set by linear algebra rather than exhaustive random search.Source: §V · p. 9

VI. SYMPLECTIC EXTENSION AND ASSEMBLY

A code with symplectic Gram rank r can be extended to a self-orthogonal code by adding r/2 coordinates, and fewer coordinates cannot suffice. The same rank supports an entanglement-assisted construction and an assembly of two codes with matching rank.

VI. SYMPLECTIC EXTENSION AND ASSEMBLY

  • A code with symplectic Gram rank r extends to a self-orthogonal additive code using r/2 new coordinates, and r/2 coordinates are necessary.The extension pairs hyperbolic generator components using new coordinates; the necessity follows because c coordinates contribute an alternating form of rank at most 2c.Source: §VI · p. 10
  • A rank-r ingredient yields an entanglement-assisted code with r/2 ebits; the [[34, 11, 6]]2 ingredient gives a BZ-verified [[33, 11, 7; 1]]2 construction.The example has distance 7 at one coordinate fewer than the ingredient’s distance 6.Source: §VI · p. 10
  • Two additive codes of equal symplectic Gram rank can be assembled into a self-orthogonal code with t1 + t2 − r generators.The assembled length is n1 + n2, and its stabilizer-code dimension is n1 + n2 − (t1 + t2 − r).Source: §VI · p. 10
  • At rank 2, all six tested identifications of the hyperbolic parts left dQ unchanged, but general validity remains open.The passage presents this as a numerical observation only.Source: §VI · p. 10

VII. THE CERTIFICATION PIPELINE

The pipeline separates heuristic screening from exact distance certification: ISD finds candidate upper bounds, while Brouwer–Zimmermann computation and independently checked witnesses establish exact distances. Screening and certification can diverge, as shown by archived candidates and the reported family calibration.

Stage 1: ISD screening with early exit

  • ISD screening on the additive F4 representation of the dual gives only upper bounds, and a shallow screen can overestimate the distance.An archived candidate’s suggested distance was refined from 38 to 19.Source: §VII · p. 10

Stage 2: exact certification

  • Brouwer–Zimmermann MinimumWeight on the additive dual proves the lower bound dQ ≥ d(C⊥ts).Table III reports measured CPU times for the exact computation.Source: §VII · p. 10, Table III · p. 11

Stage 3: witness protocol

  • Each claimed distance is paired with a dual word outside the code, independently re-verified by linear algebra.For [[91, 15, 17]]2, the exact lower bound and a weight-17 witness coincide; [[93, 15, 17]]2 also has an independent computation returning 17.Source: §VII · p. 11

Refutation case studies

  • The pipeline rejects unsupported archived candidates, including one whose suggested distance 11 was refined to 10 and a structurally invalid candidate.The legitimate T-image of the latter has certified dQ = 12.Source: §VII · p. 11

Family calibration

  • Equal-budget screening of random same-family members found a unimodal best-found range of 22–25 at n = 127.The reported calibration quantifies selection effects in the family.Source: §VII · p. 11

VIII. THE CERTIFIED RECORD-BREAKING CODES

The paper certifies record-breaking additive QC quantum codes and derives further table improvements through propagation and subcode constructions. The certified constructions are not GF(4)-linear, and most direct improvements exceed prior bounds by one.

Certified record-breaking codes

  • The listed codes exist with their stated exact minimum distances and improve the best-known lower bounds in Grassl’s code table [2]; every entry improves by exactly one except [[60, 13]]2, improved by two.The [[60, 13, 12]]2 member supplies the two-unit improvement; a second certified member has distance 11.Source: §VIII · p. 12

Construction and certification

  • Eighteen certified codes are palindromic QC codes; the other three have non-palindromic multipliers and vanishing defect symbols.Stage 2 supplies exact lower bounds and Stage 3 explicit weight-d logical operators, establishing dQ = d.Source: §VIII · p. 12

Improvement margins

  • Most Table IV improvements are +1 because entries are certified once a member clears the incumbent, not because the family has a +1 ceiling.No candidate for a +2 improvement appeared in the 9,620-code archive at the larger entries; the next-distance BZ cost remains to be evaluated.Source: §VIII · p. 12

Propagation improvements

  • Standard propagation improves thirty-four further Grassl-table entries at no computational cost.Lengthening accounts for twenty-five entries, while explicit subcode construction gives nine further improvements.Source: §VIII · p. 12, Table V · p. 13

Subcode propagation

  • Adjoining a dual word to the [[91, 15, 17]]2 stabilizer yields a self-orthogonal subcode whose retained witness keeps its distance exactly 17.The construction lowers the dimension to k = 14.Source: §VIII · p. 13

Propagation improvements

  • Zero-padding and adjoining one-qubit stabilizers give exact [[n, 14, 17]]2 codes for 91 ≤ n ≤ 101.The nine codes for 91 ≤ n ≤ 99 improve the lower bound 16; n = 100 and 101 tie 17 and supply constructions for entries marked Code Missing Construction.Source: §VIII · p. 13

Independent certified members

  • Twenty-eight independently certified codes span the twenty entries, including distinct members whose equivalence is unresolved by the reported invariants.For [[60, 13]]2, the certified distances 11 and 12 alone establish inequivalence.Source: §VIII · p. 14

GF(4)-linearity

  • All twenty-eight direct certified codes fail the GF(4)-linearity closure test and lie outside the GF(4)-linear stabilizer class.The ω-map sends each generator word outside its code.Source: §VIII · p. 14

A. Comparison with prior work

The comparison places the certified codes against prior records and distinguishes this paper’s additive constructions from nearby linear QC work. It also reports the scope of the literature search and the reproducibility standard used by the closest certification comparison.

Comparison with prior work

  • The [[73, 10, 15]]2 code strictly improves on the published [[73, 9, 15]]2 code of by one logical qubit at the same length and distance.The parameter-exact literature search found no published code matching the certified or candidate parameters, but was limited to the references listed.Source: A. Comparison with prior work · p. 14
  • The paper’s certified codes are genuinely additive and lie outside the GF(4)-linear class, complementing and rather than competing with their linear-code results.The stated additions include a lifting mechanism, exact distance law, defect-symbol analysis, and an artifact package with scripts, logs, witnesses, and SHA-256 manifests.Source: A. Comparison with prior work · p. 14

IX. EVIDENCE-LEVEL CANDIDATES

Evidence-level candidates have verified logical-operator upper bounds and heuristic screening, but no certified lower bounds or table-breaking claims. The conclusion relates distance behavior to ancestor lifting while leaving several structural questions and candidate certifications open.

IX. EVIDENCE-LEVEL CANDIDATES

  • Evidence-level candidates have re-verified logical operators but no certified lower bound, so their screening does not establish a table-breaking distance.Exact certification at these lengths is beyond the compute budget; the screening threshold is chosen relative to the Grassl table value.Source: §IX · p. 14
  • The archived [[72, 6, 16]]2 example is rejected because its generator is not self-orthogonal under ω and its legitimate T-image has certified dQ = 12.The T-image result is stated in Remark A.1.Source: §IX · p. 14

X. CONCLUSION AND OPEN PROBLEMS

  • The divisor-lattice lift bound often explains the dominant distance scale, but strict deviations occur, including mixed branches of [[91, 15, 17]]2 and [[93, 15, 17]]2.The conclusion conjectures that strict deviations are controlled by σ(g) and the local fold structure.Source: §X · pp. 15–16
  • Open problems include identification-independence, a symplectic BCH-type bound for unit-ratio graph codes, and exact certification of evidence-level candidates.The candidate certifications exceed the compute budget reported for Table III.Source: §X · p. 16

APPENDIX EXPLICIT CONSTRUCTION DATA, WITNESSES, AND ARTIFACTS

The appendix records generator constructions, additional certified members, re-verified logical witnesses, and construction-specific data for evidence-level candidates.

A. Constructions of the certified codes

  • Certified codes are given as C = ⟨(gv1, gv2)⟩, with generator polynomials and multipliers tabulated; three codes use non-palindromic multipliers whose defect symbols vanish identically.The three exceptions are [[62, 7, 14]]2, [[60, 19, 10]]2, and [[60, 20, 10]]2; the latter two come from the directed construction.Source: A. Constructions of the certified codes · p. 16, Table IX · p. 16

B. Additional certified members of the same entries

C. Witnesses of the certified codes

D. Data for the evidence-level candidates

  • Candidate data include a [[60, 13, 11]]2 case whose exact stabilizer minimum is 16 and exact dual minimum is 11, yielding dQ = 11.Other listed witnesses include period-30 lifts; the [[60, 19, 10]]2 and [[60, 20, 10]]2 codes attain lifting equality from length-30 ancestors with dQ = 5.Source: D. Data for the evidence-level… · p. 19

1) The [[34, 11, 6]]2 candidate:

The appendix describes a non-certified length-34 construction and odd-length sweep candidates, then documents archived cases that were certified or refuted and the associated census and artifacts.

1) The [[34, 11, 6]]2 candidate:

  • The [[34, 11, 6]]2 candidate uses a 22-dimensional subcode of a length-33 QC span in a symplectic extension, and has a weight-6 witness but no certified exact distance.The candidate generator matrix is archived.Source: 1) The [[34, 11, 6]]2 candidate · p. 19

2) Odd-length sweep candidates:

  • Odd-length sweep candidates are palindromic QC codes; the reported ISD expectations leave [[127, 21, ·]]2 undecidable, while [[130, 16, ≤22]]2 is consistent with dQ = 22.For [[153, 16, ·]]2, the stated expected count is E(26) ≈ 2.4, with a typical value near 26–27.Source: 2) Odd-length sweep candidates · p. 19, Table XV · p. 20

3) Even-length archive: certified and refuted cases:

  • The archived [[72, 6]]2 record is refuted: its T-image has certified dQ = 12, below the table value 15, while [[60, 20, 10]]2 and a second [[80, 7, 16]]2 member are certified.The [[72, 6]]2 generator fails self-orthogonality under ω; exact dual computation and a re-verified weight-12 logical establish the T-image distance.Source: 3) Even-length archive: certified and… · pp. 19–20

E. Artifacts and the n = 153 census

  • The even-n archive covers n=42–90 and the odd-n sweep covers odd n=45–95 with stated exclusions; 265 candidates passed the short screen and 27 finalists remained after deep screening.The archived materials include scripts, logs, witness files, candidate archives, calibration data, and a verification suite available from the authors on request.Source: E. Artifacts and the n = 153 census · pp. 20–21
Loading 2610.36700v1…