Abstract

Les ordinateurs quantiques promettent des accélérations impressionnantes sur des problèmes qui résistent même aux meilleurs supercalculateurs. Le plus célèbre exemple vient de l’algorithme de Shor qui permettrai de casser la plupart des chiffrements asymétriques classiques. Même s’il n’y a pas encore d’avantage démontré, pour les chercheurs en recherche opérationnelle, il existe plusieurs arguments justifiant de s’intéresser aux ordinateurs quantique et à leurs capacités :

• Le premier argument vient de la théorie de la complexité (l’étude de la difficulté de résolution associée à tel ou tel problème). Le fameux problème du millénaire P=NP. Les problèmes classés dans P sont « faciles » à résoudre (et il est donc facile d’en vérifier une solution). Tandis que les problèmes catégorisés NP sont « facile » à vérifier. On sait que P⊂NP. Il existe une classe de problèmes appelés BQP qui contient les problèmes « faciles » à résoudre sur un ordinateur quantique. Il existe des problèmes dans BQP et qui sont dans NP qui ne sont pas dans P. De plus pendant quelques semaines, il a existé un algorithme quantique ayant une meilleure complexité que le meilleur algorithme classique sur un problème NP-complet.
• Un deuxième argument vient du fait que l’architecture physique sur laquelle reposent plusieurs types d’ordinateurs quantiques sont strictement équivalents à des problèmes d’optimisation classiques (max-cut ou Maximum Independent Set (MIS))

Il parait naturel de chercher à savoir si il serait possible d’accélérer la résolution de problèmes de Recherche opérationnelle à l’aide de ces ordinateurs quantiques.

Bio

Martin Bombardelli est ingénieur diplômé de l’ISIMA depuis 2024, spécialisé en recherche opérationnelle et data science. Il a commencé sa formation scientifique en classe préparatoire MPSI-MP. Il est actuellement en deuxième année de thèse CIFRE avec CGI et les laboratoires LPC (Laboratoire de Physique de Clermont Auvergne) et LIMOS (Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes). Il a choisi de poursuivre en thèse car la matière qu’il a le plus appréciée durant son cursus à l’école d’ingénieur était étroitement liée à la recherche, à savoir une introduction à l’informatique quantique. Passionné par les mathématiques, la physique et l’informatique, il s’était progressivement éloigné des aspects plus théoriques de la physique et des mathématiques pendant son cursus d’ingénieur, au profit de la programmation. C’est pour cette raison qu’il a décidé de se tourner vers la recherche à la suite de son diplôme.