Single-agent Graph Embedding for Quantum Computers via reinforcement learning

In the current era, even with the advanced computational capabilities of supercomputers, NP-hard problems continue to pose significant challenges. The case of Graph Minor Embedding problem is a significant example of that, which aims to identify a smaller graph H as a minor of a larger graph G. A major quantum computing paradigm such as adiabatic quantum computing requires to embed problems on a graph of quantum bits, in order to map it and next to produce the solution after an annealing cycle. The current state of the art in this field is represented by heuristics, especially the minorminer heuristic employed by D-Wave for its Quantum Computers. A promising complementary approach to explore is Reinforcement Learning techniques, which could be employed to boost the performance of these heuristics by providing them with a so-called sweet-start, an improved starting position that helps the heuristic perform better. With this premise, in this work, we propose an implementation with Reinforcement Learning that processes the source graph H in order to increase the sparsity of nodes overcrowded with edges, with the aim of granting minorminer with a sweet-start and boost in performance. Here, we test a variety of Reinforcement Learning models with different hyperparamters, custom parameters, and algorithms on graphs with 30 nodes, and for the best performing ones, we show the embeddings produced along with other useful data that compare the performance with the state of the art heuristic. We show how in some cases there is a boost in performance even though on a general scale the heuristic still performs better. We also test the RL models on graphs with 50 nodes and assess the decrease in performance along with solutions for future implementations.

Nella corrente epoca, pur avendo a disposizione le capacità computazionali avanzate dei supercomputer, i problemi NP-hard continuano a porre delle sfide complicate. Il problema dell'Embedding del Minore di un Grafo è un esempio importante di ciò, il quale punta ad identificare il minore di un grafo H più piccolo in un grafo G più grande. I Computer Quantistici Adiabatici, un importante paradigma del Quantum Computing, necessitano di trovare l'embedding del problema sottoposto, trasformato in un grafo composto da quantum bits in modo da poterlo mappare e di produrre una soluzione dopo un ciclo di annealing. Lo stato dell'arte attuale nel campo del Graph Embedding è rappresentato dalle euristiche, specialmente dall'euristica minorminer, utilizzata da D-Wave per i suoi Computer Quantistici. Un'alternativa promettente da esplorare è l'impiego di tecniche di Apprendimento per Rinforzo, che potrebbero essere utilizzate per incrementare le performance di queste euristiche, fornendo loro un così detto sweet-start, una posizione di partenza favorita che aiuterebbe l'euristica a performare meglio. Con questa premessa, in questa tesi proponiamo un'implementazione tramite Apprendimento per Rinforzo che processa il grafo sorgente H in modo da incrementare la sparsità dei nodi sovrappopolati da archi, con l'obiettivo di fornire a minorminer uno sweet-start che possa incrementarne le performance. In questo lavoro, implementiamo una varietà di modelli RL utilizzando differenti iperparametri, parametri personalizzati e algoritmi su grafi con 30 nodi, e per i modelli più performanti mostreremo l'embedding generato insieme ad altri dati utili per il confronto con la performance dell'euristica stato dell'arte. Mostriamo come in alcuni casi ci sia stato un incremento delle performance ma comunque in generale l'euristica abbia performato meglio. Sperimentiamo anche modelli RL su grafi di 50 e valutiamo il peggioramento della performance, insieme a proporre soluzioni per future implementazioni.