Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy

Problematica

Le Reti Neurali a Grafo (GNN) sono diventate centrali per l'apprendimento da dati relazionali in chimica, biologia e ottimizzazione, spinte dal primitivo del "passaggio di messaggi" (message passing). Tuttavia, le controparti quantistiche esistenti affrontano limitazioni significative:

1. Mancanza di un vero Passaggio di Messaggi: La maggior parte dei modelli grafici quantistici proposti non esegue il passaggio di messaggi all'interno del circuito quantistico. Invece, mappano gli archi del grafo in gate del circuito ma si affidano all'elaborazione classica post-hoc per aggregare le informazioni dei vicini, perdendo i vantaggi coerenti delle operazioni quantistiche.
2. Ceto di Espressività: Le GNN standard basate sul passaggio di messaggi sono limitate dal test 1-Weisfeiler–Leman (1-WL), il che significa che non possono distinguere determinati grafi strutturalmente distinti (ad esempio, specifiche molecole non isomorfe o sottostrutture).
3. Addestrabilità e Scalabilità: I Circuiti Quantistici Variazionali (VQC) soffrono spesso del problema dei "plateau sterili" (barren plateaus), dove i gradienti svaniscono esponenzialmente all'aumentare della dimensione del circuito, rendendo impossibile l'addestramento per grafi grandi. Inoltre, pochi modelli quantistici offrono garanzie su invarianza per permutazione o scalabilità verso istanze di grafi di grandi dimensioni.

Metodologia

Gli autori introducono un framework di Rete Neurale a Grafo Quantistica (QGNN) basato su circuiti preservanti del sottospazio che opera interamente nel regime quantistico. L'architettura è composta da quattro componenti chiave:

1. Caricatore Gerarchico dei Dati ($V$): Il sistema utilizza due registri:

   • Un Registro dei Nodi ($N$ qubit) che codifica i nodi del grafo a un peso di Hamming specifico $j$. Gli stati della base rappresentano $j$-sottoinsiemi di nodi (ad esempio, singoli nodi per $j=1$, archi per $j=2$, triangoli per $j=3$).
   • Un Registro di Embedding ($D$ qubit) che codifica le caratteristiche (features) a un peso di Hamming $k$.
   • Un encoder di particelle controllato-Givens carica le caratteristiche dei nodi nel sottospazio congiunto $H^j_N \otimes H^k_D$.

2. Layer di Adiacenza Equivariante ($A(G)$): Questo livello codifica la connettività del grafo applicando rotazioni di Givens tra coppie di qubit dei nodi corrispondenti agli archi. Gli angoli di rotazione sono derivati dai pesi degli archi in un ordine canonico, garantendo che l'operazione rispetti la struttura del grafo senza fare affidamento sulle etichette dei nodi.

3. Evoluzione Addestrabile ($W(\theta)$): Agendo esclusivamente sul registro di embedding, questo livello aggiorna le caratteristiche dei nodi. Utilizza gate preservanti del sottospazio (specificamente una parametrizzazione di Cayley di $SO(D)$ elevata alla rappresentazione composta) per garantire che la dinamica rimanga entro un sottospazio strutturato, evitando il plateau sterile.

4. Mixing del Registro Congiunto ($M(\theta_M)$): Un ultimo livello accoppia i registri dei nodi e di embedding tramite rotazioni di Givens, permettendo alle informazioni di fluire tra i sottospazi strutturali e di caratteristiche.

Meccanismi Chiave:

• Passaggio di Messaggi: Il circuito esegue il passaggio di messaggi in modo coerente. Il layer di adiacenza instrada le ampiezze lungo gli archi e l'evoluzione addestrabile aggiorna le caratteristiche. Il ricaricamento (re-uploading) del loader ad ogni livello introduce non linearità.
• Equivarianza per Permutazione: L'architettura è esattamente equivariante per permutazione per costruzione. Poiché l'evoluzione addestrabile agisce solo sul registro di embedding condiviso e i layer di adiacenza/mixing seguono un ordine canonico basato sui pesi degli archi (non sulle etichette dei nodi), ridenominare i nodi si limita a ridenominare l'output senza cambiare la funzione.
• Readout: Le caratteristiche vengono lette tramite la matrice densità a una particella (1-RDM) del registro di embedding ($\gamma_{pq} = \langle \psi | a^\dagger_p a_q | \psi \rangle$). Questo può essere stimato con un costo polinomiale ($O(D^3/\epsilon^2)$) utilizzando ombre matchgate o readout deterministici Hartree–Fock, indipendentemente dal numero totale di nodi $N$.

