⚛️ quantum physics

Quantum LDPC Codes from Polynomial Minors

This paper presents a construction of quantum LDPC codes using codewords from cyclic codes and minors of a polynomial matrix, providing methods to control code dimension and yielding explicit examples with verified minimum distances, including a high-rate $[[255,80,12]]$ code.

Original authors: Vahid Nourozi, Roxana Smarandache, David G. M. Mitchell

Published 2026-10-15

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Vahid Nourozi, Roxana Smarandache, David G. M. Mitchell

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

In the quest to build a quantum computer, scientists face a fundamental problem: the information stored in these machines is incredibly fragile. Unlike a standard computer that uses bits of zero or one, a quantum computer uses quantum bits, or qubits, which can exist in multiple states at once. This delicate nature makes them prone to errors from even the slightest environmental noise. To fix this, researchers use quantum error correction, a method that spreads information across many physical qubits so that if one fails, the whole message survives. One of the most promising ways to do this is through a structure called a stabilizer code, which relies on a pair of classical error-correcting codes working together. These codes act like a set of rules that check the qubits for mistakes without destroying the quantum information they hold. The challenge has long been finding codes that are both powerful enough to catch errors and simple enough to be built into real hardware.

A team of researchers has now developed a new method to construct these essential codes using a specific mathematical tool known as polynomial minors. Imagine a grid of numbers where each entry is not just a single digit, but a short algebraic expression. The researchers took a small grid with two rows and three columns and looked at the smaller squares that could be formed inside it. By calculating the values of these smaller squares, they generated a second set of rules that perfectly complemented the first. This process ensures that the two sets of rules work together without conflicting, a requirement for the code to function. The beauty of this approach is that it allows the scientists to precisely control how much information the code can hold. By carefully choosing the algebraic expressions used to fill the grid, they can tune the system to hold more data or to be more robust against errors, depending on what is needed.

The researchers tested their method by creating thirteen distinct quantum codes, each with verified performance. One of the most significant results was a code capable of holding 80 units of information within a system of 255 physical components. This code can detect and correct errors up to a distance of 12, meaning it can handle a significant amount of noise before the information is lost. The team did not just guess that these codes would work; they mathematically proved the size of the information they could hold and exhaustively checked the smallest possible errors to confirm the code's strength. They found that by selecting specific patterns in their algebraic expressions, they could increase the amount of information the code stores without making the system too complex to manage.

A key part of their discovery involves how the information is arranged. The first set of rules, which checks for one type of error, is relatively simple and uses fewer connections between components. The second set of rules, which checks for a different type of error, is naturally more complex and involves more connections. The researchers showed that they could simplify the second set of rules by multiplying it by a specific factor, making it easier to build in a physical device without changing the code's ability to protect information. This flexibility is crucial for engineering, as it allows designers to balance the need for strong error protection with the physical limitations of building a quantum computer.

The paper also explains how to avoid common pitfalls when designing these codes. The researchers demonstrated that if the algebraic expressions are chosen poorly, the system might end up with less information than expected. However, by following a specific set of conditions regarding the remainders of their calculations, they could guarantee that the code would have the desired capacity. They provided a clear recipe for selecting these expressions to ensure the code works as intended. This work moves the field forward by offering a reliable, constructive way to generate high-performance quantum codes, providing a solid foundation for the future development of fault-tolerant quantum computers.

Technical Summary: Quantum LDPC Codes from Polynomial Minors

Problem Statement
The construction of Quantum Low-Density Parity-Check (QLDPC) codes often relies on the Calderbank-Shor-Steane (CSS) framework, which requires two classical binary linear codes, $C_X$ and $C_Z$ , satisfying the orthogonality condition $C_Z^\perp \subseteq C_X$ . While cyclic codes offer a convenient algebraic structure for generating such pairs, determining the dimension and minimum distance of the resulting quantum codes can be complex, particularly when dealing with quasi-cyclic (QC) structures. Existing algebraic constructions, such as bicycle codes, generalized bicycle codes, and lifted-product codes, utilize various polynomial and group-algebraic approaches. This paper addresses the challenge of constructing quantum codes with explicit control over dimension and verified minimum distances using polynomial matrices and their minors.

