A Quantum-Inspired Algorithm for Graph Isomorphism

Resumo Técnico: Um Algoritmo Inspirado em Computação Quântica para Isomorfismo de Grafos

Enunciado do Problema
O artigo aborda o problema do Isomorfismo de Grafos (GI): determinar se dois grafos discretos são estruturalmente idênticos até uma permutação dos rótulos de seus vértices. Embora o problema não seja conhecido por ser NP-completo, encontrar um algoritmo geral de tempo polinomial continua sendo um desafio significativo na ciência da computação teórica. A abordagem clássica de estado da arte, o algoritmo de Babai (2015), opera em tempo quase-polinomial ($2^{O(\log V)^3}$). Os autores investigam se a era NISQ (Noisy Intermediate-Scale Quantum), especificamente o Amostragem de Bósons Gaussianos (GBS), oferece um caminho para uma solução mais eficiente. Eles avaliam criticamente um algoritmo quântico proposto por Brádler et al. [13] e propõem uma alternativa clássica inspirada em seus princípios subjacentes.

Metodologia
Os autores desenvolvem um algoritmo clássico que utiliza as propriedades estatísticas de um sistema GBS para testar o isomorfismo de grafos, evitando a necessidade de um dispositivo quântico físico.

1. Codificação: Os grafos são codificados em um sistema GBS usando a decomposição de Autonne-Takagi ($A = UDU^T$) da matriz de adjacência $A$. A matriz unitária $U$ define o interferômetro, e a matriz diagonal $D$ (contendo autovalores) determina os parâmetros de squeezing de entrada. Esta codificação garante que a distribuição de amostragem reflita a estrutura do grafo.
2. Invariantes Estatísticos: Em vez de coletar amostras físicas (o que é ineficiente para a aproximação exata da distribuição), o algoritmo calcula correlações de modo (cumulantes) da distribuição de saída do amostrador.
   • A probabilidade de um padrão de saída em GBS é governada pelo Hafnian de uma submatriz, uma função classicamente difícil de computar.
   • No entanto, cumulantes de ordem inferior (correlações) podem ser computados eficientemente. Os autores definem correlações de ordem $k$ ($C^{(k)}$) usando funções de Ursell, que descrevem a correlação entre $k$ modos de saída.
   • Crucialmente, os autores não assumem um squeezing uniforme; eles utilizam os autovalores específicos do grafo para determinar um squeezing de entrada não uniforme, permitindo uma verificação prévia de isoespectralidade (uma condição necessária para o isomorfismo).
3. O Processo Algorítmico:
   • Decomposição: As matrizes de adjacência dos dois grafos são decompostas em $U$ e $D$.
   • Cálculo Iterativo de Correlação: O algoritmo calcula valores de correlação para ordens crescentes $k$ (de 1 até o número de vértices $M$).
   • Filtragem de Permutação: Para cada ordem $k$, o algoritmo compara os conjuntos de valores de correlação entre os dois grafos. Ele mantém uma matriz de permutação candidata $\sigma$ (inicialmente composta por todos uns). Se um valor de correlação existe para um vértice no Grafo 1, mas não no Grafo 2, o mapeamento correspondente em $\sigma$ é eliminado (definido como zero).
   • Terminação:
     • Se $\sigma$ tornar-se inválido (linha ou coluna vazia), os grafos são declarados não-isomorfos.
     • Se $\sigma$ reduzir-se a uma matriz de permutação única, os grafos são verificados como isomorfos.
     • Se $\sigma$ permanecer indeterminado (múltiplos mapeamentos possíveis), o algoritmo prossegue para a próxima ordem superior $k+1$.
   • Truncamento: O processo pode ser truncado em uma ordem máxima $k_{max}$ caso o custo computacional se torne proibitivo.

Principais Contribuições

• Formulação de Condição Necessária: Os autores formulam uma condição necessária para o isomorfismo de grafos baseada na equivalência das correlações de modo de ordem $k$ dos grafos codificados pelo amostrador. Eles provam que, se dois grafos forem isomorfos, seus conjuntos de correlação devem ser permutacionalmente equivalentes para todo $k$.
• Algoritmo Clássico: Eles introduzem um algoritmo clássico que testa essa condição necessária. O algoritmo utiliza propriedades estatísticas eficientemente computáveis (correlações) derivadas da matriz de adjacência do grafo para distinguir grafos não-isomorfos.
• Análise de Complexidade: O artigo demonstra que o algoritmo clássico proposto possui complexidade computacional e poder de distinção de grafos comparáveis ao algoritmo de amostragem inspirado em quântica de Brádler et al. [13] e ao algoritmo clássico de Refinamento de Cores (Weisfeiler-Leman) [23].
• Distinção de Métodos Existentes: Os autores esclarecem que, embora seu método compartilhe características de complexidade com o algoritmo de Refinamento de Cores (especificamente o teste de Weisfeiler-Leman), ele avalia informações diferentes (correlações de modo do amostrador vs. contagens de cores de vizinhança). Eles observam que é uma questão em aberto se o seu método sofre das mesmas limitações do teste de Weisfeiler-Leman em relação a famílias específicas de grafos (grafos de Cai-Fürer-Immerman).

Resultados e Limitações

• Eficiência: O cálculo dos valores de correlação é polinomial no número de vértices $M$, mas escala exponencialmente com a ordem de correlação $k$.
• Poder de Distinção: O algoritmo identifica com sucesso grafos não-isomorfos ao mostrar uma violação da condição necessária. No entanto, assim como o algoritmo de Refinamento de Cores, ele apresenta dificuldades com grafos altamente simétricos (ex: grafos regulares), onde as correlações de ordem inferior são idênticas.
• Completude: Os autores afirmam que, na ordem máxima ($k=M$), o método recupera as distribuições de probabilidade relevantes e é teoricamente suficiente para testar o isomorfismo. Contudo, isso não é eficiente, pois o custo computacional torna-se proibitivo.
• Comparação com o Estado da Arte: O artigo afirma explicitamente que seu método é categoricamente menos eficiente que o algoritmo quase-polinomial de estado da arte de Babai. Ele não oferece uma solução de tempo polinomial para o problema geral de isomorfismo de grafos.

Significância e Alegações
O artigo posiciona-se como uma avaliação crítica das alegações de vantagem quântica na era NISQ. Sua principal significância reside em:

1. Desmistificar Alegações Quânticas: Demonstra que a "vantagem quântica" proposta para o algoritmo de Brádler et al. pode ser replicada classicamente através do cálculo das mesmas propriedades estatísticas sem um dispositivo quântico físico.
2. Definir Limites: Reforça a visão de que atualmente não existe um algoritmo quântico geralmente eficiente para isomorfismo de grafos utilizando computadores quânticos ópticos lineares.
3. Distinção Metodológica: Estabelece um novo e distinto heurístico para testar a não-isomorfia baseado em estatísticas de GBS, que é teoricamente capaz de recuperar uma condição suficiente na ordem máxima, diferentemente do refinamento de cores padrão.

Os autores concluem que, embora seu método seja uma heurística útil para distinguir grafos não-isomorfos, ele não demonstra atualmente uma vantagem quântica funcional sobre as melhores abordagens clássicas.