Optimised T counts and active volume estimates for high- and low- level arithmetic subroutines

Título: Estimativas otimizadas de contagens de T e volume ativo para sub-rotinas aritméticas de alto e baixo nível

Autor: Sam Heavey (Imperial College London)

Definição do Problema

Computadores quânticos baseados em código de superfície são um forte candidato para a computação quântica tolerante a falhas. No entanto, arquiteturas "baseline" tradicionais, que dependem de matrizes 2D de qubits com conectividade local, sofrem de ineficiências significativas. Uma grande parte do volume espaço-temporal nestas computações é "ociosa", correspondendo a qubits lógicos que permanecem sem uso durante operações específicas. Este volume ocioso aumenta o custo geral de recursos (volume espaço-temporal) sem contribuir para a computação lógica.

Embora as arquiteturas de "volume ativo" (AV) visem eliminar este volume ocioso através da utilização de conectividade de longo alcance para paralelizar operações, há uma carência de um catálogo abrangente de sub-rotinas aritméticas otimizadas com estimativas precisas de volume ativo. A literatura existente foca frequentemente na redução da contagem de T em arquiteturas baseline sem considerar plenamente como a estrutura do circuito impacta o volume ativo, particularmente quando envolvem injeção de estado e medições reativas.

Metodologia

O artigo propõe uma metodologia para derivar e otimizar o volume ativo e as contagens de T para ambas as sub-rotinas aritméticas de baixo nível (ex: incremento, deslocamento, adição) e alto nível (ex: raiz quadrada, trigonometria, logaritmo).

1. Suposição de Otimalidade: O trabalho opera sob a suposição de que designs de circuitos que minimizam a contagem de T e a contagem de qubits numa arquitetura baseline também resultarão no menor volume ativo. Isto permite ao autor focar-se na minimização das contagens de T (especificamente portas Toffoli e AND temporárias) em vez de calcular volumes ativos para cada possível variação de design.
2. Otimização do Conjunto de Portas: O autor utiliza a porta "AND temporária" (introduzida por Gidney) para reduzir à metade a contagem de T de certas operações. Eles também optam por implementar portas Toffoli e AND temporárias utilizando estados CCZ em vez de estados T, uma vez que a destilação de CCZ é frequentemente mais barata no modelo de volume ativo.
3. Cálculo de Volume Ativo via Diagramas ZX Orientados:
   • O autor converte diagramas de circuitos padrão em diagramas ZX e, posteriormente, em diagramas ZX Orientados (OZX).
   • Os diagramas OZX incorporam consciência espacial, mapeando os spiders para portas específicas (U, D, N, S, E, W) de blocos de espaço-tempo 3D.
   • Ao aplicar regras de cálculo ZX (como a fusão de spiders) dentro das restrições de conectividade OZX, o autor simplifica os diagramas para contar o número mínimo de blocos lógicos (spiders) necessários.
   • O volume ativo total é calculado somando as contagens de blocos dos spiders e adicionando os custos de destilação para quaisquer estados mágicos requeridos (ex: estados CCZ).
4. Análise de Profundidade de Reação: O artigo contabiliza a "profundidade de reação", o tempo necessário para o processamento clássico dos resultados de medição para determinar operações corretivas para portas não-Clifford. A profundidade de reação total é calculada como a soma das profundidades dos componentes sequenciais, fornecendo um limite superior para o tempo de computação.

Principais Contribuições e Resultados

1. Sub-rotinas Aritméticas de Baixo Nível
O artigo apresenta circuitos otimizados para operações fundamentais, verificados via simulação Qiskit:

