Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks

Resumo Técnico: Seleção de Decomposição Verificada por Contexto e Consciente de Orçamento de Erro para Redes Toffoli

1. Definição do Problema

No hardware quântico de curto prazo (NISQ), a falha do circuito é dominada por erros de portas de dois qubits, que são uma a duas ordens de magnitude piores do que os erros de um único qubit. Consequentemente, a fidelidade efetiva de um circuito compilado é governada pelo número e tipo de portas de dois qubits executadas. A porta Toffoli (CCX) é um primitivo fundamental para aritmética quântica e lógica reversível, admitindo várias decomposições que trocam ancilas, profundidade e contagens de portas de dois qubits.

O desafio central é que as decomposições conhecidas mais "baratas" — especificamente as Toffolis de fase relativa (que introduzem uma fase diagonal em um subconjunto de estados da base) e as Toffolis aproximadas (que introduzem erro limitado) — são corretas apenas em contextos específicos. Suas fases residuais devem ser descomputadas posteriormente ou seus erros devem permanecer dentro da tolerância nos estados específicos que a porta realmente encontra. As ferramentas existentes falham em preencher a lacuna entre:

• Otimizadores conscientes de contexto, mas não verificados (ex: QContext, templates de Maslov): Estes selecionam decomposções baratas e dependentes de contexto baseadas na contagem de portas, mas carecem de modelos de fidelidade de hardware e, crucialmente, não verificam se a decomposição escolhida é válida no contexto específico do circuito. Isso leva a erros "silenciosos" onde substituições de correspondência de padrão corrompem o circuito.
• Otimizadores verificados, mas sem consciência de contexto (ex: VOQC, Quartz): Estes provam que as reescritas são corretas, mas apenas como equivalências incondicionais e independentes de contexto, otimizando para contagem de portas em vez de infidelidade de hardware.

O resultado é um risco de segurança: a substituição agressiva e gananciosa de contagem por Toffolis de fase relativa pode ser silenciosamente incorreta se o circuito circundante não cancelar a fase residual.

2. Metodologia

Os autores apresentam um passo de compilador que seleciona decomposições por Toffoli para minimizar um orçamento de erro de infidelidade de dois qubits de hardware em vez da contagem de portas. O passo é construído sobre três pilares:

1. Análise de Contexto (Admissibilidade): Para cada porta Toffoli $g$, o passo computa o conjunto de decomposições admissíveis $A(g)$ baseado no circuito circundante:

   • Decomposições exatas são sempre admissíveis.
   • Decomposições de fase relativa são admissíveis se a fase diagonal residual $D$ for inobservável downstream (ex: cancelada por uma operação inversa subsequente em um par de computação/descomputação).
   • Decomposições aproximadas são admissíveis se o erro permanecer dentro da tolerância $\epsilon$ no subespaço alcançável $R(g)$ — o span dos estados que podem realmente alcançar a porta dado o circuito upstream e os estados iniciais das ancilas — em vez de todos os $2^n$ inputs.
   • O passo constrói $R(g)$ via propagação de conjuntos direta e segura sobre a base computacional, usando super-caixas afins como sobre-aproximações quando o conjunto de suporte se torna muito grande para garantir a segurança.

2. Porta de Verificação por Instância: Nenhuma regra estrutural é confiada implicitamente. Antes de comprometer uma substituição dependente de contexto, o passo descarrega uma obrigação de equivalência condicionada ao contexto:

   • Para fase relativa, verifica se a CCX original e a decomposição candidata produzem distribuições de medição idênticas nos inputs alcançáveis, contabilizando o cancelamento downstream.
   • Para aproximadas, verifica o limite de erro no subespaço alcançável.
   • A verificação é realizada exaustivamente (tabela de verdade/unitária) para janelas pequenas ou via backends de diagramas de decisão (MQT QCEC) ou normalização ZX para janelas maiores. Se uma verificação falhar, o passo retorna à alternativa mais barata certificada (geralmente uma decomposição exata).

3. Objetivo de Orçamento de Erro: O seletor minimiza a infidelidade de dois qubits somada $B = \sum_g I(d_g)$, onde $I(d)$ é a soma das infidelidades das portas de dois qubits na decomposição $d$. Este objetivo é específico para o hardware, utilizando taxas de erro calibradas para o dispositivo alvo. A seleção é gananciosa e ótima para casos separáveis; se o compartilhamento de ancilas criar restrições, ela é formulada como um Programa Linear Inteiro (ILP).

3. Principais Contribuições

O artigo apresenta quatro contribuições primárias:

