À l'ère de la demande croissante de trafic de données et de l'expansion rapide de l'internet des objets, la cinquième génération de communications cellulaires, la 5G, a été conçue pour améliorer la connectivité internet déjà assurée par les réseaux 4G. Les innovations qui sous-tendent la 5G ont permis à ses réseaux d'atteindre la fiabilité, une vitesse de transfert de données plus élevée et d'améliorer le délai de réponse entre les appareils par rapport à l'ancienne génération de réseaux cellulaires.
Cette technologie de communication avancée a déjà prouvé ses remarquables capacités à sauver des vies en 2019, lorsque des chirurgiens ont effectué des interventions robotiques à distance, contrôlées à distance - certaines sur des milliers de kilomètres - en utilisant la 5G enChine, en Espagne, en Italie et en Allemagne.
Dans les communications sans fil, l'information voyage sur des ondes électromagnétiques, généralement dans le spectre radioélectrique, et les entreprises de communication utilisent des fréquences spécifiques de ces ondes électromagnétiques pour transmettre l'information. Pour éviter les interférences entre les services, le gouvernement réglemente les droits d'émettre des fréquences radio, et les entreprises doivent payer pour les droits d'émettre des signaux dans des bandes de fréquences spécifiques en utilisant la méthode de vente aux enchères.
L'acquisition des droits d'utilisation des fréquences pour les communications est coûteuse ; c'est pourquoi les entreprises doivent calculer avec une grande précision le nombre et la nature des fréquences dont elles ont besoin. Pour effectuer ces calculs, les entreprises considèrent de nombreuses options, telles que le nombre d'antennes, les distances entre elles et les fréquences dont elles ont besoin pour éviter les interférences tout en assurant une bonne couverture. Ce type de problème comporte souvent une grande variété d'options à combiner, c'est pourquoi on les appelle des problèmes d'optimisation combinatoire.
Trouver la meilleure option, un casse-tête dans l'informatique classique
L'optimisation combinatoire consiste à trouver la "meilleure option", selon certains critères, parmi un ensemble d'options souvent très vaste. Dans les problèmes réels, comme celui de l'attribution des fréquences de la 5G, le nombre d'options que les entreprises doivent prendre en compte avant d'acheter les droits d'utilisation des fréquences peut être prohibitif pour les ordinateurs traditionnels, même pour les ordinateurs classiques les plus puissants.
Une approche populaire pour aborder ces problèmes d'optimisation combinatoire industrielle consiste à restreindre le nombre d'options à un sous-groupe et à résoudre le sous-problème associé à ce sous-groupe. Ce sous-problème est appelé " problème maître restreint".
Mais attendez, résoudre le problème du maître restreint ne résout pas le vrai problème original. Il faut donc poursuivre le travail. L'étape suivante consiste à créer plusieurs itérations générant de nouvelles options à ajouter au problème principal restreint à chaque itération et à vérifier si le résultat s'améliore. Le nouveau sous-problème créé et résolu à chaque itération est appelé sous-problème de tarification. Le processus s'arrête lorsque le résultat ne s'améliore pas par l'ajout de nouvelles options. Cette approche est appelée méthode de génération de colonnes.
Bien que la génération de colonnes soit un algorithme puissant parce qu'il simplifie des problèmes complexes, l'étape consistant à générer de nouvelles options reste, dans de nombreux cas, extrêmement difficile et coûteuse en informatique classique.
Une méthode hybride classique-quantique pour trouver la meilleure option
À l'adresse PASQAL, nous avons récemment proposé une méthode hybride complète de génération de colonnes classiques et quantiques dans laquelle nous résolvons le problème du maître restreint à l'aide de l'informatique classique et générons les nouvelles options à l'aide de l'informatique quantique.
Notre article scientifiquemontre que l'intégration de notre approche quantique dans des algorithmes classiques de pointe améliore leurs performances en réduisant considérablement le nombre d'itérations nécessaires pour obtenir des résultats précis.
Par rapport à plusieurs approches classiques de pointe, notre tarification hybride classique-quantique réduit jusqu'à 83 % le nombre d'itérations nécessaires pour trouver des solutions précises à l'aide de l'approche de génération de colonnes.
"J'ai une grande expérience de l'utilisation d'approches informatiques classiques pour résoudre des problèmes de réseaux de télécommunications, et je sais que dans l'approche de génération de colonnes, le goulot d'étranglement est précisément la façon de générer de nouvelles options pour résoudre le problème du maître restreint. Maintenant, avec nos méthodes quantiques, nous pouvons espérer résoudre le problème complet avec moins d'itérations, améliorant ainsi la qualité de la solution finale", déclare Wesley Coelho, ingénieur en applications informatiques quantiques à PASQAL.
Comment fonctionne cette méthode ? Voyons les détails.
Trouver la meilleure option en coloriant des points
Les problèmes combinatoires peuvent naturellement être représentés par des graphes, où les données sont composées d'éléments représentés par des points appelés sommets ou nœuds, et les lignes tracées entre eux, ou arêtes, représentent la connexion entre ces éléments.
Les arêtes peuvent coder différentes informations, telles que l'importance des connexions (généralement appelées poids). Nous pouvons également attribuer des étiquettes pour différencier les sommets, et y a-t-il quelque chose de plus pratique que d'utiliser des couleurs comme étiquettes ?
Pour plusieurs problèmes d'optimisation qui peuvent être traduits en graphes, nous utilisons des couleurs comme étiquettes pour trouver ce que l'on appelle des ensembles indépendants.Un ensemble indépendant dans un graphique est un groupe de sommets tel qu'aucune paire d'éléments du groupe n'est reliée par une arête.L'idée est d'utiliser le moins de teintes possible en colorant les sommets qui ne sont pas reliés par une arête avec exactement la même couleur, mais en utilisant des couleurs différentes s'ils sont reliés par une arête. De cette manière, chaque groupe de nœuds de même couleur représente un ensemble indépendant.
Dans les problèmes de coloration des sommets, le problème original que nous voulons résoudre se traduit par la recherche du nombre minimum d'ensembles indépendants qui peuvent couvrir tous les nœuds du graphique exactement une fois. Ce faisant, vous pouvez minimiser le nombre de couleurs dont vous avez besoin pour couvrir votre graphique tout en respectant les contraintes imposées par le problème.
Revenons maintenant à notre exemple principal et voyons comment nous pouvons représenter le problème du déploiement du réseau 5G à l'aide de cette méthode.
Résoudre le problème des fréquences de la 5G en colorant des graphes
Supposons qu'une entreprise souhaite déployer des antennes 5G dans une ville et obtenir du gouvernement les droits d'utilisation des fréquences nécessaires. Pour acheter les droits d'utiliser le moins de fréquences possible et économiser de l'argent, l'entreprise doit envisager de déployer suffisamment d'antennes pour obtenir une bonne couverture de communication. Mais en même temps, ces antennes ne peuvent pas utiliser les mêmes fréquences si elles sont trop proches les unes des autres, car les signaux interfèrent.
C'est un exemple parfait de problème qui peut être résolu à l'aide de graphiques. Nous représentons chaque antenne par un sommet sur un graphique. Si deux antennes sont plus proches qu'un certain seuil pour que leurs signaux interfèrent, les nœuds correspondants sont reliés par une arête. Ensuite, nous "peignons" le graphique en laissant une couleur différente pour chaque fréquence. De cette manière, chaque ensemble indépendant est coloré avec la même couleur, ce qui signifie que les antennes de chaque ensemble indépendant peuvent utiliser la même fréquence.
Ainsi, dans ce problème, la recherche du nombre minimum d'ensembles indépendants, en minimisant le nombre de couleurs utilisées, minimisera le nombre de fréquences que l'entreprise devra acheter lors de la vente aux enchères, optimisant ainsi les coûts.
Des perspectives prometteuses
Jusqu'à présent, nous avons émulé notre approche hybride classique-quantique de l'algorithme de génération de colonnes à l'aide dePulsernotre bibliothèque Python open-source. Nous avons émulé différents processeurs quantiques PASQAL , y compris des processeurs parfaitement silencieux et des processeurs bruyants. Même avec du bruit, nos méthodes ont donné de meilleurs résultats que les autres méthodes que nous avons testées en utilisant uniquement l'informatique classique. La prochaine étape consiste à mettre en œuvre notre méthode dans nos processeurs quantiques réels.
"Dans presque toutes les approches hybrides, l'informatique classique est utilisée pour aider l'informatique quantique. Dans notre approche, nous utilisons l'informatique quantique pour aider les ordinateurs classiques à résoudre des problèmes d'optimisation combinatoire". Wesley Coelho remarque.
L'optimisation combinatoire est au cœur d'un grand nombre d'applications industrielles, telles que la logistique de livraison des marchandises d'un entrepôt aux clients, la recherche de moyens efficaces de distribution de l'électricité ou le déploiement d'une nouvelle technologie de communication, telle que la technologie 5G. Grâce à notre approche, nous sommes définitivement sur la bonne voie pour aider à résoudre ces problèmes de manière fiable et efficace, en nous rapprochant d'un avantage quantique à court terme.
Références
- Da Silva Coelho, W., Henriet, L., Henry, L-P. (2023). Un cadre de génération de colonnes basé sur la tarification quantique pour les problèmes combinatoires difficiles. Phys. Rev. A 107(3). https://link.aps.org/doi/10.1103/PhysRevA.107.032426. Préprint disponible : 2301.02637.pdf (arxiv.org).
- Henriet, L., Beguin, L., Signoles, A., Lahaye, T., Browaeys, A., Reymond, G. O., & Jurczak, C. (2020b). Quantum computing with neutral atoms. Quantum, 4, 327. https://doi.org/10.22331/q-2020-09-21-327.
Photo de Scott Elkins.
