🔢 mathematics

Insertion Correcting Capability for Quantum Deletion-Correcting Codes

This paper establishes that quantum $t$ -deletion-correcting codes can also correct a total of $t$ insertion and deletion errors under a disjoint error sphere condition, while introducing the quantum indel distance to characterize these correction capabilities.

Original authors: Ken Nakamura, Takayuki Nozaki

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ken Nakamura, Takayuki Nozaki

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 sending a precious message written on a series of magical, glowing cards. In the quantum world, these cards are called qudits (quantum digits). Sometimes, during transmission, the universe plays a trick on you: a card might vanish completely (deletion), or a random, extra card might be shoved into the stack (insertion).

This paper by Nakamura and Nozaki tackles a specific puzzle: If we build a system that can fix missing cards, can it also fix extra cards?

Here is the breakdown of their findings using simple analogies:

1. The Big Question: The "Missing vs. Extra" Puzzle

In the world of regular (classical) data, like sending a text message, it is a known rule: if your system can fix t missing letters, it can automatically fix a mix of t missing and extra letters combined. It's like having a spell that fixes a torn page; that same spell usually works if a random page was stuck in the middle too.

However, in the quantum world, things are weirder. Scientists weren't sure if this rule held up. They knew that quantum deletion codes (systems that fix missing cards) could fix some types of extra cards, but they didn't know if they could fix any combination of missing and extra cards, especially when the cards were in a messy, "mixed" state (like a deck that has been shuffled and partially destroyed).

2. The Main Discovery: The "One-Way Street"

The authors proved a powerful new rule: Yes, if a quantum code can fix t missing cards, it can also fix a total of t errors, whether those errors are missing cards, extra cards, or a mix of both.

The Analogy: Imagine you have a safety net designed to catch a falling acrobat (a missing card). The paper proves that this same net is strong enough to catch an acrobat who is also being pushed by a sudden gust of wind (an extra card) or a mix of falling and pushing. As long as the total number of "tricks" the universe plays is t or fewer, your net works.

The Catch (The "Condition"):
This rule works under a specific definition of what a "code" is. The authors define a code as a set of states where, if you make a mistake, the resulting "error sphere" (the cloud of possible messed-up states) does not overlap with the error sphere of any other valid message. Think of it like distinct islands in a foggy sea; as long as the fog (the errors) around Island A doesn't touch the fog around Island B, you can always tell which island you are on.

3. The Twist: The Reverse is NOT True

Here is where quantum mechanics gets tricky. While fixing missing cards implies you can fix extra cards, the reverse is not true.

The Analogy: You can build a machine that is great at spotting when a card has been added to the deck, but that same machine might be completely useless if a card goes missing.
The Paper's Proof: The authors constructed a specific example of a quantum code that can fix a single extra card but fails completely if a card is deleted. This is different from the classical world, where the two abilities usually go hand-in-hand. In the quantum world, being good at spotting "intruders" doesn't mean you are good at spotting "vacancies."

4. The New Tool: The "Quantum Indel Distance"

To measure how good a code is, the authors invented a new ruler called the Quantum Indel Distance.

The Analogy: Imagine you want to measure the difference between two messy piles of cards. In the past, we had rulers for "bit flips" (changing a 0 to a 1) and "classical typos." This new ruler measures the "effort" required to turn one quantum pile into another by deleting and inserting cards.
How it works: If the distance between two valid messages is large enough (specifically, greater than $2t$ ), the code is guaranteed to fix up to $t$ errors. It's like saying, "If the two islands are far enough apart, even a big storm (errors) won't make them look like the same island."

5. Handling the "Messy" States

A major technical hurdle the authors overcame was dealing with mixed states.

The Analogy: Imagine a pure quantum state is like a pristine, single-color marble. A mixed state is like a marble that has been cracked and filled with glue, making it a cloudy, unpredictable mess. Previous research could only explain what happens when you insert a card into a pristine marble.
The Breakthrough: This paper figured out exactly what happens when you insert a card into a "cloudy, messy" marble. They provided a mathematical recipe to describe these new, messy states. This was crucial because when you delete and insert cards repeatedly, the pristine marbles often turn into messy ones. Without this recipe, the proof wouldn't hold.

Summary

In short, this paper says:

Good News: If you build a quantum code that can fix t missing cards, you automatically get the ability to fix t missing or extra cards combined.
Bad News: If you build a code that fixes extra cards, it does not guarantee you can fix missing cards.
New Tool: They created a new "distance" metric to measure how robust a code is against these specific types of chaos.
New Math: They solved the math for how these errors affect "messy" (mixed) quantum states, which previous theories couldn't handle.

