⚛️ quantum physics

Pair-Partition Constructions for CPM-Based Quantum LDPC Codes

This paper introduces a construction of binary CSS quantum LDPC codes from circulant permutation matrices using pair partitions to satisfy orthogonality constraints, yielding specific high-rate, girth-six codes with verified distances through exhaustive low-weight exclusion and explicit witnesses.

Original authors: Koki Okada, Kenta Kasai

Published 2026-07-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Koki Okada, 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 you are trying to build a fortress to protect a secret message, but this fortress has a very strange rule: it must be made of a material that is both incredibly strong and incredibly light, like a dragon's scale that weighs less than a feather. This is the world of quantum computing, where scientists are trying to build "quantum computers" that can solve problems impossible for our current machines. However, these machines are incredibly fragile; a tiny whisper of noise can scramble the information, turning a brilliant calculation into gibberish. To fix this, engineers use "error-correcting codes," which are like a magical safety net that catches mistakes before they destroy the data. The challenge is that the net needs to be dense enough to catch every error, but sparse enough that the computer doesn't get overwhelmed trying to check it. This paper dives into a specific, clever way of weaving these nets using a mathematical tool called "circulant permutation matrices," which are essentially patterns that repeat in a circle, like a kaleidoscope.

The authors, Koki Okada and Kenta Kasai, have discovered a new recipe for building these quantum safety nets. They call their method "Pair-Partition Constructions." To understand their trick, imagine you are organizing a massive dance party with thousands of guests. You need to pair everyone up so that no two couples accidentally bump into each other (which would cause a "short cycle" or a mistake in the code), and you need to make sure that if one person makes a move, their partner makes a matching move to keep the music in sync (this is the "CSS orthogonality" condition). The authors realized that if you arrange the dancers into specific "pair partitions"—groups where everyone is matched up in a very precise way—you can create a set of rules (equations) that guarantees the dance floor stays clear of collisions.

