Analog Quantum Computing for NP-Hard Combinatorial Graph Problems - INSA CENTRE VAL DE LOIRE
Thèse Année : 2024

Analog Quantum Computing for NP-Hard Combinatorial Graph Problems

Calcul analogique quantique pour des problèmes combinatoires sur graphes NP-difficile

Arthur Braida
  • Fonction : Auteur
  • PersonId : 1417888
  • IdRef : 280436025

Résumé

The main objective of this thesis is to provide theoretical insight into the computational complexity of continuous-time quantum computing (QA and AQC), from understanding the physical phenomenon (AC) that leads to AQC failure to proving short constant-time QA efficiency. To achieve this goal, we use different analytical tools borrowed from theoretical physics like perturbative analysis of quantum systems and the Lieb-Robinson bound on the velocity of correlation in quantum systems. Graph manipulation and spectral graph theory are necessary to derive results on a specific class of graph. We also introduced a new parametrized version of the standard QA to tighten the analysis. First, we want to obtain a mathematical definition of an AC to be easier to grasp when studying a specific class of graph on which we want to solve the Maximum Cut problem. We support our new definition with a proven theorem that links it to exponentially small minimum gap and numerical evidence is brought to justify its more general nature compared to the previous one. With a perturbative analysis, we manage to show that on bipartite graphs, exponentially closing gap can arise if the graph is irregular enough. Our new definition of AC allows us to question the efficiency of AQC to solve it despite the exponentially long runtime the adiabatic theorem imposes to guarantee the optimal solution. The second axis is dedicated to the performance of QA at short constant times. Even though QA is inherently non-local, the LR bound allows us to approximate it with a local evolution. A first approach is used to develop the method and to show the non-triviality of the result, i.e. above random guess. Then we define a notion of local analysis by expressing the approximation ratio with only knowledge of the local structure. A tight and adaptive LR bound is developed allowing us to find a numerical value outperforming quantum and classical (strictly) local algorithms. All this research work has been pursued between Eviden QuantumLab team and the Graphes, Algorithmes et Modèles de Calcul (GAMoC) team at the Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). The numerical work has been implemented using Julia programming Language as well as Python with the QAPTIVA software of Eviden to efficiently simulate the Schrödinger equation.
L'objectif principal de cette thèse est de fournir un éclairage théorique de la complexité du calcul quantique en temps continu (QA et AQC), de la compréhension du phénomène physique (AC) qui conduit à l'échec de l'AQC jusqu'à des preuves de performance de QA en temps court et constant. Pour atteindre cet objectif, nous utilisons différents outils analytiques empruntés à la physique théorique, comme l'analyse perturbative des systèmes quantiques et la borne de Lieb-Robinson sur la vitesse de corrélation dans les systèmes quantiques. La manipulation des graphes et la théorie spectrale des graphes sont nécessaires pour obtenir des résultats sur des classes spécifiques de graphes. Nous avons également introduit une nouvelle version paramétrée du QA standard afin d'affiner l'analyse.Tout d'abord, nous souhaitons obtenir une définition mathématique d'un AC afin d'en faciliter la compréhension lors de l'étude d'une classe spécifique de graphes sur lesquels nous souhaitons résoudre le problème de Maximum Cut. En plus de l'appui analytique que nous développons, nous apportons une étude numérique pour justifier la nature plus générale de notre définition par rapport à la précédente. Grâce à une analyse perturbative, nous parvenons à montrer que sur les graphes bipartis, un gap de fermeture exponentielle peut apparaître si le graphe est suffisamment irrégulier. Notre nouvelle définition de l'AC nous permet de remettre en question l'efficacité de l'AQC pour le résoudre malgré le temps d'exécution exponentiellement long que le théorème adiabatique impose pour garantir la solution optimale. Le deuxième axe est consacré à la performance du QA en temps constant court. Bien que le QA soit intrinsèquement non-local, la borne de LR nous permet de l'approximer avec une évolution locale. Une première approche est utilisée pour développer la méthode et montrer la non trivialité du résultat, c'est-à-dire au-dessus du choix aléatoire. Ensuite, nous définissons une notion d'analyse locale en exprimant le ratio d'approximation avec la seule connaissance de la structure locale. Une borne LR fine et adaptative est développée, nous permettant de trouver une valeur numérique du ratio d'approximation surpassant les algorithmes quantiques et classiques (strictement) locaux. Tous ces travaux de recherche ont été poursuivis entre l'équipe QuantumLab d'Eviden et l'équipe Graphes, Algorithmes et Modèles de Calcul (GAMoC) du Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). Le travail numérique a été implémenté en utilisant le langage de programmation Julia ainsi que Python avec le logiciel QAPTIVA d'Eviden pour simuler efficacement l'équation de Schrödinger.
Fichier principal
Vignette du fichier
2024ORLE1017_va.pdf (13.71 Mo) Télécharger le fichier
Origine Version validée par le jury (STAR)

Dates et versions

tel-04706199 , version 1 (23-09-2024)

Identifiants

  • HAL Id : tel-04706199 , version 1

Citer

Arthur Braida. Analog Quantum Computing for NP-Hard Combinatorial Graph Problems. Computer Science [cs]. Université d'Orléans, 2024. English. ⟨NNT : 2024ORLE1017⟩. ⟨tel-04706199⟩
0 Consultations
0 Téléchargements

Partager

More