Trouver l'itinéraire le plus efficace et le plus sûr pour les drones lors de la livraison de marchandises, comprendre les interactions des utilisateurs sur les médias sociaux et étudier les produits chimiques pour prédire leur toxicité sont des problèmes totalement différents. Cependant, ils partagent tous une caractéristique intéressante : ils sont mieux représentés par des graphiques.
Un graphe est un dessin simple composé de points (appelés nœuds) et de lignes (appelées arêtes), où les nœuds représentent des entités et les arêtes représentent les relations entre les entités. Prenons l'exemple du problème logistique des drones. Dans ce cas, les nœuds représentent les cibles à livrer et les arêtes représentent les itinéraires reliant ces cibles. L'utilisation de graphes pour trouver un itinéraire efficace et optimiser l'heure d'arrivée à destination permet de réduire considérablement le coût des ressources et l'empreinte carbone.
En effet, un dessin avec des points et des lignes offre un moyen astucieux de visualiser et de comprendre les relations entre les entités ; cependant, s'attaquer à des problèmes basés sur des graphiques est plus complexe qu'il n'y paraît. Les données graphiques peuvent être extrêmement difficiles à manipuler : le nombre d'options à prendre en compte peut être énorme et les relations entre les entités peuvent être complexes.
Au fil des ans, les chercheurs ont exploré avec un certain succès les algorithmes classiques d'apprentissage automatique pour résoudre les problèmes liés aux graphes. Cependant, ces méthodes sont très coûteuses et présentent plusieurs limites. À l'adresse PASQAL , nous présentons un nouvel algorithme hybride quantique/classique pour l'apprentissage automatique des graphes qui présente de nombreux avantages prometteurs par rapport aux méthodes classiques pour l'apprentissage et l'extraction d'informations à partir de structures de graphes.
Trouver une méthode de calcul efficace et fiable pour manipuler les graphes
Les méthodes informatiques classiques largement utilisées pour traiter les informations provenant des graphes évaluent généralement leurs propriétés locales, c'est-à-dire qu'elles examinent chaque nœud et son interaction avec ses voisins immédiats. Un inconvénient majeur de cette approche est que des informations globales essentielles peuvent être perdues et que des graphes différents peuvent être considérés comme le même graphe. Cet aspect est crucial, par exemple, lorsqu'il s'agit de comprendre la chimie d'une molécule. Dans ce cas, la structure globale de la molécule est liée à la fonction d'un processus biologique dans une cellule. Un autre inconvénient est que ces techniques peuvent rencontrer de sérieuses difficultés lorsque le graphe comprend des nœuds caractérisant différentes caractéristiques (données hétérophiles). Par exemple, lorsque les nœuds représentent des types distincts de personnes qui se connectent, comme les vendeurs qui se connectent avec les acheteurs sur un marché à l'étude.
Le scénario idéal est de pouvoir représenter tous les nœuds et leurs relations dans tout ou partie du graphe, de sorte que chaque nœud et chaque arête se voient attribuer une représentation unique. La communauté des chercheurs a récemment proposé de nouvelles méthodes classiques qui permettent d'aller au-delà des voisins les plus proches, appelées "transformateurs de graphes". Le problème de ces nouvelles techniques classiques est qu'elles dépendent d'une grande quantité de données et de temps pour l'apprentissage, ce qui rend cette méthode extrêmement coûteuse. Une alternative moins coûteuse a été proposée dans le cadre de cette méthode, mais elle perd à nouveau d'importantes caractéristiques globales des graphes.
Calcul hybride quantique/classique pour l'apprentissage automatique des graphes
Le développement rapide des ordinateurs quantiques au cours des dernières années offre la possibilité d'étudier de nouvelles façons d'aborder les problèmes basés sur les graphes. À PASQAL, nous avons été en mesure de représenter les graphes de manière extrêmement efficace en utilisant l'approche analogique de l'informatique PASQAL. approche analogique de l'informatique quantique. Nous combinons nos techniques quantiques avec des architectures d'apprentissage automatique classiques de pointe en incorporant les résultats de notre système quantique dans un algorithme classique de transformation des graphes. Grâce à notre technologie, nous pouvons étudier les caractéristiques structurelles globales des graphes qui seraient autrement irréalisables par des méthodes classiques uniquement. En outre, notre approche hybride a le potentiel d'améliorer la qualité du modèle, de réduire la formation et le temps, et de diminuer la consommation d'énergie tout en bénéficiant de la puissance de la technologie Tensor de NVIDIA. GPU Tensor Core de NVIDIA.
"L'importance de cette étude réside dans le fait que nous rivalisons - et parfois battons - avec les approches de pointe en matière d'apprentissage automatique des graphes", déclare Loic Henriet, directeur technique de PASQAL. "La méthode que nous proposons est l'une des premières à mettre réellement en évidence la puissance de l'hybride quantique/classique avec une forte participation classique et avec la partie quantique boostant le modèle, ce qui est aligné avec les développements actuels de l'informatique quantique".
"Le développement rapide des solutions quantiques redéfinit les façons d'étudier les problèmes de plus en plus complexes basés sur les graphes ", a déclaré Timothy Costa, directeur de High Performance Computing and Quantum chez NVIDIA. "Le nouvel algorithme hybride quantique-classique et les processeurs quantiques de PASQAL, associés à l'accélération du GPU NVIDIA Tensor Core dans l'apprentissage automatique des graphes, pourraient ouvrir une nouvelle ère pour la recherche basée sur les graphes quantiques ".
Dans un nouvel article publié dans la base de données arxiv nous expliquons nos nouvelles méthodes en détail et comparons notre technique hybride quantique/classique à d'autres méthodes uniquement classiques en utilisant sept ensembles de données - y compris des ensembles de données étendus - qui sont standard pour comparer la performance des modèles de calcul. Nos résultats sont aussi précis que les meilleures méthodes classiques et surpassent de nombreux algorithmes classiques largement utilisés.
Le succès de notre méthode dépend du bon choix de l'architecture classique. C'est pourquoi nous avons choisi les GPU Tensor Core de NVIDIA, qui peuvent réduire de manière significative le temps et les ressources nécessaires aux calculs basés sur les graphes, par rapport aux ordinateurs à hautes performances basés sur les CPU. L'architecture parallèle des GPU est plus efficace pour traiter les calculs nécessaires pour aborder les problèmes basés sur les graphes avec des méthodes quantiques et classiques, où nous devons traiter de grandes matrices et entraîner des réseaux neuronaux avec des ensembles de données étendus.
Pour la phase d'informatique quantique, nous tirons parti de la capacité naturelle de l'informatique quantique à atomes neutres pour émuler la position de tous les nœuds et leurs relations dans des graphes entiers ou des parties essentielles de ceux-ci.
Dans la section suivante, nous montrerons que l'unité de traitement quantique d'un atome neutre est la technologie naturelle pour représenter les problèmes basés sur les graphes.
Problèmes basés sur les graphes recréés dans des dispositifs à atomes neutres
Les dispositifs quantiques à atomes neutres utilisent des lasers très focalisés, appelés pinces optiques, pour piéger et manipuler les atomes neutres individuellement afin de créer des réseaux 2D et 3D dans des configurations arbitraires. Dans ces architectures, chaque qubit est représenté par un état d'énergie atomique à deux niveaux, généralement un état fondamental et un état de Rydberg, un état d'énergie très élevé. Dans l'état de Rydberg, les atomes sont polarisés, ce qui induit des interactions de van der Waals.
En combinant les caractéristiques de ces deux dispositifs à atomes neutres, la possibilité de créer des géométries arbitraires en 2D ou 3D avec les qubits et l'utilisation d'interactions programmables entre ces qubits, notre plateforme constitue le cadre idéal pour représenter et extraire des informations essentielles à partir de problèmes basés sur des graphes. Avec cette technique, chaque qubit représente un nœud du graphe et leurs interactions de Van der Waals représentent les relations entre les nœuds, ou les arêtes, via un mécanisme qui interdit à deux atomes d'être simultanément dans l'état de Rydberg s'ils sont trop proches l'un de l'autre, un phénomène appelé blocage de Rydberg. De plus, les interactions de type Van der Waals sont caractérisées par une forte décroissance avec la distance entre les qubits, ce qui nous permet de négliger les interactions avec les seconds voisins (et les plus éloignés), nous permettant ainsi d'imiter la connectivité des nœuds du graphe avec une bonne précision. De cette manière, le système représente directement les structures des graphes, et nous pouvons aborder les problèmes basés sur les graphes en utilisant des méthodes analogiques ou numériques-analogiques.
Avec notre méthode quantique, nous extrayons des caractéristiques essentielles de chaque graphe, autrement insoluble, en préservant sa structure et en évitant l'introduction d'un ordre ou d'un étiquetage explicite des nœuds et des arêtes. Prenons l'exemple de la dynamique moléculaire, qui est à la base de la découverte de médicaments et de la prédiction de la toxicité. Dans ce cas, notre approche quantique est capable d'évaluer la présence et la structure précise des cycles dans une molécule.
Apprentissage automatique des graphes à l'aide de méthodes quantiques
Les problèmes basés sur les graphes sont intrinsèques à de nombreux scénarios scientifiques, d'ingénierie et du monde réel. Ils sont utilisés pour comprendre les réseaux sociaux, le déploiement des satellites et les processus moléculaires dans la découverte de médicaments. La capacité d'extraire la structure des graphes avec leurs relations sous-jacentes, souvent complexes, entre les entités offre un terrain fertile pour des approches informatiques hybrides quantiques/classiques innovantes.
Cette année, les entreprises commencent à utiliser les processeurs quantiques PASQAL , l'un des premiers processeurs quantiques commercialisés au monde, avec notre cluster de GPU NVIDIA, pour exécuter des tâches pour des applications industrielles et scientifiques utilisant des graphes. Ces entreprises sont en train de trouver des moyens optimaux pour recharger intelligemment les voitures électriques, de comprendre les matériaux pour concevoir des batteries et d'optimiser le trafic urbain, alors que vous lisez ce blog. Nous publierons bientôt un article sur toutes ces mises en œuvre sur notre dispositif quantique commercial. Restez à l'écoute !
Références
- Slimane Thabet, Romain Fouilland, Mehdi Djellabi, Igor Sokolov, Sachin Kasture Louis-Paul Henry et Loïc Henriet. (2023). Amélioration des réseaux neuronaux graphiques avec des encodages calculés quantiques. Disponible à l'adresse suivante https://arxiv.org/abs/2310.20519
- Henriet, L. et. al. (2023). Algorithmes de graphes avec des processeurs quantiques analogiques à atomes neutres. En préparation.
Souhaitez-vous en savoir plus sur ces techniques sur un ordinateur quantique à atomes neutres ? Familiarisez-vous avec l'informatique quantique, notre plateforme et nos algorithmes avecQuantum Discovery.
