Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

Resumo Técnico: Síntese Eficiente de Portas Toffoli Multicontroladas com Portas Clifford+P9 Ternárias

Definição do Problema
Portas Toffoli multicontroladas (MCT) são primitivas fundamentais no design de circuitos quânticos, essenciais para aritmética reversível, construção de oráculos e amplificação de amplitude. No entanto, sua decomposição torna-se progressivamente mais dispendiosa em termos de recursos à medida que o número de qubits de controle cresce. Em arquiteturas tolerantes a falhas, operações não-Clifford (como portas Toffoli) exigem preparação de estados de recurso e injeção custosas. Abordagens convencionais puramente binárias tipicamente decompõem MCTs em portas Toffoli menores e, posteriormente, em conjuntos Clifford+T, incorrendo em um compromisso entre o custo de portas T, requisitos de qubits auxiliares e profundidade do circuito. Embora construções binárias recentes usando ancilas condicionalmente limpas alcancem profundidade logarítmica, elas dependem de descomputação assistida por medição e feed-forward clássico, introduzindo sobrecargas relacionadas à latência de medição e escalonamento coerente. Alternativamente, existem métodos de síntese aproximada, mas que não fornecem construções exatas. O artigo aborda a necessidade de uma síntese de MCT exata e eficiente em recursos que evite a sobrecarga de medição enquanto melhora a profundidade e os requisitos de ancila em um cenário de tolerância a falhas.

Metodologia
Os autores propõem uma decomposição exata de portas MCT com entradas e saídas de subespaço binário utilizando a estrutura Clifford+P9 ternária. Esta abordagem aproveita a ocupação temporária do nível de qutrit não-computacional $|2\rangle$ como um espaço de trabalho, mantendo os estados lógicos codificados no subespaço binário $H_{bin} = \text{span}\{|0\rangle, |1\rangle\}$.

A metodologia central envolve uma decomposição em árvore hierárquica:

1. Primitivas: A construção utiliza três operações elementares: uma porta SUM ternária (Clifford), um incremento controlado seletivo ao estado $C_2(\text{INC})$ (não-Clifford) e um toggle estrito controlado do alvo binário $C_2(X_{01})$ (não-Clifford). O custo de recurso é medido pelo número de injeções lógicas de P9 necessárias para implementar as portas não-Clifford.
2. Estrutura de Árvore: Em vez de extensão recursiva sequencial, os controles são avaliados através de uma árvore balanceada.
   • Blocos de Folha: Grupos de três controles binários são verificados em paralelo. Um bloco de folha utiliza uma porta SUM e um $C_2(\text{INC})$ para marcar temporariamente um qutrit de controle com o estado $|2\rangle$ se, e somente se, todas as três entradas forem $|1\rangle$.
   • Blocos de Fusão (Merge Blocks): Nós internos combinam resultados de duas subárvores filhas e um controle adicional. Isso utiliza um qutrit auxiliar limpo (inicializado em $|0\rangle$) e três portas $C_2(\text{INC})$. Se ambos os marcadores das subárvores filhas forem $|2\rangle$ e o controle do meio for $|1\rangle$, a ancila atinge o estado $|2\rangle$, que então dispara o controle do meio para atingir $|2\rangle$.
   • Operação de Raiz: Uma vez que o marcador da raiz atinge $|2\rangle$ (indicando que todos os controles estão ativos), um único toggle estrito $C_2(X_{01})$ inverte o qubit alvo.
   • Descomputação: O circuito é revertido para restaurar todos os marcadores temporários e qutrits auxiliares para $|0\rangle$.

Principais Contribuições e Resultados
O artigo fornece uma análise de recursos exata para larguras de controle balanceadas $n = 2^h - 1$ e estende a construção para larguras arbitrárias.

• Eficiência de Recursos para Larguras Balanceadas ($n = 2^h - 1$):

  • Contagem de P9: A construção requer $6n + 3$ injeções lógicas de P9. Isso corresponde à contagem exata de P9 do estado da arte de baseline sem ancila recursivamente estendida (Baseline B) derivada de Bocharov et al. [16].
  • Qutrits Auxiliares: A construção requer $\frac{n-3}{4}$ qutrits auxiliares limpos. Isso é assintoticamente um quarto dos $n-2$ ancilas exigidos pela Baseline B.
  • Profundidade do Circuito: Ao avaliar subárvores independentes em paralelo, a profundidade é reduzida de linear $\Theta(n)$ para logarítmica $\Theta(\log n)$.

• Fronteira de Compromisso (Trade-off):
  O artigo identifica um compromisso construtivo entre o espaço de trabalho de ancila e o custo não-Clifford. Ao reutilizar qutrits auxiliares (reduzindo o número de ancilas simultaneamente vivos $A$), a contagem de P9 aumenta. Especificamente, usar apenas uma ancila reutilizada ($A=1$) resulta em uma contagem de P9 de $9n - 18$ e uma profundidade de $\Theta(n)$, enquanto manter $I(n)$ ancilas minimiza a contagem de P9 para $6n+3$.

• Larguras de Controle Arbitrárias:
  Para $n$ arbitrário, os autores estendem a construção selecionando um núcleo balanceado de largura $m = 2^h - 1 \leq n$ e anexando sequencialmente os $n-m$ controles restantes. Isso preserva a contagem de P9 de $6n+3$, mas resulta em uma profundidade de $O(\log m + n - m)$. No pior caso (por exemplo, $n = 2^{h+1}-2$), a profundidade escala linearmente com $n$.

Significância e Alegações
O artigo alega que a decomposição proposta fornece um bloco de construção prático para o design e compilação de algoritmos quânticos mais eficientes em recursos no regime de tolerância a falhas. Sua principal significância reside em:

1. Redução de Profundidade: Substituir a profundidade linear das baselines ternárias recursivas por profundidade logarítmica para entradas balanceadas sem depender de medição ou feed-forward.
2. Redução de Ancila: Reduzir o requisito assintótico de qutrits auxiliares limpos por um fator de quatro em comparação com as melhores baselines recursivas exatas existentes, mantendo o mesmo custo não-Clifford (P9).
3. Síntese Exata: Oferecer uma estratégia de construção exata que incorpora informação binária em sistemas multinível, distinta de regimes de síntese aproximada.

Os autores observam que, embora o caso balanceado ofereça profundidade logarítmica, a profundidade de pior caso para larguras arbitrárias permanece linear. Eles sugerem que trabalhos futuros poderiam explorar modelos de custo de tolerância a falhas mais detalhados (incluindo destilação de estado mágico e roteamento), configurações alternativas de qutrit intermediário e integração em subrotinas reversíveis maiores, como circuitos aritméticos.