⚛️ quantum physics

SDP bounds on quantum codes: rational certificates

This paper provides rigorous rational infeasibility certificates for semidefinite programming bounds on quantum codes, successfully improving 18 existing upper bounds on the maximum size of $n$ -qubit codes for $6 \leq n \leq 19$ by overcoming numerical precision limitations.

Original authors: Gerard Anglès Munné, Felix Huber

Published 2026-03-23

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Gerard Anglès Munné, Felix Huber

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 quantum vault. This vault is designed to store precious information (quantum bits, or qubits) in a way that protects it from the "noise" of the outside world, like static on a radio or a shaky hand.

The big question in this field is: How big can this vault be?

You have a fixed amount of space (the number of qubits, $n$ ) and a required level of security (the distance, $\delta$ , which determines how many errors the vault can survive). The goal is to fit as many distinct "keys" (the code size, $K$ ) into this vault as possible without it becoming insecure.

For decades, mathematicians have tried to answer: "What is the absolute maximum number of keys we can fit?"

The Problem: The "Fuzzy" Calculator

To find the answer, researchers use powerful mathematical tools called Linear Programming (LP) and Semidefinite Programming (SDP). Think of these as super-advanced calculators that try to squeeze the maximum number of items into a box.

However, there's a catch. These calculators use floating-point arithmetic.

The Analogy: Imagine trying to measure a perfect circle using a ruler that only has millimeter marks. You get a very close number, but it's not exact.
The Consequence: In the world of quantum codes, a tiny rounding error in the calculator can make a "No" look like a "Maybe," or a "Maybe" look like a "No." If the calculator says "You can't fit 100 keys," but it's actually just a rounding error, you might miss a brilliant new code. Conversely, if it says "You can fit 100," but it's a glitch, you might waste years trying to build a vault that is mathematically impossible.

Until now, the best results were "numerical guesses"—very likely correct, but not proven.

The Solution: The "Rational Certificate"

This paper introduces a way to turn those fuzzy guesses into rigorous, unbreakable proofs.

The authors, Gerard Anglès Munné and Felix Huber, used a clever trick involving Rational Certificates.

The Analogy: Imagine you are a detective trying to prove a suspect is guilty. The witness (the calculator) says, "I think I saw him, but my eyes are blurry."
The Trick: Instead of trusting the blurry eyes, the authors use a "Clustered Low-Rank Solver." This is a special tool that takes the blurry, approximate answer and rounds it to an exact, perfect fraction (like turning 3.14159... into a precise algebraic number).
The Result: They produce a "certificate." This is a mathematical document that says, "We have proven, with 100% certainty, that it is impossible to fit more than $X$ keys in this vault." If the certificate exists, the code cannot exist.

What Did They Find?

Using this new "exact proof" method, they looked at quantum vaults ranging from 6 to 19 qubits in size.

They Fixed Old Mistakes: They took 18 previous "best guesses" about the maximum size of these codes and turned them into proven facts. They confirmed that certain codes simply cannot exist.
They Shrank the Limits: For many of these codes, they didn't just confirm the old limits; they tightened them. They proved that the vaults are actually smaller than we thought. For example, they showed that for a 19-qubit vault with a certain security level, you can't fit as many keys as previously hoped.
They Solved Specific Mysteries: They provided exact proofs for codes like the 8-qubit vault with 9 keys, proving it's impossible, whereas before it was just a strong suspicion.

Why Does This Matter?

In the race to build a real quantum computer, we need to know exactly what is possible and what is impossible.

If we think a code exists when it doesn't, we waste time and money trying to build it.
If we think a code doesn't exist when it actually does, we might miss a breakthrough.

This paper is like upgrading from a "best guess" map to a GPS with perfect satellite accuracy. It tells engineers, "Stop looking here; the treasure isn't here. But look over there; the limit is exactly this."

The Bottom Line

The authors took a messy, approximate method for finding the limits of quantum codes and cleaned it up until it became a mathematical proof. They didn't just find new codes; they drew a sharper, more accurate line in the sand, telling us exactly where the quantum world stops and the impossible begins.

1. Problem Statement

The central problem in quantum coding theory addressed in this work is determining the maximum size ( $K$ ) of a quantum error-correcting code given a specific block length ( $n$ ) and distance ( $\delta$ ). This is denoted as finding the existence of a $((n, K, \delta))_2$ code.

Context: While Linear Programming (LP) bounds (based on the quantum MacWilliams identity) have long provided upper bounds on code sizes, they are often loose.
The Gap: A recent advancement introduced Semidefinite Programming (SDP) bounds, which are strictly stronger than LP bounds. However, these SDP methods rely on floating-point arithmetic. Consequently, the resulting "infeasibility certificates" (proofs that a code of a certain size cannot exist) are numerical approximations. Due to floating-point errors, these approximations cannot serve as rigorous mathematical proofs of non-existence, leaving the bounds formally unproven.

