Applying quantum annealing to an extension of the traveling salesperson problem : implementation and resulting methodology

Nowadays implementations of quantum algorithms are mainly focusing on the description of simple and well-known problems to show the possible advantages brought by quantum computing. By considering a real-world application modeled as the extension of a Traveling Salesperson Problem we aim at understanding how far quantum computing can be pushed and how effective is this technology when applied to real data. Since we considered a variation of the TSP we decided to choose the quantum annealing model that provides simple formulations of problems like the TSP belonging to the NP class. Starting from the mathematization in both the classical and the quantum worlds we begin to explain how the software is structured focusing on the most relevant steps that characterize the implementation of algorithms with quantum annealing. The extended version of the TSP will be called the LTSP for the structural change brought by "lines" in the graph that defines the problem. Our awareness grown in the field of quantum annealing made us believe that the methodology followed could be considered as a reference guide to implement algorithms as the energy of a quantum system. From the programming point of view, the quantum software developed is able to correctly solve the case study problem both on the real quantum hardware and on the hybrid solver. This is going to show the effects of quantum annealing not only on trivial examples but also on instances of the LTSP that represent a real-world application; the tuning processes on the chain strength and the anneal schedule parameters allow to explain for instance how to improve the quality of the solutions found.

Oggigiorno, le applicazioni del quantum computing riguardano principalmente semplici e ben conosciuti problemi per i quali vengono mostrati i vantaggi portati dal quantum. Sfruttando un'applicazione reale che può essere modellata come un estensione del Traveling Salesperson problem, si vogliono mostrare i limiti di questo paradigma computazionale e il suo effetto su dati reali. Abbiamo deciso di sfruttare il quantum annealing model per definire il problema grazie alla sua semplicità nella formulazione di problemi che appartengono alla classe NP. Partendo dalla modellizzazione matematica in entrambe le formulazioni classica e quantistica si possono identificare gli step più importanti che caratterizzano lo sviluppo del software basato sul quantum annealing. Dato che l'estensione corrisponde a una modifica strutturale causata dalla definizione di una "linea" nel grafo che definisce il TSP, abbiamo deciso di chiamare il problema studiato come LTSP. La consapevolezza sviluppata nell'esprimere problemi come l'energia di un sistema quantistico ci ha permesso di credere che gli step identificati nella nostra metodologia possano essere generalizzati per l'implementazione di altri algoritmi basati sul quantum annealing. Il software realizzato è in grado di risolvere correttamente istanze dell'LTSP sfruttando esecuzioni sia sulla vera macchina quantistica che sulla soluzione ibrida. Grazie a questo software è possibile vedere gli effetti del quantum computing non più su esempi ma su istanze di un problema che corrispondono ad un'applicazione reale. I processi di tuning sui parametri chiamati chain strength e anneal schedule, ad esempio, rappresentano un elemento fondamentale per migliorare la qualità delle soluzioni trovate.