Neutral atoms quantum computer scheduling by deep reinforcement learning

Nowadays, despite supercomputers' computational power, the complexity of NP-hard problems remains a computational challenge. An example is the Maximum Independent Set (MIS) problem, which looks for the largest possible group of vertices within a graph such that no pair of selected vertices share an edge. However, Quantum Computing offers a promising avenue for addressing NP-hard problems. A Neutral Atoms Quantum Computer (NAQC) with Rydberg states implements naturally the MIS problem, because of the possible logical connection between the independent set constraint and the Rydberg Blockade phenomenon. Here, we have considered Aquila, a field programmable qubit array based on 256 neutral atoms (or qubits) whose input parameters are tunable. In principle, the graph under investigation is mapped on the atoms of Aquila and after a software controlled pulse, the measurements may return the solution of the MIS problem with a certain probability (MIS probability) which depends on the specific graph. Previous studies on how to tune Aquila's scheduling in order to increase the MIS probability were done using non-gradient based algorithms such as covariance matrix adaptation evolution strategy algorithm and Nelder–Mead. Despite their exciting results, these studies left open questions about the usage of classical optimizers better suited for fine tuning these parameters. Therefore, we propose to use Deep Reinforcement Learning (Deep RL) techniques to schedule these parameters. We aim to train an agent to create the schedule for a given input graph aiming to improve the MIS probability. It is made possible by making the agent interact with Aquila simulator in a suitable RL environment. In this Thesis, initially, we test different RL environments and we show the MIS probability for each specific input graph and the corresponding scheduling found by the agent. Then, we investigate graphs with 5 vertices and for some of them we are able to find a probability close to 95% using a scheduling not documented in the literature. Finally, we examine the extension of the proposed solution with more atoms and different settings.

Al giorno d’oggi, nonostante le capacità computazionali senza precedenti dei supercomputer, la complessità dei problemi NP-hard continua a porre ostacoli computazionali. Un esempio è il problema del Maximum Independent Set (MIS), che cerca di identificare il gruppo più grande possibile di vertici all'interno di un grafo in modo tale che nessuna coppia di vertici selezionati sia connesso. L’informatica quantistica è sul punto di trasformare le capacità computazionali, offrendo una strada promettente per affrontare problemi NP-hard. Un computer quantistico ad atomi neutrali (NAQC) con stati di Rydberg implementa naturalmente il problema del MIS, per via della possibile connessione logica tra il vincolo dell'insieme indipendente e il fenomeno del blocco di Rydberg. Qui, abbiamo considerato Aquila, un array di qubit programmabile sul campo basato su 256 atomi neutri (o qubit) i cui parametri di input sono sintonizzabili. Precedenti studi sulla pianificazione dell'Aquila con la più alta probabilità di trovare il MIS sono stati condotti utilizzando algoritmi quantistici, come l'algoritmo della strategia di evoluzione dell'adattamento della matrice di covarianza e Nelder-Mead. Nonostante i risultati entusiasmanti, questi studi hanno lasciato delle domande aperte sull’utilizzo degli ottimizzatori classici più adatti per il tuning di questi parametri. Pertanto, proponiamo di utilizzare tecniche di Deep Reinforcement Learning (deep RL) per programmare questi parametri. Il nostro obiettivo è addestrare un agente a creare la pianificazione per un dato grafico di input con l'obiettivo di risolvere il massimo insieme indipendente. Ciò è reso possibile facendo interagire l'agente con il simulatore Aquila in un ambiente RL adatto. In questa tesi, inizialmente, esploriamo diversi ambienti di RL e mostriamo la probabilità di risolvere il problema del MIS per ogni specifico grafico di input e la corrispondente schedulazione trovata dall'agente. Successivamente, analizziamo dei grafi con 5 vertici e per alcuni di essi siamo in grado di trovare una probabilità vicina al 95% utilizzando una scheduling non documentata in letteratura. Infine, esaminiamo l'estensione della soluzione proposta con più atomi e impostazioni diverse.