Neural optimization for quantum architectures: graph embedding problems with Distance Encoder Networks

Enunciato del Problema

Il lavoro affronta la sfida di mappare problemi di ottimizzazione combinatoria su hardware quantistico basato su atomi neutri. Nello specifico, si concentra sul problema del Grafo a Disco Unitario Vincolato (CUDG). Nelle architetture quantistiche a atomi neutri, i qubit sono rappresentati da atomi di Rydberg posizionati su un registro 2D o 3D. Le loro interazioni sono governate da un "effetto di blocco", che crea un pattern di connettività equivalente a un Grafo a Disco Unitario (UDG).

La difficoltà fondamentale risiede nel compito di embedding: trovare le coordinate spaziali di $n$ qubit in modo che le interazioni fisiche risultanti (determinate dalle distanze interatomiche) riproducano una matrice di adiacenza desiderata (pattern di connettività) rispettando al contempo vincoli hardware rigorosi:

1. Distanza minima ($D_{min}$): Gli atomi non possono essere posizionati più vicini di una specifica soglia (ad esempio, 4 $\mu$m) a causa delle limitazioni dei pinzette ottiche.
2. Raggio massimo di interazione ($D_{adj}$): I qubit interagenti devono trovarsi entro un intervallo di distanza specifico (ad esempio, $\approx$10.26 $\mu$m).
3. Dimensione del registro ($L$): Tutti gli atomi devono rientrare in un'area circolare di raggio $L$ (ad esempio, 50 $\mu$m).
4. Massimizzazione del gap di adiacenza: La soluzione dovrebbe massimizzare la differenza tra la distanza minima delle coppie non adiacenti e il raggio di interazione delle coppie adiacenti per garantire robustezza.

Questo problema è NP-difficile e non convesso. I solver classici (come la Programmazione Quadratica a Numeri Interi Mista o la Programmazione Non Lineare) faticano con la scalabilità e spesso non riescono a trovare soluzioni ammissibili per istanze di grafi più grandi entro tempi ragionevoli.

Metodologia

Gli autori propongono un Framework di Ottimizzazione Potenziato da Reti Neurali centrato su un'architettura personalizzata chiamata Distance Encoder Network (DEN) e una specifica Funzione di Perdita per l'Embedding (ELF).

1. La Distance Encoder Network (DEN)

La DEN è un autoencoder modificato progettato per apprendere una trasformazione spaziale non lineare.

• Input: Coordinate iniziali dei vertici del grafo ($\vec{p}_i$), generate tramite una fase di pre-elaborazione.
• Architettura:
  • Autoencoder Addestrabile: Comprime le coordinate di input attraverso livelli completamente connessi con attivazioni ReLU e dropout, per poi ricostruirle in un nuovo insieme di coordinate ($\vec{p}^f_i$).
  • Calcolatore di Distanza a Pesi Fissi: Un componente non addestrabile che prende le coordinate ricostruite e calcola le distanze euclidee al quadrato tra tutte le coppie di vertici ($||\vec{p}^f_i - \vec{p}^f_j||^2$). Questo strato utilizza pesi fissi ($\pm 1, 0$) per eseguire la sottrazione vettoriale e il quadrato, garantendo che la rete produca metriche di distanza valide.
• Inizializzazione tramite Pre-elaborazione: Vengono utilizzati due metodi per generare le coordinate iniziali:
  • Scalatura: Scalatura di coordinate casuali per adattarle al raggio del dominio $L$.
  • Fruchterman-Reingold: Un algoritmo di layout basato su forze che utilizza forze attrattive/repulsive basate sulla matrice di adiacenza del grafo.

2. La Funzione di Perdita per l'Embedding (ELF)

Invece di utilizzare la retropropagazione standard su un dataset statico, la rete viene addestrata per minimizzare una funzione di perdita personalizzata che codifica direttamente i vincoli CUDG. L'ELF combina due componenti basate sulla Margin Ranking Loss:

• $ELF_{min}$: Impone limiti inferiori. Penalizza i casi in cui i vertici adiacenti sono troppo distanti o i vertici non adiacenti sono troppo vicini (violando la separazione minima per le coppie non interagenti).
• $ELF_{max}$: Impone limiti superiori. Penalizza i casi in cui i vertici adiacenti superano il raggio di interazione o i vertici non adiacenti sono troppo vicini.
• Obiettivo: La perdita totale guida la rete a trovare coordinate in cui i vincoli di distanza sono soddisfatti (ammissibilità) massimizzando implicitamente il "gap di adiacenza" (il margine tra distanze ammissibili e non ammissibili).

