Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Enunciado do Problema

O artigo aborda o problema do Isomorfismo de Grafos (GI), uma tarefa computacional que determina se dois grafos finitos são estruturalmente idênticos. Embora o problema ocupe uma posição única na teoria da complexidade (nem provado como NP-completo, nem solúvel em tempo polinomial), ele possui aplicações práticas significativas em química, biologia e redes sociais.

Os autores investigam a aplicação de Algoritmos Quânticos Variacionais (VQAs) — especificamente o Algoritmo de Otimização Aproximada Quântica (QAOA) e o Solucionador de Autovalores Quânticos Variacionais (VQE) — para resolver o GI. O desafio central reside em codificar o problema de GI em uma formulação de Otimização Binária Quadrática Não Restrita (QUBO) (ou Hamiltoniana de Ising), onde isomorfismos de grafos válidos correspondem ao estado fundamental (energia zero). O estudo foca em se a otimização variacional pode distinguir eficazmente pares de grafos isomorfos de não isomorfos no regime NISQ (Noisy Intermediate Scale Quantum), particularmente dadas as restrições de instâncias de grafos pequenos e contagens limitadas de qubits.

Metodologia

A pesquisa utiliza uma abordagem híbrida quântico-clássica usando instâncias de grafos de pequena escala (4 e 5 nós) para simular condições NISQ.

1. Formulação do Problema:

   • Os autores utilizam formulações QUBO derivadas de trabalhos anteriores (Lucas, Zick et al., e Calude et et al.).
   • A Hamiltoniana inclui termos de penalidade para impor restrições de bijeção (garantindo um mapeamento um-para-um entre vértices) e preservação de arestas (garantindo que a adjacência seja mantida).
   • O número de qubits lógicos necessários escala como $O(n^2)$ para grafos de ordem $n$, limitando o estudo a pequenos $n$ devido às restrições atuais de hardware e simulação.

2. Algoritmos:

   • QAOA: Implementado com uma profundidade de circuito rasa ($p=1$) para permanecer dentro do regime relevante para NISQ. Utiliza uma Hamiltoniana de custo derivada da QUBO e uma Hamiltoniana de mistura (mixer).
   • VQE: Implementado com um ansatz mais profundo e expressivo (circuito TwoLocal com 5 repetições) e o otimizador SPSA. Este serve como uma verificação de alta fidelidade para confirmar se a Hamiltoniana codifica corretamente a estrutura do problema.

3. Estrutura de Análise:

   • Em vez de depender apenas dos valores de energia final, os autores analisam as trajetórias de otimização.
   • Eles constroem um vetor de características composto pelo número de vértices ($N$), energia variacional final ($E_{final}$), passos de otimização e diminuição total de energia ($\Delta E$).
   • Essas características são inseridas em um conjunto de classificadores de aprendizado de máquina clássicos (Regressão Logística, SVM, Floresta Aleatória, Gradient Boosting, XGBoost, LightGBM, MLP) para testar se os dados ao nível da trajetória melhoram a discriminação entre pares isomorfos e não isomorfos.

Principais Contribuições e Resultados

1. Agrupamento de Energia de Pares Isomorfos
O estudo observa que pares de grafos isomorfos exibem um agrupamento consistente em seus landscapes de energia variacional.

• QAOA: Para sistemas pequenos ($N=4$), pares isomorfos se concentram em torno de valores de energia mais baixos. No entanto, conforme $N$ aumenta para 5, a capacidade de discriminação baseada apenas na energia mínima degrada-se rapidamente.
• VQE: Confirma o fenômeno de agrupamento com maior fidelidade, mostrando que pares isomorfos convergem para energia próxima de zero, enquanto pares não isomorfos convergem para valores positivos. Isso valida que a Hamiltoniana codifica corretamente as características estruturais.
• Ablação Controlada: Experimentos variando a topologia do grafo (remoção de arestas) enquanto o isomorfismo permanecia fixo demonstraram que os desvios de energia são impulsionados pela estrutura do grafo, não por artefatos de rotulagem, confirmando a estabilidade da codificação da Hamiltoniana.

2. Limitações da Baixa Energia como Certificador
Uma descoberta crítica é que a baixa energia variacional é um certificador não confiável de isomorfismo.

• Estados Inviáveis: A otimização frequentemente converge para estados de baixa energia que violam as restrições de bijeção (restrições de permutação).
• Sobreposição Espectral: Existe uma sobreposição substancial entre os espectros de baixa energia de instâncias isomorfas e não isomorfas. Muitos grafos não isomorfos geram energias indistinguíveis de isomorfos, particularmente em profundidades de circuito rasas.
• Degenerescência: O conjunto viável de permutações válidas é ínfimo em comparação ao espaço de Hilbert total ($N! / 2^{N^2} \to 0$), levando a um landscape dominado por superposições inviáveis.

3. Desempenho da Classificação Baseada em Trajetória
Os autores testaram se analisar o caminho de otimização (trajetória), em vez de apenas a energia final, poderia melhorar a classificação.

• Resultados: Embora métodos de conjunto não lineares (Random Forest, Gradient Boosting) tenham superado classificadores lineares, a precisão geral permaneceu modesta (melhor precisão $\approx 75\%$).
• Conclusão: O fracasso desses modelos em alcançar uma separação confiável indica que o próprio sinal variacional carece de informação discriminatória suficiente, em vez de os classificadores serem insuficientemente expressivos. A sobreposição nos espectros de baixa energia é uma limitação intrínseca da atual codificação variacional.

Significância e Alegações

O artigo posiciona suas descobertas como uma investigação de prova de conceito em vez de uma solução escalável para o problema do Isomorfismo de Grafos.

• Ferramenta de Diagnóstico vs. Solucionador: Os autores argumentam que algoritmos variacionais não devem ser vistos como solucionadores de GI na era NISQ. Em vez disso, servem como ferramentas de diagnóstico para sondar a estrutura das codificações de Hamiltoniana. O agrupamento de energia observado revela que a Hamiltoniana codifica com sucesso características estruturais, mas a incapacidade de separar classes baseando-se em energia destaca as limitações de heurísticas puramente energéticas.
• Limitações das Abordagens Atuais: O estudo ressalta que, sem mecanismos para impor explicitamente restrições globais de permutação ou ansatzes mais avançados, os algoritmos variacionais terão dificuldade em distinguir grafos isomorfos de não isomorfos devido à prevalência de estados de baixa energia inviáveis.
• Direção Futura: O trabalho sugere que o progresso requer codificações QUBO mais compactas, ansatzes adaptados ao problema e misturadores (mixers) conscientes de restrições. Também nota que escalar para grafos maiores (6–8 nós) e testar em hardware real com mitigação de erro são próximos passos necessários para reduzir a lacuna entre a simulação e a viabilidade experimental.

Em resumo, o artigo demonstra que, embora os algoritmos quânticos variacionais possam identificar bacias de baixa energia correspondentes a estruturas de grafos, a minimização de energia sozinha é insuficiente para a discriminação escalável do isomorfismo de grafos devido à alta probabilidade de convergência para estados inviáveis e à sobreposição espectral entre classes de grafos.