An Efficient Algorithm to Sample Quantum Low-Density Parity-Check Codes

Technical Summary: An Efficient Algorithm to Sample Quantum Low-Density Parity-Check Codes

Problem Statement
The paper addresses the challenge of efficiently generating random quantum Low-Density Parity-Check (LDPC) codes. While classical LDPC codes can be generated by simply sampling sparse matrices, quantum LDPC codes require an additional constraint: the parity-check matrices must satisfy the symplectic product condition (specifically, $HH^\top = 0$ for dual-containing codes) to ensure the associated Pauli group subgroup is Abelian. Existing constructions for quantum LDPC codes are predominantly algebraic (e.g., quasi-cyclic, hypergraph products, or based on specific geometric structures). These algebraic approaches impose rigid constraints on code parameters (length, dimension, sparsity) and result in codes that are far from random. The paper poses the question: Can random quantum LDPC codes be generated efficiently without relying on specific algebraic structures?

Methodology
The authors propose a purely combinatorial algorithm to sample sparse, self-orthogonal binary matrices row by row. The core methodology relies on Information Set Decoding (ISD), specifically the Lee-Brickell (LB) algorithm, adapted for this sampling task.

The algorithm proceeds in $r$ steps to construct a matrix $H \in \mathbb{F}_2^{r \times n}$:

1. Iterative Sampling: At step $u$, the algorithm assumes $u-1$ linearly independent, sparse, and mutually orthogonal vectors $\{h_1, \dots, h_{u-1}\}$ have already been found.
2. Code Definition: These vectors form the parity-check matrix of a linear code $C_u$. The algorithm seeks a new vector $h_u$ that is a codeword in $C_u$ (ensuring orthogonality to previous rows) and has a specific Hamming weight $v$ (ensuring sparsity). To enforce even weight (a requirement for self-orthogonality in binary fields), the all-ones vector is added as an additional parity-check equation.
3. ISD Utilization: To find a codeword of weight $v$ in $C_u$, the algorithm employs ISD. This is the critical component; without ISD, finding such sparse vectors in a high-dimensional space would be computationally infeasible.
4. Basis Update: If a valid $h_u$ is found that is not in the span of the previous vectors, it is added to the matrix, and the process repeats until $r$ rows are generated.

Theoretical Analysis and Parameter Selection
The paper provides a theoretical characterization of the algorithm's feasibility, focusing on the Expected Weight Distribution (EWD) of the intermediate codes $C_u$.

• Existence of Solutions: The authors derive conditions under which a codeword of weight $v$ exists with high probability. They model the parity-check matrix $H_u$ as a sample from a distribution $H_{n,u,v}$ where rows have constant weight $v$.
• Weight Constraints: Through asymptotic analysis, they prove that for a constant code rate $R$, codewords of sublinear weight $w = o(n)$ exist with high probability only if the row weight $v$ satisfies:
  $$v < \frac{\ln(2)}{1-R} \log_2(n)$$
  This implies that for the algorithm to succeed efficiently, the row weight must be logarithmic in the code length $n$.
• Complexity: The paper analyzes the time complexity using standard ISD heuristics. While the authors note that proving polynomial time rigorously requires assumptions about ISD behavior on sparse matrices (which differ from random matrices), they argue that under plausible heuristics, the algorithm runs in polynomial time when $v = O(\log n)$. Specifically, if the expected number of weight-$v$ codewords is large, the number of ISD calls required is minimal (often close to 1).

Results and Numerical Validation
The authors implemented the algorithm in Sagemath and provided benchmarks on a standard laptop.

• Feasibility: The algorithm successfully generated dual-containing codes for various parameters (e.g., $n=250, 500, 1000$) with constant rates.
• Efficiency: Table I and Table III show that for parameters satisfying the theoretical bounds, the average time to generate a code is reasonable (ranging from seconds to minutes depending on $n$ and $v$).
• ISD Calls: A key finding is that the average number of ISD calls per step is extremely close to 1 (often exactly 1), confirming that the theoretical condition $m_v^{(r)} \gg 1$ ensures the algorithm rarely gets stuck.
• Column Distribution: The paper validates that the resulting matrices have predictable column weight distributions, allowing for the removal of "unlucky" columns (e.g., null columns or columns with weight 1) via puncturing without breaking self-orthogonality.

Generalizations
The paper outlines how the approach can be extended:

• Non-binary Fields: The algorithm can be adapted to $\mathbb{F}_q$ by modifying the ISD and handling the self-orthogonality condition (which requires rejection sampling if the field characteristic is not 2).
• General Stabilizer Codes: The method can sample general quantum stabilizer codes (not just CSS codes) by iteratively sampling pairs of vectors $(a_i, b_i)$ that satisfy the symplectic product condition $a_i b_j^\top + b_i a_j^\top = 0$.

Significance and Claims
The paper claims to provide a positive answer to the question of whether random quantum LDPC codes can be generated efficiently.

• Combinatorial vs. Algebraic: Unlike existing methods, this approach does not rely on algebraic structures (like quasi-cyclicity), allowing for the sampling of codes that are as random as possible, subject only to sparsity and orthogonality.
• Modest Claims on Complexity: The authors are cautious about claiming a formal proof of polynomial time. They explicitly state that the complexity analysis relies on heuristics regarding ISD performance on sparse matrices, which differ from the standard random code assumptions. They acknowledge that while numerical simulations strongly suggest polynomial-time behavior, a rigorous theoretical proof remains an open question.
• Future Work: The authors identify the design of an ISD algorithm specifically tailored for LDPC codes as a promising direction to further improve efficiency and address open questions regarding the formal complexity bounds.

In summary, the paper presents a novel, combinatorial sampling technique that bridges the gap between the ease of generating classical LDPC codes and the structural constraints of quantum codes, demonstrating that random quantum LDPC codes are accessible via efficient, ISD-based sampling.