3. Strategia di Addestramento

Il framework tratta ogni istanza di grafo come un compito di addestramento indipendente. La rete viene addestrata per un numero fisso di epoche (ad esempio, 3000) utilizzando l'ottimizzatore AdamW. Il processo itera per trovare il miglior embedding ammissibile, aggiornando il parametro target "gap di adiacenza" ($\alpha$) ogni volta che viene trovata una soluzione ammissibile migliore.

Contributi Chiave

1. Framework Innovativo: Introduzione di un approccio di ottimizzazione potenziato da reti neurali specificamente adattato al problema CUDG nelle architetture quantistiche a atomi neutri.
2. Distance Encoder Network (DEN): Un'architettura di autoencoder specializzata che integra un calcolatore di distanza a pesi fissi per produrre direttamente distanze euclidee al quadrato, permettendo l'applicazione diretta dei vincoli alle proprietà geometriche.
3. Funzione di Perdita per l'Embedding (ELF): Una formulazione di perdita personalizzata che traduce vincoli geometrici rigidi (disuguaglianze sulle distanze) in un obiettivo di ottimizzazione differenziabile, consentendo alla rete di apprendere configurazioni spaziali ammissibili.
4. Gestione della Non Convessità: L'approccio sfrutta le capacità di approssimazione delle reti neurali per navigare nello spazio delle soluzioni non convesso del problema CUDG, dove i solver classici spesso falliscono.

Risultati Sperimentali

Gli autori hanno valutato il framework su un dataset di 200 istanze di grafi (con un numero di vertici $n$ compreso tra 10 e 100) confrontandolo con il solver classico Ipopt.

• Ammissibilità: Il framework basato su DEN ha superato significativamente Ipopt nel trovare embedding ammissibili. Mentre Ipopt non è riuscito a trovare soluzioni per molte istanze (specialmente all'aumentare di $n$), il modello DEN ha trovato con successo embedding ammissibili per una percentuale molto più ampia del dataset, incluse istanze con fino a 100 vertici nello spazio 3D.
• Dimensionalità: Il modello ha trovato soluzioni ammissibili più facilmente in 3D ($N=3$) rispetto al 2D ($N=2$), probabilmente a causa del maggior numero di gradi di libertà.
• Tempo di Calcolo: Il tempo di addestramento del modello DEN è scalato linearmente con il numero di vertici. Anche quando a Ipopt è stato concesso un tempo significativamente maggiore (10 volte il tempo di addestramento del DEN), non è riuscito a risolvere istanze che il DEN ha risolto rapidamente.
• Gap di Adiacenza: Sebbene il modello DEN abbia eccellito nel trovare soluzioni ammissibili, il solver classico (quando ha avuto successo) ha talvolta prodotto embedding con un gap di adiacenza più ampio. Gli autori notano che l'ottimizzazione del gap rimane una sfida per l'approccio neurale.

Significato e Affermazioni

Il lavoro afferma che il framework proposto fornisce un'alternativa praticabile ai solver classici per problemi di embedding nell'hardware quantistico, in particolare dove i metodi classici faticano con la non convessità e la scalabilità.

• Impatto Pratico: Consente la mappatura di complessi problemi QUBO su architetture a atomi neutri, un passaggio critico per l'utilizzo di queste macchine quantistiche.
• Generalizzabilità: Gli autori suggeriscono che l'architettura DEN e la strategia ELF sono generalizzabili ad altri problemi di ottimizzazione che coinvolgono vincoli di distanza euclidea e modellazione di disuguaglianze.
• Lavori Futuri: Il lavoro riconosce modestamente le limitazioni, in particolare riguardo alla massimizzazione del gap di adiacenza e alla necessità di regolazione degli iperparametri. Propone lavori futuri per migliorare l'utilizzo della GPU (tramite mini-batching) e per affinare l'ottimizzazione del parametro del gap di adiacenza.

Gli autori sottolineano che, sebbene l'approccio attuale non garantisca il gap di adiacenza ottimale, il suo contributo principale è la capacità di trovare soluzioni ammissibili per un insieme più ampio di istanze di grafi rispetto a quanto possibile in precedenza con i metodi classici.