Resumen Técnico: Jerarquía NPA para la Indistinguibilidad de Isomorfismo y Homomorfismo Cuántico

1. Planteamiento del Problema y Motivación

El artículo aborda la caracterización computacional y estructural del isomorfismo cuántico entre grafos. Dos grafos $G$ y $H$ son cuánticamente isomórficos ($G \cong_q H$) si existe una estrategia cuántica perfecta para el juego de isomorfismo de grafos, que involucra entrelazamiento compartido y mediciones locales.

Mientras que el isomorfismo de grafos clásico es decidible (resoluble en tiempo cuasi-polinomial), Mančinska y Roberson [FOCS'20] demostraron que decidir el isomorfismo cuántico es indecidible en general. Esto motiva el estudio de las relajaciones del isomorfismo cuántico, específicamente la jerarquía NPA (nombrada por Navascués, Pironio y Acín), que proporciona una secuencia de relajaciones de programación semidefinida (SDP) para aproximar correlaciones cuánticas.

Una cuestión central en la teoría emergente de la indistinguibilidad de homomorfismos es si la factibilidad de cada nivel de estas relajaciones SDP puede caracterizarse combinatoriamente. Específicamente, los autores preguntan: ¿Es la factibilidad del $k$-ésimo nivel de la jerarquía NPA para el juego de $(G, H)$-isomorfismo equivalente a que $G$ y $H$ sean indistinguibles por homomorfismo sobre una clase específica de grafos?

2. Metodología y Técnicas de Demostración

El artículo emplea una síntesis de combinatoria algebraica, teoría de operadores y teoría de grafos. La metodología central se basa en la correspondencia entre grafos bilabelados y tensores de homomorfismo.

Herramientas Clave

• Grafos Bilabelados y Tensores de Homomorfismo: Un grafo $(k, l)$-bilabelado $F = (F, u, v)$ se asocia con un tensor $F^G \in \mathbb{C}^{V(G)^k \times V(G)^l}$, donde las entradas cuentan los homomorfismos que mapean las etiquetas de entrada $u$ a $x$ y las etiquetas de salida $v$ a $y$. Las operaciones combinatorias en grafos bilabelados (composición en serie, composición en paralelo, permutación cíclica de etiquetas) corresponden a operaciones algebraicas en estos tensores (multiplicación de matrices, producto de Schur, permutación).
• Reformulación de la Jerarquía NPA: Los autores reformulan la existencia de un certificado para el $k$-ésimo nivel de la jerarquía NPA como la existencia de un mapa de isomorfismo cuántico de nivel-$k$. Este es un mapa completamente positivo entre álgebras de matrices que preserva propiedades estructurales específicas relacionadas con los tensores de homomorfismo.
• $k$-Equivalencia Algebraica: Introducen el concepto de $k$-equivalencia algebraica, definida como un isomorfismo de álgebra entre subálgebras generadas por tensores de homomorfismo de un conjunto específico de grafos atómicos, satisfaciendo condiciones de preservación de traza y de unidad.

Estructura de la Demostración

La demostración del teorema principal procede a través de una cadena de equivalencias:

1. Factibilidad NPA $\iff$ Mapa de Isomorfismo Cuántico: Una submatriz principal de un certificado NPA se interpreta como la matriz de Choi de un mapa completamente positivo. Se muestra que las restricciones de la jerarquía NPA son equivalentes a los axiomas de un mapa de isomorfismo cuántico de nivel-$k$ (Teorema 3.6).
2. Mapa de Isomorfismo Cuántico $\iff$ $k$-Equivalencia Algebraica: Se muestra que el mapa de isomorfismo cuántico se restringe a un isomorfismo entre las álgebras generadas por los tensores de homomorfismo de un conjunto específico de grafos atómicos, $Q_k$ (Teorema 3.9).
3. $k$-Equivalencia Algebraica $\iff$ Indistinguibilidad por Homomorfismo: Utilizando la correspondencia entre operaciones de grafos y álgebra tensorial, se muestra que la existencia de tal isomorfismo de álgebra es equivalente a que $G$ y $H$ tengan conteos de homomorfismo iguales desde una clase construida de grafos, $P_k$ (Teorema 4.4).

3. Contribuciones Principales y Resultados

Teorema Principal (Teorema 1.1)

Para grafos $G$ y $H$ y un entero $k \ge 1$, los siguientes puntos son equivalentes:

1. El $k$-ésimo nivel de la jerarquía NPA para el juego de $(G, H)$-isomorfismo es factible.
2. Existe un mapa de isomorfismo cuántico de nivel-$k$ de $G$ a $H$.
3. $G$ y $H$ son algebraicamente $k$-equivalentes.
4. $G$ y $H$ son indistinguibles por homomorfismo sobre la clase de grafos $P_k$.

Aquí, $P_k$ es una clase de grafos planos bilabelados construidos inductivamente a partir de grafos atómicos $Q_k$ mediante composición en serie, composición en paralelo con grafos atómicos específicos y permutaciones cíclicas de etiquetas.

Propiedades de la Clase de Grafos $P_k$

• Planaridad: Cada grafo en $P_k$ es plano (Lema 4.7).
• Ancho de Árbol (Treewidth) Acotado: Los grafos subyacentes de $P_k$ tienen un ancho de árbol de como máximo $3k-1$ (Lema 4.5).
• Cerrada bajo Minores: La clase $P_k$ es cerrada bajo la toma de menores (Lema 4.8).
• Unión: La unión de los grafos no etiquetados de todas las $P_k$ (para $k \in \mathbb{N}$) es exactamente el conjunto de todos los grafos planos (Corolario 4.12).

Resultado Algorítmico (Teorema 1.2)

El artículo presenta un algoritmo de tiempo polinomial aleatorizado para decidir la factibilidad exacta del $k$-ésimo nivel de la jerarquía NPA para un $k$ fijo.

• Tiempo de Ejecución: $n^{O(k)} k^{O(1)}$, donde $n = \max\{|V(G)|, |V(H)|\}$.
• Método: En lugar de resolver la SDP, el algoritmo verifica la indistinguibilidad por homomorfismo sobre $P_k$ módulo un primo $p$ elegido al azar. Calcula una base para el espacio vectorial generado por los tensores de homomorfismo de los grafos en $P_k$ sobre un campo finito.
• Significancia: Esto evita los problemas de aproximación inherentes a los resolvedores SDP estándar (como el método elipsoide) y proporciona un procedimiento de decisión exacto para niveles fijos.

Demostración Alternativa de Mančinska y Roberson [FOCS'20]

Combinando el teorema principal con la convergencia de la jerarquía NPA y el hecho de que $\bigcup_k P_k$ es el conjunto de todos los grafos planos, los autores derivan una nueva prueba de que $G \cong_q H$ si y solo si $G$ y $H$ son indistinguibles por homomorfismo sobre todos los grafos planos.

• Distinción: A diferencia de la prueba original en [FOCS'20], que dependía fuertemente de la teoría de grupos cuánticos compactos e intervinientes, esta prueba es puramente combinatoria y algebraica, utilizando la jerarquía NPA y los tensores de homomorfismo.

4. Significancia y Reivindicaciones

El artículo afirma proporcionar una caracterización de la indistinguibilidad por homomorfismo para la jerarquía NPA, situando las relajaciones de isomorfismo cuántico dentro del marco teórico más amplio de las relaciones de indistinguibilidad por homomorfismo.

• Unificación Teórica: Cierra la brecha entre la jerarquía NPA no conmutativa y la jerarquía de Lasserre clásica (que fue caracterizada previamente por Roberson y Seppelt [ICALP'23] usando clases de grafos $L_k$).
• Ventaja Computacional: Establece que la factibilidad exacta para niveles fijos de la jerarquía NPA es decidible en tiempo polinomial aleatorizado, un resultado que no es inmediatamente obvio solo desde la formulación de la SDP.
• Simplificación de la Teoría del Isomorfismo Cuántico: El artículo ofrece una prueba de la caracterización fundamental del isomorfismo cuántico (vía grafos planos) que evita la "maquinaria pesada" de los grupos cuánticos, apoyándose en la estructura combinatoria de las restricciones NPA.

Los autores señalan que, aunque $P_k$ es una subclase de grafos planos con ancho de árbol acotado, la relación estructural precisa entre la clase $P_k$ y las clases de grafos $L_k$ (usadas para las relajaciones de isomorfismo clásico) sigue siendo un problema abierto (Problema 6.1). También plantean la pregunta de si existe una clase de grafos donde el isomorfismo cuántico esté determinado por un nivel fijo de la jerarquía NPA pero difiera del isomorfismo clásico (Problema 6.2).