Topology-preserving embedding of maximum independent set instances for Rydberg-atom quantum optimizers
Riccardo Vidali · AMS Degree Thesis (University of Bologna) · 2025
Questo lavoro studia la risoluzione di un famoso problema NP-completo, il problema dell'insieme indipendente massimale (MIS), nel contesto dei grafi a disco unitario bidimensionali. Il MIS è un problema paradigmatico di elevata complessità, con applicazioni che spaziano dalla progettazione di reti e dall’allocazione di risorse alla teoria dei codici, e rappresenta un banco di prova standard sia per metodi di ottimizzazione classici sia quantistici. Nel nostro approccio, riformuliamo innanzitutto il MIS come un problema QUBO (quadratic unconstrained binary optimization) vincolato, ottenendo così un grafo di interazione tridimensionale. Introduciamo quindi un algoritmo di integrazione geometrica che mappa questa istanza tridimensionale in un UDG bidimensionale con sole interazioni tra primi vicini, mantenendo al contempo l’equivalenza topologica con il grafo di interazione originale (cioè preservandone la connettività), rendendola così compatibile con dispositivi quantistici a atomi neutri basati su registri di stati di Rydberg. Analizziamo le prestazioni di questo algoritmo in termini di probabilità di successo e di scalabilità della dimensione finale del grafo rispetto alla dimensione e alla connettività del sistema originale. Infine, affrontiamo il problema MIS sui grafi finali utilizzando un algoritmo ibrido variazionale quantistico-classico della famiglia QAOA (quantum approximate optimization algorithm), e ne confrontiamo le prestazioni con quelle di un risolutore classico di forza bruta. Ciò ci permette di caratterizzare i regimi in cui tali approcci di ispirazione quantistica possono trattare efficacemente istanze di MIS derivanti da grafi a disco unitario, sotto vincoli hardware realistici.