Decoding Algorithm to Composite Errors Consisting of Deletions and Insertions for Quantum Deletion-Correcting Codes Based on Quantum Reed-Solomon Codes

Technical Summary: Decoding Algorithm to Composite Errors for Hagiwara Codes

Problem Statement
Quantum information systems are susceptible to synchronization errors, specifically quantum deletion errors (loss of a qubit) and quantum insertion errors (addition of a new qubit). While quantum Reed-Solomon (RS) codes and their derivatives, known as Hagiwara codes, have been established as capable of correcting composite errors consisting of both deletions and insertions, an efficient decoding algorithm for such composite errors remained an open problem. Existing decoding methods for Hagiwara codes were primarily limited to correcting only deletions or only insertions, or single instances of each, but not general composite scenarios where the total number of errors is bounded.

Methodology
The authors propose a decoding algorithm for Hagiwara codes that handles composite errors consisting of $t_d$ deletions and $t_i$ insertions, where $t_d + t_i \le t$ and $t_d, t_i \neq 0$. The methodology proceeds in two stages:

1. Classical Counterpart Development: The authors first generalize a previous algorithm for single-insertion/single-deletion errors to a classical setting. Hagiwara codes are constructed by inserting "marker" sequences (specifically $0^{(t)}1^{(t)}$) between blocks of a classical Reed-Solomon (RS) code. The algorithm (Algorithm 1) analyzes the received sequence by examining the regions surrounding these markers. It detects whether the marker format is preserved or destroyed and counts the number of deletions and insertions relative to the expected marker boundaries.

   • If the marker format is preserved but shifted, the algorithm identifies the shift to determine if deletions or insertions occurred within the data block.
   • If the marker format is destroyed (e.g., a '0' is inserted into a '1' region), the algorithm flags the block as containing an insertion error.
   • The output of this stage is a sequence of classical blocks where some are identified as erasures (blocks with detected errors) and others as substitutions (blocks with undetected but corrected errors), along with the positions of the erasures.

2. Extension to Quantum Domain: The classical algorithm is extended to the quantum domain. The authors define "block-transformation errors" as errors transforming a quantum block $R_b$ into a state in the density matrix space. They demonstrate that a composite error of deletions and insertions ($I_Q \circ D_P$) can be decomposed into a complex linear combination of Pauli errors acting on the affected qubits and a permutation of qubit positions.

   • By measuring the marker qubits (which does not destroy the data qubits in the RS code blocks), the receiver obtains a classical sequence of outcomes.
   • The classical Algorithm 1 is applied to these measurement outcomes to identify which blocks suffered erasures (loss of information) and which suffered unitary transformations (substitutions).
   • The quantum decoding then reduces to correcting erasures and unitary errors on the underlying CSS code structure (built from RS codes $C_1$ and $C_2$), a task for which efficient algorithms already exist.

Key Contributions

• Algorithm Proposal: The paper presents the first efficient decoding algorithm for Hagiwara codes capable of correcting general composite errors ($t_d$ deletions and $t_i$ insertions) where $t_d + t_i \le t$.
• Theoretical Justification: The authors provide a rigorous proof (Theorem 2) that the proposed algorithm transforms the received sequence into a form containing at most $e$ block-erasures and $m$ block-substitutions, satisfying the condition $e + 2m \le t$. This ensures the error is within the correction capability of the underlying Reed-Solomon codes.
• Error Decomposition: The paper establishes (Theorem 1 and Corollary 1) that any composite deletion/insertion error on a Hagiwara code block can be represented as a linear combination of Pauli errors on the affected qubits. This bridges the gap between synchronization errors and standard quantum error correction frameworks.

Results
The paper demonstrates the algorithm's operation through a specific example involving a classical Hagiwara code with $t=4$. The example illustrates how the algorithm correctly identifies a mix of insertions and deletions across multiple blocks, converting them into a pattern of erasures and substitutions that the underlying RS decoder can resolve. The theoretical results confirm that the algorithm successfully maps the complex synchronization errors into a correctable form for the quantum RS code.

Significance
The paper claims to resolve a significant gap in the literature regarding Hagiwara codes. While the construction of these codes was known to theoretically correct composite errors, the lack of a practical decoding method limited their utility. By providing a concrete decoding algorithm and proving its correctness, this work enables the practical application of Hagiwara codes for quantum communication systems subject to synchronization errors. The work builds upon the foundational definitions of Hagiwara codes and extends previous decoding efforts for single errors to the more complex composite error scenario.