Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems

Riepilogo Tecnico: Embedding di Grafi a Disco Unitario Alimentato da Reti Neurali per Problemi QUBO

Enunciato del Problema
Il documento affronta la sfida critica di mappare problemi di Ottimizzazione Binaria Quadratica Senza Vincoli (QUBO) su simulatori quantistici basati su atomi neutri, in particolare quelli che utilizzano atomi di Rydberg (ad esempio, il prototipo Pasqal Chadoq2). A differenza dei computer quantistici basati su porte o degli annealer a topologia fissa (come D-Wave), i dispositivi a atomi neutri consentono il posizionamento arbitrario dei qubit in spazi 2D o 3D. Tuttavia, le interazioni fisiche tra questi qubit sono governate dall'effetto di blocco di Rydberg: i qubit separati da una distanza inferiore a un specifico "raggio di blocco" ($r_b$) non possono essere eccitati simultaneamente, creando un pattern di adiacenza equivalente a un grafo a Disco Unitario (UD).

La difficoltà principale risiede nel problema di embedding di grafi a Disco Unitario: trovare un insieme di coordinate fisiche per i qubit tale che:

1. I qubit adiacenti nel grafo QUBO target siano entro il raggio di blocco ($d_{ij} \leq \tilde{r}_b$).
2. I qubit non adiacenti siano fuori dal raggio di blocco ($d_{hk} > \tilde{r}_b$).
3. Tutti i qubit rientrino nei vincoli del registro fisico (ad esempio, un dominio circolare di raggio 50 $\mu$m) e rispettino i limiti di separazione minima (ad esempio, 4 $\mu$m) per evitare sovrapposizioni.

Gli autori osservano che, sebbene calcolare l'adiacenza dalle coordinate sia banale, il problema inverso — trovare coordinate che soddisfino una specifica matrice di adiacenza — è NP-difficile. I solver classici spesso non riescono a trovare embedding fattibili per istanze QUBO complesse o su larga scala entro tempi ragionevoli.

Metodologia: GEAN (Graph Embedding Autoencoder Network)
Gli autori propongono GEAN, un'euristica basata su reti neurali progettata per trasformare una configurazione iniziale di qubit, spesso non fattibile, in un embedding UD valido. L'approccio tratta il compito di embedding come un problema di trasformazione di dominio piuttosto che come un compito di previsione standard.

• Architettura:
  • Input/Output: La rete prende le coordinate iniziali 2D o 3D $(x_i, y_i, z_i)$ per $n$ qubit e restituisce coordinate trasformate $(x'_i, y'_i, z'_i)$.
  • Componente Autoencoder: Una rete simmetrica completamente connessa (input $\to$ livelli nascosti $\to$ output) trasforma le coordinate. Il livello di output utilizza un'attivazione tanh scalata al dominio fisico ($\pm 50$ $\mu$m).
  • Livello di Distanza Differenziabile: Un livello specializzato, non addestrabile e sparso, calcola la distanza euclidea tra tutte le coppie di qubit basandosi sulle coordinate trasformate. Questo permette alla rete di "vedere" i vincoli geometrici durante l'addestramento.
• Funzione di Perdita: L'obiettivo dell'addestramento non è minimizzare l'errore di previsione, ma soddisfare simultaneamente quattro vincoli fisici. La funzione di perdita è la somma di quattro termini di penalità:
  1. Confine Globale: Penalizza le coppie che superano il raggio massimo del registro (100 $\mu$m).
  2. Separazione Minima: Penalizza le coppie più vicine della distanza fisica minima (4 $\mu$m).
  3. Vincolo di Adiacenza: Penalizza i qubit adiacenti che sono troppo distanti ($> \tilde{r}_b$).
  4. Vincolo di Non-Adiacenza: Penalizza i qubit non adiacenti che sono troppo vicini ($\leq \tilde{r}_b + \epsilon$).
• Ottimizzazione: Il modello viene addestrato utilizzando l'ottimizzatore AdamW. Il set di addestramento consiste in un singolo campione (l'istanza QUBO specifica), e la rete itera per trovare un insieme di coordinate che minimizzi la perdita, risolvendo effettivamente il problema di embedding per quel grafo specifico.

