La nature peut aider à résoudre les problèmes d’optimisation
Les meilleurs ordinateurs numériques d’aujourd’hui luttent encore pour résoudre, dans un délai pratique, une certaine classe de problèmes : les problèmes d’optimisation combinatoire, ou ceux qui impliquent de passer au peigne fin un large éventail de possibilités pour trouver la meilleure solution. Les ordinateurs quantiques ont le potentiel de s’attaquer à ces problèmes, mais l’augmentation du nombre de bits quantiques dans ces systèmes demeure un obstacle.
Aujourd’hui, les chercheurs du MIT Lincoln Laboratory ont mis au point une méthode alternative, basée sur l’analogique, pour accélérer le calcul de ces problèmes. Notre ordinateur fonctionne en » informatisant avec la physique » et utilise la nature elle-même pour aider à résoudre ces problèmes difficiles d’optimisation « , explique Jeffrey Chou, co-auteur principal d’un article sur le cet ouvrage publié dans Nature’s Rapports scientifiques. « Il est fait de composants électroniques standard, ce qui nous permet de faire évoluer notre ordinateur rapidement et à moindre coût en tirant parti de l’industrie existante des puces électroniques. »
Le problème d’optimisation combinatoire le plus connu est peut-être celui du vendeur itinérant. Le problème consiste à trouver le chemin le plus court qu’un vendeur peut prendre à travers un certain nombre de villes, en commençant et en finissant par la même ville. Cela peut sembler simple avec seulement quelques villes, mais le problème devient exponentiellement difficile à résoudre à mesure que le nombre de villes augmente, enlisant même les meilleurs supercalculateurs. Pourtant, les problèmes d’optimisation doivent être résolus quotidiennement dans le monde réel ; les solutions sont utilisées pour planifier les quarts de travail, minimiser les risques financiers, découvrir les médicaments, planifier les expéditions, réduire les interférences sur les réseaux sans fil, et bien plus encore.
« On sait depuis très longtemps que les ordinateurs numériques sont fondamentalement mauvais pour résoudre ce type de problèmes « , explique Suraj Bramhavar, également co-auteur principal. « De nombreux algorithmes qui ont été conçus pour trouver des solutions doivent sacrifier la qualité de la solution sur l’autel du temps. Trouver la solution optimale absolue prend un temps déraisonnablement long quand la taille du problème augmente. » Trouver de meilleures solutions et le faire en beaucoup moins de temps pourrait faire économiser des milliards de dollars aux industries. Ainsi, les chercheurs ont cherché de nouvelles façons de construire des systèmes conçus spécifiquement pour l’optimisation.
Trouver le rythme
La nature aime optimiser l’énergie ou atteindre ses objectifs de la manière la plus efficace et la plus distribuée possible. Ce principe peut être observé dans la synchronisation de la nature, comme les cellules cardiaques qui battent ensemble ou les bancs de poissons qui ne font qu’un. De même, si vous placez deux pendules sur la même surface, quel que soit le moment où les pendules individuelles sont mises en mouvement, elles seront éventuellement bercées dans un rythme synchronisé, atteignant leur sommet en même temps mais se déplaçant dans des directions opposées (ou déphasées). Ce phénomène a été observé pour la première fois en 1665 par le scientifique néerlandais Christiaan Huygens. Ces horloges sont un exemple d’oscillateurs couplés, disposés de telle sorte que l’énergie peut être transférée entre eux.
« Nous avons essentiellement construit une version électronique programmable de ce système (réglage de l’horloge) à l’aide d’oscillateurs non linéaires couplés « , explique M. Chou. vidéo YouTube de métronomes présentant un phénomène similaire. « L’idée est que si vous mettez en place un système qui code le paysage énergétique de votre problème, alors le système va naturellement essayer de minimiser l’énergie en synchronisant et, ce faisant, va s’installer sur la meilleure solution. Nous pourrons alors lire cette solution. »
Le prototype du laboratoire est un type de machine Ising, un ordinateur basé sur un modèle en physique qui décrit un réseau d’aimants dont chacun a une orientation magnétique « spin » qui ne peut pointer que vers le haut ou le bas. L’orientation finale de chaque pirouette dépend de son interaction avec toutes les autres pirouettes. Les interactions spin-spin individuelles sont définies avec un poids d’accouplement spécifique, qui indique la force de leur connexion. Le but d’une machine Ising est de trouver, grâce à un réseau de force d’accouplement spécifique, la configuration correcte de chaque rotation, vers le haut ou vers le bas, qui minimise l’énergie globale du système.
Mais comment une machine Ising peut-elle résoudre un problème d’optimisation ? Il s’avère que les problèmes d’optimisation peuvent être mappés directement sur le modèle Ising, de sorte qu’un ensemble de spins avec certains poids de couplage peut représenter chaque ville et les distances entre eux dans le problème du vendeur itinérant. Ainsi, trouver la configuration de pirouettes la moins énergivore dans le modèle Ising se traduit directement dans la solution pour l’itinéraire le plus rapide du vendeur. Cependant, résoudre ce problème en vérifiant individuellement chacune des configurations possibles devient prohibitif lorsque les problèmes atteignent des tailles même modestes.
Au cours des dernières années, des efforts ont été déployés pour construire des machines quantiques qui correspondent au modèle d’Ising, dont la plus remarquable est celle de la société canadienne D-Wave Systems. Ces machines peuvent offrir un moyen efficace de rechercher le grand espace de solution et de trouver la bonne réponse, bien qu’elles fonctionnent à des températures cryogéniques.
Le système du laboratoire effectue une recherche similaire, mais en utilisant des oscillateurs électroniques simples. Chaque oscillateur représente une rotation dans le modèle d’Ising, et prend également une phase binaire, où les oscillateurs qui sont synchronisés, ou en phase, représentent la configuration « spin up » et ceux qui sont déphasés représentent la configuration « spin down ». Pour configurer le système afin de résoudre un problème d’optimisation, le problème est d’abord mis en correspondance avec le modèle Ising, le traduisant en poids de couplage programmables reliant chaque oscillateur.
Avec les masses d’accouplement programmées, les oscillateurs peuvent fonctionner comme le bras de balancier de chaque horloge qui se déclenche. Le système se détend alors naturellement à son état énergétique global minimum. La lecture électronique de la phase finale de chaque oscillateur, représentant « spin up » ou « spin down », présente la réponse à la question posée. Lorsque le système s’est heurté à plus de 2 000 problèmes d’optimisation aléatoires, il a trouvé la bonne solution 98 % du temps.
Auparavant, les chercheurs de l’Université de Stanford a fait la démonstration d’une machine Ising qui utilise des lasers et de l’électronique pour résoudre des problèmes d’optimisation. Ce travail a révélé le potentiel d’une accélération significative par rapport à l’informatique numérique bien que, selon Chou, le système puisse être difficile et coûteux à mettre à l’échelle pour des tailles plus grandes. L’objectif de trouver une solution de rechange plus simple a enflammé les recherches du laboratoire.
Mise à l’échelle
Le circuit d’oscillateur individuel que l’équipe a utilisé dans sa démonstration est semblable aux circuits que l’on trouve à l’intérieur des téléphones cellulaires ou des routeurs Wi-Fi. Un ajout qu’ils ont fait est une architecture de barre transversale qui permet à tous les oscillateurs du circuit d’être directement couplés les uns aux autres. « Nous avons trouvé une architecture qui est à la fois évolutive pour la fabrication et qui peut permettre une connectivité complète à des milliers d’oscillateurs « , explique M. Chou. Un système entièrement connecté permet de l’adapter facilement à une grande variété de problèmes d’optimisation.
« Ce travail du Lincoln Laboratory utilise de manière innovante une architecture à barres transversales dans la construction d’une machine Ising analogique-électronique « , explique Peter McMahon, professeur adjoint de physique appliquée et d’ingénierie à l’Université Cornell qui n’a pas participé à ces recherches. « Il sera intéressant de voir comment les développements futurs de cette architecture et de cette plate-forme se dérouleront. »
La machine Ising prototype du laboratoire utilise quatre oscillateurs. L’équipe travaille actuellement à l’élaboration d’un plan pour adapter le prototype à un plus grand nombre d’oscillateurs, ou « nœuds », et le fabriquer sur une carte de circuit imprimé. « Si nous pouvons atteindre, disons, 500 nœuds, il y a une chance que nous puissions commencer à concurrencer les ordinateurs existants, et à 1 000 nœuds, nous pourrions être en mesure de les battre « , dit Bramhavar.
L’équipe voit une voie claire vers la mise à l’échelle parce que la technologie est basée sur des composants électroniques standard. C’est aussi extrêmement bon marché. Toutes les pièces de leur prototype se trouvent dans un laboratoire d’électrotechnique de premier cycle et ont été achetées en ligne pour environ 20 $.
« Ce qui m’excite, c’est la simplicité « , ajoute Bramhavar. « On s’attend à ce que les ordinateurs quantiques démontrent des performances étonnantes, mais les défis scientifiques et techniques nécessaires à leur mise à l’échelle sont assez difficiles. Démontrer ne serait-ce qu’une petite fraction des gains de performance envisagés avec les ordinateurs quantiques, mais en utilisant le matériel de l’industrie électronique existante, serait un énorme bond en avant. Exploiter le comportement naturel de ces circuits pour résoudre des problèmes réels présente une alternative très convaincante pour ce que pourrait être la prochaine ère de l’informatique. »
