Quantum Circuit Synthesis Using an Exact T Library

Resumo Técnico: Síntese de Circuitos Quânticos Usando uma Biblioteca Exata de T

Enunciação do Problema
Na computação quântica tolerante a falhas (FTQC), a execução de portas não-Clifford, especificamente portas T, domina o custo espaço-tempo devido à sobrecarga da destilação e injeção de estados mágicos. Enquanto as portas Clifford podem ser executadas transversalmente com sobrecarga negligenciável, as portas T exigem cultivo de estado dispendioso. Consequentemente, a minimização da contagem de T é crítica para aplicações práticas.

Os fluxos de síntese existentes mapeam tipicamente funções booleanas sobre uma base $\{XOR, AND, NOT\}$ (XAG) e minimizam o número de portas AND como um proxy para a contagem de T. Essa abordagem baseia-se na Complexidade Multiplicativa (MC), que mede a não linearidade clássica. No entanto, o artigo argumenta que a MC é um proxy impreciso para o custo quântico T, pois falha em contabilizar cancelamentos de fase e simplificações estruturais únicas aos circuitos quânticos (por exemplo, portas Hadamard bloqueando otimizações de T). Como resultado, fluxos convencionais frequentemente produzem circuitos subótimos onde oportunidades estruturais perdidas não podem ser recuperadas por otimizações pós-mapeamento.

Metodologia
Os autores propõem um framework de síntese que otimiza diretamente a contagem exata de T, em vez de usar a MC como um proxy. A metodologia consiste em três componentes principais:

1. Canonicidade Equivalente a Clifford:
   O artigo introduz uma forma canônica para funções bilineares sob equivalência Clifford. Diferentemente da MC clássica, que usa um tensor de multiplicação para representar acoplamentos entrada-saída, os autores utilizam um tensor de polinômio de fase. Este tensor captura acoplamentos de paridade tripla entre todos os fios (entradas e saídas) em um cenário reversível. Essa formulação revela que operações quânticas podem emaranhar entradas e saídas, criando interações de terceira ordem que permitem "atalhos" na decomposição, levando a um custo T menor do que as estimativas de MC clássica.

2. Síntese de Biblioteca Exata de T:
   Os autores formulam o problema de síntese exata de T como um problema de programação inteira com restrições.

   • Entrada: Uma função bilinear $f$ com $n$ entradas e $m$ saídas, mapeada para $N = n+m$ qubits.
   • Restrições: O problema busca um vetor de seleção $s$ de candidatos a T (termos de paridade) tal que seu polinômio de fase combinado seja igual ao polinômio de fase da função alvo módulo 2.
   • Otimização: O objetivo é minimizar a cardinalidade de $s$ (a contagem de T).
   • Condições "Don't-Care": A formulação explora qubits "ancilla limpa" (inicializados em $|0\rangle$) como condições "don't-care". Fases nesses estados ancilla são inobserváveis, permitindo reescritas Clifford sem custo (por exemplo, substituir combinações específicas de T por portas S gratuitas) para reduzir ainda mais a contagem de T.
   • Algoritmo: Um algoritmo eficiente de síntese de biblioteca pré-computa a matriz de mapeamento e uma base do espaço nulo. Utiliza uma busca acelerada por CUDA para encontrar soluções exatas para funções com até sete variáveis ($N \le 7$) e soluções subótimas para entradas maiores.

3. Mapeamento de Biblioteca Personalizado:
   Para aproveitar plenamente a biblioteca exata de T, os autores desenvolveram um mapeador personalizado que se integra ao fluxo XAG.

   • Enumeração de Cortes Bilineares: O mapeador prioriza cortes que revelam estruturas bilineares (termos de grau 2 na Forma Normal Algébrica). Ele poda cortes que introduziriam monômios de grau 3 ou superior, que não são suportados pela biblioteca.
   • Modelo de Custo: Em vez de estimar o custo via contagem de AND, o mapeador consulta a biblioteca Exata de T pré-computada para recuperar o custo T preciso para cada corte válido.
   • Programação Dinâmica: O mapeador realiza programação dinâmica padrão orientada a área sobre cortes, mas utiliza as pontuações exatas de T para selecionar implementações, preservando a estrutura subjacente da rede lógica.

Principais Contribuições

• Formulação Exata de T: Uma mudança da minimização de contagens de AND (MC) para a minimização de contagens exatas de T, canonicizando funções booleanas sob equivalência Clifford usando tensores de polinômio de fase.
• Biblioteca Pré-computada: Uma biblioteca de implementações ótimas em T para funções bilineares com até sete variáveis, sintetizada usando uma abordagem de programação inteira que considera condições "don't-care" de ancilla limpa.
• Mapeador Personalizado: Um algoritmo de mapeamento que preserva explicitamente estruturas bilineares durante a enumeração e classificação de cortes, utilizando a biblioteca exata de T para guiar decisões de otimização.

Resultados Experimentais
Os autores avaliaram sua abordagem em várias famílias de benchmarks, incluindo benchmarks aritméticos do EPFL, oráculos QLUT aleatórios, exponenciação modular (algoritmo de Shor) e multiplicadores GF($2^n$) para AES.

• Benchmarks EPFL: Comparado a fluxos de mapeamento XAG anteriores impulsionados por MC exata, o método proposto alcançou uma redução de até 14,3% na contagem de T em benchmarks aritméticos (por exemplo, multiplicadores). A redução média geométrica entre os benchmarks foi de 5,3%.
• Módulos Criptográficos: Quando integrado a um fluxo de síntese completo (incluindo ressíntese), a abordagem reduziu as contagens de T de melhor conhecimento para vários módulos criptográficos em até 40%.
• Comparação com o Estado da Arte: O método superou otimizações de T autônomas como AlphaTensor e FastTODD, bem como implementações existentes de QROM e SelectSwap, particularmente em cenários com alta estrutura bilinear.
• Sobrecarga de Tempo de Execução: A computação adicional introduzida pela consulta à biblioteca exata de T e pelo mapeamento personalizado representou no máximo 11,7% do tempo de execução total, o que os autores observam ser um custo único amortizado sobre a reutilização de designs de módulos quânticos.

Significado
O artigo afirma que assumir uma transformação uniforme de portas AND para um número fixo de portas T leva a uma perda irreversível de optimalidade. Ao preservar a estrutura XAG enquanto raciocina com custos exatos de T, a abordagem proposta produz melhorias tangíveis na qualidade do circuito. O trabalho demonstra que a otimização direta da contagem de T, facilitada por uma forma canônica equivalente a Clifford e um mapeador personalizado, pode reduzir significativamente a sobrecarga de recursos para aplicações quânticas tolerantes a falhas, superando as limitações de proxies de não linearidade clássica.