Contributi Chiave

1. Euristica Neurale per Embedding NP-Difficile: Il documento introduce una nuova applicazione degli autoencoder per risolvere il problema di embedding di grafi a Disco Unitario vincolato, superando i limiti dei solver classici esatti per grafi più grandi o complessi.
2. Integrazione dei Vincoli Fisici: La metodologia incorpora esplicitamente i limiti fisici dell'hardware a atomi neutri (raggio di blocco, separazione minima e dimensione del registro) direttamente nella funzione di perdita e nell'architettura della rete neurale.
3. Flessibilità Dimensionale: L'approccio è dimostrato sia in 2D che in 3D. Gli autori mostrano che estendere la rete al 3D permette l'embedding di grafi con connettività più elevata (clique più grandi e gradi superiori) che è impossibile embeddere in 2D a causa dei limiti di impacchettamento geometrico.
4. Limiti Teorici: Il documento identifica le condizioni necessarie per l'embeddabilità in 2D basandosi sul Teorema di Thue relativo all'impacchettamento di cerchi, stabilendo che la dimensione massima della clique per l'embedding 2D è 7 e il grado massimo è 18 sotto i parametri specifici della macchina ($\tilde{r}_b \approx 10.26$ $\mu$m).

Risultati
Gli autori hanno valutato GEAN contro il solver Gurobi (un solver quadratico classico all'avanguardia) su tre tipi di istanze QUBO:

• Antenne QUBO MIS: Dati reali dalle posizioni delle antenne a Torino. GEAN ha embeddato con successo componenti connesse (fino a 87 qubit in 3D) dove Gurobi non è riuscito a trovare una soluzione fattibile entro il limite di tempo di 2 minuti.
• Folding Proteico: Istanze modellate come problemi di Insieme Indipendente Massimo. GEAN ha trovato embedding fattibili per tutte le istanze testate, mentre Gurobi ha fallito sull'istanza $G_{17,7}$.
• Colorazione di Grafi: Un problema di 3-colorazione mappato su un grafo a 21 qubit. GEAN ha trovato un embedding 3D fattibile in 767 epoche, mentre Gurobi non è riuscito a convergere.

Metriche di Prestazione:

• Velocità: GEAN ha trovato costantemente soluzioni entro 2 minuti su hardware consumer standard, anche per l'istanza 3D più complessa a 87 qubit.
• Fattibilità: Nei casi in cui Gurobi non è riuscito a trovare alcun embedding fattibile entro il limite di tempo, GEAN ha avuto successo.
• Qualità: Le coordinate trasformate hanno soddisfatto tutti i vincoli fisici (distanza minima, distanza massima e separazione del raggio di blocco), convertendo efficacemente configurazioni iniziali "non fattibili" (spesso derivate da layout Fruchterman-Reingold) in layout pronti per l'hardware.

Significato e Affermazioni
Il documento afferma che GEAN fornisce un ponte pratico tra le formulazioni QUBO teoriche e le realtà fisiche dell'hardware quantistico a atomi neutri. Sfruttando le reti neurali per ottimizzare il posizionamento dei qubit, il metodo:

• Supera i Limiti Classici: Supera i solver esatti tradizionali (come Gurobi) nel trovare embedding fattibili per grafi complessi entro tempi pratici.
• Minimizza il Sovraccarico di Risorse: A differenza di approcci che richiedono atomi "cavo" ausiliari o strutture reticolari fisse, GEAN utilizza la piena flessibilità del registro, richiedendo il numero minimo di qubit fisici necessari per il problema.
• Abilita la Scalabilità: La capacità di risolvere rapidamente questi problemi di embedding permette ai ricercatori di testare problemi QUBO non banali sull'hardware attuale, che ha un numero limitato di qubit, senza essere ostacolati dal processo di embedding stesso.

Gli autori concludono che, sebbene il modello sia attualmente sintonizzato su parametri specifici della macchina, il framework è adattabile ad altri vincoli hardware e potrebbe aprire la strada alla risoluzione di classi più ampie di problemi di ottimizzazione oltre il semplice embedding. È proposta un'attività futura per caratterizzare ulteriormente i limiti degli embedding UD fattibili e per validare questi risultati su hardware quantistico reale.