Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Dichiarazione del Problema

Il documento affronta il problema dell'Isomorfismo di Grafi (GI), un compito computazionale che consiste nel determinare se due grafi finiti siano strutturalmente identici. Sebbene il problema occupi una posizione unica nella teoria della complessità (né dimostrato come NP-completo né risolvibile in tempo polinomiale), esso possiede significative applicazioni pratiche in chimica, biologia e reti sociali.

Gli autori investigano l'applicazione degli Algoritmi Quantistici Variazionali (VQA) — specificamente il Quantum Approximate Optimization Algorithm (QAOA) e il Variational Quantum Eigensolver (VQE) — per risolvere il GI. La sfida centrale risiede nel codificare il problema del GI in una formulazione di Ottimizzazione Binaria Quadratica Non Vincolata (QUBO) (o Hamiltoniana di Ising) dove gli isomorfismi di grafi validi corrispondono allo stato fondamentale (energia zero). Lo studio si concentra sulla capacità dell'ottimizzazione variazionale di distinguere efficacemente coppie di grafi isomorfi da quelle non isomorfi nel regime NISQ (Noisy Intermediate Scale Quantum), specialmente date le restrizioni delle istanze di grafi piccoli e dei limitati conteggi di qubit.

Metodologia

La ricerca impiega un approccio ibrido quantistico-classico utilizzando istanze di grafi su piccola scala (4 e 5 nodi) per simulare le condizioni NISQ.

1. Formulazione del Problema:

   • Gli autori utilizzano formulazioni QUBO derivate da lavori precedenti (Lucas, Zick et al., e Calude et al.).
   • L'Hamiltoniana include termini di penalità per imporre i vincoli di biiezione (garantendo una mappatura uno-a-uno tra i vertici) e la preservazione degli archi (garantendo che l'adiacenza sia mantenuta).
   • Il numero di qubit logici richiesti scala come $O(n^2)$ per grafi di ordine $n$, limitando lo studio a piccoli valori di $n$ a causa delle attuali restrizioni hardware e di simulazione.

2. Algoritmi:

   • QAOA: Implementato con una profondità di circuito superficiale ($p=1$) per rimanere nel regime rilevante per il NISQ. Utilizza un'Hamiltoniana di costo derivata dalla QUBO e un'Hamiltoniana di mixer.
   • VQE: Implementato con un ansatz più profondo ed espressivo (circuito TwoLocal con 5 ripetizioni) e l'ottimizzatore SPSA. Questo funge da controllo ad alta fedeltà per confermare se l'Hamiltoniana codifica correttamente la struttura del problema.

3. Framework di Analisi:

   • Inveve di fare affidamento esclusivamente sui valori di energia finale, gli autori analizzano le traiettorie di ottimizzazione.
   • Costruiscono un vettore di caratteristiche composto dal numero di vertici ($N$), dall'energia variazionale finale ($E_{final}$), dai passi di ottimizzazione e dalla diminuzione totale dell'energia ($\Delta E$).
   • Queste caratteristiche vengono fornite a una suite di classificatori di machine learning classici (Regressione Logistica, SVM, Random Forest, Gradient Boosting, XGBoost, LightGBM, MLP) per testare se i dati a livello di traiettoria migliorino la discriminazione tra coppie isomorfe e non isomorfe.

Contributi Chiave e Risultati

1. Clustering Energetico delle Coppie Isomorfe
Lo studio osserva che le coppie di grafi isomorfi esibiscono un clustering coerente nei loro paesaggi di energia variazionale.

