Des chercheurs ont réussi à mettre en œuvre un nouvel algorithme sur un ordinateur quantique PASQAL , jetant ainsi les bases de la résolution d'un problème complexe dans les réseaux de communication cellulaire.
Lorsque vous marchez dans la rue, votre smartphone est constamment à la recherche de la cellule la plus proche pour se connecter et transférer des données afin de fonctionner. Au fur et à mesure que vous vous déplacez, le signal doit être transféré d'une cellule à l'autre. Mais vous n'êtes pas seul, presque tout le monde autour de vous porte des appareils qui jouent le même jeu. Les réseaux de communication cellulaire sont généralement très denses et, pour que chaque appareil ait accès à une part équitable de la capacité du réseau, leur structure doit être très bien planifiée.
Pour organiser le processus de transfert des signaux mobiles d'une cellule à l'autre, les réseaux utilisent des identificateurs, techniquement appelés identificateurs de cellule physique (PCI). Ces identificateurs sont limités et constamment réutilisés, et leur mauvaise affectation peut entraîner de multiples dysfonctionnements, tels que l'interruption d'un appel ou la perte d'une connexion de données. Par exemple, si les deux cellules dans le processus de transfert partagent le même identifiant, un smartphone peut interpréter la commande comme s'il devait rester connecté à la même cellule et le service sera interrompu. Pour éviter les conflits d'attribution, deux cellules voisines qui utilisent la même fréquence radio doivent avoir des identifiants différents.
Le problème de l'attribution de l'identifiant de la cellule physique peut être représenté à l'aide d'un problème de coloration de graphe. Un graphe comporte des points, appelés nœuds, et des lignes reliant les points, appelées arêtes. Dans le cas d'un réseau cellulaire, chaque nœud représente une cellule, et si deux cellules sont suffisamment proches l'une de l'autre pour que le processus de transfert ait lieu, cette proximité peut être représentée par une arête.
La coloration des graphes consiste à attribuer à chaque nœud une couleur telle que les nœuds qui partagent la même arête aient des couleurs différentes. En d'autres termes, la règle est que deux nœuds partageant une arête ne peuvent pas avoir la même couleur, comme le montre la figure ci-dessous.
Ainsi, pour le problème de l'attribution des identificateurs de cellules physiques, chaque couleur différente représente un identificateur. Comme vous l'avez probablement déjà deviné, dans un réseau cellulaire dense et complexe, les combinaisons satisfaisant à cette condition peuvent être nombreuses et l'optimisation du nombre de couleurs utilisées sur le graphique associé peut s'avérer une tâche très complexe.
Les dispositifs à atomes neutres, le meilleur choix pour résoudre le problème de coloration des graphes
Trouver la solution optimale pour un réseau cellulaire réel en colorant des graphes pourrait être excessivement coûteux sur le plan informatique, ce qui a incité les scientifiques et les ingénieurs à explorer les synergies qui émergent rapidement entre les ordinateurs quantiques et les ordinateurs classiques. Cependant, de nombreuses architectures quantiques sont fondamentalement différentes, et les entreprises et les instituts de recherche doivent choisir celle qui répond à leurs besoins.
Parmi la variété des technologies quantiques développées jusqu'à présent, les processeurs quantiques à atomes neutres sont extrêmement adaptés à l'approche des problèmes d'optimisation combinatoire des graphes, tels que la coloration des graphes. C'est pourquoi des chercheurs de la fondation LINKS-spécialisée dans la recherche appliquée, la recherche exploratoire, l'innovation et le transfert de technologie, avec de fortes compétences en calcul à haute performance et en informatique quantique, et soutenue par CINECA, ont choisi la technologie quantique à atome neutre de PASQAL pour résoudre un problème de coloration de graphe qui émerge dans plusieurs applications industrielles, telles que l'attribution d'identificateurs de cellules physiques (PCI).
Les unités de traitement quantique sont encore bruyantes, mais l'utilisation intelligente de ces technologies a permis d'obtenir des résultats impressionnants. L'équipe LINKS Quantum Computing, qui fait partie du domaine de recherche Advanced Computing, Photonics and Electromagnetics (CPE), a créé et mis en œuvre avec succès un algorithme hybride quantique-classique sur Fresnel, le premier dispositif commercial PASQAL et l'un des premiers dispositifs quantiques disponibles sur le marché, démontrant ainsi que leur nouvelle méthode est résistante au bruit.
"Le point fort de cette expérience est qu'elle exploite les caractéristiques de la machine à courant PASQAL de telle sorte que l'algorithme résiste aux variations des résultats", a déclaré Chiara Vercellino, chercheuse de l'équipe d'informatique quantique du CPE LINKS.
"L'aspect le plus impressionnant de cette mise en œuvre est que les résultats obtenus par l'équipe de LINKS sont très fiables, même si une unité de traitement quantique (QPU) est encore bruyante", a déclaré Mauro D'Arcangelo, développeur principal de logiciels quantiques à l'adresse PASQAL. "À condition de pouvoir intégrer le graphe dans notre QPU, l'algorithme fonctionne. Vous pouvez l'utiliser dès maintenant. Il suffit d'avoir suffisamment d'atomes dans le registre pour représenter le graphe que l'on souhaite".
Mais comment fonctionne ce nouvel algorithme ? Jetons un coup d'œil rapide.
Un nouvel algorithme quantique hybride classique pour résoudre un problème crucial d'affectation de réseau cellulaire
L'idée maîtresse de l'algorithme est de créer un arbre de solutions colorées à l'aide d'un processus hybride faisant appel à la fois à des calculs quantiques et à des calculs classiques. Voici comment cela fonctionne : Étant donné un graphique représentant un problème que nous voulons résoudre, le dispositif quantique produit autant de solutions que possible. Chaque solution correspond à une couleur qui a été attribuée aux nœuds de telle sorte que, si un nœud possède la couleur, ses voisins partageant une arête avec lui ne peuvent pas être colorés. Voir quelques exemples simples ci-dessous.
L'ordinateur classique utilise l'algorithme Branch and Bound pour choisir la meilleure solution possible produite par le dispositif quantique. Au début de la procédure d'optimisation, c'est-à-dire à la racine de l'arbre, le graphe n'est pas coloré. En appelant la QPU, nous obtenons un ensemble d'assignations de couleurs viables, chacune d'entre elles générant une branche. En se déplaçant le long des branches, les nœuds colorés sont supprimés du graphe original et le dispositif quantique répète le processus pour le nouveau graphe en produisant d'autres solutions qui ajouteront des couleurs au graphe. L'algorithme classique continue à choisir les meilleures solutions et donc à élaguer l'arbre jusqu'à ce qu'il ne reste plus aucun nœud non coloré et qu'une solution satisfaisante soit trouvée.
Du coloriage de points au coloriage d'atomes
Pourquoi la technologie quantique à atomes neutres est-elle idéale pour résoudre les problèmes de graphisme ? En effet, ce matériel utilise des lasers très concentrés et intenses, appelés pinces optiques, pour capturer les atomes individuellement et les manipuler afin de créer des formes arbitraires en 2D ou en 3D. La possibilité de positionner les atomes dans n'importe quelle configuration est essentielle pour résoudre les problèmes liés aux graphes. Dans ces architectures, l'information quantique est codée dans les niveaux d'énergie atomique, généralement un état fondamental et un état de Rydberg très élevé.
Un atome dans un état de Rydberg croît physiquement en influençant les atomes adjacents, les empêchant d'atteindre l'état de Rydberg lorsqu'ils sont plus proches qu'une certaine distance, appelée distance de blocage. La machine utilise ces propriétés des atomes dans l'état de Rydberg pour représenter naturellement des graphes, où les atomes représentent les nœuds et, lorsque deux atomes sont plus proches que leur distance de blocage, ils sont considérés comme connectés par une arête.
L'équipe de recherche de LINKS, en collaboration avec l'équipe de PASQAL , a mis en œuvre son algorithme hybride quantique-classique pour résoudre le problème de coloration des graphes pour quatre graphes avec 7, 7, 10 et 19 nœuds. Dans les quatre graphes, l'algorithme a trouvé une solution de coloration optimale en excellent accord avec les simulations numériques correspondantes.
"Lors de sa mise en œuvre sur un dispositif quantique PASQAL , le flux de travail a montré une interaction naturelle entre l'ordinateur classique et l'unité de traitement quantique", a déclaré Mauro D'Arcangelo.
"Le code a fonctionné sans problème sur la machine et nous savions dès le départ que nous pouvions nous attendre à de bons résultats", a expliqué Chiara Vercellino. "Le temps de résolution pour de nombreux nœuds croît de manière exponentielle si l'on considère les méthodes utilisant uniquement des ordinateurs classiques. C'est donc pour les très grands graphes que nous verrons le véritable avantage d'utiliser des approches hybrides quantiques-classiques.
Le nouvel algorithme hybride quantique-classique proposé par l'équipe de LINKS jette les bases d'une résolution efficace du problème de l'attribution des identificateurs de cellules physiques (PCI) dans les réseaux cellulaires et pour de nombreuses autres applications, telles que la planification des emplois (où les créneaux horaires de travail doivent être attribués efficacement au personnel), la planification des taxis ou d'autres formes de transport public.
L'intégration de dispositifs quantiques dans les flux de travail informatiques et, plus précisément, de technologies d'atomes neutres, pourrait s'avérer essentielle pour résoudre ces problèmes et d'autres problèmes industriels et scientifiques urgents.
Références
- Vercellino, C., Vitali, G., Viviani, P., Scionti, A., Scarabosio, A., Terzo, O., ... &Montrucchio, B. (2023, juin). Neural optimization for quantum architectures:graph embedding problems with Distance Encoder Networks. In 2023 IEEE47th Annual Computers, Software, and Applications Conference (COMPSAC) (pp.380-389). IEEE.
- Henriet, L., Beguin, L., Signoles,A., Lahaye, T., Browaeys, A., Reymond, G. O., & Jurczak, C. (2020). Quantumcomputing with neutral atoms. Quantum, 4, 327.
Vous souhaitez en savoir plus sur ces techniques sur un ordinateur quantique à atomes neutres ? Familiarisez-vous avec l'informatique quantique, notre plateforme et nos algorithmes avec Découverte quantique.
