⚛️ quantum physics

A Symplectic Proof of the Quantum Singleton Bound

This paper presents a symplectic linear-algebraic proof of the Quantum Singleton Bound for stabiliser quantum error-correcting codes, accompanied by a Lean4 formalisation that relies on distance-based erasure correctability and the cleaning lemma to derive the bound $k + 2(d-1) \le n$ without using entropy-based machinery.

Original authors: Frederick Dehmel, Shilun Li

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Frederick Dehmel, Shilun Li

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 send a precious, fragile message across a noisy, chaotic ocean. To protect your message, you don't just send it once; you wrap it in a complex, magical bubble of "quantum code." This bubble is designed so that if a few waves (errors) hit it, you can still recover the original message.

However, there's a fundamental law of the universe governing these bubbles: You can't have it all. You can't make the bubble huge (lots of data), make it incredibly tough (high error protection), and keep it small (few resources) all at the same time. This limit is called the Quantum Singleton Bound.

For a long time, proving this limit required heavy, complex mathematics involving "entropy" (a measure of disorder and information) and abstract theories about how quantum states behave. It was like trying to prove a law of physics by analyzing the weather patterns of the entire universe.

This paper offers a simpler, cleaner way to prove the same rule. The authors, Frederick Dehmel and Shilun Li, decided to look at the problem through the lens of geometry and algebra instead of thermodynamics. They used a tool called "Symplectic Linear Algebra," which is essentially a fancy way of mapping out how different parts of the quantum code interact with each other, like a map of a city's traffic flow.

Here is how they did it, using simple analogies:

1. The Map of the Code (Symplectic Vector Spaces)

Think of the quantum code not as a mysterious cloud of probability, but as a grid of switches.

Each "switch" represents a tiny piece of the code (a qudit).
The authors created a mathematical map where every possible error or piece of information is a line drawn on this grid.
In this world, two lines "commute" (get along) if they are perpendicular in a specific way. This geometric relationship is the key to understanding how the code works.

2. The "Cleaning" Trick (The Cleaning Lemma)

Imagine you have a secret message hidden in a room full of furniture.

The Rule: If a specific corner of the room is "safe" (meaning no damage can happen there that would ruin the message), then the secret message can be "cleaned" out of that corner and moved entirely to the rest of the room.
The Insight: The authors proved that if you have a safe zone, the information must be hiding in the unsafe zone. It's like saying, "If the front door is locked and secure, the thief must be in the backyard."
They showed that the "amount" of information you can hide in a safe zone plus the amount you can hide in the rest of the room always adds up to the total amount of information you started with.

3. The Two-Pronged Attack (The Proof)

Now, let's apply this to the limit.

Imagine your code has a "distance" of $d$ . This means it can survive if up to $d-1$ switches break.
The authors picked two separate groups of switches, Group A and Group B, each with exactly $d-1$ switches.
Because the code is strong enough to survive $d-1$ broken switches, both Group A and Group B are "safe zones."
The Logic:
1. Since Group A is safe, the secret message can be "cleaned" out of A and must live in the rest of the code (Group B + the rest).
2. Since Group B is also safe, the secret message can be "cleaned" out of B and must live in the rest (Group A + the rest).
3. If you combine these two facts, the secret message must be hiding in the middle section (the part that is neither A nor B).
The Result: The middle section is the only place left to hide the information. Therefore, the size of your message ( $k$ ) cannot be bigger than the size of that middle section.
Mathematically, this leads to the formula: Message Size + 2 × (Protection Level) ≤ Total Size.

Why This Matters

Simplicity: Instead of using heavy "entropy" physics, they used basic geometry (counting dimensions and spaces). It's like solving a puzzle by counting the pieces rather than weighing the box.
Trust: The authors didn't just write the proof on paper; they built a digital robot (using a tool called Lean4) to check every single step of their logic. This robot verified that there are no holes in their argument. It's like having a super-strict accountant double-check the math to ensure the bank won't go bankrupt.

The Big Picture

This paper is a victory for clarity. It shows that even the most complex rules of quantum computing can sometimes be understood through simple, elegant geometry. It proves that the "Quantum Singleton Bound" isn't just a mysterious law of nature, but a logical consequence of how information can be distributed and protected in a geometric space.

In short: You can't pack a giant suitcase into a tiny box without breaking the box, and this paper proves it using a ruler and a map instead of a weather forecast.

1. Problem Statement

The Quantum Singleton Bound is a fundamental limit in quantum error correction, stating that for any stabilizer code with parameters $[[n, k, d]]$ (where $n$ is the number of physical qubits, $k$ is the number of logical qubits, and $d$ is the code distance), the following inequality must hold:
$k + 2(d - 1) \leq n$
Codes achieving equality are known as Quantum Maximum-Distance Separable (MDS) codes.

While the bound was originally proven by Knill and Laflamme and later by Bennett et al. using information-theoretic arguments (specifically von Neumann entropy and the no-cloning theorem), these proofs rely on heavy analytic machinery. For stabilizer codes, which possess a fundamentally algebraic structure based on the Pauli group and symplectic geometry, it remained an open question whether the bound could be derived purely through linear algebra without invoking entropy or quantum channel theory. Additionally, there was a lack of machine-checked (formal) proofs for this fundamental bound in the context of quantum coding theory.

