Retour

Une méthode d'optimisation prometteuse testée sur un dispositif quantique industriel fiable

Publié par

Alexandra De Castro

,

22 février 2024

‍L'algorithme hybride quantique-classique proposé offre la possibilité de résoudre des problèmes insolubles pour les ordinateurs classiques, tels que le problème de l'ordonnancement, l'amarrage macromoléculaire ou la conception de réseaux de distribution d'eau .

 

Dans la quête de l'avantage quantique, tester de nouveaux algorithmes hybrides quantiques-classiques pour résoudre des problèmes inaccessibles aux ordinateurs classiques est une étape cruciale. Un cas pertinent de problème inaccessible, omniprésent dans toutes les industries, apparaît lorsque nous devons trouver la meilleure option parmi de nombreuses combinaisons pour tirer le meilleur parti des ressources disponibles.

Prenons, par exemple, le défi de la planification. Supposons que vous soyez le directeur d'une entreprise de livraison chargée de charger une vaste flotte de camions. Il y a tellement de camions sous votre responsabilité qu'il est impossible de les charger en une seule fois. Vous devez également répartir les tâches de chargement de manière à ce que vos employés n'interfèrent pas les uns avec les autres, afin de maximiser l'équité et la satisfaction des employés et de minimiser le nombre de travailleurs temporaires que votre entreprise doit embaucher. Ce serait formidable si vous pouviez réaliser tout cela ! Mais c'est loin d'être facile.

Le défi de l'ordonnancement, ainsi que de nombreux autres problèmes d'optimisation combinatoire, tels que l'arrimage de macromolécules ou la conception de réseaux de distribution d'eau, se traduisent par un temps de calcul exponentiel en fonction du nombre de combinaisons. Ces problèmes sont qualifiés d'insolubles pour une bonne raison : dans le monde réel, au-delà de quelques centaines de camions et de tâches de chargement, les capacités de calcul classiques sont largement saturées. Nous pourrions parler de millions d'années de temps de calcul classique !

Les entreprises suivent de près l'évolution de l'informatique quantique, qui est appelée à jouer un rôle essentiel dans la prochaine génération de superordinateurs. Les algorithmes quantiques, conçus pour travailler en synergie avec les méthodes classiques, devraient augmenter raisonnablement (au maximum de façon polynomiale) avec le nombre de combinaisons et trouver des solutions fiables. L'une des approches hybrides classiques-quantiques les plus prometteuses pour résoudre les problèmes d'optimisation combinatoire utilise l'algorithme d'optimisation approximative quantique (QAOA).

Depuis quelques années, la méthode QAOA est testée sur différentes plateformes quantiques expérimentales, telles que des réseaux d'atomes neutres, des processeurs supraconducteurs et des simulateurs d'ions piégés

Cette année, des chercheurs de l'université de Bologne, soutenus par CINECA, ont mis en œuvre une méthode QAOA sur Fresnel, le premier dispositif commercial de PASQAL. C'est la première fois qu'une méthode hybride quantique-classique impliquant le QAOA a été testée sur un dispositif quantique industriellement fiable. De plus, la routine classique exécutée sur un centre HPC (High Performance Computing) a collaboré avec le dispositif quantique de manière automatisée et sans faille. 

"Il est très impressionnant que nous n'ayons pas eu besoin de faire beaucoup d'essais pour notre algorithme [sur la machine PASQAL]", a déclaré Simone Tibaldi, doctorant en information et calcul quantiques, sous la direction du professeur Elisa Ercolessi, de l'université de Bologne. "Habituellement, ce type d'optimisation nécessite de nombreux essais. Lorsque l'on utilise d'autres types de plates-formes, il faut plus de temps pour reconstruire le bruit et appliquer des techniques d'atténuation des erreurs, mais avec Fresnel, il nous a suffi d'effectuer quelques essais pour obtenir immédiatement une solution."  

 

L'image de gauche est une photo des atomes représentant les graphes des 15 nœuds sur un dispositif quantique PASQAL. L'image de droite est le graphique et son histogramme, la barre rouge représentant le résultat le plus probable, c'est-à-dire la solution attendue.

Deux graphes avec leur MIS représenté sur le QPU de Fresnel.

Problèmes d'optimisation combinatoire représentés par des graphes

L'équipe de l'université de Bologne a utilisé sa nouvelle approche de l'algorithme hybride pour représenter un problème combinatoire à l'aide de graphes. Un graphe est un dessin composé de points appelés nœuds, représentant des entités, et de lignes, appelées arêtes, qui relient les nœuds, représentant la relation entre les nœuds.

Par exemple, le problème de l'ordonnancement des livraisons peut être représenté dans un graphe de la manière suivante : Considérons trois créneaux horaires différents : le premier chargement doit être effectué de 14 heures à 17 heures, le deuxième de 16 heures à 22 heures et le troisième de 21 heures à 23 heures. Le premier chargement n'empiète pas sur le troisième, mais le premier et le deuxième le font. Si les créneaux horaires sont représentés par des nœuds dans un graphe, le chevauchement sera représenté par les arêtes.

