List-Decodable Folded Quantum Hermitian Codes

Resumo Técnico: Códigos Quânticos Hermitianos Dobrados List-Decodáveis

Declaração do Problema
Códigos quânticos de correção de erros derivados de códigos de geometria algébrica (AG) têm sido há muito tempo objeto de estudo, com curvas Hermitianas desempenhando um papel proeminente devido aos seus ricos grupos de automorfismo e parâmetros assintóticos favoráveis. Embora a list-decodificação clássica tenha avançado significativamente — culminando em códigos Reed-Solomon dobrados que se aproximam do limite de Singleton —, traduzir essas técnicas para o cenário quântico apresenta desafios. Especificamente, códigos quânticos Reed-Solomon dobrados, construídos recentemente por Bergamaschi, Golowich e Gunn, atingem o limite quântico de Singleton, mas sofrem com tamanhos de alfabeto grandes. Para mitigar isso, esses trabalhos empregaram "amplificação de distância quântica", uma técnica que aumenta a complexidade. O problema central abordado neste artigo é se códigos quânticos dobrados podem ser construídos a partir de curvas de gênero positivo (especificamente curvas Hermitianas) para alcançar desempenho de list-decodificação comparável e aproximar-se do limite quântico de Singleton, enquanto utilizam tamanhos de alfabeto menores, potencialmente tornando a amplificação de distância desnecessária.

Metodologia
Os autores empregam o framework Calderbank-Shor-Steane (CSS) para construir códigos quânticos a partir de códigos AG clássicos dobrados. A metodologia procede através das seguintes etapas:

1. Dobramento Clássico: Os autores utilizam o grupo de automorfismo da curva Hermitiana $H$ sobre $\mathbb{F}_{q^2}$. Diferentemente dos códigos Reed-Solomon, que dependem de uma única órbita cíclica, os códigos Hermitianos utilizam automorfismos $\sigma_{\delta, \mu}$ que particionam os pontos racionais afins em múltiplas órbitas estruturadas. Avaliações consecutivas ao longo dessas órbitas são agrupadas em símbolos únicos sobre um corpo de extensão $\mathbb{F}_{q^m}$, criando códigos Hermitianos de um ponto dobrados $C^{(\sigma, m)}$.
2. Construção CSS: Dois códigos Hermitianos clássicos dobrados, $C_1^{(\sigma, m)}$ e $C_2^{(\sigma, m)}$, são selecionados de modo que o dual do segundo esteja contido no primeiro ($(C_2^{(\sigma, m)})^\perp \subseteq C_1^{(\sigma, m)}$). Os autores formalizam a condição sob a qual o dobramento comuta com a construção CSS, garantindo que o código quântico resultante seja bem definido.
3. Extensão Assistida por Emaranhamento: O artigo também apresenta uma construção para códigos quânticos AG dobrados assistidos por emaranhamento. Essa abordagem relaxa o requisito estrito de inclusão ($C_2^\perp \subseteq C_1$) ao utilizar emaranhamento pré-compartilhado (ebits), permitindo que quaisquer dois códigos Hermitianos dobrados definam um código quântico.
4. Análise de Decodificação: A list-decodabilidade dos códigos quânticos resultantes é analisada aproveitando a list-decodabilidade dos códigos Hermitianos clássicos dobrados subjacentes. Os autores aplicam um lema de trabalho anterior (Bergamaschi et al.) afirmando que, se os códigos clássicos constituintes são $(\tau, L)$-list-decodáveis, o código CSS resultante é $(\tau, L^2)$-list-decodável quântico.

Principais Contribuições e Resultados

• Construção de Códigos Quânticos Hermitianos Dobrados (FQHC): O artigo fornece construções explícitas de códigos quânticos Hermitianos dobrados usando o framework CSS. Esses códigos são derivados de códigos Hermitianos de um ponto dobrados via automorfismos específicos da curva Hermitiana.
• List-Decodabilidade até o Limite Quântico de Singleton: Os autores provam que os FQHCs são $(\tau, L)$-list-decodáveis com um raio de decodificação $\tau = \frac{1 - R_{FQHC}}{2} - \epsilon$, onde $R_{FQHC}$ é a taxa do código quântico. Esse raio aproxima-se do limite quântico de Singleton ($1 - R$), igualando o desempenho dos códigos quânticos Reed-Solomon dobrados.
• Eficiência do Tamanho do Alfabeto: Um resultado primário é a demonstração de que os FQHCs alcançam esse desempenho com um tamanho de alfabeto de $(1/\epsilon)^{O(1/\epsilon^2)}$. Em contraste, códigos quânticos Reed-Solomon dobrados que atingem limites semelhantes requerem amplificação de distância quântica, resultando em um tamanho de alfabeto de $2^{O(1/\epsilon^5)}$. Os autores mostram que, para qualquer $\epsilon$, o tamanho do alfabeto do FQHC é estritamente menor, eliminando a necessidade de amplificação de distância.
• Algoritmo de Decodificação Determinístico: O artigo estabelece a existência de um algoritmo determinístico de list-decodificação quântica. O procedimento envolve medir estabilizadores para obter síndromes clássicas, executar decodificadores de lista clássicos nos códigos Hermitianos dobrados constituintes para gerar listas candidatas de erros e emparelhar essas listas para formar uma lista de tamanho polinomial de erros de Pauli candidatos. O tempo total de execução é $N^{O(1/\epsilon^2)}$.
• Construção Assistida por Emaranhamento: O artigo estende o framework para códigos assistidos por emaranhamento, permitindo a construção de códigos quânticos a partir de qualquer par de códigos Hermitianos dobrados sem exigir a condição de contenção do dual, ao custo de consumir emaranhamento.

Significância
O artigo afirma que sua construção de códigos quânticos Hermitianos dobrados oferece uma alternativa mais eficiente aos códigos quânticos Reed-Solomon dobrados. Ao aproveitar a estrutura geométrica de curvas de gênero positivo, os autores alcançam list-decodabilidade até o limite quântico de Singleton, mantendo um tamanho de alfabeto significativamente menor. Crucialmente, o trabalho demonstra que a técnica "custosa" de amplificação de distância quântica não é necessária para alcançar raios de decodificação quase ótimos ao utilizar curvas Hermitianas. Isso sugere que curvas de gênero positivo fornecem um trade-off superior entre taxa, raio de correção de erros e tamanho do alfabeto para códigos quânticos dobrados. O artigo conclui observando que a construção de códigos quânticos AG dobrados explícitos a partir de outras curvas de gênero positivo e a exploração de construções além dos frameworks CSS e assistidos por emaranhamento permanecem problemas em aberto.