Classical and quantum approaches to computational Optimal Transport

Optimal Transport (OT) has been a problem of general interest for centuries. From economics to neuroscience, people have encountered many applications in diverse fields. Its applications and mathematical richness make it a vibrant and attractive problem. Indeed, OT is a convergence point of several branches of modern mathematics. However, modern use cases are computationally demanding and often intractable, making it imperative to seek for new methods to find numerical solutions. Recent advances in quantum computing (QC) are promising candidates for solving computationally demanding problems. Google, for example, claimed quantum supremacy in 2017, and while the claim is highly controversial, it is clear that advances in QC boost advances in classical computing and vice versa. As an attempt to contribute to this symbiotic relationship, this work explores some classical and quantum algorithms for solving OT problems. Along with classical combinatorial methods, and motivated by Brenier's theorem, we write optimal transport plans for quadratic costs as the gradient of convex functions that we estimate using parametrized quantum circuits. We study two alternatives: a new classical approach based on convex interpolation, and a solution based on variational quantum linear solvers for NISQ devices implemented in IBM's quantum processors. Finally, we discuss the advantages and disadvantages of the quantum version of the problem and compare various performance metrics against their classical counterparts.

Il Trasporto Ottimale (OT per il suo acronimo in inglese) è da secoli un problema di interesse generale. Dall’economia alle neuroscienze, le persone hanno riscontrato molte applicazioni in diversi campi. Le sue applicazioni e la ricchezza matematica lo rendono un problema vibrante e attraente. In fatti, OT è un punto di convergenza di diversi aree della matematica moderna. Tuttavia, i casi d’uso moderni sono impegnativi dal punto di vista computazionale e spesso intrattabili, rendendo imperativo cercare nuovi metodi per trovare soluzioni numeriche. I recenti progressi nel campo della computazione quantistica (QC) sono candidati promettenti per risolvere problemi computazionalmente impegnativi. Google, ad esempio, ha rivendicato la supremazia quantistica nel 2017 e, sebbene l’affermazione sia molto controversa, è chiaro che i progressi nel controllo di qualità stimolano i progressi nell’informatica classica e viceversa. Nel tentativo di contribuire a questa relazione simbiotica, questo lavoro esplora alcuni algoritmi classici e quantistici per risolvere problemi OT. Insieme ai metodi combinatori classici e motivati dal teorema di Brenier, scriviamo piani di trasporto ottimali per i costi quadratici come il gradiente di funzioni convesse che stimiamo utilizzando circuiti quantistici parametrizzati. Studiamo due alternative: un nuovo approccio classico basato sull'interpolazione convessa e una soluzione basata su solutori lineari quantistici variazionali per dispositivi NISQ implementati nei processori quantistici IBM. Infine, discutiamo i vantaggi e gli svantaggi della versione quantistica del problema e confrontiamo vari parametri di prestazione con le loro controparti classiche.