• Incremento & Incremento Controlado: Modificados para utilizar portas AND temporárias, reduzindo a contagem de T para $7n - 14$ (para incremento) e $7n - 7$ (para incremento controlado).
• Deslocamentos (Shifts): Demonstrou-se que, em arquiteturas de volume ativo, deslocamentos não controlados são "gratuitos" (custo zero de bloco lógico) via renomeação; deslocamentos controlados são otimizados usando fusões de spiders ZX, embora a redução na contagem de blocos seja marginal comparada à versão não otimizada.
• Adição/Subtração Controlada (CAS): Um novo somador controlado no estilo de Gidney é desenhado. Ele alcança uma redução de $\approx 8\%$ no volume ativo em comparação com uma soma direta de custos, com uma contagem de T de $7n - 7$.
• Multiplicação: É proposto um novo multiplicador utilizando uma matriz Toffoli e somadores de Overflow Controlado de Gidney (COG). Ele alcança uma redução de 62% no fator de liderança da contagem de T em comparação com o design de estado da arte de Muñoz-Coreas & Thapliyal [21].
• Quadrado (Squaring): Otimizado ao trocar contagem de qubits por portas CNOT, reduzindo o requisito de qubits de $6n+2$ para $5n$ para multiplicação, com ajustes específicos para o cálculo do quadrado.

2. Sub-rotinas Aritméticas de Alto Nível
O autor estende estes componentes de baixo nível para funções complexas:

• Raiz Quadrada: Um algoritmo de raiz quadrada não-restaurador otimizado é apresentado. Ele reduz significamente a contagem de T em comparação com o design de liderança [19], embora requeira ligeiramente mais qubits ($3n$ vs $2n+1$).
• Trigonometria (Avaliação de Polinómio por Partes - PPE): O artigo adapta o circuito de Häner. Ao substituir os somadores e multiplicadores originais pelas versões otimizadas do autor (somador OG, multiplicador COG) e um novo comparador, a contagem de T é reduzida em aproximadamente 2/3 nos termos de liderança em comparação com a implementação original [20].
• Trigonometria Inversa (Arco Seno): Um circuito combinando avaliação polinomial e raiz quadrada é construído. O novo design alcança uma redução de quase 6 vezes no termo $n^2$ da contagem de T em comparação com a implementação de Häner [20].
• Logaritmo: Uma implementação do método qFBE de Wang et al. é adaptada para computação de volume ativo. O artigo fornece as primeiras estimativas de volume ativo e contagem de T para este método, observando que é $O(n^3)$ em operações quânticas.

3. Sensibilidade Estrutural do Volume Ativo
Uma descoberta crítica é que a estrutura do circuito impacta o volume ativo independentemente das contagens de portas. O autor demonstra que circuitos logicamente equivalentes com contagens de portas idênticas podem ter volumes ativos diferentes devido ao arranjo de controles e alvos. Especificamente, designs que maximizam linhas ininterruptas de controles e alvos permitem fusões de spiders mais eficientes no cálculo ZX, reduzindo a contagem de blocos. Isto sugere que otimizar apenas para contagem de portas é insuficiente para arquiteturas de volume ativo.

Significância e Alegações

O artigo afirma fornecer uma "metodologia simples" para estimar e otimizar volumes ativos usando diagramas ZX orientados. A sua principal significância reside em:

• Redução de Recursos: Redução significativa das contagens de T e volumes ativos para uma vasta gama de sub-rotinas aritméticas, que são os blocos de construção para grandes algoritmos quânticos (ex: fatoração, HHL).
• Consciência Arquitetural: Destacar que a métrica de "volume ativo" é sensível à topologia do circuito, não apenas à complexidade de portas. Isto exige uma mudança na forma como os circuitos são desenhados para arquiteturas com conectividade de longo alcance.
• Expansão do Catálogo: Fornecer um recurso necessário de sub-rotinas otimizadas (incluindo funções de alto nível como $\log x$ e $\arcsin x$) que anteriormente eram escassas no contexto de computação de volume ativo.

O autor conclui que, embora o seu trabalho se foque em contagens de T e volumes ativos, trabalhos futuros também deverão considerar a otimização de portas Clifford e a inclusão de outras sub-rotinas de baixo nível, como somadores de busca de carry (carry look-ahead) e circuitos de divisão. Eles não alegam ter resolvido todos os problemas de estimativa de recursos, mas pretendem estimular investigações adicionais sobre o design de circuitos conscientes de AV.