CNOT-Distance is NP-complete under all-to-all connectivity

Resumo Técnico: A Distância CNOT é NP-completa sob conectividade todos-para-todos

Enunciado do Problema
O artigo aborda a complexidade computacional do problema da Distância CNOT. Dada uma matriz binária invertível $A \in GL(N, 2)$ representada explicitamente e um inteiro $K$, o problema questiona se $A$ pode ser implementada por um circuito de no máximo $K$ portas CNOT em $N$ fios fixos e rotulados com conectividade todos-para-todos. O modelo assume a ausência de fios ancilares (embora variantes com ancilas sejam consideradas), sem restrições de não-cancelamento e sem ordem prescrita para as portas. O objetivo é determinar a contagem mínima de portas (comprimento de palavra no grafo de Cayley de $GL(N, 2)$ gerado por transveções) necessária para sintetizar $A$.

Embora a eliminação de Gauss forneça um limite superior de $O(N^2)$ e algoritmos aprimorados existam para limites de pior caso, a complexidade de encontrar a contagem exata de portas para uma instância específica permanece não resolvida. Resultados de dureza anteriores focaram em topologias restritas, redes de paridade com codificações de entrada específicas ou conjuntos de portas incluindo Clifford+T. A dureza específica da síntese CNOT de rótulos fixos e todos-para-todos era uma questão em aberto.

Metodologia
Os autores provam a NP-completude via uma redução do problema do Cobertura Mínima de Vértices em grafos simples finitos.

1. Construção de Matrizes Alvo:
   Para um determinado grafo $G = (V, E)$, os autores constroem uma matriz unitriangular superior específica $A_G \in GL(2|V| + |E| + 1, 2)$. A matriz atua sobre um conjunto de fios incluindo um fio distinguido $z$, pares de fios $(q_v, x_v)$ para cada vértice $v \in V$, e um fio $y_e$ para cada aresta $e \in E$. A transformação é definida de tal forma que:

   • $q'_v = q_v + z$
   • $x'_v = x_v + q_v$
   • $y'_e = y_e + z + x_u + x_v$ (para a aresta $e=\{u,v\}$)

2. Identidade de Distância Exata:
   O cerne da prova estabelece a identidade exata:
   $$\ell_{\text{CNOT}}(A_G) = 2|V| + 2|E| + \tau(G)$$
   onde $\tau(G)$ é o tamanho da cobertura mínima de vértices de $G$.

3. Construção do Limite Superior:
   Os autores demonstram que qualquer cobertura de vértices $C$ produz um circuito CNOT de comprimento $2|V| + 2|E| + \tau(G)$. Nesta construção, os fios dos vértices selecionados carregam temporariamente a contribuição de $z$ para as saídas das arestas incidentes, implementando efetivamente as paridades necessárias.

4. Limite Inferior via Projeção-Contração:
   O limite inferior é a contribuição inovadora. Os autores mostram que qualquer circuito CNOT arbitrário que implementa $A_G$ (mesmo com cancelamentos e reutilização intermediária) pode ser "desdobrado" em um grafo acíclico dirigido (DAG) de XOR. Ao aplicar projeção (definindo entradas específicas como zero) e contração (mesclando nós com valores projetados idênticos), eles removem sistematicamente os componentes de "contabilidade reversível" do circuito.

   • Projetar as entradas dos vértices força a deleção de $2|V|$ nós.
   • Projetar as entradas privadas das arestas força a deleção de $|E|$ nós.
   • A estrutura restante é um programa de linha reta XOR computando o conjunto de formas $F_G = \{z + x_u + x_v \mid \{u,v\} \in E\}$.
   • Usando um lema de especialização binária de Boyar-Matthews-Peralta, o comprimento deste programa restante é mostrado como sendo pelo menos $|E| + \tau(G)$.
   • Combinando estes, obtém-se o limite inferior $L \ge 2|V| + 2|E| + \tau(G)$.

5. Robustez de Ancila:
   Os autores provam que a adição de qualquer número finito de fios ancilares limpos ou emprestados não reduz a contagem de portas ótima para esta família de matrizes. O argumento de projeção-contração estende-se a estes casos ao tratar as variáveis ancilares como entradas adicionais para projeção.

Principais Contribuições e Resultados

• NP-Completude: O problema da Distância CNOT é provado como NP-completo. Isso se mantém mesmo para instâncias altamente restritas onde:
  • $A$ é unitriangular superior.
  • Cada linha tem peso de Hamming no máximo 4.
  • $A$ tem ordem exata 4 (ou seja, $(A-I)^3=0$ e $A^4=I$).
  • O orçamento de portas $K < 2N$.
• Dureza da Computação Exata: Calcular a distância CNOT exata $\ell_{\text{CNOT}}(A)$ é NP-difícil.
• Dureza de Aproximação:
  • Aditiva: É NP-difícil aproximar a distância dentro de qualquer constante aditiva fixa $c$.
  • Multiplicativa: O problema de otimização é APX-difícil (via uma redução L de Cobertura Mínima de Vértices em grafos cúbicos), implicando que não existe um Esquema de Aproximação de Tempo Polinomial (PTAS) a menos que P=NP.
• Invariância de Ancila: Para a família construída $A_G$, a contagem mínima de portas é idêntica para os modelos sem ancila, com ancila limpa e com ancila emprestada.
• Decodificador Construtivo: A redução inclui um decodificador de tempo polinomial que, dado qualquer circuito CNOT para $A_G$, extrai uma cobertura de vértices para $G$ cujo tamanho é limitado pelo comprimento do circuito menos um fator constante. Isso é crucial para estabelecer a redução L para a dureza APX.

Significado e Alegações
O artigo resolve a questão fundamental de se a síntese de CNOT de tamanho mínimo permanece computacionalmente difícil quando as restrições arquiteturais (roteamento, disponibilidade de portas) são removidas. Os autores alegam que a dificuldade surge intrinsecamente da minimização da própria implementação linear-reversível, e não da geometria de um dispositivo específico.

Os resultados esclarecem a fronteira entre a síntese tratável e a intratável:

• O problema permanece difícil mesmo para matrizes esparsas e estruturadas (unitriangular superior com baixo peso de Hamming).
• A dificuldade persiste independentemente do uso de fios ancilares (limpos ou emprestados), desde que devam ser restaurados.
• A técnica de projeção-contração fornece um método geral para extrair núcleos não-reversíveis (como complexidade XOR) de implementações reversíveis arbitrárias, sugerindo que cancelamentos e reutilizações intermediárias não contornam a dificuldade combinatória fundamental do problema.

Os autores observam que, embora o resultado implique NP-dureza para qualquer família de arquitetura que possa embarcar um grafo bidirecionado completo (via a propriedade de uniformidade da redução), ele não determina a complexidade para topologias esparsas fixas (como caminhos ou estrelas), pois restringir o conjunto gerador altera inteiramente a métrica de distância.