A Quantum-Inspired Algorithm for Graph Isomorphism

Sintesi Tecnica: Un Algoritmo di Ispirazione Quantistica per l'Isomorfismo di Grafi

Definizione del Problema
Il documento affronta il problema dell'Isomorfismo di Grafi (GI): determinare se due grafi discreti siano strutturalmente identici a meno di una permutazione delle etichette dei loro vertici. Sebbene il problema non sia noto essere NP-completo, la ricerca di un algoritmo polinomiale generale rimane una sfida significativa nella teoria dell'informazione. L'approccio classico allo stato dell'arte, l'algoritmo di Babai (2015), opera in tempo quasi-polinomiale ($2^{O(\log V)^3}$). Gli autori indagano se l'era NISQ (Noisy Intermediate-Scale Quantum), specificamente il Gaussian Boson Sampling (GBS), offra una via verso una soluzione più efficiente. Essi valutano criticamente un algoritmo quantistico proposto da Brádler et al. [13] e propongono un'alternativa classica ispirata ai suoi principi sottostanti.

Metodologia
Gli autori sviluppano un algoritmo classico che utilizza le proprietà statistiche di un sistema GBS per testare l'isomorfismo di grafi, evitando la necessità di un dispositivo quantistico fisico.

1. Codifica: I grafi vengono codificati in un sistema GBS utilizzando la decomposizione di Autonne-Takagi ($A = UDU^T$) della matrice di adiacenza $A$. La matrice unitaria $U$ definisce l'interferometro, e la matrice diagonale $D$ (contenente gli autovalori) determina i parametri di squeezing in ingresso. Questa codifica assicura che la distribuzione di probabilità del campionatore rifletta la struttura del grafo.
2. Invarianti Statistici: Invece di raccogliere campioni fisici (il che sarebbe inefficiente per un'approssimazione esatta della distribuzione), l'algoritmo calcola le correlazioni di modo (cumulanti) della distribuzione di output del campionatore.
   • La probabilità di un pattern di output in GBS è governata dall'Hafnian di una sottomatrice, una funzione classicamente difficile da calcolare.
   • Tuttavia, i cumulanti di ordine inferiore (correlazioni) possono essere calcolati efficientemente. Gli autori definiscono le correlazioni di ordine $k$ $C^{(k)}$ utilizzando le funzioni di Ursell, che descrivono la correlazione tra $k$ modi di output.
   • Fondamentalmente, gli autori non assumono uno squeezing uniforme; utilizzano gli specifici autovalori del grafo per determinare uno squeezing in ingresso non uniforme, permettendo un controllo preventivo dell'isospettralità (una condizione necessaria per l'isomorfismo).
3. Il Processo Algoritmico:
   • Decomposizione: Le matrici di adiacenza dei due grafi vengono decomposte in $U$ e $D$.
   • Calcolo Iterativo delle Correlazioni: L'algoritmo calcola i valori di correlazione per ordini crescenti $k$ (da 1 fino al numero di vertici $M$).
   • Filtraggio delle Permutazioni: Per ogni ordine $k$, l'algoritmo confronta gli insiemi di valori di correlazione tra i due grafi. Mantiene una matrice di permutazione candidata $\sigma$ (inizialmente composta da tutti uni). Se un valore di correlazione esiste per un vertice nel Grafo 1 ma non nel Grafo 2, la corrispondente mappatura in $\sigma$ viene eliminata (impostata a zero).
   • Terminazione:
     • Se $\sigma$ diventa invalida (riga o colonna vuota), i grafi sono dichiarati non isomorfi.
     • Se $\sigma$ si riduce a una matrice di permutazione unica, i grafi sono verificati come isomorfi.
     • Se $\sigma$ rimane indeterminata (molteplici mappature possibili), l'algoritmo procede all'ordine superiore $k+1$.
   • Troncamento: Il processo può essere troncato a un ordine massimo $k_{max}$ se il costo computazionale diventa proibitivo.

Contributi Chiave

• Formulazione della Condizione Necessaria: Gli autori formulano una condizione necessaria per l'isomorfismo di grafi basata sull'equivalenza delle correlazioni di modo di ordine $k$ dei grafi codificati dal campionatore. Dimostrano che se due grafi sono isomorfi, i loro insiemi di correlazioni devono essere permutazionalmente equivalenti per ogni $k$.
• Algoritmo Classico: Introducono un algoritmo classico che testa questa condizione necessaria. L'algoritmo utilizza proprietà statistiche facilmente computabili (correlazioni) derivate dalla matrice di adiacenza del grafo per distinguere grafi non isomorfi.
• Analisi della Complessità: Il documento dimostra che il proposto algoritmo classico ha una complessità computazionale e una capacità di distinzione dei grafi comparabile all'algoritmo di campionamento di ispirazione quantistica di Brádler et al. [13] e all'algoritmo classico di Color Refinement (Weisfeiler-Leman) [23].
• Distinzione dai Metodi Esistenti: Gli autori chiariscono che, sebbene il loro metodo condivida caratteristiche di complessità con l'algoritmo di Color Refinement (specificamente il test di Weisfeiler-Leman), esso valuta informazioni diverse (correlazioni di modo del campionatore rispetto ai conteggi dei colori di vicinato). Notano che è un problema aperto se il loro metodo soffra delle stesse limitazioni del test di Weisfeiler-Leman riguardo a specifiche famiglie di grafi (grafi Cai-Fürer-Immerman).

Risultati e Limitazioni

• Efficienza: Il calcolo dei valori di correlazione è polinomiale rispetto al numero di vertici $M$, ma scala esponenzialmente con l'ordine di correlazione $k$.
• Capacità di Distinzione: L'algoritmo identifica con successo grafi non isomorfi mostrando una violazione della condizione necessaria. Tuttavia, come l'algoritmo di Color Refinement, fatica con grafi altamente simmetrici (ad esempio, grafi regolari) dove le correlazioni di ordine inferiore sono identiche.
• Completezza: Gli autori affermano che al massimo ordine ($k=M$), il metodo recupera le distribazioni di probabilità rilevanti ed è teoricamente sufficiente per testare l'isomorfismo. Tuttavia, questo non è efficiente, poiché il costo computazionale diventa proibitivo.
• Confronto con lo Stato dell'Arte: Il documento afferma esplicitamente che il loro metodo è categoricamente meno efficiente dell'algoritmo quasi-polinomiale allo stato dell'arte di Babai. Non offre una soluzione in tempo polinomiale per il problema generale dell'isomorfismo di grafi.

Significato e Rivendicazioni
Il documento si pone come una valutazione critica delle rivendicazioni di vantaggio quantistico nell'era NISQ. Il suo significato primario risiede in:

1. Demistificazione delle Rivendicazioni Quantistiche: Dimostra che il "vantaggio quantistico" proposto per l'algoritmo di Brádler et al. può essere replicato classicamente calcolando le stesse proprietà statistiche senza un dispositivo quantistico fisico.
2. Definizione dei Limiti: Rafforza la visione secondo cui attualmente non esiste un algoritmo quantistico generalmente efficiente per l'isomorfismo di grafi utilizzando computer quantistici ottici lineari.
3. Distinzione Metodologica: Stabilisce un nuovo, distinto euristica per testare la non-isomorfia basata sulla statistica GBS, che è teoricamente capace di recuperare una condizione sufficiente all'ordine massimo, diversamente dal color refinement standard.

Gli autori concludono che, sebbene il loro metodo sia un'euristica utile per distinguere grafi non isomorfi, non dimostra attualmente un vantaggio quantistico funzionale rispetto ai migliori approcci classici.