PaperlayerView exact revision on arXiv

Source-linked AI summary

Lifted-Product QLDPC Codes in the Polynomial Domain

Vahid Nourozi, Mohsen Moradi, Roxana Smarandache, David G. M. Mitchell

arXiv:2609.01305v1cs.IT

TL;DR

Finite-length lifted-product QLDPC codes need compact, explicit algebraic constructions. The paper formulates them over a quotient ring, proves CSS orthogonality through conjugate-compatible lifting, and evaluates selected constructions with BP-based decoders on the depolarizing channel.

  • Problem

    Finite-length lifted-product QLDPC codes require compact polynomial descriptions that preserve structured binary representations and support algebraic verification.

  • Method

    The paper constructs lifted-product parity-check matrices over R_L = F2[D]/(D^L + 1), lifts polynomial entries to binary circulant blocks, and uses conjugate compatibility to prove CSS commutation.

  • Results

    Selected constructed codes were evaluated over the depolarizing channel with QBP, QBPGD, and RL-S, with RL-S improving block error rate relative to QBP for the N = 600 code.

  • Takeaways & Limitations

    The framework provides a structured method for constructing finite-length lifted-product QLDPC codes from small polynomial base matrices and testing them with practical iterative decoders.

Abstract

from arXiv · show

This paper presents a finite-length polynomial-domain formulation of lifted-product quantum low-density parity-check (QLDPC) codes. We formulate the code construction over the quotient ring F 2[D]/(D L + 1), where polynomial base matrices are lifted entrywise to binary circulant blocks. This representation gives a compact algebraic description of the lifted-product parity-check matrices and allows CSS orthogonality to be analyzed before binary expansion. We show that the standard circulant lifting map is compatible with polynomial conjugation, which implies that the resulting binary matrices satisfy the CSS commutation constraint. The construction is illustrated with a constraint length 7, rate 1/2 NASA convolutional code example, and numerical examples are provided from a 3 x 4 polynomial parity-check matrix. The finite-length performance of selected constructed codes is then evaluated over the depolarizing channel using various benchmark decoders. The resulting framework gives a structured method to construct finite-length lifted-product QLDPC codes from small polynomial base matrices.

I. INTRODUCTION

The paper targets finite-length lifted-product QLDPC codes with compact polynomial descriptions over a quotient ring. It uses conjugate-compatible circulant lifting to verify CSS commutation before binary expansion.

  • Finite-length implementations require explicit algebraic descriptions, controlled block size, and structured hardware-oriented representations.
  • Polynomial and quasi-cyclic descriptions lift small base matrices into large sparse binary parity-check matrices.The formulation uses the quotient ring F2[D]/(D^L + 1) for entrywise circulant lifting.
  • The construction formulates lifted-product parity-check matrices directly over R_L = F2[D]/(D^L + 1).Small polynomial base matrices compactly describe the corresponding circulant-lifted binary matrices.
  • Conjugate-compatible circulant lifting provides a polynomial-domain proof of the CSS commutation condition H_XH_Z^T = 0.
  • The framework connects convolutional-code polynomial parity checks with finite-length lifted-product construction through tail-biting circulant lifting.It is illustrated with a constraint length 7, rate R = 1/2 NASA convolutional code and a 3 × 4 polynomial parity-check matrix.
  • The quotient ring identifies polynomials modulo D^L + 1, giving unique representatives of degree less than L and reducing exponents modulo L.Because the field has characteristic two, D^L = 1 and D^-1 = D^(L-1).

B. Circulant Matrices and Lifting

The lifting operation maps polynomial entries to binary circulant blocks, producing finite block-circulant parity-check matrices. This gives polynomial convolutional-code components a finite tail-biting representation.

  • A circulant permutation matrix shifts the identity matrix row-by-row by s positions to the right modulo L.
  • This operation provides a finite circulant, or tail-biting, block representation of polynomial convolutional-code components.
  • The lifting operation maps p(D) in R_L to a binary circulant matrix by summing shift matrices over F2.
  • A coefficient a_i = 1 includes the circulant shift by i, while a_i = 0 omits it; the rows are cyclic shifts of the coefficient vector.
  • The polynomial–circulant correspondence replaces each polynomial entry with an L × L binary circulant matrix.
  • The resulting matrix has dimensions mL × nL and consists of L × L circulant blocks.