2. Methodology

The authors provide a proof entirely within the framework of finite-dimensional symplectic vector spaces. Their approach isolates the algebraic structure of stabilizer codes and avoids analytic tools. The methodology consists of three core components:

A. Symplectic Model of Stabilizer Codes

Vector Space: The $n$ -qudit Pauli group (modulo phases) is modeled as a $2n$ -dimensional vector space $V \cong \mathbb{F}_p^{2n}$ over a prime field $\mathbb{F}_p$ .
Symplectic Form: A bilinear, alternating form $\langle u, v \rangle$ encodes the commutation relations of Pauli operators. Two operators commute if and only if their symplectic pairing is zero.
Code Definition: A stabilizer code is defined by an isotropic subspace $S \subseteq V$ $S \subseteq V$ (where $S \subseteq S^\perp$ $S \subseteq S^{⊥}$ ) with dimension $n-k$ $n - k$ .
- $S$ : The stabilizer group.
- $S^\perp$ : The centralizer of the stabilizer.
- $S^\perp / S$ : The space of logical operators (dimension $2k$ ).

B. Key Lemmas and Concepts

Distance Implies Erasure Correctability:
If a code has distance $d$ , any set of erasures $E$ with $|E| \leq d-1$ is correctable. In the symplectic model, this is equivalent to the condition:
$S^\perp \cap V_E \subseteq S$
where $V_E$ is the subspace of vectors supported only on $E$ . This means no non-trivial logical operator can be supported entirely within a correctable erasure region.
The Cleaning Lemma (Dimension Identity):
For any partition of qubits into a set $M$ and its complement $M^c$ , the dimensions of the spaces of logical operators supported on $M$ and $M^c$ satisfy:
$g(M) + g(M^c) = 2k$
where $g(M) = \dim((S^\perp \cap V_M) / (S \cap V_M))$ . This identity quantifies how logical information can be "cleaned" off a correctable region onto its complement.
Two Disjoint Correctable Sets:
The authors consider two disjoint sets $A$ and $B$ , each of size $d-1$ . Since $|A|, |B| \leq d-1$ , both are correctable erasures.
- Because $A$ is correctable, $g(A) = 0$ .
- By the Cleaning Lemma, $g(A^c) = 2k$ .
- Since $A^c = B \cup C$ (where $C$ is the remaining qubits), the logical operators must be representable on $B \cup C$ .
- Because $B$ is also correctable, logical operators cannot be supported entirely on $B$ . Through a dimension-counting argument involving restriction maps, the authors show that the logical space must effectively reside on $C$ .
- This leads to the inequality: $2k \leq \dim(V_C) = 2|C|$ , implying $k \leq |C|$ .

C. Derivation of the Bound

By choosing disjoint sets $A$ and $B$ of size $d-1$ , the remaining set $C$ has size $n - 2(d-1)$ . The dimension argument yields:
$k \leq n - 2(d-1) \implies k + 2(d-1) \leq n$

3. Key Contributions

Purely Algebraic Proof: The paper presents the first self-contained proof of the Quantum Singleton Bound for stabilizer codes that relies exclusively on symplectic linear algebra. It avoids von Neumann entropy, the no-cloning theorem, and decoupling principles, thereby clarifying the algebraic mechanism underlying the bound.
Formal Verification (Lean4): The authors provide the first machine-checked proof of the Quantum Singleton Bound.
- Tool: Lean4 proof assistant using the Mathlib library.
- Scope: Approximately 1,300 lines of code covering the symplectic model, stabilizer definitions, the cleaning lemma, and the main theorem.
- Significance: This demonstrates that structural impossibility results in quantum coding theory are amenable to formal verification, distinct from the more common verification of quantum circuits or programs.

4. Results

Theorem: For any $[[n, k, d]]$ stabilizer code over a prime field, $k + 2(d-1) \leq n$ .
Robustness: The proof handles edge cases where $n < 2(d-1)$ naturally (the bound holds trivially as $k \geq 0$ ).
Generality: While the formal proof uses prime fields $\mathbb{F}_p$ , the authors note the argument extends straightforwardly to non-prime fields $\mathbb{F}_{p^m}$ using trace-symplectic forms.

5. Significance

Theoretical Clarity: By stripping away information-theoretic machinery, the proof reveals that the Quantum Singleton Bound is a direct consequence of the linear algebraic constraints of the symplectic vector space. This offers a more intuitive understanding for researchers working in algebraic coding theory.
Formal Verification Milestone: The work bridges the gap between quantum information theory and formal methods. It proves that complex coding-theoretic bounds can be mechanized, paving the way for future formalizations of other quantum bounds (e.g., the Hamming bound or Plotkin bound) and ensuring the correctness of theoretical foundations used in fault-tolerant quantum computing.
Educational Value: The proof is described as "short, elementary, and entirely algebraic," making it a valuable pedagogical tool for teaching stabilizer codes without requiring advanced quantum information theory prerequisites.

In summary, Dehmel and Li successfully re-derive a cornerstone of quantum error correction using only linear algebra and provide a rigorous, machine-verified foundation for this result, marking a significant step forward in the formalization of quantum coding theory.