⚛️ quantum physics

Quantum Error Correction with Girth-16 Non-Binary LDPC Codes via Affine Permutation Construction

This paper proposes a method for constructing non-binary LDPC quantum error-correcting codes with girth 16 using affine permutation matrices and randomized sequential selection, which significantly improves error floor performance and minimum distance bounds compared to conventional girth-12 constructions.

Original authors: Kenta Kasai

Published 2026-08-17

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Kenta Kasai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers don't just calculate numbers but manipulate the very fabric of reality, using particles that can be in two places at once. This is the realm of quantum computing, a technology promising to solve problems that would take today's supercomputers thousands of years to crack. However, these magical machines are incredibly fragile. Like a house of cards in a hurricane, the slightest whisper of noise or a tiny temperature change can cause their calculations to collapse into gibberish. To keep these quantum systems standing, scientists need a way to protect them, much like a body's immune system fights off viruses. This protection is called Quantum Error Correction.

The paper you are about to explore tackles a specific, tricky part of this immune system. It focuses on a method called "Low-Density Parity-Check" (LDPC) codes, which act as a sophisticated net designed to catch errors before they destroy the data. Think of this net as a giant puzzle made of interlocking pieces. If the pieces fit together perfectly in a specific pattern, the net is strong. But if the pattern has small, tight loops, the net develops weak spots where errors can hide and multiply. For years, the best-known designs for these nets had a limit: the smallest loops they could avoid were a certain size, leaving the system vulnerable to a specific type of failure known as an "error floor," where the computer stops getting better no matter how much you try to fix it. This research asks a bold question: Can we redesign the puzzle pieces to eliminate those tiny, dangerous loops entirely, making the net stronger and more reliable?

The Puzzle of the Perfect Net

In the world of quantum computing, data is stored in "logical qubits," which are built from thousands of noisy physical qubits. To keep this data safe, researchers use mathematical structures called Tanner graphs. You can picture a Tanner graph as a map of a city where intersections represent data bits and roads represent the rules that check if those bits are correct. The "girth" of this graph is simply the length of the shortest loop you can drive around without retracing your steps.

Why does the size of the loop matter? Imagine driving through a city with very short, tight blocks. If you make a wrong turn, you might get stuck in a tiny circle, confusing your GPS (the decoder) and making it impossible to figure out where you actually are. In quantum terms, these short loops create "low-weight codewords"—essentially, tiny, hidden patterns of errors that the computer's error-checking system fails to notice. If the loops are too short, the system hits a "wall" in performance called an error floor, where it can't correct errors any better, no matter how much noise is reduced.

For a long time, the standard way to build these quantum nets relied on Circulant Permutation Matrices (CPMs). Think of these as puzzle pieces that are all just rotated versions of the same shape. While easy to manufacture, these pieces have a geometric flaw: they inevitably create loops that are too short. Specifically, previous research showed that using these standard pieces, the shortest possible loop (the girth) could never be larger than 12. It was like trying to build a city with only square blocks; you just couldn't avoid those tight, confusing corners.

The New Construction: Breaking the Loop

In this paper, Kenta Kasai from the Institute of Science Tokyo proposes a clever new way to build these quantum nets. Instead of using the rigid, rotated square blocks (CPMs), the author introduces Affine Permutation Matrices (APMs). If CPMs are like simple sliding tiles, APMs are like tiles that can also be stretched, skewed, or twisted in more complex ways. This extra flexibility allows the designer to arrange the pieces so that the tight, short loops simply cannot form.

However, simply having flexible pieces isn't enough. The pieces must still fit together to form a valid quantum code, which requires a strict mathematical handshake called orthogonality. If the pieces don't handshake correctly, the whole code falls apart. The author uses a "randomized sequential selection" method to find the perfect arrangement. Imagine a game where you try to place one puzzle piece at a time. After placing each piece, you check: "Does this create a short loop? Does it break the handshake rule?" If the answer is "yes" to either, you throw the piece back and try a different one. You keep doing this until you have a full, valid net with no short loops.

The paper focuses on a specific target: creating a net with a girth of 16. This means the shortest loop in the new design is 16 steps long, significantly longer than the previous limit of 12. The author successfully constructed these codes using a specific set of parameters: a block size of $P = 12600$ , with sequences of 8 permutations ( $L=8$ ).

What the Experiments Showed

To see if this new design actually works, the author ran massive computer simulations. They tested the new "Girth-16" codes against the old "Girth-12" codes over a noisy channel, using a decoding method called joint belief propagation. This is like sending a message through a storm and seeing how well the receiver can reconstruct the original text.

The results revealed a classic trade-off in engineering, but with a very promising twist:

The Waterfall Region: In the beginning of the test, when the noise is moderate, the new Girth-16 codes performed slightly worse than the old ones. It's as if the new, more complex city map took a tiny bit longer for the GPS to figure out the route at first.
The Error Floor: This is where the magic happens. As the noise increased, the old codes hit a hard wall. They stopped improving around a Frame Error Rate of $10^{-4}$ (meaning 1 error in every 10,000 attempts). The new Girth-16 codes, however, kept getting better and better, showing no noticeable error floor even down to $10^{-6}$ (1 error in every 1,000,000 attempts).

The author also looked at the "minimum distance" of the codes, which is a measure of how many errors the code can theoretically fix. By analyzing the shortest loops (length 16) in the new design, they found that the proposed code has an upper bound on its minimum distance of 14, compared to 9 for the conventional code. This suggests the new net is not just avoiding loops; it is fundamentally stronger and capable of catching much more complex errors.

The Verdict

