Resumo Técnico: Hierarquia NPA para Indistinguibilidade de Isomorfismo e Homomorfismo Quântico

1. Enunciado do Problema e Motivação

O artigo aborda a caracterização computacional e estrutural do isomorfismo quântico entre grafos. Dois grafos $G$ e $H$ são quânticos isomórficos ($G \cong_q H$) se existe uma estratégia quântica perfeita para o jogo de isomorfismo de grafos, envolvendo emaranhamento compartilhado e medições locais.

Embora o isomorfismo de grafos clássico seja decidível (resolvível em tempo quase polinomial), Mančinska e Roberson [FOCS'20] provaram que decidir o isomorfismo quântico é indecidível em geral. Isso motiva o estudo de relaxações do isomorfismo quântico, especificamente a hierarquia NPA (nomeada em homenagem a Navascués, Pironio e Acín), que fornece uma sequência de relaxações de programação semidefinida (SDP) para aproximar correlações quânticas.

Uma questão central na teoria emergente da indistinguibilidade de homomorfismo é se a viabilidade de cada nível dessas relaxações de SDP pode ser caracterizada combinatoriamente. Especificamente, os autores perguntam: A viabilidade do $k$-ésimo nível da hierarquia NPA para o jogo de isomorfismo $(G, H)$ é equivalente a $G$ e $H$ serem indistinguíveis por homomorfismo sobre uma classe específica de grafos?

2. Metodologia e Técnicas de Prova

O artigo emprega uma síntese de combinatória algébrica, teoria de operadores e teoria dos grafos. A metodologia central baseia-se na correspondência entre grafos bilabelados e tensores de homomorfismo.

Ferramentas Principais

• Grafos Bilabelados e Tensores de Homomorfismo: Um grafo $(k, l)$-bilabelado $F = (F, u, v)$ é associado a um tensor $F^G \in \mathbb{C}^{V(G)^k \times V(G)^l}$, onde as entradas contam homomorfismos que mapeiam os rótulos de entrada $u$ para $x$ e os rótulos de saída $v$ para $y$. Operações combinatórias em grafos bilabelados (composição em série, composição paralela, permutação cíclica de rótulos) correspondem a operações algébricas nesses tensores (multiplicação de matrizes, produto de Schur, permutação).
• Reformulação da Hierarquia NPA: Os autores reformulam a existência de um certificado para o $k$-ésimo nível da hierarquia NPA como a existência de um mapa de isomorfismo quântico de nível-$k$. Este é um mapa completamente positivo entre álgebras de matrizes que preserva propriedades estruturais específicas relacionadas aos tensores de homomorfismo.
• Equivalência Algébrica $k$: Eles introduzem o conceito de equivalência algébrica $k$, definida como um isomorfismo de álgebra entre subálgebras geradas por tensores de homomorfismo de um conjunto específico de grafos atômicos, satisfazendo condições de preservação de traço e unitariedade.

Estrutura da Prova

A prova do teorema principal procede através de uma cadeia de equivalências:

1. Viabilidade NPA $\iff$ Mapa de Isomorfismo Quântico: Uma submatriz principal de um certificado NPA é interpretada como a matriz de Choi de um mapa completamente positivo. As restrições da hierarquia NPA são mostradas como equivalentes aos axiomas de um mapa de isomorfismo quântico de nível-$k$ (Teorema 3.6).
2. Mapa de Isomorfismo Quântico $\iff$ Equivalência Algébrica $k$: O mapa de isomorfismo quântico é mostrado como restringindo-se a um isomorfismo entre as álgebras geradas pelos tensores de homomorfismo de um conjunto específico de grafos atômicos, $Q_k$ (Teorema 3.9).
3. Equivalência Algébrica $k$ $\iff$ Indistinguibilidade de Homomorfismo: Usando a correspondência entre operações de grafos e álgebra tensorial, a existência de tal isomorfismo de álgebra é mostrada como equivalente a $G$ e $H$ terem contagens de homomorfismo iguais a partir de uma classe construída de grafos, $P_k$ (Teorema 4.4).

3. Contribuições Principais e Resultados

Teorema Principal (Teorema 1.1)

Para grafos $G$ e $H$ e um inteiro $k \ge 1$, os seguintes são equivalentes:

1. O $k$-ésimo nível da hierarquia NPA para o jogo de isomorfismo $(G, H)$ é viável.
2. Existe um mapa de isomorfismo quântico de nível-$k$ de $G$ para $H$.
3. $G$ e $H$ são algebricamente $k$-equivalentes.
4. $G$ e $H$ são indistinguíveis por homomorfismo sobre a classe de grafos $P_k$.

Aqui, $P_k$ é uma classe de grafos planares bilabelados construída indutivamente a partir de grafos atômicos $Q_k$ usando composição em série, composição paralela com grafos atômicos específicos e permutação cíclica de rótulos.

Propriedades da Classe de Grafos $P_k$

• Planaridade: Todo grafo em $P_k$ é planar (Lema 4.7).
• Treewidth Limitado: Os grafos subjacentes de $P_k$ têm treewidth no máximo $3k-1$ (Lema 4.5).
• Fechado sob Minores: A classe $P_k$ é fechada sob a tomada de seus minores (Lema 4.8).
• União: A união dos grafos subjacentes não rotulados de todos os $P_k$ (para $k \in \mathbb{N}$) é exatamente o conjunto de todos os grafos planares (Corolário 4.12).

Resultado Algorítmico (Teorema 1.2)

O artigo apresenta um algoritmo de tempo polinomial randomized para decidir a viabilidade exata do $k$-ésimo nível da hierarquia NPA para um $k$ fixo.

• Tempo de Execução: $n^{O(k)} k^{O(1)}$, onde $n = \max\{|V(G)|, |V(H)|\}$.
• Método: Em vez de resolver o SDP, o algoritmo verifica a indistinguibilidade por homomorfismo sobre $P_k$ módulo um primo $p$ escolhido aleatoriamente. Ele calcula uma base para o espaço vetorial gerado pelos tensores de homomorfismo de grafos em $P_k$ sobre um corpo finito.
• Significância: Isso evita os problemas de aproximação inerentes aos resolvedores de SDP padrão (como o método elipsoide) e fornece um procedimento de decisão exato para níveis fixos.

Prova Alternativa de Mančinska e Roberson [FOCS'20]

Combinando o teorema principal com a convergência da hierarquia NPA e o fato de que $\bigcup_k P_k$ é o conjunto de todos os grafos planares, os autores derivam uma nova prova de que $G \cong_q H$ se, e somente se, $G$ e $H$ são indistinguíveis por homomorfismo sobre todos os grafos planares.

• Distinção: Ao contrário da prova original em [FOCS'20], que dependia fortemente da teoria de grupos quânticos compactos e intertwinadores, esta prova é puramente combinatória e algébrica, utilizando a hierarquia NPA e tensores de homomorfismo.

4. Significância e Alegações

O artigo afirma fornecer uma caracterização de indistinguibilidade de homomorfismo para a hierarquia NPA, colocando as relaxações de isomorfismo quântico dentro do quadro teórico mais amplo das relações de indistinguibilidade de homomorfismo.

• Unificação Teórica: Ele une a lacuna entre a hierarquia NPA não-comutativa e a hierarquia Lasserre clássica (que foi anteriormente caracterizada por Roberson e Seppelt [ICALP'23] usando classes de grafos $L_k$).
• Vantagem Computacional: Estabelece que a viabilidade exata para níveis fixos da hierarquia NPA é decidível em tempo polinomial randomized, um resultado que não é imediatamente óbvio apenas a partir da formulação de SDP.
• Simplificação da Teoria de Isomorfismo Quântico: O artigo oferece uma prova da caracterização fundamental do isomorfismo quântico (via grafos planares) que evita a "máquina pesada" de grupos quânticos, baseando-se na estrutura combinatória das restrições NPA.

Os autores observam que, embora $P_k$ seja uma subclasse de grafos planares com treewidth limitado, a relação estrutural precisa entre a classe de grafos $P_k$ e as classes de grafos $L_k$ (usadas para relaxações de isomorfismo clássico) permanece um problema em aberto (Problema 6.1). Eles também questionam se existe uma classe de grafos onde o isomorfismo quântico é determinado por um nível fixo da hierarquia NPA, mas difere do isomorfismo clássico (Problema 6.2).