C. Depolarizing Channel Model and BP-based Decoders

The paper evaluates finite-length codes under the depolarizing channel with BP-based decoders. QBP models the coupled Pauli errors, while guided decimation and learned sequential scheduling address decoding difficulties differently.

  • QBP performs message passing on CSS Tanner graphs while maintaining beliefs over the four Pauli symbols I, X, Y, and Z.
  • Under the depolarizing channel, each of X, Y, and Z occurs independently with probability p.
  • QBP accounts for coupling introduced by Y errors, then checks its hard Pauli estimate for syndrome consistency and logical correctness.
  • QBPGD interleaves short QBP runs with G reliability-based decimation steps that fix highly reliable qubits.This can break symmetric failures caused by short cycles and degeneracy, but may increase decoding cost.
  • RL-S retains BP message updates but replaces flooding with a learned sequential variable-node update order during inference.Its policy is trained offline and selects the next variable node from local state information.

III. THE CONJUGATE TRANSPOSE OPERATION IN QUOTIENT RINGS

The conjugate operation in the quotient ring is the algebraic mechanism underlying the paper’s orthogonality proofs. It is linear, involutive, multiplicative, and extends to matrix conjugate transposes.

  • Polynomial conjugation maps p(D) to p*(D) = p(D^-1) within the quotient ring, with D^L interpreted as 1.
  • The conjugation map is F2-linear, involutive, and multiplicative.
  • The conjugate transpose transposes a polynomial matrix and replaces each entry with its conjugate polynomial.
  • The paper performs conjugation within R_L using its defined quotient-ring operation, distinct from Hermitian transpose terminology.
  • For conformable polynomial matrices, conjugate transpose distributes over addition and reverses multiplication order.
  • For Kronecker products, conjugation distributes as (A ⊗ B)* = A* ⊗ B*.

A. Lifting map and the conjugate-compatibility condition

The paper defines standard circulant lifting over R_L and establishes its compatibility with polynomial conjugation. This compatibility extends entrywise to matrices and links polynomial operations to binary circulant-matrix operations.

  • Lifting map: The lifting map LL sends elements of R_L to binary L × L circulant matrices.The map is used entrywise to lift polynomial matrices.
  • Lifting map: LL preserves addition and multiplication, including entrywise operations on lifted matrices.These identities follow because circulant-matrix arithmetic corresponds to polynomial arithmetic in R_L.
  • Conjugate compatibility: Conjugate-compatible lifting requires LL(p∗) = LL(p)T for every p ∈ R_L.This condition identifies polynomial conjugation with matrix transposition after lifting.
  • Conjugate compatibility: Standard circulant lifting satisfies LL(p∗) = LL(p)T for all p ∈ R_L and extends this identity to matrices.The proof checks monomials, uses cyclic-index reduction modulo L, and extends by F2-linearity and entrywise application.

B. Lifted-product polynomial check matrices

The lifted-product construction begins with arbitrary polynomial parity-check base matrices over R_L and forms asymmetric polynomial check matrices using Kronecker products. Binary parity-check matrices are then obtained by applying the lifting map.

  • Polynomial check matrices: The construction allows arbitrary polynomial parity-check base matrices over R_L.These matrices are used to define the asymmetric lifted-product checks.
  • Polynomial check matrices: The asymmetric LP polynomial check matrices use Kronecker products over R_L and identity matrices I_s.The Kronecker product is taken over the coefficient ring R_L.

C. Conditional LP orthogonality theorem

