Un processeur d’inspiration quantique évolutif et entièrement couplé résout les problèmes d’optimisation

Avez-vous déjà été confronté à un problème où vous deviez trouver une solution optimale parmi de nombreuses options possibles, comme trouver l’itinéraire le plus rapide vers un certain endroit, en tenant compte à la fois de la distance et du trafic ?

Si tel est le cas, le problème auquel vous étiez confronté est ce que l’on appelle formellement un “problème d’optimisation combinatoire”. Bien que formulés mathématiquement, ces problèmes sont courants dans le monde réel et surviennent dans plusieurs domaines, notamment la logistique, le routage réseau, l’apprentissage automatique et la science des matériaux.

Cependant, les problèmes d’optimisation combinatoire à grande échelle sont très gourmands en calcul pour être résolus à l’aide d’ordinateurs standard, ce qui oblige les chercheurs à se tourner vers d’autres approches. Une de ces approches est basée sur le “modèle d’Ising”, qui représente mathématiquement l’orientation magnétique des atomes, ou “spins”, dans un matériau ferromagnétique.

A haute température, ces spins atomiques sont orientés de manière aléatoire. Mais à mesure que la température diminue, les spins s’alignent pour atteindre l’état d’énergie minimum où l’orientation de chaque spin dépend de ses voisins. Il s’avère que ce processus, connu sous le nom de “recuit”, peut être utilisé pour modéliser des problèmes d’optimisation combinatoire tels que l’état final des spins donne la solution optimale.

Les chercheurs ont essayé de créer des processeurs de recuit qui imitent le comportement des spins à l’aide de dispositifs quantiques et ont tenté de développer des dispositifs à semi-conducteurs en utilisant la technologie d’intégration à grande échelle (LSI) dans le but de faire de même. En particulier, le groupe de recherche du professeur Takayuki Kawahara à l’Université des sciences de Tokyo (TUS) au Japon a fait des percées importantes dans ce domaine particulier.

En 2020, le professeur Kawahara et ses collègues ont présenté à la conférence internationale 2020, IEEE SAMI 2020, l’un des premiers processeurs de recuit LSI entièrement couplés (c’est-à-dire tenant compte de toutes les interactions spin-spin possibles au lieu des interactions avec les seuls spins voisins), comprenant 512 spins entièrement connectés.

Leurs travaux ont paru dans la revue IEEE Transactions on Circuits and Systems I: Documents réguliers. Ces systèmes sont notoirement difficiles à mettre en œuvre et à mettre à l’échelle en raison du grand nombre de connexions entre les spins qui doivent être prises en compte. Alors que l’utilisation de plusieurs puces entièrement connectées en parallèle était une solution potentielle au problème d’évolutivité, cela rendait le nombre requis d’interconnexions (fils) entre les puces prohibitif.

Dans une étude récente publiée dans Microprocesseurs et Microsystèmes, le professeur Kawahara et son collègue ont démontré une solution astucieuse à ce problème. Ils ont développé une nouvelle méthode dans laquelle le calcul de l’état énergétique du système est d’abord divisé entre plusieurs puces entièrement couplées, formant un “calculateur matriciel”.

Un deuxième type de puce, appelée “puce de contrôle”, collecte ensuite les résultats du reste des puces et calcule l’énergie totale, qui est utilisée pour mettre à jour les valeurs des spins simulés. “L’avantage de notre approche est que la quantité de données transmises entre les puces est extrêmement faible”, explique le professeur Kawahara. “Bien que son principe soit simple, cette méthode nous permet de réaliser un système LSI évolutif et entièrement connecté pour résoudre des problèmes d’optimisation combinatoire par recuit simulé.”

Les chercheurs ont réussi à mettre en œuvre leur approche en utilisant des puces FPGA commerciales, qui sont des dispositifs semi-conducteurs programmables largement utilisés. Ils ont construit un système de recuit entièrement connecté avec 384 spins et l’ont utilisé pour résoudre plusieurs problèmes d’optimisation, notamment un problème de coloration de graphe à 92 nœuds et un problème de coupe maximale à 384 nœuds.

Plus important encore, ces expériences de preuve de concept ont montré que la méthode proposée apporte de véritables avantages en termes de performances. Par rapport à un processeur moderne standard modélisant le même système de recuit, la mise en œuvre du FPGA était 584 fois plus rapide et 46 fois plus économe en énergie lors de la résolution du problème de coupe maximale.

Maintenant, avec cette démonstration réussie du principe de fonctionnement de leur méthode dans le FPGA, les chercheurs prévoient de passer au niveau supérieur. “Nous souhaitons produire une puce LSI conçue sur mesure pour augmenter la capacité et améliorer considérablement les performances et l’efficacité énergétique de notre méthode”, déclare le professeur Kawahara. “Cela nous permettra de réaliser les performances requises dans les domaines du développement de matériaux et de la découverte de médicaments, qui impliquent des problèmes d’optimisation très complexes.”

Enfin, le professeur Kawahara note qu’il souhaite favoriser la mise en œuvre de leurs résultats pour résoudre de vrais problèmes de société. Son groupe espère s’engager dans des recherches conjointes avec des entreprises et amener leur approche au cœur de la technologie de conception de semi-conducteurs, ouvrant ainsi les portes à la renaissance des semi-conducteurs au Japon.