Methodology
The authors propose a construction based on a $2 \times 3$ polynomial matrix $H(x)$ over the ring $R_N = \mathbb{F}_2[x]/(x^N + 1)$ , where $N$ is the lifting factor. The construction proceeds as follows:

Matrix Formation: The entries of the matrix $H_X(x)$ are chosen as codewords from a cyclic code generated by a polynomial $g(x)$ . Specifically, the authors utilize a specialized form where the second row is determined by the first row via a shift and permutation, reducing the number of independent polynomials required.
Minor-Based Construction: The three $2 \times 2$ minors of the $2 \times 3$ matrix $H_X(x)$ are computed. These minors form the rows of a second polynomial matrix, $H_Z(x)$ .
Orthogonality: Based on Lemma 1 and Theorem 2 from prior literature, the authors demonstrate that the minors of a matrix naturally lie in the kernel of that matrix. Consequently, the construction guarantees the CSS orthogonality condition $H_X H_Z^T = 0$ , ensuring the existence of a valid quantum code $Q(C_X, C_Z)$ of length $3N$ .
Dimension Analysis: The dimension $K$ of the quantum code is derived using the Smith invariants of the polynomial matrices. The authors express $K$ in terms of the greatest common divisors (gcd) of the matrix entries and the minors with respect to $x^N + 1$ . For odd $N$ , the formula simplifies to $K = \deg(g) + 2\deg(g_1)$ , where $g$ is the gcd of the entries and $g_1$ is the gcd of the minors.
Dimension Control: To control the dimension, the authors introduce residue conditions. By selecting polynomials $a, b, c$ such that their residues modulo specific irreducible factors of $x^N + 1$ satisfy specific algebraic relations (e.g., forming a rank-1 matrix modulo a factor), additional common factors can be introduced into the minors, thereby increasing the code dimension without altering the code length.
Generator Modification: The paper provides a condition (Proposition 7) for multiplying the minor vector by a polynomial $q$ to change the generator weights of $H_Z$ without altering the code space or its dimension, provided $\gcd(q, (x^N+1)/g_1) = 1$ .

Key Contributions

Explicit Construction: A systematic method to generate CSS quantum codes from a $2 \times 3$ polynomial matrix where the $Z$ -stabilizers are derived directly from the minors of the $X$ -stabilizer matrix.
Dimension Formula: A simplified formula for the code dimension for odd lifting factors $N$ , expressed explicitly through the degrees of the gcds of the entries and minors.
Residue Characterization: A characterization of how polynomial residues modulo irreducible factors of $x^N + 1$ influence the gcd of the minors, offering a method to engineer the code dimension by selecting specific polynomial residues.
Weight Management: A technique using multipliers to reduce the row weights of the $H_Z$ matrix while preserving the code properties.

Results
The authors present explicit polynomial constructions yielding 13 quantum codes with verified minimum distances. Notable results include:

A [[255, 80, 12]] code with a rate of approximately 0.3137. The minimum distance $d=12$ was established through explicit logical operators and exhaustive enumeration.
A [[189, 58, 10]] code.
A [[153, 51, 8]] code with a rate of exactly 1/3.
Various other codes with lengths ranging from 27 to 255 qubits.

For the [[255, 80, 12]] code, the authors verified that the $X$ -distance is 12 and the $Z$ -distance is at least 12 (with an upper bound of 20). The construction utilized polynomials with low weights for $H_X$ (weight 22) and higher weights for $H_Z$ (weight 61) using the identity multiplier ( $q=1$ ). The paper notes that while multipliers can be used to reduce these weights, the specific example presented did not employ such optimization.

Significance
The paper claims that this construction provides a direct algebraic link between the minors of a polynomial matrix and the orthogonality required for CSS codes. The primary significance lies in the ability to explicitly control the code dimension through polynomial selection and residue conditions, rather than relying on random or heuristic searches. Furthermore, the authors emphasize that the minimum distances for the presented codes are verified exactly through exhaustive enumeration and logical operator analysis, a rigorous standard often difficult to achieve for large quantum codes. The work extends the family of known algebraic QLDPC constructions, offering specific parameters that may be useful for practical implementations, though the authors note that decoding performance and codes with low weights in both $H_X$ and $H_Z$ remain topics for future work.

More like this