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

Resumo Técnico: Decodificação de Algoritmo para Erros Compostos em Códigos de Hagiwara

Declaração do Problema
Sistemas de informação quântica são suscetíveis a erros de sincronização, especificamente erros de deleção quântica (perda de um qubit) e erros de inserção quântica (adição de um novo qubit). Embora códigos quânticos de Reed-Solomon (RS) e seus derivados, conhecidos como códigos de Hagiwara, tenham sido estabelecidos como capazes de corrigir erros compostos consistindo tanto de deleções quanto de inserções, um algoritmo de decodificação eficiente para tais erros compostos permanecia um problema em aberto. Métodos de decodificação existentes para códigos de Hagiwara eram primariamente limitados a corrigir apenas deleções ou apenas inserções, ou instâncias únicas de cada uma, mas não cenários compostos gerais onde o número total de erros é limitado.

Metodologia
Os autores propõem um algoritmo de decodificação para códigos de Hagiwara que lida com erros compostos consistindo em $t_d$ deleções e $t_i$ inserções, onde $t_d + t_i \le t$ e $t_d, t_i \neq 0$. A metodologia procede em duas etapas:

1. Desenvolvimento do Contraparte Clássico: Os autores primeiro generalizam um algoritmo anterior para erros de inserção única/deleção única para um cenário clássico. Códigos de Hagiwara são construídos inserindo sequências "marcadoras" (especificamente $0^{(t)}1^{(t)}$) entre blocos de um código clássico de Reed-Solomon (RS). O algoritmo (Algoritmo 1) analisa a sequência recebida examinando as regiões ao redor desses marcadores. Ele detecta se o formato do marcador é preservado ou destruído e conta o número de deleções e inserções em relação aos limites esperados do marcador.

   • Se o formato do marcador for preservado, mas deslocado, o algoritmo identifica o deslocamento para determinar se deleções ou inserções ocorreram dentro do bloco de dados.
   • Se o formato do marcador for destruído (por exemplo, um '0' é inserido em uma região de '1'), o algoritmo sinaliza o bloco como contendo um erro de inserção.
   • A saída desta etapa é uma sequência de blocos clássicos onde alguns são identificados como apagamentos (blocos com erros detectados) e outros como substituições (blocos com erros não detectados, mas corrigidos), juntamente com as posições dos apagamentos.

2. Extensão ao Domínio Quântico: O algoritmo clássico é estendido ao domínio quântico. Os autores definem "erros de transformação de bloco" como erros que transformam um bloco quântico $R_b$ em um estado no espaço de matriz densidade. Eles demonstram que um erro composto de deleções e inserções ($I_Q \circ D_P$) pode ser decomposto em uma combinação linear complexa de erros de Pauli atuando nos qubits afetados e uma permutação das posições dos qubits.

   • Ao medir os qubits marcadores (o que não destrói os qubits de dados nos blocos do código RS), o receptor obtém uma sequência clássica de resultados.
   • O Algoritmo 1 clássico é aplicado a esses resultados de medição para identificar quais blocos sofreram apagamentos (perda de informação) e quais sofreram transformações unitárias (substituições).
   • A decodificação quântica reduz-se então a corrigir apagamentos e erros unitários na estrutura subjacente do código CSS (construído a partir dos códigos RS $C_1$ e $C_2$), uma tarefa para a qual algoritmos eficientes já existem.

Principais Contribuições

• Proposta de Algoritmo: O artigo apresenta o primeiro algoritmo de decodificação eficiente para códigos de Hagiwara capaz de corrigir erros compostos gerais ($t_d$ deleções e $t_i$ inserções) onde $t_d + t_i \le t$.
• Justificativa Teórica: Os autores fornecem uma prova rigorosa (Teorema 2) de que o algoritmo proposto transforma a sequência recebida em uma forma contendo no máximo $e$ apagamentos de bloco e $m$ substituições de bloco, satisfazendo a condição $e + 2m \le t$. Isso garante que o erro esteja dentro da capacidade de correção dos códigos de Reed-Solomon subjacentes.
• Decomposição de Erros: O artigo estabelece (Teorema 1 e Corolário 1) que qualquer erro composto de deleção/inserção em um bloco de código de Hagiwara pode ser representado como uma combinação linear de erros de Pauli nos qubits afetados. Isso preenche a lacuna entre erros de sincronização e estruturas padrão de correção de erros quânticos.

Resultados
O artigo demonstra a operação do algoritmo através de um exemplo específico envolvendo um código clássico de Hagiwara com $t=4$. O exemplo ilustra como o algoritmo identifica corretamente uma mistura de inserções e deleções através de múltiplos blocos, convertendo-os em um padrão de apagamentos e substituições que o decodificador RS subjacente pode resolver. Os resultados teóricos confirmam que o algoritmo mapeia com sucesso os erros complexos de sincronização em uma forma corrigível para o código quântico RS.

Significância
O artigo afirma resolver uma lacuna significativa na literatura referente aos códigos de Hagiwara. Embora a construção desses códigos fosse conhecida por corrigir teoricamente erros compostos, a falta de um método de decodificação prático limitava sua utilidade. Ao fornecer um algoritmo de decodificação concreto e provar sua correção, este trabalho habilita a aplicação prática de códigos de Hagiwara para sistemas de comunicação quântica sujeitos a erros de sincronização. O trabalho baseia-se nas definições fundamentais dos códigos de Hagiwara e estende esforços anteriores de decodificação para erros únicos até o cenário mais complexo de erro composto.