High-Girth Regular Quantum LDPC Codes from Square-Base Hypergraph Products via CPM Lifts

This paper introduces a class of square-base hypergraph product codes that achieve high girth and regularity, demonstrating through a specific CPM-lifted instance that such codes can exhibit exceptional error-correction performance under depolarizing noise.

The Gist

Imagine you are trying to build a super-strong, self-repairing digital vault. This vault needs to store secret information (quantum data) that is incredibly fragile and easily corrupted by noise, like a whisper in a hurricane. To protect it, you need a "net" made of mathematical rules that can catch errors before they destroy the data. This is what Quantum LDPC codes are: a sophisticated net designed to catch digital noise.

This paper is about designing a specific, very strong type of net using a clever construction method called the Square-Base Hypergraph Product. Here is the breakdown in everyday language:

1. The Blueprint: The "Base Matrix"

Think of the code as a massive building. Instead of designing the whole skyscraper from scratch, the authors start with a small, perfect blueprint (called the Base Matrix).

• The Grid: This blueprint is a square grid of 1s and 0s.
• The Rules: The authors found specific rules for this grid:
  • Every row and column must have the same number of 1s (like every room in a hotel having the same number of windows).
  • The grid must avoid certain "short loops." Imagine walking through the building; you don't want to take a shortcut that brings you back to where you started too quickly, because those shortcuts create weak spots where errors can hide.
  • The grid must have a specific "hidden depth" (mathematically called corank) that allows the vault to actually store data.

2. The Expansion: The "CPM Lift" (The Photocopier)

Once they have the perfect small blueprint, they use a mathematical "photocopier" called a CPM Lift to expand it into a massive code.

• The Process: They take every single "1" in the small blueprint and replace it with a whole new, larger pattern of 1s and 0s.
• The Result: This turns a tiny 15x15 grid into a giant 28,800-bit code. It's like taking a small, intricate tile pattern and tiling an entire stadium floor with it, ensuring the pattern fits perfectly everywhere.

3. The "Unavoidable Loop" Problem

Here is the tricky part. The authors discovered a mathematical law: because of the way these quantum codes must be built to work (a rule called CSS orthogonality), there are certain "loops" in the net that cannot be removed.

• The Metaphor: Imagine you are building a fence. You want the fence to have no small holes. However, the laws of physics (in this case, quantum math) force you to have a specific type of 8-step loop in the fence design. You can't make the loops bigger than 8 steps; you just have to accept that 8 is the best you can do.
• The Finding: The authors proved that for their specific design, the "shortest loop" in the net is exactly 8 steps. They showed that no matter how you tweak the photocopier settings, you can't get rid of these 8-step loops.

4. The Test: The "Hurricane Simulation"

To see if their code actually works, they put it through a massive stress test.

