Heuristic Search for Minimum-Distance Upper-Bound Witnesses in Quantum APM-LDPC Codes
Kenta Kasai
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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper develops a systematic framework for establishing certified upper bounds on the minimum distance of a specific family of CSS quantum LDPC codes constructed from affine permutation matrices (APM). Rather than proving general lower bounds on code distance—which remains intractable for this family—the author constructs explicit low-weight logical operators (non-stabilizer codewords) that serve as witnesses for upper bounds. The key innovation is organizing multiple independent search strategies under a unified certification framework: latent row relations, three variants of restricted-lift subspaces (block-compressed, selected-fiber, CRT-stripe), cycle-8 elementary trapping set (ETS) structures, and decoder-failure residuals. Each method generates candidates heuristically, but the final bound claims rest entirely on algebraic verification (kernel membership and row-space exclusion tests).
The paper also identifies conditions (block-constant kernel hypothesis, Theorem A.1) under which the latent distance component can be determined exactly via a rank test plus SAT/SMT exhaustion, providing a partial exactness result within an otherwise heuristic framework.
Methodological Rigor
The mathematical framework is carefully constructed. The decomposition into active and latent matrices (Section 2), the descent of affine permutations under block compression (Lemma 5.2), and the fiber-quotient and CRT-stripe restricted-lift constructions are all stated precisely with complete proofs. The propositions establishing sufficient conditions for valid witnesses (Propositions 4.2, 5.4, 5.7, 5.9, 6.1, Corollary 6.6, Proposition 6.7) are straightforward but correctly formulated.
The paper is explicit about what is proven versus what is computed. The separation between search (heuristic) and certification (exact) is maintained throughout, which is methodologically sound. Each worked example (Examples 7.1–7.8) includes explicit support sets and rank computations, making verification reproducible.
However, there are notable methodological limitations. The paper only provides upper bounds—there is no mechanism to assess how tight these bounds are, except for the latent component where exact certification is sometimes possible. The paper acknowledges this honestly but it significantly limits the utility of the results. The explored parameter range (P ≤ 768, corresponding to blocklengths up to ~9216) is modest. The observation that bounds grow "roughly linearly with blocklength" is presented cautiously but remains inconclusive given the limited data points.
Potential Impact
The practical impact appears limited in several respects:
1. Narrow code family: The results apply specifically to APM-LDPC codes with (J,L)=(3,12) and girth-8 active Tanner graphs. While this family is motivated by companion work, it remains one of many competing quantum LDPC constructions.
2. Upper bounds only: Upper bounds on minimum distance are inherently less useful than lower bounds for code design. They tell us that the distance is *at most* some value but cannot certify error-correction capability. The paper is transparent about this limitation.
3. Sharpening prior bounds: The main practical outcome is updating the distance upper bounds from the companion paper [20]. The improvements are real (e.g., from d≤48 to d≤24 for C9) but incremental in nature.
4. Framework utility: The multi-pronged witness search framework could be adapted to other structured quantum LDPC families. The fiber-quotient and CRT-stripe constructions are somewhat novel search-space restrictions that might transfer to other quasi-cyclic or lifted code families.
5. The supplementary website as a living table: Maintaining a publicly updated parameter table is a useful community resource, analogous to Grassl's code tables.
Timeliness & Relevance
Quantum LDPC codes are highly active research area, driven by both theoretical breakthroughs (asymptotically good qLDPC codes by Panteleev-Kalachev, Leverrier-Zémor) and practical needs for fault-tolerant quantum computing. Finite-length distance evaluation is indeed a bottleneck—asymptotic results don't directly inform practical code selection. However, the paper addresses this bottleneck only partially, as it provides bounds rather than exact distances.
The focus on non-prime-power lift sizes driven by commutation constraints (companion paper [24]) adds a layer of specificity that may limit broader relevance but does address a genuine structural constraint in this construction family.
Strengths
Limitations
Overall Assessment
This is a technically careful but narrowly scoped paper that develops useful tools for upper-bounding minimum distance in a specific quantum LDPC code family. The mathematical framework is sound and the computational methodology is transparent. However, the contribution is primarily incremental—it refines parameter estimates for an existing code family without resolving the fundamental question of whether these codes have growing distance. The impact is likely confined to researchers working specifically on APM-based quantum LDPC constructions.
Generated Apr 17, 2026
Comparison History (28)
Paper 2 has higher potential impact due to broader applicability and timeliness: a circuit-level, implementable quantum Metropolis-Hastings workflow connects directly to widely used MCMC applications (physics, Bayesian inference, ML) and addresses practical obstacles to realizing quantum speedups. Its emphasis on explicit implementation, necessary modifications, and simulation-based validation targets near-future fault-tolerant quantum computing. Paper 1 is methodologically careful and valuable for a specific quantum LDPC code family, but its impact is narrower (distance upper bounds for APM-LDPC codes) and more specialized within quantum error correction.
Paper 1 addresses multipartite entanglement preparation using linear optics, a fundamental topic with broad applications in quantum communication and variational quantum computing. It introduces a general family of schemes for postselecting high-dimensional Dicke states, which are widely useful quantum resources. Paper 2 addresses a narrower technical problem—upper-bounding minimum distances of a specific family of quantum LDPC codes—with more limited scope and audience. Paper 1's broader applicability across quantum information science, clearer practical relevance, and wider potential audience give it higher estimated impact.
Paper 2 proposes a novel approach to quantum gravimetry that offers a significant leap in sensitivity (two orders of magnitude over traditional schemes) and scales advantageously with mass. This has broad, immediate real-world applications in geophysics, navigation, and fundamental physics. In contrast, Paper 1 is highly specialized, focusing on heuristic bounds for a specific subset of quantum error-correcting codes, which limits its broader scientific impact outside of theoretical quantum computing.
Paper 1 is more novel and broadly impactful: it links the canonical 2-Forrelation separation to the highly restricted IQP model, answers a recent open question, and strengthens an oracle separation result, potentially influencing quantum complexity, quantum advantage proposals, and IQP theory. It provides new structural tools (algebraic identity, Fourier growth bounds) with relevance beyond a single code family. Paper 2 is methodologically careful and useful for quantum coding practice, but its impact is narrower (specific APM-LDPC family, heuristic witness search) and less likely to shift foundational understanding across fields.
Paper 1 presents a foundational tool for quantum-classical co-compilation integrating with widely used frameworks (LLVM, CUDA, MPI). Its practical utility and broad applicability across quantum software development give it a significantly higher potential for widespread adoption and real-world impact compared to Paper 2, which focuses on a narrow theoretical aspect of a specific quantum error correction code family.
Paper 1 addresses quantum LDPC codes, a critical component for achieving fault-tolerant quantum computing. Given the current global push towards building scalable quantum computers, advancements in quantum error correction have high timeliness, broad interdisciplinary interest, and significant potential for real-world technological application. Paper 2 presents valuable theoretical work in mathematical physics (Yang-Mills equations), but its impact is likely more confined to specialized subfields of high-energy physics compared to the broader, more immediate applicability of Paper 1's findings.
Paper 2 addresses fundamental questions in quantum many-body physics—metastability, chaos, ergodicity, and localization in Bose-Hubbard systems—which are broadly relevant across condensed matter, quantum simulation, and cold-atom experiments. Its semiclassical tomographic approach connecting spectra to classical phase-space structures is novel and applicable to far-from-equilibrium scenarios of active experimental interest. Paper 1, while technically rigorous, addresses a narrow problem in quantum error correction (upper bounds on minimum distance for a specific LDPC code family), limiting its breadth of impact.
Paper 1 has higher potential scientific impact due to stronger novelty and rigor in quantum error correction: it develops certified, testable methods to obtain upper bounds on minimum distance for an explicit quantum LDPC family, improving known bounds with verifiable kernel/row-space exclusion. This addresses a timely core bottleneck for fault-tolerant quantum computing and can influence code design, benchmarking, and decoding across quantum information theory. Paper 2 is more application-oriented and resembles classical adaptive image transforms framed with POVMs; its broader appeal is possible but the methodological contribution appears less foundational and less likely to shift practice beyond niche “quantum-inspired” image processing.
Paper 2 has higher potential impact due to its broader relevance across quantum chaos, many-body physics, and quantum information. Demonstrating integrable, mixed, and chaotic dynamics coexisting within different symmetry sectors of a single, well-known model (Ising ATA) is conceptually novel and provides a new paradigm analogous to the Bunimovich billiard. This has implications for quantum simulation, noise resilience, and fundamental understanding of quantum chaos. Paper 1, while technically rigorous, addresses a narrow problem in quantum LDPC code distance bounds with limited cross-field impact.
Paper 2 addresses a fundamental question about quantum advantage boundaries, demonstrating that existing theoretical bounds systematically underestimate quantum advantage. Its Master Theorem provides a strictly tighter unified lower bound applicable over arbitrary finite fields, with concrete demonstrations of 26 parameter points where quantum advantage was previously missed. This has broader implications for quantum computing theory and applications. Paper 1, while technically rigorous, focuses on narrower code-specific upper bound improvements for a specific LDPC code family, with more limited cross-field impact.