Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Énoncé du problème

Le document traite du problème de l'isomorphisme de graphes (GI), une tâche computationnelle consistant à déterminer si deux graphes finis sont structurellement identiques. Bien que ce problème occupe une position unique dans la théorie de la complexité (ni prouvé NP-complet, ni résoluble en temps polynomial), il possède des applications pratiques significatives en chimie, en biologie et dans les réseaux sociaux.

Les auteurs étudient l'application des algorithmes quantiques variationnels (VQA) — spécifiquement l'Algorithme d'Optimisation Quantique Approchée (QAOA) et le Variational Quantum Eigensolver (VQE) — pour résoudre le problème de l'isomorphisme de graphes. Le défi central réside dans l'encodage du problème de l'isomorphisme de graphes sous une forme d'Optimisation Binaire Quadratique sans Contrainte (QUBO) (ou Hamiltonien d'Ising), où les isomorphismes de graphes valides correspondent à l'état fondamental (énergie zéro). L'étude se concentre sur la capacité de l'optimisation variationnelle à distinguer efficacement les paires de graphes isomorphes des paires non isomorphes dans le régime NISQ (Noisy Intermediate Scale Quantum), compte tenu notamment des contraintes liées aux petites instances de graphes et au nombre limité de qubits.

Méthodologie

La recherche emploie une approche hybride quantique-classique utilisant de petites instances de graphes (4 et 5 nœuds) pour simuler les conditions NISQ.

1. Formulation du problème :

   • Les auteurs utilisent des formulations QUBO dérivées de travaux antérieurs (Lucas, Zick et al., et Calude et al.).
   • L'Hamiltonien inclut des termes de pénalité pour imposer les contraintes de bijection (garantissant une correspondance un à un entre les sommets) et la préservation des arêtes (garantissant le maintien de l'adjacence).
   • Le nombre de qubits logiques requis évolue en $O(n^2)$ pour des graphes d'ordre $n$, ce qui limite l'étude à de petites valeurs de $n$ en raison des contraintes actuelles du matériel et de la simulation.

2. Algorithmes :

   • QAOA : Implémenté avec une faible profondeur de circuit ($p=1$) pour rester dans le régime pertinent pour le NISQ. Il utilise un Hamiltonien de coût dérivé du QUBO et un Hamiltonien de mélange (mixer).
   • VQE : Implémenté avec un ansatz plus profond et plus expressif (circuit TwoLocal avec 5 répétitions) et l'optimiseur SPSA. Il sert de vérification de haute fidélité pour confirmer que l'Hamiltonien encode correctement la structure du problème.

3. Cadre d'analyse :

   • Au lieu de se fier uniquement aux valeurs d'énergie finales, les auteurs analysent les trajectoires d'optimisation.
   • Ils construisent un vecteur de caractéristiques comprenant le nombre de sommets ($N$), l'énergie variationnelle finale ($E_{final}$), les étapes d'optimisation et la diminution totale de l'énergie ($\Delta E$).
   • Ces caractéristiques sont injectées dans une suite de classificateurs d'apprentissage automatique classiques (Régression Logistique, SVM, Forêt Aléatoire, Gradient Boosting, XGBoost, LightGBM, MLP) pour tester si les données au niveau de la trajectoire améliorent la discrimination entre les paires isomorphes et non isomorphes.

Contributions clés et résultats

1. Regroupement énergétique des paires isomorphes
L'étude observe que les paires de graphes isomorphes présentent un regroupement cohérent dans leurs paysages d'énergie variationnelle.