Pour optimiser ce problème de graphe, nous devons trouver le nombre maximum de nœuds qui ne sont pas reliés par une arête. En d'autres termes, étant donné un graphique, nous voulons trouver le plus grand nombre de nœuds qui ne sont pas reliés par une arête, évitant ainsi le chevauchement des créneaux horaires. Ce plus grand ensemble de nœuds non reliés par une arête est appelé l'ensemble indépendant maximal (MIS). Le QAOA est l'une des méthodes hybrides les plus prometteuses pour résoudre le problème de l'ensemble indépendant maximal et aider à trouver les meilleures solutions possibles au défi de l'ordonnancement et à de nombreux autres problèmes d'optimisation combinatoire basés sur les graphes.

QAOA mis en œuvre sur un dispositif à atomes neutres  

Le QAOA est une méthode polyvalente qui peut être mise en œuvre sur des plates-formes quantiques numériques et analogiques. Dans l'informatique quantique numérique, l'ordinateur exécute des algorithmes en plusieurs étapes à l'aide de portes quantiques, tandis qu'avec la méthode analogique, l'ordinateur quantique évolue vers une réponse de manière continue en une seule étape. Si l'informatique numérique est universelle, le risque d'erreur augmente pour chaque porte créée. En effet, les portes individuelles sont bruyantes et les erreurs se cumulent. En revanche, le mode analogique est moins sensible au bruit.

Parmi les quelques plateformes quantiques disponibles, les ordinateurs à atomes neutres se sont révélés être les meilleurs candidats pour traiter les problèmes basés sur les graphes en utilisant le mode analogique, en s'attaquant efficacement aux problèmes d'optimisation combinatoire. C'est pourquoi les chercheurs de l'université de Bologne ont choisi Fresnel pour tester leur méthode hybride QAOA. Ils ont résolu avec succès les problèmes MIS pour des graphes de 6 à 15 nœuds.

En outre, la nouvelle approche présentée par Elisa Ercolessi et Simone Tibaldi, de l'université de Bologne, a mis en œuvre une nouvelle approche classique qui réduit considérablement le nombre d'appels au dispositif quantique, ajoutant ainsi une couche essentielle d'efficacité à leur méthode.

"Nos résultats sont objectivement concluants, nous avons obtenu exactement la solution au problème, même avec 15 qubits représentant un nœud de 15. Nous avons également effectué une simulation du même problème et la solution obtenue sur le dispositif quantique réel est en fait meilleure que la simulation quantique", a fait remarquer Simone Tibaldi.

L'avenir des algorithmes d'optimisation quantique

L'informatique quantique promet de relever des défis impossibles à résoudre et de les transformer en problèmes pouvant être résolus en un temps raisonnable, ce qui est précisément le cas de l'optimisation combinatoire. Les algorithmes hybrides quantiques-classiques tels que le QAOA devraient permettre d'accélérer considérablement les calculs.

Les émulations du QAOA sur des dispositifs classiques utilisant des réseaux tensoriels montrent qu'avec plus de 50 qubits, nous devrions déjà commencer à obtenir de meilleures performances que certains algorithmes classiques naïfs et approximatifs.

"Cet algorithme hybride [mis en œuvre par l'équipe de l'université de Bologne] est également utile lorsqu'il s'agit d'optimiser une fonction sur un appareil qui peut être un peu bruyant", explique Lucas Leclerc, ingénieur en logiciel quantique chez PASQAL.

Le dispositif commercial PASQAL actuel fonctionne avec plus de 100 qubits et nous prévoyons de lancer bientôt cette année la prochaine génération qui fonctionnera avec plus de 1000 qubits. Avec une telle puissance, nous espérons résoudre des problèmes tels que le défi de l'ordonnancement, en offrant à différentes industries (énergie, transport, communications, soins de santé...) des moyens efficaces d'utiliser leurs ressources.

Références

  • Tibaldi, S., Vodola, D., Tignone, E. et Ercolessi, E. (2023). Bayesian Optimization for QAOA. IEEE Transactions on Quantum Engineering, 4, 1-11. https://doi.org/10.1109/tqe.2023.3325167
  • Tibaldi, S., Vodola, D., Tignone, E. et Ercolessi, E. (2024). QAOA analogique avec optimisation bayésienne sur la QPU des atomes de Rydberg. En cours.

Si vous êtes curieux de savoir comment les problèmes basés sur les graphes peuvent être abordés naturellement sur des appareils à atomes neutres, lisez notre article avec NVIDIA. Pour une compréhension approfondie des différences entre les méthodes numériques et analogiques, jetez un coup d'œil à nos blogs : L'avantage de l'atome neutre analogique sur l'informatique quantique numérique à l'ère des Qubits bruyants ou Pourquoi l'informatique quantique à atomes neutres analogiques est la direction la plus prometteuse pour un avantage quantique précoce.

Vous souhaitez en savoir plus sur ces techniques sur un ordinateur quantique à atomes neutres ? Commencez votre voyage quantique en utilisant nos plateformes et algorithmes avec Quantum Discovery.

 

Vous avez des questions sur notre technologie et nos applications ? N'hésitez pas à nous contacter!

 

Photo de couverture d'iStock. Crédit : TommL