Japanese overview · English overview · Main page

Kasai Code Catalog

This catalog restores the individual Kasai-code instances, parameter files, and minimum-distance records formerly published on the main English page.

Classification: the affine-coset, two-branch finite-field, rate-2/3 two-branch, and Okada–Kasai PP constructions are separate code families and are not included in this catalog.

---

Binary LDPC-based quantum codes

In Breaking the Orthogonality Barrier in Quantum LDPC Codes , we focus on the orthogonality constraints between X/Z parity-check matrices, which tend to introduce short cycles and limit code distance. This barrier also means that classical LDPC design principles, such as degree-distribution design, girth control, and short-cycle removal, cannot be freely imported into quantum LDPC construction. We control the commutativity of permutation matrices and restrict orthogonality constraints to the “active” part of the construction, while preserving a regular sparse structure. This yields explicit CSS LDPC codes with large girth, avoiding short cycles in the Tanner graph, and aims to recover within qLDPC construction the design freedom developed in classical LDPC coding.

---

Minimum-distance benchmark from degree distributions

We use a distance benchmark based on the average weight enumerator of regular LDPC-type ensembles to see how favorable a given degree distribution is from the minimum-distance viewpoint.

The colored curves are not exact minimum-distance computations for the constructed finite-length CSS codes. They are typical-relative-distance benchmarks obtained from the average weight enumerator of a \((J,L)\)-regular random LDPC-type ensemble. For relative weight \(\delta=d/n\), write the expected number of codewords as \(\mathbb{E}A_{\delta n}\doteq \exp(n\gamma_{J,L}(\delta))\). The plotted distance benchmark for each \((J,L)\) point is the first positive \(\delta\) satisfying \(\gamma_{J,L}(\delta)=0\). Here \[ \gamma_{J,L}(\delta) = h(\delta) +\frac{J}{L}\log P_L(x) -J\delta\log x -J h(\delta), \qquad P_L(x)=\frac{(1+x)^L+(1-x)^L}{2}, \] where \(x\) is the positive saddle-point solution of \[ \frac{xP_L'(x)}{P_L(x)}=L\delta . \] The curve for a fixed \(J\) is obtained by varying \(L\) and plotting the CSS design rate \(R=1-2J/L\). The black CSS GV curve is \(R=1-2h_2(\delta)\).

---

Live Upper-Bound Table

Upper-bound definitions are summarized here. The accompanying manuscript is arXiv:2604.15307.

The parameter files themselves are linked from the code entries below. See this short guide for how to read those files, and this note on upper-bound constructions for formal definitions of Latent UB, m-block UB, Fiber-quotient UB, CRT UB, Cycle-8 ETS UB, Direct CSS UB, and Decoder-fail UB. The m-block UB column records the full-fiber block-compression case, while Fiber-quotient UB records proper selected-fiber patterns only; the two columns are therefore separated method-specific entries, not a single minimized fiber-pattern value.

A consolidated supplementary page for this project is available here.

Exploratory Girth-6 Upper-Bound Table

These exploratory rows use girth at least 6 and enforce the two noncommuting pairs \((0,3)\) and \((1,2)\). They are kept separate from the girth-8 table below. The lower bound \(d \geq 8\) comes from an exact low-weight screening: odd weights are excluded by column weight 3, weight 2 is excluded by the girth condition, and weights 4 and 6 were not found in either CSS kernel. The decoder-fail upper bound also includes nondegenerate logical residuals found by the decoder-failure search.

A 3-Mac follow-up for smaller \(P\) found candidates at \(P=28,36,42,48\), but each was removed by a weight-6 logical witness. Rows whose upper-bound evidence already fixes \(d=8\) are omitted from this exploratory list; the current smallest listed row is \(P=92\). The exclusion summary is available as TSV. The \(P=192\) S1--S4 rows are the four survivor family members from the Toward-style P192 search.

Entries written as \(d=\cdots\) are exact: exhaustive low-weight search excludes every nontrivial logical operator below the stated weight on both CSS sides, and an independently checked logical witness attains the stated weight.

Rows are sorted by increasing \(P\). All 47 listed girth-6 codes now report a rigorously verified exact distance \(d\): exhaustive no-witness certificates through \(d-1\) on both CSS sides, together with an independently checked weight-\(d\) logical witness.

This table records upper bounds obtained from witnesses checked by the mechanisms named in the column headers.

In the Cycle-8 ETS UB column, NF means that the recorded evaluation produced no CSS witness, whereas NE means that no evaluation is recorded for that row. Neither label should be read as an exhaustive proof of nonexistence.

In the DFC trials column, -- means that no decoder-failure trial count is recorded for that row.

---

---

Rigorous minimum-distance verification

Every catalog entry written as \(d=d_0\) is backed by two logically separate computations: a complete no-witness search below \(d_0\) on both CSS sides, and an independently checked logical operator of weight \(d_0\). Decoder failures, topology catalogues, and heuristic upper-bound searches may locate useful witnesses, but they are not used as lower-bound certificates.

1. CSS quotient searched

Let \(H_XH_Z^{\mathsf T}=0\), with all linear algebra over \(\mathbb F_2\). The two distances are

\[ d_X=\min\{\operatorname{wt}(x):H_Zx^{\mathsf T}=0, \ x\notin\operatorname{rowspan}(H_X)\}, \] \[ d_Z=\min\{\operatorname{wt}(z):H_Xz^{\mathsf T}=0, \ z\notin\operatorname{rowspan}(H_Z)\}, \qquad d=\min(d_X,d_Z). \]

Thus an X-side search uses \((H,G)=(H_Z,H_X)\), and a Z-side search uses \((H,G)=(H_X,H_Z)\). It looks for \(\ker H\setminus\operatorname{rowspan}(G)\), not merely for a low-weight vector in \(\ker H\).

2. Complete connected-support search

For a weight limit \(W\), a depth-first-search state consists of a selected support \(S\), a locally forbidden set \(F\), and the syndrome \(\sigma(S)=H\mathbf 1_S^{\mathsf T}\). The search is performed as follows.

1. Choose a root variable and require it to be the least variable in the support. Every permitted root is searched.
2. If \(\sigma(S)=0\), test \(\mathbf 1_S\) by exact binary row reduction. If it is outside \(\operatorname{rowspan}(G)\), return it as a logical witness; otherwise close this branch.
3. If the syndrome is nonzero, choose an unsatisfied check \(c\). Every zero-syndrome extension must add a variable from \(A_c=N(c)\setminus(S\cup F)\), so branch over every member of \(A_c\). After a branch is completed, add its candidate to the local forbidden set to avoid duplicate enumeration without deleting any support.
4. Prune only when impossibility is proved: \(A_c=\varnothing\), the weight limit is exceeded, or a rigorous lower bound on the number of additional variables exceeds the remaining budget. Examples are \(\lceil|\sigma(S)|/\Delta\rceil\), where \(\Delta\) is the maximum column weight of \(H\), and a packing of unsatisfied checks having pairwise-disjoint available-variable sets.

A minimum logical operator has a Tanner-connected support and contains no proper nonempty zero-syndrome support. Consequently, closing a branch when it reaches a stabilizer does not hide a minimum logical operator, and the branching rule retains a path to every possible minimum logical support. A completed search returns no witness if and only if \(d(H,G)>W\).

3. Root coverage for APM codes

For a generic affine-permutation-matrix (APM) lift, the rigorous default is to use all \(n=LP\) physical variables as roots. The CPM reduction from \(LP\) roots to \(L\) roots uses a common cyclic translation and must not be applied automatically to APM blocks. For \(h(a)=\alpha a+\beta\), in general \(h(a+c)\neq h(a)+c\) when \(\alpha\neq1\). Root reduction is used only when an automorphism preserving both \(\ker H\) and \(\operatorname{rowspan}(G)\) has been explicitly verified; one root per verified orbit is then sufficient.

4. What constitutes an exact-distance certificate

• \(d>W\): both the X-side and Z-side searches finish with no witness through weight \(W\), with complete coverage of the required roots.
• \(d=d_0\): the preceding condition holds for \(W=d_0-1\), and a weight-\(d_0\) vector is independently verified to have zero syndrome and to lie outside the opposing stabilizer row space.
• A timeout, an unfinished root interval, or a heuristic failure to find a witness is recorded as incomplete and is not a distance lower bound.

The method and its completeness proof are given as the distance-verification algorithm in Okada and Kasai, Pair-Partition Constructions for CPM-Based Quantum LDPC Codes . The proof is stated for general binary matrices \(H,G\); cyclic symmetry is an optional CPM-specific acceleration, not a requirement for correctness.

Back to top