Contributi Chiave

1. Garanzie Teoriche: Il paper dimostra che la QGNN esegue un vero passaggio di messaggi, è esattamente equivariante per permutazione e raggiunge l'espressività $j$-WL. Impostando il numero di particelle del registro dei nodi $j \ge 3$, il modello può distinguere coppie di grafi che il test 1-WL standard (e quindi tutte le GNN standard basate sul passaggio di messaggi) non può distinguere.
2. Scalabilità tramite Preservazione del Sottospazio: Confinando la dinamica in un sottospazio di dimensione fissa (determinata da $D$ e $k$, non da $N$), il modello evita la scomparsa esponenziale del gradiente associata ai generici VQC.
3. Strategia di Pre-addestramento: Il framework adotta un approccio "addestra-piccolo, distribuisci-grande". Poiché i parametri addestrabili agiscono solo sul registro di embedding (che è indipendente dalla dimensione del grafo), un modello addestrato su grafi piccoli può essere trasferito a istanze più grandi inizializzando il modello più grande con i parametri del modello più piccolo.

Risultati

Il framework è stato validato attraverso simulazioni classiche su larga scala (fino a 56 qubit) su tre dataset:

1. Grafi Cai–Fürer–Immerman (CFI):

   • Obiettivo: Distinguere coppie di grafi non isomorfi che il 1-WL non può separare.
   • Risultato: La QGNN ha raggiunto il 100% di accuratezza nel test esattamente ai numeri di particelle previsti ($j=3$ per CFI(K3) e $j=4$ per CFI(K4)), mentre i baseline 1-WL rimanevano al caso. Ciò conferma la capacità del modello di superare il limite 1-WL.

2. Predizione di Proprietà Molecolari QM9:

   • Obiettivo: Predire il gap HOMO–LUMO per 130.831 molecole.
   • Risultato: L'aumento del numero di particelle $j$ da 1 a 3 ha ridotto l'Errore Assoluto Medio (MAE) da 0,398 eV a 0,235 eV, nonostante il mantenimento di un numero di parametri quasi costante. Ciò dimostra che una risoluzione strutturale di ordine superiore migliora le prestazioni su compiti chimici reali.

3. Problema del Commesso Viaggiatore Euclideo (TSP):

   • Obiettivo: Trovare tour quasi ottimali per $N$ città ($N$ fino a 50).
   • Risultato: Il modello ha prodotto tour con un rapporto di 1,201 per $N=50$ (dove 1,0 è l'ottimo). Fondamentalmente, il modello è rimasto addestrabile a queste scale.
   • Addestrabilità: La varianza del gradiente è rimasta polinomiale (non esponenziale) all'aumentare del numero di qubit fino a 56. Il transfer learning (inizializzare modelli più grandi da modelli più piccoli addestrati) ha mantenuto i segnali di gradiente di 1–2 ordini di grandezza più alti rispetto all'inizializzazione casuale.
   • Readout: I readout basati su matchgate hanno superato significativamente quelli basati sulla base computazionale, recuperando le informazioni fuori diagonale essenziali per la prestazione del compito.

Significatività e Rivendicazioni

Il paper sostiene di aprire una strada per algoritmi quantistici nel regime NISQ (Near-term Intermediate-Scale Quantum) che possiedano sia garanzie teoriche che scalabilità pratica.

• Colmare il divario tra Teoria e Pratica: Porta i principi dell'apprendimento su grafi (passaggio di messaggi, equivarianza, gerarchia WL) direttamente nel design dei circuiti quantistici, andando oltre i modelli quantistici euristici.
• Risolvere l'Addestrabilità: Utilizzando la dinamica preservante il sottospazio e il pre-addestramento, il lavoro affronta il collo di bottiglia dei plateau sterili, dimostrando che i modelli grafici quantistici possono essere addestrati su istanze di grandi dimensioni.
• Espressività: Fornisce il primo modello grafico quantistico con garanzia dimostrata capace di superare il limite di espressività 1-WL, offrendo una base teorica per distinguere strutture di grafi complesse che le reti di passaggio di messaggi classiche non riescono a cogliere.

Gli autori sottolineano che, sebbene la validazione attuale sia tramite simulazione classica, l'architettura è progettata per essere compatibile con l'hardware quantistico nel vicino futuro (richiedendo circa 56 qubit per $N=50$), con costi di readout che scalano polinomialmente con la dimensione delle feature piuttosto che con la dimensione del grafo.