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

Résumé technique : Décodage d'algorithmes pour les erreurs composites dans les codes de Hagiwara

Énoncé du problème
Les systèmes d'information quantique sont sensibles aux erreurs de synchronisation, notamment les erreurs de suppression quantique (perte d'un qubit) et les erreurs d'insertion quantique (ajout d'un nouveau qubit). Bien que les codes de Reed-Solomon (RS) quantiques et leurs dérivés, connus sous le nom de codes de Hagiwara, aient été établis comme capables de corriger les erreurs composites composées à la fois de suppressions et d'insertions, un algorithme de décodage efficace pour de telles erreurs composites restait un problème ouvert. Les méthodes de décodage existantes pour les codes de Hagiwara étaient principalement limitées à la correction de suppressions uniquement ou d'insertions uniquement, ou d'instances uniques de chacune, mais pas de scénarios composites généraux où le nombre total d'erreurs est borné.

Méthodologie
Les auteurs proposent un algorithme de décodage pour les codes de Hagiwara qui gère les erreurs composites composées de $t_d$ suppressions et de $t_i$ insertions, où $t_d + t_i \le t$ et $t_d, t_i \neq 0$. La méthodologie se déroule en deux étapes :

1. Développement de l'équivalent classique : Les auteurs généralisent d'abord un algorithme précédent pour les erreurs de suppression unique/insertion unique à un cadre classique. Les codes de Hagiwara sont construits en insérant des séquences « marqueur » (spécifiquement $0^{(t)}1^{(t)}$) entre les blocs d'un code de Reed-Solomon (RS) classique. L'algorithme (Algorithme 1) analyse la séquence reçue en examinant les régions entourant ces marqueurs. Il détecte si le format du marqueur est préservé ou détruit et compte le nombre de suppressions et d'insertions par rapport aux limites de marqueur attendues.

   • Si le format du marqueur est préservé mais décalé, l'algorithme identifie le décalage pour déterminer si des suppressions ou des insertions se sont produites dans le bloc de données.
   • Si le format du marqueur est détruit (par exemple, un '0' est inséré dans une région '1'), l'algorithme signale le bloc comme contenant une erreur d'insertion.
   • La sortie de cette étape est une séquence de blocs classiques où certains sont identifiés comme des effacements (blocs avec des erreurs détectées) et d'autres comme des substitutions (blocs avec des erreurs non détectées mais corrigées), ainsi que les positions des effacements.

2. Extension au domaine quantique : L'algorithme classique est étendu au domaine quantique. Les auteurs définissent les « erreurs de transformation de bloc » comme des erreurs transformant un bloc quantique $R_b$ en un état dans l'espace de la matrice de densité. Ils démontrent qu'une erreur composite de suppressions et d'insertions ($I_Q \circ D_P$) peut être décomposée en une combinaison linéaire complexe d'erreurs de Pauli agissant sur les qubits affectés et d'une permutation des positions des qubits.

   • En mesurant les qubits marqueurs (ce qui ne détruit pas les qubits de données dans les blocs de code RS), le récepteur obtient une séquence classique de résultats.
   • L'Algorithme 1 classique est appliqué à ces résultats de mesure pour identifier quels blocs ont subi des effacements (perte d'information) et lesquels ont subi des transformations unitaires (substitutions).
   • Le décodage quantique se réduit alors à la correction des effacements et des erreurs unitaires sur la structure de code CSS sous-jacente (construite à partir des codes RS $C_1$ et $C_2$), une tâche pour laquelle des algorithmes efficaces existent déjà.

Contributions clés

• Proposition d'algorithme : L'article présente le premier algorithme de décodage efficace pour les codes de Hagiwara capable de corriger les erreurs composites générales ($t_d$ suppressions et $t_i$ insertions) où $t_d + t_i \le t$.
• Justification théorique : Les auteurs fournissent une preuve rigoureuse (Théorème 2) que l'algorithme proposé transforme la séquence reçue en une forme contenant au plus $e$ effacements de bloc et $m$ substitutions de bloc, satisfaisant la condition $e + 2m \le t$. Cela garantit que l'erreur est dans la capacité de correction des codes de Reed-Solomon sous-jacents.
• Décomposition des erreurs : L'article établit (Théorème 1 et Corollaire 1) que toute erreur composite de suppression/insertion sur un bloc de code de Hagiwara peut être représentée comme une combinaison linéaire d'erreurs de Pauli sur les qubits affectés. Cela comble le fossé entre les erreurs de synchronisation et les cadres standards de correction d'erreurs quantiques.

Résultats
L'article démontre le fonctionnement de l'algorithme à travers un exemple spécifique impliquant un code de Hagiwara classique avec $t=4$. L'exemple illustre comment l'algorithme identifie correctement un mélange d'insertions et de suppressions à travers plusieurs blocs, les convertissant en un motif d'effacements et de substitutions que le décodeur RS sous-jacent peut résoudre. Les résultats théoriques confirment que l'algorithme mappe avec succès les erreurs de synchronisation complexes vers une forme corrigeable pour le code RS quantique.

Importance
L'article prétend combler une lacune significative dans la littérature concernant les codes de Hagiwara. Bien que la construction de ces codes ait été connue pour corriger théoriquement les erreurs composites, l'absence d'une méthode de décodage pratique limitait leur utilité. En fournissant un algorithme de décodage concret et en prouvant sa correction, ce travail permet l'application pratique des codes de Hagiwara pour les systèmes de communication quantique soumis à des erreurs de synchronisation. Le travail s'appuie sur les définitions fondamentales des codes de Hagiwara et étend les efforts de décodage précédents pour les erreurs uniques au scénario d'erreur composite plus complexe.