Graph neural networks and reinforcement learning for minor embedding in Quantum Annealing

Quantum Annealers (QA) are a paradigm of Quantum Computers designed to solve combinatorial optimization problems by leveraging quantum mechanical laws, such as quantum tunnelling and entanglement. Quantum Annealers are a promising technology with the potential of solving NP-hard combinatorial optimization problems in a reasonable time, offering a relevant speed-up w.r.t classical computers. One of the main challenges when solving a problem on a QA, is the process of mapping the problem written in the QUBO formulation to the topology of the QA. Due to the variable structure of the problem to be solved and the rigid and sparse structure of the Quantum Annealers, finding a good mapping can become computationally expensive and it can reduce the advantage obtained by using a Quantum Computer. In this thesis we develop a PPO-based Reinforcement Learning model capable of finding Minor Embeddings for QUBO problems. The model is shaped to work as a Curriculum Learning process and it is integrated with Graph Neural Networks to help the agent better understand the structure of the problem and the topology of the QA. The model is trained on a dataset composed of connected graphs with 3 to 11 nodes representing generic QUBO problems, ordered by increasing size and equally distributed according to their isomorphisms and their number of edges. The embeddings are performed on D-Wave Chimera and Zephyr topologies with up to 1152 and 2176 qubits, respectively. The goodness of the results is compared with state-of-the-art heuristic MinorMiner, since for the problems faced this algorithm's solutions are near-optimal. We show that our model is always able to find valid embeddings using on average a maximum of 21% more qubits than MinorMiner. Overall the quality of the results is good and the model developed represents an innovative and promising approach, it has the potential to serve as a starting point for using Reinforcement Learning models to find Minor Embedding for Quantum Annealers.

I Quantum Annealers (QA) sono un paradigma di computer quantistici progettati per risolvere problemi di ottimizzazione combinatoria sfruttando leggi della meccanica quantistica. I Quantum Annealers rappresentano una tecnologia promettente, con il potenziale di risolvere in modo efficiente problemi di ottimizzazione combinatoria NP-hard, offrendo un rilevante vantaggio in termini di velocità rispetto ai computer classici. Una delle principali sfide nella risoluzione di un problema su un QA è il processo di mappatura del problema, scritto nella formulazione QUBO, sulla topologia del QA. A causa della struttura variabile del problema da risolvere e della struttura rigida e sparsa dei Quantum Annealers, trovare una buona mappatura può diventare computazionalmente costoso, riducendo così il vantaggio ottenuto con l’uso di un computer quantistico. In questa tesi sviluppiamo un modello di Reinforcement Learning basato su PPO, capace di trovare Minor Embeddings per problemi QUBO. Il modello è strutturato per funzionare come un processo di Curriculum Learning ed è integrato con Graph Neural Networks per aiutare l’agente a comprendere meglio la struttura del problema e la topologia del QA. Il modello è stato addestrato su un dataset composto da grafi connessi con 3 a 11 nodi, che rappresentano problemi QUBO generici, ordinati per dimensione crescente e distribuiti equamente in base ai loro isomorfismi e al numero di archi. Gli embeddings sono stati eseguiti sulle topologie Chimera e Zephyr di D-Wave, con un massimo di 1152 e 2176 qubits rispettivamente. La qualità dei risultati è confrontata con l’algoritmo MinorMiner, considerato di riferimento, poiché le soluzioni di questo algoritmo sono quasi ottimali per i problemi affrontati. Dimostriamo che il nostro modello riesce sempre a trovare embeddings validi, utilizzando in media un massimo del 21% di qubit in più rispetto a MinorMiner. Complessivamente, la qualità dei risultati è buona e il modello sviluppato rappresenta un approccio innovativo e promettente, con il potenziale per costituire un punto di partenza nell’uso di modelli di Reinforcement Learning per trovare Minor Embedding per Quantum Annealers.