Breaking the Orthogonality Barrier in Quantum LDPC Codes

Technical Summary: Breaking the Orthogonality Barrier in Quantum LDPC Codes

Problem Statement
Classical Low-Density Parity-Check (LDPC) codes rely on increasing the girth of the Tanner graph to improve belief-propagation (BP) decoding performance and minimum distance. However, this principle does not directly translate to quantum LDPC codes, specifically Calderbank–Shor–Steane (CSS) codes, due to the orthogonality constraint between the $X$ and $Z$ parity-check matrices ($H_X H_Z^T = 0$).

In standard CSS constructions, enforcing both orthogonality and regular degree distributions typically forces a reduction in girth and induces structural upper bounds on the minimum distance. A primary mechanism for this degradation is the "row deletion" method used to adjust code rates. When rows are deleted from parent matrices to form active check matrices, the latent (deleted) rows often remain orthogonal to the active matrices. Consequently, these low-weight latent rows can become non-trivial logical operators, capping the minimum distance at the row weight. Existing constructions, such as those based on circulant permutation matrices (CPMs), often face fixed upper bounds on girth (e.g., girth $\le 6$ for column weight $\ge 3$) or require complex lifting that does not fully resolve the distance degradation issue.

Methodology
The author proposes a construction framework that breaks the "orthogonality barrier" by decoupling the orthogonality requirement of the full parent matrices from that of the active submatrices. The core methodology involves:

1. Active vs. Latent Orthogonality: Instead of requiring the full parent matrices $\hat{H}_X$ and $\hat{H}_Z$ to be orthogonal, the design enforces orthogonality only on the active parts ($H_X H_Z^T = 0$). Crucially, the design ensures that the latent parts ($\tilde{H}_X, \tilde{H}_Z$) are not orthogonal to the active matrices ($H_X \tilde{H}_Z^T \neq 0$ and $H_Z \tilde{H}_X^T \neq 0$). This prevents low-weight latent rows from automatically becoming logical operators.
2. Generalized Hagiwara–Imai Codes with APMs: The construction utilizes generalized Hagiwara–Imai codes, which are protograph-based with block-circulant structures. The author employs Affine Permutation Matrices (APMs) rather than standard CPMs. APMs allow for controlled commutativity via algebraic congruence conditions.
3. Commutativity Control: The author derives sufficient conditions where specific pairs of permutation matrices commute to satisfy active orthogonality, while other pairs are deliberately made non-commuting to break parent orthogonality. This is formalized through interaction matrices $\Psi_r$. The design ensures $\Psi_r = 0$ for differences $r$ present in the active set $\Delta$, while $\Psi_r \neq 0$ for differences outside $\Delta$.
4. Sequential Construction and Trapping Set Suppression: A sequential search algorithm, guided by a multi-armed bandit heuristic, selects APM parameters to satisfy commutativity constraints while avoiding short cycles (specifically 4- and 6-cycles). The author explicitly constructs a library of Elementary Trapping Sets (ETS) and selects parameters to minimize harmful trapping structures that cause BP decoding stalls.

Key Contributions

• Theoretical Framework: The paper establishes a theoretical mechanism to prevent distance degradation caused by row deletion. It proves that if the latent part is not orthogonal to the active part, the latent rows do not trivially become logical operators.
• Girth Improvement: The work demonstrates that by using APMs and relaxing parent-matrix orthogonality, it is possible to construct regular quantum LDPC codes with girth 8, surpassing the girth-6 limit often associated with regular quantum CPM-LDPC codes with column weight $\ge 3$.
• Explicit Construction: The author provides a concrete construction of a $(3, 12)$-regular quantum LDPC code with parameters $[[9216, 4612, \le 48]]$.
  • Block length $n = 9216$.
  • Number of logical qubits $k = 4612$ (rate $\approx 0.5$).
  • Girth $g = 8$.
  • Latent-based distance bounds $d^{(lat)}_X = d^{(lat)}_Z = 48$.
• Decoding Strategy: The paper implements a joint BP decoder for the depolarizing channel (treating $X$ and $Z$ errors as correlated) combined with a low-complexity post-processing algorithm. This post-processing utilizes an ETS library, Flip-History Decoding (FHD), and Ordered Statistics Decoding (OSD) to resolve BP stalls.

Results

• Performance: Under BP decoding with post-processing, the constructed code achieves a Frame Error Rate (FER) of $10^{-8}$ on the depolarizing channel with an error probability of $4\%$.
• Distance Analysis: The author rigorously proves that the latent-based distance is exactly 48. While they cannot provide a certified lower bound for non-latent logical operators, they report that no low-weight non-latent logical operators were found in their searches. The minimum distance is thus bounded above by 48 ($d_{min} \le 48$).
• Threshold Behavior: Density evolution analysis suggests the code approaches a BP threshold of $p \approx 0.05702$ for a non-orthogonal random ensemble, indicating the construction retains sufficient randomness for effective decoding.
• Error Floor: The error floor is dominated by stalls caused by trapping sets of size on the order of tens, rather than low-weight logical operators, suggesting the design successfully mitigated the specific distance-degradation mechanism associated with row deletion.

Significance and Claims
The paper claims to overcome a fundamental structural limitation in quantum LDPC code design: the trade-off between regularity, high girth, and large minimum distance imposed by the CSS orthogonality constraint. By localizing the commutativity constraints to the active part of the code and using APMs to break parent orthogonality, the author demonstrates that it is possible to construct regular quantum LDPC codes with girth 8 and a minimum distance that is not trivially upper-bounded by the row weight.

The significance lies in providing a construction principle that preserves classical LDPC structural advantages (regularity, large girth) while adapting them for quantum error correction. The author modestly notes that while the latent distance is certified, the exact minimum distance of the full code remains an open lower-bound problem, and the reported performance relies on the specific instance selection and post-processing. However, the results suggest that the proposed method effectively suppresses the low-weight logical operators typically induced by row deletion, offering a viable path toward high-performance, regular quantum LDPC codes.