Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability

Resumo Técnico: Códigos de Grupos Quânticos para Lógica Não-Clifford

Definição do Problema
Os esquemas atuais de computação quântica tolerante a falhas sofrem com sobrecargas significativas de espaço e tempo, dificultando a realização de computadores quânticos práticos. Embora os códigos de Calderbank-Shor-Steane (CSS) que suportam portas transversais ofereçam um caminho para a tolerância a falhas, as construções existentes enfrentam duas limitações primárias:

1. Complexidade de Decodificação: Os códigos de Geometria Algébrica (AG) quântica de última geração que suportam portas transversais não-Clifford (essenciais para a Destilação de Estados Mágicos, ou MSD) dependem de algoritmos de decodificação com complexidade de tempo cúbica ($O(n^3)$). Essa alta complexidade se propaga para o protocolo MSD, limitando sua eficiência.
2. Endereçabilidade e Paralelizabilidade: Os códigos existentes com portas não-Clifford transversais tipicamente implementam operações globais que atuam em todos os qudits físicos simultaneamente. Essa falta de "endereçabilidade" — a capacidade de direcionar subconjuntos específicos de qudits lógicos — limita a flexibilidade algorítmica. Além disso, trabalhos recentes mostraram a existência de códigos com portas endereçáveis, mas as construções frequentemente dependem de famílias muito específicas de códigos AG transitivos, e a paralelizabilidade dessas portas requer otimização adicional para reduzir a profundidade do circuito.

Metodologia
Os autores propõem um framework baseado em códigos de grupos quânticos, derivados de códigos de quase grupo clássicos com propriedades de multiplicação específicas. A metodologia procede em três estágios principais:

1. Definição do Framework (Códigos de Grupos Quânticos):
   Os autores definem uma classe de códigos CSS quânticos onde os códigos clássicos subjacentes ($C_0$ e $C_1$) são códigos quasi-$G$ (isomorfos a ideais à direita de uma álgebra de grupo $F_q[G]$). Ao garantir a existência de uma seção de homomorfismo de $G$-módulo para o mapa quociente, eles estabelecem condições sob as quais esses códigos quânticos admitem portas multi-controle-Z ($C_{m-1}Z$) transversais paralelizáveis e endereçáveis.

   • Mecanismo Chave: A ação de grupo permite a construção de funções de modulação que possibilitam a implementação de portas lógicas em órbitas específicas de qudits lógicos usando circuitos físicos de profundidade um.

2. Construção de Códigos via Levantamento (Lifting):
   Para gerar códigos com bons parâmetros e decodificação eficiente, os autores empregam um procedimento de levantamento baseado em teoria de corpos de classes (especificamente de [CG26]).

   • Eles partem de um código AG clássico $C$ sobre $F_q$ que satisfaz a propriedade de $m$-multiplicação.
   • Eles constroem uma extensão não ramificada abeliana do corpo de funções subjacente, criando um novo código $\tilde{C}$ sobre $F_{q^2}$.
   • Este processo de levantamento confere ao novo código um grande grupo de automorfismo de permutação abeliano $G$, tornando-o um módulo livre $F_{q^2}[G]$. Crucialmente, o levantamento preserva a propriedade de $m$-multiplicação necessária para as portas transversais.

3. Otimização de Decodificação:
   Os autores aproveitam a estrutura de módulo dos códigos levantados. Diferente dos códigos AG padrão que exigem decodificação de tempo cúbico, a estrutura de módulo livre permite a adaptação de algoritmos de decodificação para utilizar multiplicação de matrizes rápida sobre a álgebra de grupo. Isso resulta em um decodificador de tempo quase-quadrático ($O(n^2 \cdot \text{polylog}(n))$) com um raio de decodificação linear.

Contribuições Principais e Resultados

• Teorema 1.1 (Famílias de Códigos): O artigo constrói duas famílias de códigos de grupos quânticos de qudits de dimensão $q$ (onde $q=t^4$):

  1. Família Totalmente Endereçável: Códigos com parâmetros $[[n, \Theta(n/\log n), \Theta(n)]]_q$. Estes admitem portas $C_{\tilde{m}-1}Z$ transversais totalmente endereçáveis. A profundidade dos circuitos lógicos envolvendo $m$ blocos de código é limitada superiormente por $O(k^{\tilde{m}-1})$.
  2. Família de Alta Taxa: Códigos com parâmetros $[[n, \Theta(n), \Theta(n)]]_q$. Estes admitem uma porta $C_{\tilde{m}}Z$ transversal global e portas $C_{\tilde{m}-1}Z$ endereçáveis por órbita através de $\Theta(\log n)$ órbitas.
  • Em ambos os casos, os códigos suportam um decodificador de tempo $O(n^2 \cdot \text{polylog}(n))$ com um raio de decodificação linear, uma melhoria significativa em relação à complexidade $O(n^3)$ das construções anteriores baseadas em AG.

• Corolário 1.2 (Destilação de Estados Mágicos): Ao aplicar a família de alta taxa aos protocolos de Destilação de Estados Mágicos (MSD), os autores demonstram a existência de um protocolo de destilação de overhead constante para estados mágicos CCZ-qubit com complexidade de tempo $O(n^2 \cdot \text{polylog}(n))$. Isso representa uma redução quase linear na complexidade de tempo em comparação com os protocolos de estado da arte $O(n^3)$.

• Paralelizabilidade: O trabalho estabelece que circuitos multi-controle-Z lógicos podem ser paralelizados em alto grau. Para circuitos densos, a profundidade mínima é limitada por $O(k^{m-1})$, o que é ótimo para tais circuitos.

Significado
O artigo afirma que seu trabalho aborda gargalos críticos na computação quântica tolerante a falhas:

1. Eficiência: Ao reduzir a complexidade de decodificação de cúbica para quase-quadrática, o overhead de tempo para protocolos MSD é substancialmente diminuído, aproximando a computação prática tolerante a falhas da viabilidade.
2. Flexibilidade: A introdução de portas não-Clifford endereçáveis e paralelizáveis vai além de operações globais, permitindo um controle mais preciso sobre qudits lógicos. Isso é essencial para compilação de circuitos e algoritmos que não requerem emaranhamento global.
3. Generalização: A construção vai além dos códigos AG transitivos específicos usados em trabalhos anteriores, utilizando uma classe mais ampla de códigos AG levantados com grandes grupos de automorfismo abelianos. Isso fornece um conjunto de ferramentas mais versátil para o design de códigos quânticos com portas não-Clifford transversais.

Os autores enfatizam que seus resultados são derivados de construções teóricas e técnicas de levantamento existentes, verificando que essas transformações preservam as propriedades necessárias para portas não-Clifford transversais enquanto melhoram a eficiência de decodificação.