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

Resumen Técnico: La Distancia-CNOT es NP-completa bajo conectividad todos-contra-todos

Planteamiento del Problema
El artículo aborda la complejidad computacional del problema de la Distancia-CNOT. Dada una matriz binaria invertible $A \in GL(N, 2)$ representada explícitamente y un entero $K$, el problema pregunta si $A$ puede implementarse mediante un circuito de como máximo $K$ puertas CNOT en $N$ hilos fijos y etiquetados con conectividad todos-contra-todos. El modelo asume la ausencia de hilos ancilares (aunque se consideran variantes con ancillas), sin restricciones de no-cancelación y sin un orden de puerta prescrito. El objetivo es determinar el recuento mínimo de puertas (longitud de palabra en el grafo de Cayley de $GL(N, 2)$ generado por transvecciones) requerido para sintetizar $A$.

Si bien la eliminación gaussiana proporciona un límite superior de $O(N^2)$ y existen algoritmos mejorados para límites de peor caso, la complejidad de encontrar el recuento de puertas exacto para una instancia específica sigue sin resolverse. Los resultados de dureza previos se han centrado en topologías restringidas, redes de paridad con codificaciones de entrada específicas o conjuntos de puertas que incluyen Clifford+T. La dureza específica de la síntesis CNOT de etiquetas fijas y todos-contra-todos era una cuestión abierta.

Metodología
Los autores demuestran la NP-completitud mediante una reducción del problema de Cobertura de Vértices Mínima en grafos simples finitos.

1. Construcción de Matrices Objetivo:
   Para un grafo dado $G = (V, E)$, los autores construyen una matriz un triangular superior específica $A_G \in GL(2|V| + |E| + 1, 2)$. La matriz actúa sobre un conjunto de hilos que incluye un hilo distinguido $z$, pares de hilos $(q_v, x_v)$ para cada vértice $v \in V$, y un hilo $y_e$ para cada arista $e \in E$. La transformación se define de tal manera que:

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

2. Identidad de Distancia Exacta:
   El núcleo de la prueba establece la identidad exacta:
   $$\ell_{\text{CNOT}}(A_G) = 2|V| + 2|E| + \tau(G)$$
   donde $\tau(G)$ es el tamaño de la cobertura de vértices mínima de $G$.

3. Construcción del Límite Superior:
   Los autores demuestran que cualquier cobertura de vértices $C$ produce un circuito CNOT de longitud $2|V| + 2|E| + |C|$. En esta construcción, los hilos de vértices seleccionados transportan temporalmente la contribución de $z$ a las salidas de las aristas incidentes, implementando efectivamente las paridades requeridas.

4. Límite Inferior mediante Proyección-Contracción:
   El límite inferior es la contribución novedosa. Los autores muestran que cualquier circuito CNOT arbitrario que implemente $A_G$ (incluso con cancelaciones y reutilización intermedia) puede "desplegarse" en un grafo acíclico dirigido (DAG) de XOR. Al aplicar proyección (establecer entradas específicas en cero) y contracción (fusionar nodos con valores proyectados idénticos), eliminan sistemáticamente los componentes de "contabilidad reversible" del circuito.

   • Proyectar las entradas de los vértices fuerza la eliminación de $2|V|$ nodos.
   • Proyectar las entradas privadas de las aristas fuerza la eliminación de $|E|$ nodos.
   • La estructura restante es un programa de línea recta de XOR que computa el conjunto de formas $F_G = \{z + x_u + x_v \mid \{u,v\} \in E\}$.
   • Utilizando un lema de especialización binaria del lema de Boyar-Matthews-Peralta, se demuestra que la longitud de este programa restante es al menos $|E| + \tau(G)$.
   • Combinar esto produce el límite inferior $L \ge 2|V| + 2|E| + \tau(G)$.

5. Robustez de Ancillas:
   Los autores prueban que la adición de cualquier número finito de hilos ancilares limpios o prestados no reduce el recuento de puertas óptimo para esta familia de matrices. El argumento de proyección-contracción se extiende a estos casos tratando las variables ancilares como entradas adicionales para proyectar.

Contribuciones Clave y Resultados

• NP-Completitud: Se demuestra que el problema de la Distancia-CNOT es NP-completo. Esto se mantiene incluso para instancias altamente restringidas donde:
  • $A$ es un triangular superior unitaria.
  • Cada fila tiene un peso de Hamming de como máximo 4.
  • $A$ tiene orden exacto 4 (es decir, $(A-I)^3=0$ y $A^4=I$).
  • El presupuesto de puertas $K < 2N$.
• Dureza de la Computación Exacta: Calcular la distancia CNOT exacta $\ell_{\text{CNOT}}(A)$ es NP-duro.
• Dureza de la Aproximación:
  • Aditiva: Es NP-duro aproximar la distancia dentro de cualquier constante aditiva fija $c$.
  • Multiplicativa: El problema de optimización es APX-duro (mediante una reducción L desde Cobertura de Vértices Mínima en grafos cúbicos), lo que implica que no existe un Esquema de Aproximación en Tiempo Polinomial (PTAS) a menos que P=NP.
• Invarianza de Ancillas: Para la familia construida $A_G$, el recuento mínimo de puertas es idéntico para los modelos sin ancillas, con ancillas limpias y con ancillas prestadas.
• Decodificador Constructivo: La reducción incluye un decodificador de tiempo polinomial que, dado cualquier circuito CNOT para $A_G$, extrae una cobertura de vértices para $G$ cuyo tamaño está acotado por la longitud del circuito menos un factor constante. Esto es crucial para establecer la reducción L para la dureza de APX.

Significado y Reivindicaciones
Este artículo resuelve la pregunta básica de si la síntesis de CNOT de tamaño mínimo sigue siendo computacionalmente difícil cuando se eliminan las restricciones arquitectónicas (enrutamiento, disponibilidad de puertas). Los autores afirman que la dureza surge intrínsecamente de la minimización de la propia implementación lineal-reversible, no de la geometría de un dispositivo específico.

Los resultados aclaran el límite entre la síntesis tratable e intratable:

• El problema sigue siendo difícil incluso para matrices dispersas y estructuradas (triangulares superiores con bajo peso de Hamming).
• La dureza persiste independientemente del uso de hilos ancilares (limpios o prestados), siempre que deban ser restaurados.
• La técnica de proyección-contracción proporciona un método general para extraer núcleos no reversibles (como la complejidad XOR) de implementaciones reversibles arbitrarias, lo que sugiere que las cancelaciones y la reutilización intermedia no eluden la dificultad combinatoria fundamental del problema.

Los autores señalan que, si bien este resultado implica NP-dureza para cualquier familia de arquitectura que pueda embeber un grafo bidireccional completo (vía la propiedad de uniformidad de la reducción), no determina la complejidad para topologías dispersas fijas específicas (por ejemplo, caminos o estrellas), ya que restringir el conjunto generador cambia enteramente la métrica de distancia.