pith. sign in

arxiv: 2604.15307 · v1 · submitted 2026-04-16 · 🪐 quant-ph · cs.IT· math.IT

Heuristic Search for Minimum-Distance Upper-Bound Witnesses in Quantum APM-LDPC Codes

Kenta Kasai This is my paper

Pith reviewed 2026-05-10 11:03 UTC · model grok-4.3

classification 🪐 quant-ph cs.ITmath.IT
keywords quantum LDPC codesminimum distanceupper boundsheuristic searchlogical operatorsAPM-LDPCTanner graphserror correction
0
0 comments X

The pith

Heuristic search constructs certified low-weight non-stabilizer logical operators that improve upper bounds on the minimum distance of quantum APM-LDPC codes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops methods to find low-weight logical operators in a family of quantum LDPC codes built from affine permutation matrices. These operators serve as witnesses that upper-bound the code distance once verified to be outside the stabilizer space and inside the parity-check kernel. By combining heuristic candidate generation with explicit certification tests, the approach yields sharper bounds than previously known for the codes examined. A sympathetic reader would care because exact distances of quantum LDPC codes remain difficult to compute, and tighter bounds clarify their error-correction potential without requiring a full lower-bound proof.

Core claim

Rather than proving a general lower bound, the work constructs low-weight non-stabilizer logical representatives from latent row relations, restricted-lift subspaces, cycle-8 trapping sets, and decoder residuals; after kernel-membership and row-space-exclusion verification, these representatives provide concrete upper bounds on minimum distance, sharpening earlier reports for representative APM-LDPC codes of girth eight.

What carries the argument

A unified framework that generates candidate witnesses via latent row relations, block-compressed and other restricted-lift subspaces, cycle-8 elementary trapping-set structures, and decoder-failure residuals, then certifies them through kernel and row-space tests.

Load-bearing premise

The kernel-membership and row-space-exclusion tests correctly certify the found representatives as valid non-stabilizer logical operators for every candidate generated by the heuristic search.

What would settle it

An independent verification showing that any reported witness fails the kernel-membership test or lies inside the stabilizer row space for one of the examined codes.

Figures

Figures reproduced from arXiv: 2604.15307 by Kenta Kasai.

