Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Probleemstelling

Het artikel behandelt het Grafenisomorfisme-probleem (GI), een computationele taak waarbij wordt bepaald of twee eindige grafen structureel identiek zijn. Hoewel dit probleem een unieke positie inneemt in de complexiteitstheorie (noch bewezen NP-volledig, noch oplosbaar in polynomiale tijd), heeft het belangrijke praktische toepassingen in de chemie, biologie en sociale netwerken.

De auteurs onderzoeken de toepassing van Variational Quantum Algorithms (VQA's)—specifiek het Quantum Approximate Optimization Algorithm (QAOA) en de Variational Quantum Eigensolver (VQE)—om GI op te lossen. De kernuitdaging ligt in het coderen van het GI-probleem in een Quadratic Unconstrained Binary Optimization (QUBO)-formulering (of Ising-Hamiltoniaan), waarbij geldige graafisomorfismen overeenkomen met de grondtoestand (nulenergie). De studie richt zich op de vraag of variabele optimalisatie effectief isomorfische van niet-isomorfische graafparen kan onderscheiden in het Noisy Intermediate Scale Quantum (NISQ)-regime, met name gezien de beperkingen van kleine graafinstanties en beperkte qubit-aantallen.

Methodologie

Het onderzoek maakt gebruik van een hybride quantum-klassieke benadering met behulp van kleine schaal grafeninstanties (4 en 5 knopen) om NISQ-condities te simuleren.

1. Probleemformulering:

   • De auteurs maken gebruik van QUBO-formuleringen afgeleid van eerder werk (Lucas, Zick et al., en Calude et al.).
   • De Hamiltoniaan bevat straftermen om bijjectieve restricties af te dwingen (het waarborgen van een één-op-één mapping tussen vertices) en randbehoud (het waarborgen dat nabijheid behouden blijft).
   • Het aantal logische qubits vereist schaalt als $O(n^2)$ voor grafen van orde $n$, wat de studie beperkt tot kleine $n$ vanwege huidige hardware- en simulatiebeperkingen.

2. Algoritmen:

   • QAOA: Geïmplementeerd met een ondiepe circuitdiepte ($p=1$) om binnen het NISQ-relevante regime te blijven. Het gebruikt een kosten-Hamiltoniaan afgeleid van de QUBO en een mixer-Hamiltoniaan.
   • VQE: Geïmplementeerd met een dieper, expressiever ansatz (TwoLocal circuit met 5 herhalingen) en de SPSA-optimizer. Dit dient als een high-fidelity controle om te bevestigen dat de Hamiltoniaan de probleemstructuur correct codeert.

3. Analyseframework:

   • In plaats van uitsluitend te vertrouwen op finale energiewaarden, analyseren de auteurs optimalisatietrajecten.
   • Zij construeren een feature-vector bestaande uit het aantal vertices ($N$), de finale variabele energie ($E_{final}$), optimalisatiestappen en de totale energiedaling ($\Delta E$).
   • Deze features worden ingevoerd in een reeks klassieke machine learning-classificaties (Logistic Regression, SVM, Random Forest, Gradient Boosting, XGBoost, LightGBM, MLP) om te testen of data op trajectniveau de discriminatie tussen isomorfische en niet-isomorfische paren verbetert.

Belangrijkste Bijdragen en Resultaten

1. Energie-clustering van Isomorfe Paren
De studie observeert dat isomorfe graafparen een consistente clustering vertonen in hun variabele energielandschappen.

• QAOA: Voor kleine systemen ($N=4$) concentreren isomorfe paren zich rond lagere energiewaarden. Echter, naarmate $N$ toeneemt naar 5, degradeert het vermogen om enkel op basis van minimale energie te discrimineren snel.
• VQE: Bevestigt het clusteringfenomeen met een hogere getrouwheid, waarbij isomorfe paren convergeren naar een energie nabij nul, terwijl niet-isomorfe paren convergeren naar positieve waarden. Dit valideert dat de Hamiltoniaan de structurele kenmerken correct codeert.
• Gecontroleerde Ablatie: Experimenten waarbij de graaftopologie werd gevarieerd (door randverwijdering) terwijl de isomorfie constant bleef, toonden aan dat energieschuiven worden gedreven door de graafstructuur en niet door label-artefacten, wat de stabiliteit van de Hamiltoniaan-codering bevestigt.

2. Beperkingen van Lage Energie als Certificaat
Een cruciale bevinding is dat lage variabele energie een onbetrouwbare certifier is voor isomorfisme.

• Onhaalbare Toestanden: De optimalisatie convergeert frequent naar toestanden met lage energie die de bijjectieve restricties (permutatierestricties) schenden.
• Spectrale Overlap: Er is een substantiële overlap tussen de lage-energiespectra van isomorfe en niet-isomorfe instanties. Veel niet-isomorfe grafen leveren energieën op die ononderscheidbaar zijn van isomorfe grafen, vooral bij ondiepe circuitdieptes.
• Degeneratie: De haalbare verzameling van geldige permutaties is verwaarloosbaar klein vergeleken met de totale Hilbertruimte ($N! / 2^{N^2} \to 0$), wat leidt tot een landschap dat gedomineerd wordt door onhaalbare superposities.

3. Prestaties van Traject-gebaseerde Classificatie
De auteurs testten of het analyseren van het optimalisatiepad (traject) in plaats van enkel de finale energie de classificatie kon verbeteren.

• Resultaten: Hoewel niet-lineaire ensemble-methoden (Random Forest, Gradient Boosting) beter presteerden dan lineaire classificaties, bleef de algehele nauwkeurigheid bescheiden (beste nauwkeurigheid $\approx 75\%$).
• Conclusie: Het falen van deze modellen om een betrouwbare scheiding te bereiken, wijst erop dat het variabele signaal zelf onvoldoende discriminerende informatie bevat, in plaats van dat de classificaties onvoldoende expressief zijn. De overlap in lage-energiespectra is een intrinsieke beperking van de huidige variabele codering.

Betekenis en Claims

Het artikel positioneert de bevindingen als een proof-of-principle onderzoek in plaats van een schaalbare oplossing voor het Grafenisomorfisme-probleem.

• Diagnostisch Instrument vs. Solver: De auteurs stellen dat variabele algoritmen niet moeten worden beschouwd als solvers voor GI in het NISQ-tijdperk. In plaats daarvan dienen ze als diagnostische instrumenten om de structuur van Hamiltoniaan-coderingen te onderzoeken. De geobserveerde energie-clustering laat zien dat de Hamiltoniaan structurele kenmerken succesvol codeert, maar het onvermogen om klassen te scheiden op basis van energie benadrukt de beperkingen van louter energetische heuristieken.
• Beperkingen van Huidige Benaderingen: De studie onderstreept dat zonder mechanismen om expliciet globale permutatierestricties af te dwingen of meer geavanceerde ansatse te gebruiken, variabele algoritmen moeite zullen hebben om isomorfe van niet-isomorfe grafen te onderscheiden vanwege de prevalentie van onhaalbare toestanden met lage energie.
• Toekomstige Richting: Het werk suggereert dat vooruitgang compacte QUBO-coderingen, op het probleem toegesneden ansatse en restrictie-bewuste mixers vereist. Er wordt ook opgemerkt dat opschalen naar grotere grafen (6–8 knopen) en testen op echte hardware met foutenmitigatie noodzakelijke vervolgstappen zijn om de kloof tussen simulatie en experimentele haalbaarheid te overbruggen.

Samenvattend demonstreert het artikel dat hoewel variabele quantumalgoritmen lage-energiebekkens kunnen identificeren die overeenkomen met graafstructuren, energie-minimalisatie alleen onvoldoende is voor schaalbare grafenisomorfisme-discriminatie vanwege de hoge waarschijnlijkheid van convergentie naar onhaalbare toestanden en de spectrale overlap tussen grafenklassen.