1. Primeiro Seletor Dirigido por Orçamento de Erro: Um passo de compilador que otimiza para infidelidade de dois qubits de hardware em vez de contagem de portas, especificamente para a seleção de Toffoli dependente de contexto.
2. Camada de Verificação por Instância: Um mecanismo que admite decomposições de fase relativa ou de subespaço alcançável apenas após cumprir uma obrigação de equivalência condicionada ao contexto, tornando a seleção agressiva segura. Isso inclui um teorema de segurança (Teorema 1) e uma composição de orçamento de erro limitado (Corolário 1).
3. Critério de Admissibilidade de Subespaço Alcançável: Um centro técnico que certifica decomposições contra os estados realmente alcançáveis em contexto, em vez de todos os inputs. Isso permite "controle exato no alcançável" (removendo Toffolis com controles comprovadamente constantes) e admite mais decomposições do que a compilação aproximada de unidade inteira.
4. Resultado de Segurança: A demonstração de que a substituição de fase relativa por correspondência de padrão é silenciosamente incorreta na prática. Os autores mostram que um otimizador aberto de correspondência de padrão contém 66 reescritas de biblioteca não equivalentes, e uma abordagem gananciosa de contagem corrompe silenciosamente 6 de 12 circuitos de benchmark, enquanto o passo com portão certifica 0 erros.

4. Resultados

A avaliação foi conduzida em dois conjuntos: um conjunto de 12 circuitos (até 8 qubits) para verificação exaustiva e um conjunto de 20 circuitos (12–24 qubits) para escalabilidade.

• Segurança: O passo com portão elimina todos os erros silenciosos. Enquanto a substituição gananciosa de contagem e a análise de contexto sem verificação corromperam 6 de 12 circuitos, o passo completo com portão introduziu 0 erros.
• Redução do Orçamento de Erro:
  • No conjunto de 12 circuitos (pesado em computação/descomputação), o passo com portão alcançou uma redução de 39,5% em portas de dois qubits e uma redução de 36,7% na infidelidade estimada em comparação com as bases apenas exatas.
  • Comparado ao Qiskit opt-level-3 e tket, as reduções foram de aproximadamente 39% e 35%, respectivamente.
  • No conjunto maior de 12–24 qubits, a redução agregada foi de 15,6% em portas e 11,7% em infidelidade.
  • A redução é altamente dependente da carga de trabalho: oráculos de escada AND de Grover (totalmente pareados) viram ~49% de redução, somadores carry-lookahead ~28%, somadores ripple ~6% e multiplicadores de matriz 0% (pois seus ANDs são "vivos" e não podem ser simplificados).
• Escalabilidade: O backend de verificação escala efetivamente. Para circuitos de até 24 qubits, as verificações de diagrama de decisão certificaram cada substituição aceita em menos de 0,025 segundos. O cruzamento da verificação exaustiva para a de diagrama de decisão ocorre em torno de 11–12 qubits, proporcionando um aumento de velocidade de >3000x.
• Aplicação no Mundo Real: Em um circuito de reset de estado quântico (palavra de sincronização), o passo removeu 48,8% das portas nativas de dois qubits, com cada substituição verificada, tornando um experimento de sincronização limitado por orçamento viável.
• Relevância de Hardware: Nas taxas de erro atuais para dispositivos supercondutores (IBM, Google) e de íons aprisionados (IonQ, Quantinuum), as substituições certificadas reduzem a infidelidade estimada do circuito em 36–43%.

5. Significância e Alegações

O artigo afirma fechar a lacuna entre otimizadores conscientes de contexto, mas não verificados, e otimizadores verificados, mas sem consciência de contexto. Seu resultado central é uma garantia de segurança: a substituição de fase relativa por correspondência de padrão é inerentemente arriscada sem verificação por instância. Os autores afirmam que sua abordagem torna a seleção de Toffoli agressiva e orientada pela fidelidade comprovadamente segura por instância.

O trabalho não pretende resolver todos os problemas de otimização; ele nota explicitamente limitações:

• O regime de aproximação limitada (admitindo decomposições com $\epsilon > 0$) é atualmente inerte sob a análise de alcance baseada em conjuntos, pois o método rastreia estados da base, não amplitudes. Ativar essa troca requer um front-end de alcance consciente de amplitude, o que é deixado para trabalhos futuros.
• A redução em portas e infidelidade é estritamente uma função da estrutura do circuito (a fração de pares de computação/descomputação), não uma constante universal para todos os circuitos.

Os autores concluem que este framework fornece uma camada sólida e consciente do orçamento de erro que melhora a viabilidade de execuções de computação quântica física limitadas por orçamento de erro, com cada redução certificada como segura.