Stage de Master 2 à EDF Lab Paris-Saclay - Algorithmique quantique

Contexte

Les algorithmes quantiques représentent une nouvelle branche de l’algorithmique, offrant des avantages potentiels par rapport aux algorithmes classiques pour certains problèmes binaires (comme le stable de taille maximum ou la coupe maximale) ou des problèmes formulés naturellement sous forme de problème binaire quadratique sans contraintes (QUBO). De nombreux problèmes de management de l’énergie possèdent des composantes correspondant à cette description.

Cependant, l’algorithmique quantique présente également des limitations intrinsèques ou découlant des limitations associées aux machines actuelles [1],[2] :

• Caractère probabiliste et bruit : La nature probabiliste des mesures et les problèmes de bruit ne garantissent pas l’obtention de la solution optimale.
• Manque d’expressivité : Les différentes approches quantiques ne permettent pas de prendre en compte de manière efficace toutes les contraintes d’un problème industriel, notamment celles comportant des variables continues.
• Limitations matérielles : Les machines quantiques actuelles sont limitées en termes de nombre de qubits et en nombre d’opérations que l’on peut effectuer, ce qui restreint la taille des problèmes pouvant être résolus.

Pour surmonter ces limitations, nous proposons de mettre au point une approche hybride classique-quantique avec les caractéristiques suivantes :

• Résolution itérative : Pour ne pas être limité par des solutions sous-optimales induites par des mesures probabilistes et du bruit.
• Structure de résolution à deux niveaux : Pour inclure les aspects non pris en compte par les algorithmes quantiques.
• Contrôle de la taille du problème quantique résolu : Pour gérer les limitations des machines quantiques actuelles.

Les heuristiques primales basées sur les décompositions, telles que la génération de coupes et de colonnes [3], présentent ces caractéristiques en construisant une approximation du problème initial par l’ajout de variables ou de contraintes, et en contrôlant la taille du problème par branchement.

Objectifs

L’objectif du stage est l’étude des possibilités offertes par des approches hybrides classique-quantiques, en particulier dans le cadre des approches heuristiques itératives basées sur des décompositions. Des résultats liés à des études précédentes réalisées à la R&D d’EDF pourront être utilisés pour certaines composantes de l’approche à développer, notamment les algorithmes quantiques variationnels (QAA et QAOA), la recherche quantique (Groover, amplification d’amplitude), ainsi que les résultats obtenus lors d’une précédente thèse CIFRE [4]. Le stage pourra être poursuivi par une thèse CIFRE.

Conditions matérielles

• Lieu du stage : EDF Lab Paris-Saclay (7, Boulevard Gaspard Monge ; 91120 Palaiseau). Le site est accessible par transports en commun.
• Durée : 6 mois.
• Rémunération : Les stages sont rémunérés en fonction du niveau d’étude et de la formation préparée.

Profil du stagiaire

• Domaines de compétence : École d’ingénieur ou master recherche, niveau master.
• Profil : Algorithmique quantique, recherche opérationnelle, algorithme de décomposition.

Renseignements complémentaires

Candidature (lettre de motivation, CV et relevé de notes) à adresser de préférence directement aux encadrants :

• Rodolphe Griset : rodolphe.griset@edf.fr
• Pascale Bendotti : pascale.bendotti@edf.fr

Références

[1] Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79.

[2] Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., ... & Coles, P. J. (2021). Variational quantum algorithms. Nature Reviews Physics, 3(9), 625-644.

[3] Sadykov, R., Vanderbeck, F., Pessoa, A., Tahiri, I., & Uchoa, E. (2019). Primal heuristics for branch and price: The assets of diving methods. INFORMS Journal on Computing, 31(2), 251-267.

[4] Veshchezerova, M. (2022). Quantum algorithms for energy management optimization problems. Theses, Université de Lorraine, décembre.