• The Setup: They simulated a "hurricane" of digital noise (called a depolarizing channel) hitting their code.
• The Decoder: They used a smart detective (a Belief Propagation decoder) to try and find the errors. If the detective got stuck, they used a "Lite" repair tool (OSD-lite) to fix the remaining mess.
• The Result: They ran this simulation 299 million times (that's nearly 300 million trials!).
• The Score: At a very high noise level (14% error rate), the code never failed to recover the data. In fact, the statistical chance of it failing is less than 1 in 100 million.

5. The Trade-off

The paper notes a specific trade-off:

• The "Design" Rate: If you look at the math on paper, the code looks like it stores zero data (a rate of 0).
• The "Real" Rate: However, because of the "hidden depth" (corank) in the blueprint, the code actually does store data (62 bits in their biggest example).
• The Analogy: It's like a building that looks empty from the outside, but because of clever internal architecture, it actually has 62 secret rooms.

Summary

The authors built a new type of quantum error-correcting code by:

1. Designing a small, perfect square grid.
2. Expanding it into a giant code using a mathematical photocopier.
3. Proving that while some small loops (8 steps) are unavoidable, the code is still incredibly strong.
4. Testing it against massive noise and showing it works flawlessly in over 299 million trials.

They didn't invent a new way to use quantum computers yet; they just built a much better "safety net" for the data inside them.

Technical Summary

1. Problem Statement

The paper addresses the challenge of designing finite-length, regular, high-girth Quantum Low-Density Parity-Check (QLDPC) codes within the Calderbank–Shor–Steane (CSS) framework.

• Constraints: CSS codes require two classical parity-check matrices ($H_X$ and $H_Z$) that must commute ($H_X H_Z^T = 0$). This orthogonality constraint limits the ability to independently optimize row and column degrees (regularity) and girth (short-cycle exclusion) compared to classical irregular LDPC codes.
• The Gap: While Hypergraph Product (HGP) codes provide a systematic way to generate QLDPCs with positive asymptotic rates, finite-length constructions often suffer from:
  1. Low Girth: Short cycles (4-cycles, 6-cycles) degrade the performance of Belief Propagation (BP) decoders.
  2. Zero Design Rate: Standard square-base HGP constructions often have a design rate of zero, relying on rank deficiencies to produce logical qubits.
  3. Orthogonality-Forced Cycles: It is unclear how the CSS orthogonality constraint interacts with Circulant Permutation Matrix (CPM) lifts to force specific cycle lengths, potentially capping the achievable girth.

2. Methodology

The authors propose a construction strategy based on Square-Base Hypergraph Products combined with CPM Lifts.

A. Square-Base HGP Construction

Instead of arbitrary classical codes, the authors restrict the input to a square binary base matrix $B \in \mathbb{F}_2^{s \times s}$.

• Construction: The CSS check matrices are defined as:
  $$H_X(B) = [B \otimes I_s \mid I_s \otimes B^T], \quad H_Z(B) = [I_s \otimes B \mid B^T \otimes I_s]$$
• Regularity: Theorem 2 proves that if $B$ is a $w$-regular matrix (all rows and columns have weight $w$), the resulting quantum code is $(w, 2w)$-regular.
• Logical Qubits: The number of logical qubits $k$ is determined by the corank ($c_B$) of the base matrix: $k = 2c_B^2$. The design rate is technically zero ($n = m_X + m_Z$), but the actual rate is positive due to rank deficiency.

B. Short-Cycle Analysis and CPM Lifts

The authors analyze how CPM lifts (replacing 1s with $P \times P$ circulant permutation matrices) affect the Tanner graph girth.

• Base Girth: They establish that if the base matrix $B$ has no 4-cycles or simple 6-cycles, the base HGP code inherits this property.
• Orthogonality-Forced 8-Cycles: A key theoretical contribution is Lemma 4 and Theorem 5, which prove that specific local patterns in the base matrix (arising from CSS orthogonality) force Tanner 8-cycles to exist in every CPM lift, regardless of the shift values chosen.
  • Implication: For these specific square-base constructions, the Tanner girth cannot exceed 8. Increasing the lift size $P$ cannot eliminate these 8-cycles.
• Rank Preservation: Theorem 7 provides a lower bound for the number of logical qubits after lifting, showing that $\hat{k} \geq k$ (the base value), ensuring that lifting does not destroy the logical space.

C. Base Matrix Design

The authors design specific base matrices $B$ to satisfy:

1. Regularity: Fixed column weight $w$ (tested for $w=3$ and $w=4$).
2. Girth: Exclusion of 4-cycles and 6-cycles (except for the Fano plane example which allows 6-cycles).
3. Corank: Maximizing the corank $c_B$ to increase the number of logical qubits.
4. Connectivity: Ensuring the base Tanner graph is connected to avoid trivial code duplication.

They utilize finite geometry structures (Fano plane, Generalized Quadrangles $W(2), W(3)$) and combinatorial modifications (edge-switching, randomized local search) to generate these matrices.

3. Key Contributions

1. Theoretical Limit on Girth: The paper rigorously proves that for square-base HGP codes, CSS orthogonality forces Tanner 8-cycles in any CPM lift. Consequently, the maximum achievable girth for this specific family is 8, and no amount of lifting can push it to 10.
2. Explicit Finite-Length Constructions: The authors provide explicit parameters for several regular codes:
   • Column Weight 3:
     • $B_7$ (Fano Plane): Girth 6, $[[98, 18, 4]]$.
     • $B_{15}$ (Generalized Quadrangle $W(2)$): Girth 8, $[[450, 50, 6]]$.
     • $B_{30}$ (Connected enlargement of $B_{15}$): Girth 8, $[[1800, 162, 6]]$.
     • $B_{17}, B_{18}$: Low-corank and randomized examples.
   • Column Weight 4:
     • $B_{13}$ (Projective Plane $PG(2,3)$): Girth 6, $[[338, 2, 13]]$.
     • $B_{40}$ (Generalized Quadrangle $W(3)$): Girth 8, $[[3200, 450, 8]]$.
3. High-Performance Decoding Results:
   • A randomized CPM lift of the $B_{15}$ base with $P=64$ was constructed, resulting in a $[[28800, 62]]$ code with girth 8.
   • Decoding Performance: Using a degeneracy-aware Belief Propagation (BP) decoder followed by Ordered Statistics Decoding-lite (OSD-lite) post-processing, the code achieved zero decoding failures in $2.993 \times 10^8$ trials at a depolarizing error probability of $p = 0.1402$.
   • The 95% Wilson upper confidence bound for the failure rate at this point is $1.28 \times 10^{-8}$.

4. Results Summary

Base Matrix	Source	Weight	Girth	Base Params ($n, k, d$)	Lifted Example ($P=64$)
$B_7$	Fano Plane	(3,6)	6	$[[98, 18, 4]]$	N/A
$B_{15}$	$W(2)$	(3,6)	8	$[[450, 50, 6]]$	$[[28800, 62]]$ (Girth 8)
$B_{30}$	Edge-switched	(3,6)	8	$[[1800, 162, 6]]$	N/A
$B_{40}$	$W(3)$	(4,8)	8	$[[3200, 450, 8]]$	N/A

• Performance: The $[[28800, 62]]$ code operates very close to the theoretical BP density-evolution threshold ($p_{DE} \approx 0.1529$) for the (3,6) ensemble, demonstrating that high-girth regular codes can achieve excellent finite-length performance despite the "zero design rate" constraint.
• Degeneracy: The results highlight the importance of degenerate decoding (accepting errors that differ by stabilizers). The dominant success mode was degenerate success, not exact error correction.

5. Significance and Limitations

Significance:

• Design Framework: Provides a clear, checkable set of conditions for designing regular QLDPC codes with high girth, moving away from purely random search to structured finite-geometric designs.
• Girth Limitation Clarification: Resolves the question of whether CPM lifts can arbitrarily increase girth for square-base HGP codes, proving that girth 8 is a hard ceiling due to orthogonality constraints.
• Practical Performance: Demonstrates that codes with design rate zero (but positive actual rate via corank) can still be highly effective for finite-length applications, outperforming many previous constructions in terms of failure rates at high noise levels.

Limitations:

• Distance Certification: The paper notes that while decoding failures were zero at $p=0.1402$, the failures observed at higher noise levels were syndrome-mismatch failures, not logical errors. Thus, the minimum distance of the lifted codes is not rigorously certified (only lower-bounded by the base distance).
• Girth Cap: The inability to achieve girth $>8$ for this specific family limits the potential for further performance gains via girth optimization alone.
• Connectedness: While the authors ensure connectedness, the mechanism for increasing logical qubits ($\hat{k} > k$) in connected lifts remains an open challenge, as it requires non-trivial rank deficiency not inherited from the base.

In conclusion, this work establishes a robust theoretical and practical framework for constructing high-girth, regular quantum LDPC codes, proving that finite-geometric base matrices combined with CPM lifts can yield codes with exceptional finite-length performance, even under the strict constraints of CSS orthogonality.