• QAOA: Per sistemi piccoli ($N=4$), le coppie isomorfe si concentrano attorno a valori di energia più bassi. Tuttavia, all'aumentare di $N$ a 5, la capacità di discriminare basandosi esclusivamente sull'energia minima degrada rapidamente.
• VQE: Conferma il fenomeno del clustering con maggiore fedeltà, mostrando che le coppie isomorfe convergono verso un'energia prossima allo zero, mentre le coppie non isomorfe convergono verso valori positivi. Ciò valida che l'Hamiltoniana codifica correttamente le caratteristiche strutturali.
• Ablazione Controllata: Gli esperimenti variando la topologia del grafo (rimozione di archi) mantenendo fisso l'isomorfismo hanno dimostrato che gli spostamenti energetici sono guidati dalla struttura del grafo e non da artefatti di etichettatura, confermando la stabilità della codifica dell'Hamiltoniana.

2. Limiti dell'Energia Bassa come Certificatore
Un risultato critico è che l'energia bassa variazionale è un certificatore inaffidabile di isomorfismo.

• Stati Infeasibili: L'ottimizzazione converge frequentemente a stati a bassa energia che violano i vincoli di biiezione (vincoli di permutazione).
• Sovrapposizione Spettrale: Esiste una sostanziale sovrapposizione tra gli spettri a bassa energia delle istanze isomorfe e non isomorfe. Molti grafi non isomorfi producono energie indistinguibili da quelle isomorfe, particolarmente a profondità di circuito superficiali.
• Degenerazione: L'insieme ammissibile di permutazioni valide è infinitamente piccolo rispetto al totale dello spazio di Hilbert ($N! / 2^{N^2} \to 0$), portando a un paesaggio dominato da superposizioni inammissibili.

3. Performance della Classificazione Basata sulla Traiettoria
Gli autori hanno testato se l'analisi del percorso di ottimizzazione (traiettoria), piuttosto che solo dell'energia finale, potesse migliorare la classificazione.

• Risultati: Sebbene i metodi ensemble non lineari (Random Forest, Gradient Boosting) abbiano superato i classificatori lineari, l'accuratezza complessiva è rimasta modesta (migliore accuratezza $\approx 75\%$).
• Conclusione: Il fallimento di questi modelli nel raggiungere una separazione affidabile indica che il segnale variazionale stesso manca di informazioni discriminatorie sufficienti, piuttosto che i classificatori siano insufficientemente espressivi. La sovrapposizione negli spettri a bassa energia è un limite intrinseco della codifica variazionale attuale.

Significatività e Rivendicazioni

Il documento pone i propri risultati come un'investigazione di prova di concetto piuttosto che come una soluzione scalabile al problema dell'Isomorfismo di Grafi.

• Strumento Diagnostico vs Solutore: Gli autori sostengono che gli algoritmi variazionali non debbano essere visti come solutori per il GI nell'era NISQ. Al contrario, essi fungono da strumenti diagnostici per sondare la struttura delle codifiche Hamiltoniane. Il clustering energetico osservato rivela che l'Hamiltoniana codifica con successo le caratteristiche strutturali, ma l'incapacità di separare le classi basandosi sull'energia evidenzia i limiti degli euristiche puramente energetiche.
• Limiti degli Approcci Attuali: Lo studio sottolinea che, senza meccanismi per imporre esplicitamente i vincoli globali di permutazione o ansatz più avanzati, gli algoritmi variazionali faticheranno a distinguere grafi isomorfi da non isomorfi a causa della prevalenza di stati a bassa energia inammissibili.
• Direzioni Future: Il lavoro suggerisce che il progresso richieda codifiche QUBO più compatte, ansatz progettati per il problema e mixer consapevoli dei vincoli. Nota inoltre che la scalabilità a grafi più grandi (6–8 nodi) e il test su hardware reale con mitigazione degli errori sono i passi successivi necessari per colmare il divario tra simulazione e fattibilità sperimentale.

In sintesi, il documento dimostra che, sebbene gli algoritmi quantistici variazionali possano identificare bacini a bassa energia corrispondenti alle strutture dei grafi, la sola minimizzazione dell'energia è insufficiente per una discriminazione scalabile dell'isomorfismo di grafi a causa dell'alta probabilità di convergere verso stati inammissibili e della sovrapposizione spettrale tra le classi di grafi.