Optimisation quantique pour problèmes de tournées de véhicules

Description du projet

Contexte 

L’équipe du Professeur Yves Bérubé-Lauzière a récemment obtenu un financement de plus de 550k$ sur 4 ans pour le projet Quantum Quick Route (QQR), et cherche à compléter l’équipe de recherche. Réalisé dans le cadre d’un partenariat entre la compagnie PASQAL et l’Université de Sherbrooke, ce projet vise à développer de nouvelles approches et algorithmes pour résoudre des problèmes de tournées de véhicules (le fameux « vehicle routing problem », ou VRP qui est une version élaborée du problème du commis voyageur – « traveling salesman problem ») à l’aide d’ordinateurs quantiques à atomes neutres tels que développés et fabriqués par PASQAL. Ces problèmes, où l’on désire optimiser la route pour chaque véhicule d’une flotte pour minimiser le coût des trajets, sont présents dans de nombreuses industries (p.ex. pour des livraisons). Il s’agit d’un problème difficile de classe NP où les approches exactes prennent un temps exponentiel. Les pistes de solution les plus couramment utilisées relèvent des méthodes heuristiques classiques, tels que le recuit simulé ou les algorithmes génétiques. Il a été proposé que les ordinateurs quantiques pourraient accélérer la solution de plusieurs problèmes combinatoires tels le VRP, mais les approches génériques n’ont pour l’instant offert aucun avantage pour les problèmes de tournées de véhicules. La compagnie PASQAL a récemment démontré d’importants résultats en optimisation combinatoire à l’aide de nouveaux algorithmes utilisant son ordinateur quantique pour générer des résultats partiels accélérant la convergence vers un résultat optimal. Ces approches hybrides utilisent à leur avantage la possibilité de reprogrammer des registres d’atomes neutres ainsi que la haute-fidélité du contrôle global des états quantiques pour réaliser des algorithmes quantiques analogiques. 

Description du projet

L’objectif du projet QQR est de développer de nouveaux algorithmes hybrides compatibles avec la plateforme de calcul quantique du partenaire industriel PASQAL pour résoudre différents problèmes de routage, tels que le problème du commis voyageur ou bien le problème de tournées de véhicules. Le mode de calcul quantique dit « analogique » sera à la base des algorithmes à développer. Le candidat retenu pour ce postdoctorat devra contribuer au développement théorique des algorithmes et sera chargé de développer l’architecture hybride de la librairie Python pour le partenaire industriel ainsi que d’améliorer l’efficacité des sous-routines classiques.

Partenaire

PASQAL est un leader mondial dans la fabrication de processeurs quantiques construits à partir de réseaux d'atomes piégés. Basée en France, PASQAL est très présente dans la zone d'innovation quantique de Sherbrooke, avec une chaîne de montage déjà établie dans l'Espace Quantique 1 de la ville.

Équipe et environnement

La candidate ou le candidat aura accès à des super-calculateurs parallèle et séquentiel accessibles à l’Université de Sherbrooke (http://ccs.usherbrooke.ca/). Un PC et les outils logiciels nécessaires aux travaux seront également fournis. La personne recherchée fera partie d’un groupe de recherche comprenant un coordonnateur à la recherche ainsi qu’un étudiant au doctorat en cours de recrutement. De plus, nous faisons partie de l'environnement de recherche dynamique de l'Institut quantique, un institut de recherche qui comprend plus de 30 groupes de recherche de la Faculté des sciences, de la Faculté de génie, de la Faculté des lettres et sciences humaines et de l'École de gestion, 25 membres du personnel technique et professionnel, et plus de 200 personnes étudiantes et stagiaires postdoctoraux.


Profil recherché

Le projet fait intervenir des notions d’informatique quantique (algorithmes analogiques, atomes neutres, techniques d’optimisation hybrides quantique/classique), de mathématiques numériques et appliquées (méthodes numériques, optimisation combinatoire et recherche opérationnelle) et de programmation en Python. La candidate ou le candidat doit avoir eu une formation (physique, ingénierie, mathématique ou informatique) en lien avec le projet et être à l’aise avec ces différentes notions et manifester un grand intérêt pour celles-ci. Il doit également avoir un solide dossier académique. La connaissance de la programmation orientée-objet en C/C++ ainsi qu’une familiarité avec les logiciels de contrôle de version Git seront des atouts.

Financement

La candidate ou le candidat retenu se verra attribuer un financement compétitif sur les fonds de M. Bérubé-Lauzière pour une durée maximale de 36 mois. 

Candidature

Les personnes intéressées doivent fournir les éléments suivants :
- Lettre de motivation;
- CV comprenant (i) une liste de publications et (ii) les noms et coordonnées de deux références.
SVP envoyer un courriel à yves.berube-lauziere@usherbrooke.ca ayant comme sujet "Candidature - QQR".

Financement offert

Oui

Partenaire(s)

Pasqal

La dernière mise à jour a été faite le 17 mai 2024. L’Université se réserve le droit de modifier ses projets sans préavis.