This paper doesn't claim to have solved quantum error correction forever, but it offers a significant leap forward. By swapping rigid, rotated puzzle pieces for flexible, affine ones and using a smart, random search to assemble them, the author has demonstrated a way to push the girth of quantum LDPC codes from 12 to 16.

The findings suggest that while these new codes might take a tiny bit longer to decode in the early stages, they are vastly superior at preventing the system from getting stuck in an error floor. The simulations indicate that these codes significantly reduce the number of dangerous, low-weight errors that plague older designs. For anyone hoping to build a large-scale, reliable quantum computer, this method offers a promising blueprint for building a stronger, more resilient shield against the chaos of the quantum world.

Technical Summary: Quantum Error Correction with Girth-16 Non-Binary LDPC Codes via Affine Permutation Construction

Problem Statement
Recent advancements in quantum computing have enabled systems with tens of reliable logical qubits, yet scaling to thousands remains a critical challenge requiring highly efficient Quantum Error Correction (QEC). While non-binary Low-Density Parity-Check (LDPC) codes based on Calderbank–Shor–Steane (CSS) constructions offer a promising approach, conventional methods utilizing Circulant Permutation Matrices (CPMs) face inherent structural limitations. Specifically, CPM-based constructions restrict the Tanner graph girth to a maximum of 12 and impose strict constraints on submatrix sizes, limiting design flexibility. Although previous extensions using general permutation matrices improved performance, the specific challenge of constructing codes with a girth of 16—a length sufficient to eliminate short cycles that degrade decoding performance—remained unaddressed within the framework of structured quantum LDPC codes.

Methodology
The author proposes a novel construction method for quantum LDPC codes that achieves a Tanner graph girth of 16 by replacing CPMs with Affine Permutation Matrices (APMs) and employing a randomized sequential selection procedure.

Algebraic Framework: The construction utilizes the Komoto–Kasai framework for CSS codes, which defines parity-check matrices $\hat{H}_X$ and $\hat{H}_Z$ from two sequences of permutations, $f$ and $g$ . To ensure the orthogonality condition ( $\hat{H}_X \hat{H}_Z^T = 0$ ) required for CSS codes, the permutations must satisfy specific commutativity conditions between $f$ and $g$ blocks.
Girth Constraints: The paper identifies that any parity-check matrix containing a $QP$-valued (Circulant) $2 \times 3$ subarray is limited to a girth of at most 12 due to the existence of totally closed block cycles. To overcome this, the proposed method utilizes the broader set of Affine Permutations ($AP$), where $f(j) = aj + b \mod P$ with $\gcd(a, P) = 1$ .
Randomized Sequential Construction: The core innovation is Algorithm 1, a sequential randomized algorithm. It iteratively selects affine permutations for the sequences $f$ $f$ and $g$ $g$ one by one. At each step, a candidate is generated and tested against three criteria:
- (a) Commutativity between the current $f_i$ and $g_j$ pairs to satisfy the orthogonality requirement.
- (b) Non-commutativity among elements within the $f$ sequence and within the $g$ sequence to prevent the formation of $2 \times 3$ totally closed block cycles.
- (c) The absence of any closed block cycles of length up to 12 in the resulting partial matrices.
  Candidates violating these constraints are rejected, and the process repeats until valid sequences of length $L/2$ (where $L=8$ ) are constructed.

Key Contributions

Girth-16 Construction: The paper presents a construction of structured quantum LDPC codes with a Tanner graph girth of 16, extending beyond the theoretical limit of 12 imposed by CPM-based designs.
Affine Permutation Flexibility: By leveraging the full flexibility of APMs rather than the restricted set of CPMs, the method successfully eliminates short cycles that typically lead to error floors.
Algorithmic Approach: The introduction of a randomized sequential selection process allows for the discovery of permutation sequences that satisfy the complex interplay of orthogonality and girth constraints, which would be difficult to achieve through deterministic algebraic methods alone.

Numerical Results
The author evaluated the proposed codes (parameters $J=2, L=8, P=12600$ ) against conventional girth-12 codes using joint belief propagation decoding over depolarizing channels.

Error Floor Performance: The proposed codes demonstrated a substantial improvement in the error floor region. While conventional codes exhibited an observable error floor around a frame error rate (FER) of $10^{-4}$ , the proposed codes showed no noticeable error floor down to at least $10^{-6}$ .
Waterfall Region: A slight degradation in performance was observed in the waterfall region compared to conventional designs. The authors attribute this to a known trade-off in LDPC code design, where algebraically constructed codes often favor error floor performance at the expense of the waterfall region, whereas random constructions favor the waterfall region.
Minimum Distance: The study enumerated codewords formed by the shortest cycles (length 16). The results indicated an upper bound on the minimum bitwise distance of 14 for the proposed code, compared to 9 for the conventional code. The author notes that while this is an upper bound, the use of a large finite field size ( $q=2^8$ ) suggests the bound is likely tight.
Low-Weight Codewords: The proposed construction significantly reduced the number of low-weight codewords, which is the primary driver for the improved error floor performance.

Significance and Claims
The paper claims that the proposed method effectively mitigates short cycles in quantum LDPC codes, leading to a significant reduction in low-weight codewords and a substantial improvement in error floor performance. The author posits that the combination of Affine Permutation Matrices and randomized construction is an effective strategy for enhancing the reliability of quantum error correction, particularly for large-scale systems where error floors are a limiting factor. The work suggests that while a minor trade-off exists in the waterfall region, the gains in the error floor regime and the increased minimum distance upper bound represent a meaningful advancement over conventional girth-12 constructions. Future work is identified as extending the construction to larger $L$ , applying spatial coupling, and developing analytical methods to predict error floor behavior.

The Puzzle of the Perfect Net

The New Construction: Breaking the Loop

What the Experiments Showed

The Verdict

More like this