Résumé
Cette thèse est dédiée à la conception et à l’application d’algorithmes quantiques pour la résolution de problèmes d’optimisation combinatoire ferroviaires. Aujourd’hui, les problèmes d’optimisation auxquels fait face la SNCF sont complexes, empêchant souvent une résolution à l’optimalité via des méthodes classiques en un temps raisonnable. L’informatique quantique est pressentie pour améliorer la qualité des solutions et diminuer le temps de calcul pour certains de ces problèmes. Actuellement, les algorithmes quantiques pour l’optimisation se divisent en deux classes : les algorithmes exacts et les heuristiques. Les premiers présentent un avantage théorique pour plusieurs problèmes, mais ne sont pas implémentables sur les machines actuelles car trop gourmands en ressources. Les seconds sont implémentables dès aujourd’hui, au moins sur de petites instances, ouvrant la porte aux premières applications, bien qu’ils ne présentent pas encore de garanties de performances ni d'avantage quantique. Dans cette thèse, nous analysons et proposons des algorithmes qui appartiennent à chacune de ces deux classes.D’une part, nous étudions une classe d’heuristiques appelée Algorithmes Variationnels Quantiques. Il s’agit d’algorithmes hybrides quantique-classique, qui alternent entre l’exécution d’un circuit quantique paramétré et l’optimisation classique des paramètres. Ils permettent de résoudre des problèmes non contraints à variables binaires, et nous proposons une méthode générale pour reformuler des problèmes contraints à variables entières sous cette forme. Nous présentons certaines propriétés des Algorithmes Variationnels Quantiques, nécessaires pour envisager des preuves théoriques de garanties de performances. En particulier, nous étudions QAOA (Quantum Approximate Optimization Algorithm) en l'analysant à la lumière des précédentes propriétés et en donnant une décomposition universelle de son circuit quantique pour des problèmes dont la fonction objectif est polynomiale. Avec cet algorithme, nous résolvons un problème de conception de plan de transport de la SNCF. Ce problème a pour but de trouver un plan de transport qui correspond au meilleur compromis économique entre les bénéfices générés par la vente de billets aux voyageurs et les coûts d'exploitation, tout en respectant la disponibilité du réseau ferroviaire. Pour résoudre ce problème avec QAOA, nous proposons deux simplifications correspondant à différentes adaptations du problème métier initial.D’autre part, nous élaborons des algorithmes quantiques-classiques exacts pour deux grandes familles de problèmes combinatoires. La première famille concerne les problèmes d’ordonnancement. L’algorithme proposé s’applique à une large classe de problèmes d’ordonnancement à une machine, NP-difficiles, qui satisfont une propriété de programmation dynamique particulière (Dynamic Programming Across the Subsets). L’algorithme, reprenant l’idée de Ambainis et al. (2019), allie la programmation dynamique classique et l’algorithme quantique de recherche du minimum dans une table (basé sur l’algorithme de Grover). Il permet de réduire la complexité en temps pire-cas, parfois au détriment de l’introduction d’un terme pseudo-polynomial. Nous étendons cet algorithme au problème du flowshop à trois machines, pour lequel une accélération est aussi obtenue. La deuxième famille relève des problèmes d’optimisation robuste où l’ensemble d’incertitude est un polytope. Nous proposons un algorithme qui, partant de l’algorithme classique traitant de ces problèmes, remplace certaines opérations par des routines quantiques afin d’obtenir une accélération. Précisément, nous étudions l'utilisation des deux routines quantiques suivantes : la recherche du minimum dans une table et la résolution d’un système linéaire.