• QAOA : Pour les petits systèmes ($N=4$), les paires isomorphes se concentrent autour de valeurs d'énergie plus basses. Cependant, à mesure que $N$ augmente pour atteindre 5, la capacité de discrimination basée uniquement sur l'énergie minimale se dégrade rapidement.
• VQE : Confirme le phénomène de regroupement avec une fidélité plus élevée, montrant que les paires isomorphes convergent vers une énergie proche de zéro tandis que les paires non isomorphes convergent vers des valeurs positives. Cela valide le fait que l'Hamiltonien encode correctement les caractéristiques structurelles.
• Ablation contrôlée : Des expériences faisant varier la topologie du graphe (suppression d'arêtes) tout en maintenant l'isomorphisme fixe ont démontré que les décalages d'énergie sont pilotés par la structure du graphe et non par des artefacts d'étiquetage, confirmant la stabilité de l'encodage de l'Hamiltonien.

2. Limites de la basse énergie comme certificat
Une conclusion critique est que la faible énergie variationnelle est un certificat peu fiable de l'isomorphisme.

• États infaisables : L'optimisation converge fréquemment vers des états de basse énergie qui violent les contraintes de bijection (contraintes de permutation).
• Recouvrement spectral : Il existe un chevauchement substantiel entre les spectres de basse énergie des instances isomorphes et non isomorphes. De nombreux graphes non isomorphes produisent des énergies indiscernables de celles des graphes isomorphes, particulièrement à de faibles profondeurs de circuit.
• Dégénérescence : L'ensemble des permutations valides est extrêmement petit par rapport à l'espace de Hilbert total ($N! / 2^{N^2} \to 0$), ce qui conduit à un paysage dominé par des superpositions infaisables.

3. Performance de la classification basée sur la trajectoire
Les auteurs ont testé si l'analyse du chemin d'optimisation (trajectoire), plutôt que de la seule énergie finale, pouvait améliorer la classification.

• Résultats : Bien que les méthodes d'ensemble non linéaires (Forêt Aléatoire, Gradient Boosting) aient surpassé les classificateurs linéaires, la précision globale est restée modeste (meilleure précision $\approx 75\%$).
• Conclusion : L'échec de ces modèles à atteindre une séparation fiable indique que le signal variationnel lui-même manque d'informations discriminatoires suffisantes, plutôt que les classificateurs qui seraient insuffisamment expressifs. Le chevauchement dans les spectres de basse énergie est une limitation intrinsèque de l'encodage variationnel actuel.

Signification et affirmations

Le papier positionne ses conclusions comme une investigation de preuve de concept plutôt que comme une solution scalable au problème de l'isomorphisme de graphes.

• Outil de diagnostic vs Solveur : Les auteurs soutiennent que les algorithmes variationnels ne doivent pas être considérés comme des solveurs pour l'isomorphisme de graphes dans l'ère NISQ. Au contraire, ils servent d'outils de diagnostic pour sonder la structure des encodages d'Hamiltoniens. Le regroupement d'énergie observé révèle que l'Hamiltonien encode avec succès les caractéristiques structurelles, mais l'incapacité à séparer les classes sur la base de l'énergie souligne les limites des heuristiques purement énergétiques.
• Limites des approches actuelles : L'étude souligne que sans mécanismes pour imposer explicitement les contraintes de permutation globales ou des ansatz plus avancés, les algorithmes variationnels auront du mal à distinguer les graphes isomorphes des graphes non isomorphes en raison de la prévalence des états de basse énergie infaisables.
• Direction future : Le travail suggère que les progrès nécessiteront des encodages QUBO plus compacts, des ansatz adaptés au problème et des mélangeurs (mixers) sensibles aux contraintes. Il note également que le passage à des graphes plus grands (6–8 nœuds) et les tests sur du matériel réel avec correction d'erreurs sont les prochaines étapes nécessaires pour combler l'écart entre la simulation et la faisabilité expérimentale.

En résumé, le papier démontre que bien que les algorithmes quantiques variationnels puissent identifier des bassins de basse énergie correspondant aux structures de graphes, la minimisation de l'énergie seule est insuffisante pour une discrimination scalable de l'isomorphisme de graphes en raison de la probabilité élevée de convergence vers des états infaisables et du chevauchement spectral entre les classes de graphes.