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

Resumen Técnico: Algoritmo de Decodificación para Errores Compuestos en Códigos Hagiwara

Enunciado del Problema
Los sistemas de información cuántica son susceptibles a errores de sincronización, específicamente errores de borrado cuántico (pérdida de un qubit) y errores de inserción cuántica (adición de un nuevo qubit). Si bien los códigos Reed-Solomon (RS) cuánticos y sus derivados, conocidos como códigos Hagiwara, se han establecido como capaces de corregir errores compuestos que consisten tanto en borrados como en inserciones, un algoritmo de decodificación eficiente para tales errores compuestos permaneció como un problema abierto. Los métodos de decodificación existentes para los códigos Hagiwara se limitaban principalmente a corregir solo borrados o solo inserciones, o instancias individuales de cada uno, pero no escenarios compuestos generales donde el número total de errores está acotado.

Metodología
Los autores proponen un algoritmo de decodificación para códigos Hagiwara que maneja errores compuestos consistiendo en $t_d$ borrados y $t_i$ inserciones, donde $t_d + t_i \le t$ y $t_d, t_i \neq 0$. La metodología procede en dos etapas:

1. Desarrollo del Contraparte Clásico: Los autores generalizan primero un algoritmo anterior para errores de única inserción/único borrado a un entorno clásico. Los códigos Hagiwara se construyen insertando secuencias "marcadoras" (específicamente $0^{(t)}1^{(t)}$) entre bloques de un código Reed-Solomon (RS) clásico. El algoritmo (Algoritmo 1) analiza la secuencia recibida examinando las regiones que rodean estos marcadores. Detecta si el formato del marcador se conserva o se destruye y cuenta el número de borrados e inserciones en relación con los límites esperados del marcador.

   • Si el formato del marcador se conserva pero está desplazado, el algoritmo identifica el desplazamiento para determinar si ocurrieron borrados o inserciones dentro del bloque de datos.
   • Si el formato del marcador se destruye (por ejemplo, se inserta un '0' en una región de '1'), el algoritmo marca el bloque como conteniendo un error de inserción.
   • La salida de esta etapa es una secuencia de bloques clásicos donde algunos se identifican como borrados (bloques con errores detectados) y otros como sustituciones (bloques con errores no detectados pero corregidos), junto con las posiciones de los borrados.

2. Extensión al Dominio Cuántico: El algoritmo clásico se extiende al dominio cuántico. Los autores definen "errores de transformación de bloque" como errores que transforman un bloque cuántico $R_b$ en un estado en el espacio de la matriz de densidad. Demuestran que un error compuesto de borrados e inserciones ($I_Q \circ D_P$) puede descomponerse en una combinación lineal compleja de errores de Pauli actuando sobre los qubits afectados y una permutación de las posiciones de los qubits.

   • Mediante la medición de los qubits marcadores (lo cual no destruye los qubits de datos en los bloques del código RS), el receptor obtiene una secuencia clásica de resultados.
   • Se aplica el Algoritmo 1 clásico a estos resultados de medición para identificar qué bloques sufrieron borrados (pérdida de información) y cuáles sufrieron transformaciones unitarias (sustituciones).
   • La decodificación cuántica se reduce entonces a corregir borrados y errores unitarios en la estructura subyacente del código CSS (construida a partir de los códigos RS $C_1$ y $C_2$), una tarea para la cual ya existen algoritmos eficientes.

Contribuciones Clave

• Propuesta de Algoritmo: El artículo presenta el primer algoritmo de decodificación eficiente para códigos Hagiwara capaz de corregir errores compuestos generales ($t_d$ borrados y $t_i$ inserciones) donde $t_d + t_i \le t$.
• Justificación Teórica: Los autores proporcionan una demostración rigurosa (Teorema 2) de que el algoritmo propuesto transforma la secuencia recibida en una forma que contiene a lo sumo $e$ borrados de bloque y $m$ sustituciones de bloque, satisfaciendo la condición $e + 2m \le t$. Esto asegura que el error está dentro de la capacidad de corrección de los códigos Reed-Solomon subyacentes.
• Descomposición de Errores: El artículo establece (Teorema 1 y Corolario 1) que cualquier error compuesto de borrado/inserción en un bloque de código Hagiwara puede representarse como una combinación lineal de errores de Pauli sobre los qubits afectados. Esto cierra la brecha entre los errores de sincronización y los marcos estándar de corrección de errores cuánticos.

Resultados
El artículo demuestra el funcionamiento del algoritmo mediante un ejemplo específico que involucra un código Hagiwara clásico con $t=4$. El ejemplo ilustra cómo el algoritmo identifica correctamente una mezcla de inserciones y borrados a través de múltiples bloques, convirtiéndolos en un patrón de borrados y sustituciones que el decodificador RS subyacente puede resolver. Los resultados teóricos confirman que el algoritmo mapea con éxito los complejos errores de sincronización a una forma corregible para el código RS cuántico.

Significado
El artículo afirma resolver una brecha significativa en la literatura respecto a los códigos Hagiwara. Si bien se sabía que la construcción de estos códigos corregía teóricamente errores compuestos, la falta de un método de decodificación práctico limitaba su utilidad. Al proporcionar un algoritmo de decodificación concreto y demostrar su corrección, este trabajo habilita la aplicación práctica de los códigos Hagiwara para sistemas de comunicación cuántica sujetos a errores de sincronización. El trabajo se basa en las definiciones fundamentales de los códigos Hagiwara y extiende los esfuerzos previos de decodificación para errores individuales al escenario más complejo de errores compuestos.