In their study, they used these rules to build twelve different "fortresses" (quantum codes) of varying sizes. They didn't just guess; they used a computer to exhaustively check every possible dance move to ensure no mistakes could slip through. They found codes that are surprisingly efficient. For example, they built a code with 944 "dancers" (qubits) that can protect 478 of them, with a safety rating (distance) of at least 20. This means the code can handle a significant amount of chaos before the message is lost. They also found smaller, highly efficient codes, like one with 276 dancers that protects 98 of them. The authors are very confident in these numbers because they didn't just simulate the dance; they mathematically proved that no "ghost" errors (vectors that look like mistakes but aren't) exist below a certain weight. While they couldn't prove the exact maximum strength for the largest code, they established a certified lower bound, meaning they know for a fact it is at least as strong as they claim.

The core of their discovery is a way to turn a complex puzzle into a simple set of instructions. By arranging the "dance partners" (the pair partitions) into a grid and solving a few linear equations, they can generate the entire structure of the code. This is a big deal because it allows them to create codes with a "girth" of six. In the language of these mathematical graphs, "girth" is the length of the shortest loop in the network. A girth of six means the shortest loop is quite long, which is crucial because short loops are like echo chambers that confuse the computer's error-checking brain. By ensuring the loops are long, the computer can "think" more clearly and correct errors more effectively.

The paper also addresses a common worry in this field: how do we know the code is actually strong? The authors didn't just rely on theory. They ran a "low-weight exclusion" search, which is like sending a team of inspectors to look for any weak spots in the wall that are smaller than a certain size. If they find nothing, they know the wall is stronger than that size. For most of their examples, they found a specific "witness"—a concrete example of a mistake that the code can catch, proving exactly how strong it is. For the largest example, they proved it is at least strong enough to catch mistakes of size 20, even if they haven't found the exact breaking point yet.

In the end, this paper is a blueprint for building better quantum safety nets. It shows that by using a specific pattern of pairings and a bit of algebra, we can construct codes that are both sparse (easy to manage) and strong (hard to break). The authors provide the exact blueprints for twelve of these structures, complete with verification data that anyone can check. They aren't claiming to have solved the entire problem of quantum error correction, but they have added a very sturdy, well-tested brick to the foundation, showing that with the right mathematical dance steps, we can build quantum computers that are much more reliable than we thought possible.

Technical Summary: Pair-Partition Constructions for CPM-Based Quantum LDPC Codes

Problem Statement
The paper addresses the construction of binary Calderbank–Shor–Steane (CSS) quantum low-density parity-check (LDPC) codes using circulant permutation matrices (CPMs). While quasi-cyclic (QC) LDPC matrices offer compact representations, ensuring the CSS orthogonality condition ( $H_X H_Z^T = 0$ ) while simultaneously avoiding short cycles (specifically 4-cycles to ensure girth $\ge 6$ ) and maximizing code distance remains a challenging design problem. Existing algebraic constructions often rely on specific structures or affine permutations; this work focuses strictly on the CPM subclass to provide explicit, high-rate examples with verified structural properties.

Methodology
The authors propose a construction parameterized by column weight $J$ , row weight $L$ , and a prime lift size $P$ . The core innovation is the use of a pair-partition array to enforce CSS orthogonality algebraically.

Pair-Partition Framework:
- A $J \times J$ array of pair partitions $(M_{ij})$ is defined, where each entry partitions the $L$ column types into $L/2$ unordered pairs.
- Mixed-Difference Equations: For every pair $(u, v) \in M_{ij}$ , a linear equation is imposed on the exponent arrays $(e_{j\ell})$ and $(d_{j\ell})$ over the finite field $\mathbb{F}_P$ :
  $d_{j,u} - e_{i,u} = d_{j,v} - e_{i,v}$
  This forces the "mixed differences" for the endpoints of each pair to be equal.
- CSS Orthogonality: Lemma 1 proves that these pairing constraints ensure $H_X H_Z^T = 0$ . The logic relies on the fact that for any block row pair, the contributions from paired column types are identical CPMs, which cancel out in $\mathbb{F}_2$ .
Structural Constraints:
- Mixed-Distinctness: To ensure that X-checks and Z-checks intersect in either zero or exactly two positions (preventing weight-1 logical operators and controlling intersections), the mixed values $\delta_{ij}(p)$ derived from the pairs must be distinct within each cell.
- Girth Constraints: Standard type-level 4-cycle tests are applied to the exponent arrays of $H_X$ and $H_Z$ separately to ensure the Tanner graph has a girth of at least six.
Search and Verification Pipeline:
- Candidate Generation: The linear system defined by the pair-partition equations is solved to find a solution space for the exponent arrays. Candidates are sampled from this space.
- Screening: Candidates are filtered based on the mixed-distinctness condition and 4-cycle tests. A "forbidden-pattern bank" is used as a heuristic prefilter to discard assignments likely to produce low-weight logical operators.
- Distance Verification: For surviving candidates, the paper employs two rigorous checks:
  - Lower Bound: An exhaustive, computer-assisted search excludes all non-stabilizer zero-syndrome vectors up to a specific weight $W$ . The search utilizes connected component decomposition and pruning based on unsatisfied check nodes.
  - Upper Bound: Explicit non-stabilizer zero-syndrome vectors (witnesses) are identified to establish the exact distance. For the largest instance, only a certified lower bound is reported.

Key Contributions

Algebraic Construction: The paper formalizes a method to convert prescribed pair partitions into a linear paired-difference system that guarantees CSS orthogonality for CPM-based codes.
Compact Search Space: By imposing the same-type 4-cycle inequalities on the solution space of the orthogonality equations, the authors define a compact search space for CPMs that can be combined with distance-guided filters.
Exact Distance Verification: Unlike many works that rely on asymptotic bounds or heuristic estimates, this paper provides exact distances for specific lifted matrices through exhaustive low-weight exclusion and explicit witness construction.
High-Rate Examples: The construction yields CSS codes where the minimum distance $d$ exceeds the row weight $L$ ( $d > L$ ), a desirable property for quantum LDPC codes.

Results
The authors report twelve specific CPM-based CSS instances with girth six, varying in column weight ( $J=3$ and $J=4$ ) and lift size ( $P$ ). Notable results include:

Column Weight 4 ( $J=4$ ):
- $[[276, 98, 14]]$ with rate 0.355.
- $[[574, 252, 18]]$ with rate 0.439.
- $[[944, 478, \ge 20]]$ with rate 0.506 (certified lower bound only).
Column Weight 3 ( $J=3$ ):
- $[[472, 122, 14]]$ and $[[488, 126, 14]]$ .
Verification: For the first eleven instances, exact distances are established by excluding non-stabilizer vectors up to $d-2$ and providing an explicit witness of weight $d$ . The final instance ( $[[944, 478, \ge 20]]$ ) is recorded with a certified lower bound of 20, as no upper-bound witness was claimed.

Significance and Claims
The paper positions itself as a structural contribution to the design of quantum LDPC codes. It explicitly states that it does not optimize decoders or propose new decoding algorithms; rather, it provides structural instances with verified parameters for use with existing decoders (such as belief propagation with ordered-statistics postprocessing).

The significance lies in the ability to generate explicit, high-rate quantum codes with large girth and verified distances using a purely algebraic CPM framework. The authors emphasize that the distance claims are separate from the algebraic construction, relying on computer-assisted exhaustive searches and explicit witnesses to validate the parameters. The work serves as a repository of concrete, verified code instances that satisfy strict structural constraints (girth 6, CSS orthogonality) and offer competitive rates and distances compared to other known constructions.

Technical Summary: Pair-Partition Constructions for CPM-Based Quantum LDPC Codes

More like this