This work solidifies our understanding of how to protect quantum information from the chaotic nature of losing or gaining data units.

Technical Summary: Insertion Correcting Capability for Quantum Deletion-Correcting Codes

Problem Statement
In classical coding theory, it is a established result that a code capable of correcting $t$ deletion errors is also capable of correcting a total of $t$ combined insertion and deletion errors. However, in quantum coding theory, this equivalence remains an open problem. Previous research by Shibayama et al. [10, 12] demonstrated that a quantum code correcting $t$ deletion errors also corrects $t$ separable insertion errors (where the inserted qudit is not entangled with the original system). This limitation arises because the Knill-Laflamme (KL) condition, used in those proofs, restricts insertion errors to separable cases. In composite error scenarios involving both deletions and insertions, the system may transition from pure to mixed states, rendering separable assumptions insufficient. Furthermore, the KL condition requires orthogonality of bases after errors at distinct positions, which is a stronger condition than necessary for error correction; a code may satisfy basis orthogonality yet fail to distinguish distinct codewords that collapse into the same state. Consequently, it remains unproven whether a general quantum $t$ -deletion-correcting code can correct a total of $t$ arbitrary insertion and deletion errors.

Methodology
To address these limitations, the authors adopt a geometric approach analogous to classical coding theory, focusing on the concept of "error spheres" rather than the KL condition.

Generalization of Insertion States: The paper first generalizes the description of quantum states after insertion errors. While previous work [11] described insertions into pure states, this paper explicitly derives the form of quantum states after insertion errors applied to mixed states (Theorem 2 and Corollary 1). This is achieved by analyzing the structure of density matrices under partial traces and principal minors.
Composite Error Analysis: The authors prove that any composite error consisting of $s$ deletions and $t$ insertions can be represented as a sequence where all $t$ insertions occur after all $s$ deletions (Theorem 3). This is established through a series of lemmas (Lemmas 4–6) demonstrating that the set of states resulting from mixed error sequences is a subset of the set resulting from $t$ insertions following $s$ deletions ( $I_t \circ D_s$ ).
Error Sphere Disjointness: The paper defines a quantum error-correcting code as a set of quantum states whose deletion/insertion spheres are disjoint. Using this definition, the authors analyze the intersection of error spheres to determine correcting capabilities.

Key Contributions and Results

Equivalence of Correction Capabilities: The main result (Theorem 4) proves that any quantum code $X$ that corrects $t$ deletion errors also corrects a total of $t$ combined insertion and deletion errors. This holds under the definition that a code is valid if the error spheres of its codewords are disjoint. This resolves the open problem regarding the equivalence of deletion and combined indel correction capabilities in the general case, removing the restriction to separable insertion errors.
Non-Reciprocity of Correction: The paper demonstrates that the converse does not hold. A quantum code that corrects $t$ insertion errors does not necessarily correct $t$ deletion errors. An example is provided (Example 4) showing a set of states that corrects single insertions but fails to correct single deletions. This contrasts with classical coding theory, where the equivalence is bidirectional.
Quantum Indel Distance: The authors define the "quantum indel distance" ( $d(\rho_1, \rho_2)$ ) as the minimum sum of deletions and insertions required to transform one quantum state into another. They prove this distance satisfies the properties of a metric (Theorem 5).
Characterization via Distance: The paper establishes that a set of quantum states $X$ corrects a total of $t$ insertion and deletion errors if and only if the minimum quantum indel distance between distinct states in $X$ is at least $2t + 1$ (Corollary 3). This provides a distance-based bound for quantum indel-correcting codes, analogous to the Hamming distance for bit-flip errors.

Significance
The paper claims significance in three primary areas:

Theoretical Resolution: It resolves the open problem regarding the equivalence of $t$ -deletion and total $t$ -indel correction capabilities for general quantum codes, moving beyond the restrictive separable insertion assumptions of prior work.
Methodological Advancement: By explicitly characterizing quantum states after insertion errors into mixed states, the paper provides the necessary mathematical tools to analyze composite errors where the system state becomes mixed.
New Metric: The introduction of the quantum indel distance offers a new framework for characterizing and bounding the error-correcting capability of quantum codes against synchronization errors (insertions and deletions), similar to how Hamming distance characterizes bit-flip errors.

The authors maintain a modest scope, noting that while the main theorem holds for codes defined by disjoint error spheres, the converse (insertion-only codes correcting deletions) is false, highlighting a fundamental asymmetry in quantum indel error correction not present in the classical domain.