2. Methodology

The authors propose a method to convert numerical SDP solutions into rigorous, rational infeasibility certificates.

A. Theoretical Framework

The work builds upon the SDP formulation introduced in a previous study (MNH25), which characterizes quantum codes using a moment matrix $\Gamma(\varrho)$ derived from the code projector.

Knill-Laflamme Conditions: The existence of a code is linked to the feasibility of a system of linear and semidefinite constraints on the matrix $\Gamma$ .
Symmetry Reduction: To make the SDP computationally tractable for $n \le 19$ , the authors utilize the non-binary Terwilliger algebra. This reduces the number of variables from $O(n^4)$ (in the full matrix formulation) to a manageable size by averaging over Pauli strings of constant weight and support, resulting in "matrix weights" $\lambda_{i,j}^{t,p}$ .

B. The Rational Certificate Pipeline

The core innovation lies in the post-processing of the numerical solution:

Low-Rank Solver: They employ a specialized high-precision primal-dual interior-point solver (the Clustered Low-Rank Solver by Leijenhorst et al.). This solver exploits the low-rank structure of the solution and the clustering of constraints to find an approximate numerical solution.
Heuristic Rounding: The approximate numerical solution is rounded to exact values in the field of algebraic numbers.
Verification: To prove infeasibility rigorously, the authors verify the positive semidefiniteness of the dual solution matrices. Instead of relying on floating-point eigenvalues, they perform an $LDL^T$ decomposition over algebraic extensions (specifically $\mathbb{Q}(\sqrt{3})$ $Q (3)$ ).
- They check the non-negativity of the diagonal entries of $D$ by bounding the irrational components (e.g., $\sqrt{3}$ ) with rational numbers ( $r_\ell < \sqrt{3} < r_u$ ).
- If the decomposition holds with non-negative diagonals under these rational bounds, the infeasibility is mathematically proven.

C. Variants of the SDP

The authors solve the dual of four specific SDP variants to cover different code types:

General Codes: Standard symmetry-reduced SDP.
Pure Codes: Additional constraints forcing detectable errors to be orthogonal to the code space.
Self-Dual Codes: A relaxation based on the Lovász theta number, specifically for $K=1$ .
Additive (Stabilizer) Codes: Constraints enforcing integer weights and specific parity conditions.

3. Key Contributions

Rigorous Proofs: The paper provides the first exact, rational infeasibility certificates for quantum code bounds derived from SDP. This transforms numerical evidence into formal mathematical proofs.
Improved Bounds: The method successfully improves upon 18 existing upper bounds for the maximum size of $n$ -qubit codes where $6 \le n \le 19$ .
Scalability Demonstration: The work demonstrates that SDP, when combined with symmetry reduction and rational rounding, is a practical and scalable tool for quantum coding theory, overcoming previous limitations regarding numerical precision.
Open Data: All certificates and code are made publicly available, allowing for independent verification.

4. Results

The authors present a comprehensive table of bounds for non-additive quantum codes. Key findings include:

Exact Certificates for Known Cases: They provide exact proofs for the non-existence of codes previously shown only numerically, such as $((8, 9, 3))_2$ , $((10, 5, 4))_2$ , and $((7, 1, 4))_2$ .
New Upper Bounds:
- For $n=14, \delta=3$ , the bound is tightened from 295 to 290 (for pure codes).
- For $n=17, \delta=5$ , the bound is tightened to 59 (previously 64), proving that a stabilizer code $[[17, 6, 5]]_2$ does not exist.
- For $n=19, \delta=5$ , the bound is tightened to 249, proving the non-existence of a non-additive code $((19, 28, 5))_2$ (and by extension, the stabilizer code $[[19, 28, 5]]_2$ ).
Impurity Constraints: The results confirm that certain codes, such as $((6, 2, 3))_2$ , must be impure (i.e., they cannot satisfy the stricter pure code conditions), extending previous analytical results.
Comparison: The SDP bounds consistently outperform standard Linear Programming bounds, particularly for higher distances and larger $n$ .

5. Significance

This paper bridges the gap between numerical optimization and rigorous mathematical proof in quantum information theory.

Reliability: By eliminating floating-point ambiguity, the results provide a solid foundation for the design of future quantum computers, ensuring that researchers are not relying on potentially erroneous bounds.
Methodological Impact: The technique of using low-rank solvers combined with algebraic rounding and $LDL^T$ verification is applicable to other problems in semialgebraic geometry and quantum information where rigorous bounds are required.
Code Classification: The refined bounds help classify the landscape of achievable quantum codes, distinguishing clearly between additive (stabilizer) and non-additive codes, and identifying the limits of pure vs. impure codes.

In summary, the authors have successfully upgraded the state-of-the-art in quantum code bounds from "numerically likely" to "mathematically proven," providing a robust toolkit for the quantum coding community.