Figure 1
Figure 1. Figure 1: Representative cycle-8-connected ETS patterns used in the library of [ [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
read the original abstract

This paper investigates certified upper bounds on the minimum distance of an explicit family of Calderbank-Shor-Steane quantum LDPC codes constructed from affine permutation matrices. All codes considered here have active Tanner graphs of girth eight. Rather than attempting to prove a general lower bound for the full code distance, we focus on constructing low-weight non-stabilizer logical representatives, which yield valid upper bounds once they are verified to lie in the opposite parity-check kernel and outside the stabilizer row space. We develop a unified framework for such witnesses arising from latent row relations, restricted-lift subspaces including block-compressed, selected-fiber, and CRT-stripe constructions, cycle- 8 elementary trapping-set structures, and decoder-failure residuals. In every case, search is used only to generate candidates; the reported bounds begin only after explicit kernel and row-space exclusion tests have been passed. For the latent part, we also identify a block-compression criterion under which the certification becomes exact. Applying these methods to representative APM-LDPC codes sharpens previously reported upper bounds and provides concrete certified values across the explored parameter range.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a heuristic search framework to generate candidate low-weight vectors for quantum APM-LDPC codes (with girth-8 Tanner graphs) that are subsequently verified to lie in the kernel of the parity-check matrix but outside the stabilizer row space. These verified vectors serve as non-stabilizer logical operators and thereby certify upper bounds on minimum distance. The framework unifies several constructions (latent row relations, restricted-lift subspaces including block-compressed, selected-fiber and CRT-stripe, cycle-8 trapping sets, and decoder-failure residuals). Reported bounds are produced only after the algebraic tests pass; an exact-certification criterion is identified for the latent block-compressed case. The method is applied to representative codes and yields sharpened upper bounds together with concrete certified values across the explored parameter range.

Significance. If the verification steps are implemented correctly, the work supplies reliable, concrete upper bounds that improve on previously published figures for this explicit family of quantum LDPC codes. The explicit post-search algebraic certification (kernel membership plus row-space exclusion) is a methodological strength that distinguishes the contribution from purely heuristic distance estimates.

major comments (2)
  1. [Abstract] Abstract and the description of the verification procedure: the claim that bounds are reported only after explicit kernel-membership and row-space-exclusion tests is central to the certification of all upper bounds, yet the manuscript supplies no concrete description of the linear-algebra implementation over GF(2), handling of numerical stability, or edge-case checks (e.g., zero vectors or full-rank anomalies). This detail is load-bearing for the weakest assumption identified in the review.
  2. [Latent constructions] Latent block-compressed case: the block-compression criterion is asserted to render certification exact, but the manuscript does not specify the precise algebraic condition (e.g., rank relations or subspace dimension constraints) that guarantees the representative lies outside the stabilizer row space without further testing. This directly affects the reliability of the exact-certification claim.
minor comments (2)
  1. Notation for the various lift constructions (selected-fiber, CRT-stripe) is introduced without a consolidated table or diagram that would allow a reader to compare their algebraic properties at a glance.
  2. [Introduction] The abstract refers to 'representative APM-LDPC codes' without indicating the precise parameter tuples (n, k, d) or the range of block sizes explored; a short summary table in the introduction would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the methodological contribution, and constructive suggestions for improving clarity. We address the two major comments point by point below. Both points concern missing implementation details that can be supplied without altering the technical claims; we have therefore prepared a minor revision that incorporates the requested clarifications.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the description of the verification procedure: the claim that bounds are reported only after explicit kernel-membership and row-space-exclusion tests is central to the certification of all upper bounds, yet the manuscript supplies no concrete description of the linear-algebra implementation over GF(2), handling of numerical stability, or edge-case checks (e.g., zero vectors or full-rank anomalies). This detail is load-bearing for the weakest assumption identified in the review.

    Authors: We agree that an explicit description of the GF(2) verification steps strengthens the paper. In the revised manuscript we have inserted a new paragraph in Section 3 together with pseudocode in the appendix. All arithmetic is performed exactly over GF(2) using bit-packed vectors and standard Gaussian elimination (XOR-based row reduction). Kernel membership is checked by confirming that the candidate vector v satisfies H v = 0 (mod 2). Row-space exclusion is performed by comparing the rank of the stabilizer generator matrix with the rank of the same matrix augmented by v; if the ranks differ, v lies outside the row space. Because the field is GF(2) and all operations are integer modulo 2, no floating-point arithmetic or numerical stability issues arise. Edge cases are handled explicitly: the search discards the zero vector before verification, and we confirm that the parity-check matrix has the expected row rank given by the code parameters. These additions make the certification procedure fully reproducible. revision: yes

  2. Referee: [Latent constructions] Latent block-compressed case: the block-compression criterion is asserted to render certification exact, but the manuscript does not specify the precise algebraic condition (e.g., rank relations or subspace dimension constraints) that guarantees the representative lies outside the stabilizer row space without further testing. This directly affects the reliability of the exact-certification claim.

    Authors: We thank the referee for highlighting the need for a more formal statement. The revised Section 4.1 now states the precise condition: when a candidate is block-compressed to a single block whose support is confined to that block, and the rank of the corresponding compressed stabilizer submatrix equals the number of independent rows in that block, any nonzero vector orthogonal to the submatrix is automatically linearly independent from the full stabilizer row space. This follows directly from the block-diagonal structure of the latent relations and the direct-sum decomposition of the stabilizer space; the argument is now accompanied by a short rank-equality proof. The exact-certification claim therefore rests on this explicit rank condition rather than on an additional test. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central procedure uses heuristic search solely to generate candidate vectors for potential low-weight logical operators. Reported upper bounds on minimum distance are produced only after these candidates undergo independent, explicit algebraic verification: kernel-membership tests against the parity-check matrix and row-space-exclusion tests to confirm they lie outside the stabilizer space. These verification steps are standard linear-algebra checks for CSS quantum codes and are not defined in terms of the search outputs or any fitted parameters. The abstract and description explicitly separate candidate generation from certification, with no self-referential equations, ansatzes smuggled via citation, or uniqueness theorems invoked to force the results. The process is therefore self-contained against external algebraic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard linear-algebra facts over GF(2) for kernel and row-space membership; no free parameters, ad-hoc axioms, or new invented entities are introduced in the abstract.

axioms (1)
  • standard math Linear dependence and independence over GF(2) correctly identify stabilizer membership and logical operators.
    Invoked when performing kernel and row-space exclusion tests on candidate vectors.

pith-pipeline@v0.9.0 · 5491 in / 1239 out tokens · 37979 ms · 2026-05-10T11:03:08.196797+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Two-Branch Finite-Field Construction for Regular CSS LDPC Bases

    quant-ph 2026-05 unverdicted novelty 6.0

    A finite-field two-branch coset construction generates regular CSS LDPC bases for multiple (J,L) pairs, with a (3,10) example lifted 64-fold to a [[10240,4108,10≤d≤32]] code and post-processed FER of 1e-7 at p=0.058.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · cited by 1 Pith paper

  1. [1]

    R. G. Gallager,Low-Density Parity-Check Codes. MIT Press, 1963

    work page 1963

  2. [2]

    A recursive approach to low complexity codes,

    R. M. Tanner, “A recursive approach to low complexity codes,”IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533–547, 1981

    work page 1981

  3. [3]

    Expander codes,

    M. Sipser and D. A. Spielman, “Expander codes,”IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 1710–1722, 1996

    work page 1996

  4. [4]

    Quasi-cyclic low-density parity-check codes from circulant permutation matrices,

    M. P. C. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,”IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1788–1793, 2004

    work page 2004

  5. [5]

    Quasi-cyclic LDPC codes based on pre-lifted protographs,

    D. G. M. Mitchell, R. Smarandache, and D. J. Costello, “Quasi-cyclic LDPC codes based on pre-lifted protographs,”IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 5856–5874, 2014

    work page 2014

  6. [6]

    Good quantum error-correcting codes exist,

    A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”Physical Review A, vol. 54, no. 2, pp. 1098–1105, 1996

    work page 1996

  7. [7]

    Multiple-particle interference and quantum error correction,

    A. M. Steane, “Multiple-particle interference and quantum error correction,”Proceedings of the Royal Society of London. Series A, vol. 452, no. 1954, pp. 2551–2577, 1996

    work page 1954

  8. [8]

    Sparse-graph codes for quantum error correction,

    D. J. C. MacKay, G. Mitchison, and P. L. McFadden, “Sparse-graph codes for quantum error correction,”IEEE Transactions on Information Theory, vol. 50, no. 10, pp. 2315–2330, 2004

    work page 2004

  9. [9]

    Quantum quasi-cyclic LDPC codes,

    M. Hagiwara and H. Imai, “Quantum quasi-cyclic LDPC codes,” inIEEE International Symposium on Information Theory, 2007, pp. 806–810

    work page 2007

  10. [10]

    Quantum LDPC codes with positive rate and minimum dis- tance proportional to the square root of the blocklength,

    J.-P. Tillich and G. Zemor, “Quantum LDPC codes with positive rate and minimum dis- tance proportional to the square root of the blocklength,”IEEE Transactions on Informa- tion Theory, vol. 60, no. 2, pp. 1193–1202, 2014. 22

    work page 2014

  11. [11]

    Asymptotically good quantum and locally testable classical LDPC codes,

    P. Panteleev and G. Kalachev, “Asymptotically good quantum and locally testable classical LDPC codes,” inProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 375–388

    work page 2022

  12. [12]

    Quantum tanner codes,

    A. Leverrier and G. Zemor, “Quantum tanner codes,” inProceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, 2022, pp. 872–883

    work page 2022

  13. [13]

    Good quantum LDPC codes with linear time decoders,

    I. Dinur, M.-H. Hsieh, T.-C. Lin, and T. Vidick, “Good quantum LDPC codes with linear time decoders,” inProceedings of the 55th Annual ACM Symposium on Theory of Comput- ing, 2023, pp. 905–918

    work page 2023

  14. [14]

    Quantum error correction near the coding theoretical bound,

    Y. Komoto and K. Kasai, “Quantum error correction near the coding theoretical bound,” npj Quantum Information, vol. 11, p. 154, 2025

    work page 2025

  15. [15]

    Random construction of quantum LDPC codes,

    K. Okada and K. Kasai, “Random construction of quantum LDPC codes,” 2025, arXiv:2511.04634

    work page arXiv 2025

  16. [16]

    Finite-degree quantum LDPC codes reaching the gilbert–varshamov bound,

    K. Kasai, “Finite-degree quantum LDPC codes reaching the gilbert–varshamov bound,” 2026, arXiv:2603.24588

    work page arXiv 2026

  17. [17]

    A combining method of structured LDPC codes from affine permutation matrices,

    N. Myung, H. Yang, and J. Park, “A combining method of structured LDPC codes from affine permutation matrices,” inIEEE International Symposium on Information Theory, 2006, pp. 747–751

    work page 2006

  18. [18]

    Quantum error correction beyond the bounded distance decoding limit,

    K. Kasai, M. Hagiwara, H. Imai, and K. Sakaniwa, “Quantum error correction beyond the bounded distance decoding limit,”IEEE Transactions on Information Theory, vol. 58, no. 2, pp. 1223–1230, 2012

    work page 2012

  19. [19]

    Quantum error correction with girth-16 non-binary LDPC codes via affine permutation construction,

    K. Kasai, “Quantum error correction with girth-16 non-binary LDPC codes via affine per- mutation construction,” inProceedings of the 13th International Symposium on Topics in Coding (ISTC 2025), 2025, pp. 1–5, arXiv:2504.17790

    work page arXiv 2025

  20. [20]

    Breaking the orthogonality barrier in quantum LDPC codes,

    ——, “Breaking the orthogonality barrier in quantum LDPC codes,” 2026, arXiv:2601.08824

    work page arXiv 2026

  21. [21]

    Efficient mitigation of error floors in quantum error correction using non-binary low-density parity-check codes,

    ——, “Efficient mitigation of error floors in quantum error correction using non-binary low-density parity-check codes,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

    work page 2025

  22. [22]

    Quantum error correction exploiting degeneracy to approach the hashing bound,

    ——, “Quantum error correction exploiting degeneracy to approach the hashing bound,” 2025, arXiv:2506.15636

    work page arXiv 2025

  23. [23]

    Sharp error-rate transitions in quantum QC-LDPC codes under joint BP decoding,

    D. Komoto and K. Kasai, “Sharp error-rate transitions in quantum QC-LDPC codes under joint BP decoding,” inProceedings of the 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 2, 2025, pp. 564–565, arXiv:2507.11534

    work page arXiv 2025

  24. [24]

    Cross-commuting nonabelian squares in affine groups over finite commutative principal ideal rings,

    K. Kasai, “Cross-commuting nonabelian squares in affine groups over finite commutative principal ideal rings,” 2026, arXiv:2604.02063

    work page arXiv 2026

  25. [25]

    An efficient algorithm for finding dominant trapping sets of LDPC codes,

    M. Karimi and A. H. Banihashemi, “An efficient algorithm for finding dominant trapping sets of LDPC codes,”IEEE Transactions on Information Theory, vol. 58, no. 11, pp. 6942– 6958, 2012

    work page 2012

  26. [26]

    New characterization and efficient exhaustive search algorithm for leafless elementary trapping sets of variable-regular LDPC codes,

    S. H. Hashemi and A. H. Banihashemi, “New characterization and efficient exhaustive search algorithm for leafless elementary trapping sets of variable-regular LDPC codes,” IEEE Transactions on Information Theory, vol. 62, no. 12, pp. 6713–6736, 2016. 23

    work page 2016

  27. [27]

    Supplementary upper-bound tables for APM-based quantum LDPC codes,

    K. Kasai, “Supplementary upper-bound tables for APM-based quantum LDPC codes,” 2026, https://kasai.ict.eng.isct.ac.jp/en.html#live-upper-bound-table

    work page 2026

  28. [28]

    A probabilistic algorithm for computing minimum weights of large error- correcting codes,

    J. S. Leon, “A probabilistic algorithm for computing minimum weights of large error- correcting codes,”IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1354–1359, 1988

    work page 1988

  29. [29]

    A method for finding codewords of small weight,

    J. Stern, “A method for finding codewords of small weight,” inCoding Theory and Appli- cations, ser. Lecture Notes in Computer Science, vol. 388. Springer, 1989, pp. 106–113

    work page 1989

  30. [30]

    A new algorithm for finding minimum-weight words in a linear code: Application to mceliece’s cryptosystem and to narrow-sense BCH codes of length 511,

    A. Canteaut and F. Chabaud, “A new algorithm for finding minimum-weight words in a linear code: Application to mceliece’s cryptosystem and to narrow-sense BCH codes of length 511,”IEEE Transactions on Information Theory, vol. 44, no. 1, pp. 367–378, 1998

    work page 1998

  31. [31]

    Searching for linear codes with large minimum distance,

    M. Grassl, “Searching for linear codes with large minimum distance,” inDiscovering Math- ematics with Magma, ser. Algorithms and Computation in Mathematics, W. Bosma and J. Cannon, Eds. Springer, 2006, vol. 19, pp. 287–313

    work page 2006

  32. [32]

    Algorithms for the minimum weight of linear codes,

    P. Lisonˇ ek and L. Trummer, “Algorithms for the minimum weight of linear codes,”Advances in Mathematics of Communications, vol. 10, no. 1, pp. 195–207, 2016

    work page 2016

  33. [33]

    Bounds on the minimum distance of linear codes and quantum codes,

    M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” 2007, [Online]. Available: https://www.codetables.de. Accessed: Apr. 2, 2026. 24

    work page 2007