Quasi-Cyclic Qudit Lifted Product Codes with Almost Linear Minimum Distance

The paper in detail

A qudit of dimension \(q=p^m\) carries Pauli operators labelled by \(\mathbb F_q\). A CSS code is given by two parity-check matrices \(H_x\), \(H_z\) whose rows must be orthogonal. The LP construction builds them from two small matrices whose entries are not numbers but elements of a ring, here \(R_\ell=\mathbb F_q[x]/\langle x^\ell-1\rangle\). Each entry becomes an \(\ell\times\ell\) circulant matrix through the lift \(\rho(ax^k)=aP^k\), with \(P\) the cyclic shift. The stacking order \(s\) controls whether the code is \(\mathbb F_q\)-linear (\(s=m\), fully stacked) or only additive.

For matrices \(H_1\) (\(r_1\times n_1\)) and \(H_2\) over \(R_\ell\) the code uses \[H_x=\rho\bigl([\,H_1\otimes I\ \ I\otimes H_2^{\mathsf T}\,]\bigr),\qquad H_z=\rho^*\bigl([\,I\otimes H_2\ \ -H_1^{\mathsf T}\otimes I\,]\bigr),\] up to stacking factors, with \(\rho^*(\alpha)=\rho(\alpha)^{\mathsf T}\). Because the lift is a ring homomorphism and \(R_\ell\) is commutative, the product \(H_xH_z^{\mathsf T}\) is the lift of \(H_1\otimes H_2^{\mathsf T}-H_1\otimes H_2^{\mathsf T}=0\). Every block is circulant, so the code is invariant under simultaneous cyclic shifts within each block of \(\ell\) qudits. With \(\ell=1\) it reduces to the stacked hypergraph product.

