Le 03/11/2023 par Rodolphe Griset :
Les systèmes quantiques programmables utilisant des grilles d’atomes de Rydberg sont bien adaptés pour
résoudre efficacement des algorithmes quantiques. Le problème de stable de cardinalité maximum ou
maximal Independent Set (MIS), un problème NP-difficile très important en recherche opérationnelle, est
nativement encodable sur ce type de systèmes [1]. Les contraintes du MIS se représentent classiquement
sur un graphe dont deux sommets adjacents sont en conflit et ne peuvent appartenir à la solution. Chaque
sommet correspond à un qubit sur une grille 2D et deux atomes adjacents sont naturellement en interaction
dans la limite d’un disque constant supposé unitaire, ce qui correspond à la contrainte du MIS. Cet encodage
appelé Unit Disk Graph (UDG) ajoute toutefois une contrainte géométrique puisque les qubits en interaction
sont limités aux voisins sur la grille. Il est possible de lever cette dernière contrainte en ajoutant des gadgets
avec des qubits auxiliaires [2]. Un objectif important est de minimiser le nombre de qubits pour l’encodage
pour une connectivité quelconque.
Des algorithmes d’optimisation quantique permettent de résoudre des problèmes combinatoires par le
contrôle de la dynamique de systèmes quantiques. L’idée est faire en sorte que leur état final corresponde
aux solutions du problème. L’évolution est contrôlée par le principe adiabatique dans l’algorithme quantique
de recuit (QAA) ou plus généralement par des approches variationelles comme en particulier le Quantum
Approximate Optimization Algorithm (QAOA). Toutefois leur nature heuristique rend difficile d’anticiper les
performances atteignables. Des travaux précédents ont été menés dans le cadre d’une thèse à EDF R&D sur
le problème du MIS appliqué au smart-charging de véhicules électriques par mise en oeuvre de l’approche
QAOA [3]. Des résultats en simulation ont permis d’obtenir des solutions présentant de très bons ratios
d’approximation, au prix d’un paramétrage de la méthode assez délicat à obtenir.
Un objectif prioritaire du stage est de prendre en compte les aspects encodage, ce qui n’a pas été étudié lors
des travaux précédents à EDF R&D. L’enjeu est double. Il s’agit d’une part de lever la contrainte de
connectivité et d’autre part de trouver un encodage efficacement et systématiquement. Un second objectif
est de proposer des algorithmes quantiques pour la résolution. Etant donné que l’encodage du MIS est natif
sur ce type de système, cela devrait être la meilleure configuration pour utiliser QAA dont les réglages sont
plus naturels que ceux de QAOA. Il s’agira d’identifier le potentiel et les limites de cet algorithme sur la base
de l’encodage optimisé.
Pour les tests, des instances du problème de smart-charging seront utilisées sans contraintes additionnelles
puis avec pour voir l’incidence, ainsi que des instances plus générales du MIS incluant celles de cas difficiles
du problème. On pourra faire des essais sur des machines Pasqal.
Conditions matérielles :
Lieu du stage : EDF R&D ; 7, Boulevard Gaspard Monge ; 91120 Palaiseau. Le site est accessible par transports
en commun ou navette depuis Paris Porte d’Orléans. Durée : 6 mois. Rémunération : selon école : entre
960 – 1300 Euros / mois.
Connaissances requises : niveau M2 ou 3ème année école d’ingénieurs
Profil : Recherche opérationnelle, connaissances en informatique / c++, python, notions d’informatique
quantique et algorithme quantique serait appréciable.
Renseignements complémentaires :
Joseph Mikael E-mail : joseph.mikael@edf.fr
Pascale Bendotti E-mail : pascale.bendotti@edf.fr
Références:
[1] Hannes Pichler, Sheng-Tao Wang, Leo Zhou, Soonwon Choi and Mikhail D. Lukin. Quantum Optimization
for Maximum Independent Set Using Rydberg Atom Arrays, arXiv:1808.10816 (2018).
[2] Minh-Thi Nguyen, Jin-Guo Liu, Jonathan Wurtz, Mikhail D. Lukin, Sheng-Tao Wang, and Hannes Pichler.
Quantum optimization with arbitrary connectivity using Rydberg atom arrays. PRX Quantum 4, 010316
(2023).
[3] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron,
and Margarita Veshchezerova. Qualifying quantum approaches for hard industrial optimization problems. A
case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology, 8:12 (2021).