Under conjugate-compatible lifting, lifted-product check matrices are orthogonal in the polynomial domain and therefore satisfy binary CSS commutation after expansion. The NASA example illustrates the construction with finite dimensions and a valid CSS pair.

  • Conditional LP orthogonality theorem: Theorem 1 states that conjugate-compatible lifting makes lifted-product matrices satisfy the required orthogonality relation for any base matrices over R_L.The theorem is conditional on the lifting map satisfying the conjugate-compatibility definition.
  • NASA example: The lifted pair satisfies HXHZT = 0 over F2 and therefore defines a valid CSS code.The example is intended to illustrate the polynomial-domain construction and conjugate-compatible lifting argument.
  • Conditional LP orthogonality theorem: The polynomial-domain proof expands the product into two Kronecker terms, applies the mixed-product rule, and cancels them because the coefficient ring has characteristic two.The proof uses commutativity of R_L and the identity (A ⊗ C)(B ⊗ D) = (AB) ⊗ (CD).
  • Conditional LP orthogonality theorem: Binary lifting transfers the polynomial orthogonality identity to HXHZT = 0.The transfer uses the lifting map's multiplicative property and conjugate compatibility.
  • NASA example: The NASA example uses a constraint length 7, rate R = 1/2 convolutional code with a symmetric lifted-product construction.It sets B1 = B2 = B, m = 1, and n = 2.
  • NASA example: The example forms polynomial LP checks, applies standard circulant lifting entrywise, and obtains binary matrices with 35 columns and 14 rows.The dimensions are HX, HZ ∈ F2^14×35.

V. NUMERICAL RESULTS

The numerical study constructs a family of finite-length lifted-product QLDPC codes from a searched 3 × 4 polynomial base matrix and compares benchmark decoders over the depolarizing channel. Results span multiple lifting sizes, with RL-S outperforming QBP for one code and avoiding the severe error floor observed for BP-based decoders on the largest code.

  • Code construction: The selected 3 × 4 polynomial base matrix was found by computational search for sparse lifted codes with nonzero rate and balanced X- and Z-distance behavior.For each lifting size, entries are reduced modulo D^L + 1 and used to form the CSS parity-check matrices.
  • Code family: Changing the lifting size produces structured finite-length QLDPC codes with different block lengths, dimensions, and distance estimates.Table I summarizes the resulting code parameters.
  • Decoder evaluation: The simulations compare QBP, QBPGD, and RL-S using block error rate over the depolarizing channel.Block error rate counts decoder failures to return a consistent syndrome or a recovery in the wrong logical coset.
  • L = 17: For the [[425, 21, 18]] code at L = 17, BP-based methods decode effectively over the depolarizing channel.Figure 1 compares QBP, QBPGD, and RL-S with different iteration budgets.
  • L = 24: For the [[600, 32, d ≤20]] code at L = 24, RL-S improves block error rate relative to QBP, with its larger iteration budget performing best among plotted decoders.The code has dX, dZ, d ≤20 from a minimum-distance search.
  • L = 83: For the [[2075, 87, d ≤34]] code at L = 83, QBP and QBPGD show a severe error floor, whereas RL-S does not.The graph contains 30,378 4-cycles, and the improvement is reported as consistent with prior RL decoding results for polar codes.

VI. CONCLUSIONS

The paper develops a polynomial-domain formulation and verification framework for finite-length lifted-product QLDPC codes, linking conjugate-compatible lifting to CSS commutation and practical code construction. It positions the framework as a design tool rather than a new asymptotic lifted-product result.

  • Conjugate-compatible circulant lifting enables the CSS commutation condition HXH^T_Z = 0 to be proved directly in the polynomial domain.The proof occurs before binary expansion, simplifying verification of the resulting binary parity-check matrices.
  • The formulation connects classical convolutional-code polynomial descriptions with finite-length lifted-product QLDPC construction.The construction uses a constraint length 7 NASA convolutional code and a 3 × 4 polynomial base matrix to produce structured finite-length codes.
  • Selected constructed codes were evaluated over the depolarizing channel with BP-based decoders and were compatible with practical iterative decoding methods.
  • The work is a description and verification framework for new LP-QLDPC code design, not a new asymptotic lifted-product result.Future directions include distance-search constraints, polynomial-base-matrix optimization, and syndrome-extraction schedules adapted to the structure.
Loading 2609.01305v1…