The almost-linear family takes \(H_2=b=x-1\) and \(H_1\) the parity-check matrix of a Tanner code on a cyclic lift of a Ramanujan graph, with lift size \(\ell=2^{\Theta(n_0)}\) and local code chosen so that \(H_1\) and its transpose are \((\alpha,\beta)\)-expanding. The number of logical qudits is \[k=\dim\ker H_1(1)+\dim\ker H_1(1)^{\mathsf T}\ \ge\ n-m=\Theta(\log\ell).\] The distance is at least \(\gamma\ell\) with \(\gamma=\min(\alpha/2e,\ \alpha\beta/4ew')\), where \(e\) is the order of \(b\) and \(w'=\max(w,\lvert b\rvert)\). Since \(N=(n+m)\ell\) and \(n+m=\Theta(\log\ell)\), this is \(\Theta(N/\log N)\).

The numerics use three codes: two hypergraph products (one is \([[900,36,10]]\) fully stacked) and an LP code \([[1054,140,20]]\) with circulant size 31, built from a known Tanner code with random \(\mathrm{GF}(q)\) labels. Belief propagation on the stacked Tanner graph gains strongly from \(\mathrm{GF}(2)\) to \(\mathrm{GF}(4)\) and then saturates. The authors trace this to stacking, which copies each check node into \(m\) replicas that share neighbours and so creates \(\binom m2\) 4-cycles per degree-2 check. The merged-syndrome decoder runs non-binary BP on the unstacked graph and recovers up to an order of magnitude at \(\mathrm{GF}(8)\).

Open problems listed are a distance bound for partially stacked codes, better constants for general \(b\), the product of two lifted Tanner codes (expected to give linearly many logical qudits with the same distance scaling) and non-abelian group algebras, which would recover asymptotically good codes at the cost of the circulant structure.

Transferable methods

1. Lifting over a commutative group algebra

   An earlier qudit generalisation lifted field elements and collapsed to a hypergraph product. Lifting over the ring \(R_\ell\) instead keeps the polynomial structure that gives LP codes their distance, and commutativity of \(R_\ell\) is exactly what makes the CSS condition automatic.

   The lift \(\rho\) is the left regular representation of \(R_\ell\): \(\rho(\alpha\beta)=\rho(\alpha)\rho(\beta)\) and \(\rho(\alpha)\) is the circulant with first column the coefficients of \(\alpha\). With \(M=[\,H_1\otimes I\ \ I\otimes H_2^{\mathsf T}\,]\) and \(N=[\,I\otimes H_2\ \ -H_1^{\mathsf T}\otimes I\,]\), \[\rho(M)\,\rho^*(N)^{\mathsf T}=\rho(M)\,\rho(N^{\mathsf T})=\rho(MN^{\mathsf T}),\qquad MN^{\mathsf T}=H_1\otimes H_2^{\mathsf T}-H_1\otimes H_2^{\mathsf T}=0.\]

   For \(b=x-1\), which is irreducible with root 1, the logical count reduces to evaluating \(H_1\) at \(x=1\): \(k=\dim\ker H_1(1)+\dim\ker H_1(1)^{\mathsf T}\) over \(\mathbb F_q\).

   Editorial check: twelve random lifted products over \(\mathrm{GF}(3)\), \(\mathrm{GF}(5)\) and \(\mathrm{GF}(7)\), with \(\ell\in\{5,6,7,9\}\) and \(H_1\) of size up to \(3\times5\), all satisfied \(H_xH_z^{\mathsf T}=0\). In every case \(k=N-\mathrm{rank}\,H_x-\mathrm{rank}\,H_z\) equalled the value predicted from \(H_1(1)\), including cases where it exceeded \(n-m\).

   How to reuse it

   To generalise a binary algebraic code construction to other alphabets while keeping its structure, look for a commutative ring whose regular representation produces the desired block pattern. Orthogonality conditions that hold formally in the ring then transfer to the lifted matrices for free.

2. Cycle determinants and decoder oscillation

   Qudit codes decoded better in simulation, and the authors wanted a mechanism. They analyse the smallest harmful structure, a single 4-cycle, under a hard-decision symbol-flipping decoder, and find that over larger fields most 4-cycles are harmless.

   A 4-cycle is a \(2\times2\) check matrix \(H=\bigl(\begin{smallmatrix}h_{00}&h_{01}\\h_{10}&h_{11}\end{smallmatrix}\bigr)\) with nonzero entries; let \(\Delta=\det H\). Each check proposes for each neighbour the value that would satisfy it, and a symbol changes only when both checks agree. If \(\Delta=0\) the columns are parallel, so any nonzero syndrome is a multiple of both columns: both symbols flip, the estimate overshoots to a residual of \(-\tilde s\), both flip back, and the decoder oscillates with period 2. If \(\Delta\ne0\), a weight-1 error is corrected in one step and a weight-2 error leaves the decoder stuck.

   Over \(\mathrm{GF}(2)\) every entry is 1, so \(\Delta=0\) always. For uniformly random nonzero labels \(\Pr[\Delta=0]=1/(q-1)\), since \(h_{11}\) is then determined, and with symbol errors of probability \(p\), \[P_{\mathrm{osc}}=\frac{1}{q-1}\Bigl(2p-p^2-\frac{p^2}{q-1}\Bigr).\]

   Editorial check: exhaustive enumeration over all labelings and all error pairs for \(q=3,5,7\) confirmed the three cases of Theorem 42 without exception, and at \(p=0.05\) gave oscillation probabilities 0.048125, 0.024219 and 0.016181, equal to Eq. (92).

   How to reuse it

   When a hard-decision decoder fails on short cycles, check whether failure depends on an algebraic invariant of the cycle's labels; over larger alphabets random labels make the bad invariant value rare, which is a design criterion, not just an empirical observation.

Source: Definitions 19–21, Proposition 22, Remark 23; Theorems 28, 30, 36 and Corollary 37; Definition 41, Theorem 42, Corollary 43. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The construction gives families of quasi-cyclic qudit LDPC codes with provable near-linear distance in the form that hardware decoders are designed for. It also identifies the 4-cycles created by stacking as the bottleneck that limited earlier qudit decoders, with a decoder that avoids them.

Limitations. The family has only \(\Theta(\log N)\) logical qudits, and its constants come from expander and Tanner-code bounds that are not made explicit; the simulated codes are small instances (\([[900,36,10]]\), \([[1054,140,20]]\)), not members of the asymptotic family. Comparing qudit and qubit codes at the same symbol error probability is not resource-fair, as the authors note. The distance of partially stacked codes is unproven, and the 4-cycle analysis concerns a simple symbol-flipping decoder rather than belief propagation itself. The authors state that Claude Opus 5.5 was used for language editing and to fill some gaps in the minimum-distance proof, as well as for figure captions and auxiliary simulation scripts; the decoders, simulations and methodology are the authors' own.

Description based on the full arXiv HTML of v1, read 2026-11-14: Sections I, IV, V (Theorems 28, 30, 36 and Corollary 37, without the proofs of Lemmas 31–35), VI and VII including Theorem 42 and Corollary 43, the conclusions and the AI statement; Sections II–III (qudit background and hypergraph products) were skimmed. Proposition 22 and the logical-qudit formula of Theorem 30 were checked on random small codes, and Theorem 42 and Eq. (92) by exhaustive enumeration.