Les meilleurs ordinateurs numériques d'aujourd'hui ont encore du mal à résoudre, dans un délai pratique, une certaine classe de problèmes :problèmes d'optimisation combinatoire, ou celles qui impliquent de passer au peigne fin un large éventail de possibilités pour trouver la meilleure solution. Les ordinateurs quantiques ont le potentiel pour résoudre ces problèmes, mais augmenter le nombre de bits quantiques dans ces systèmes reste un obstacle.

Maintenant, Les chercheurs du MIT Lincoln Laboratory ont démontré une alternative, moyen analogique pour accélérer le calcul de ces problèmes. "Notre ordinateur fonctionne en 'calculant avec la physique' et utilise la nature elle-même pour aider à résoudre ces problèmes d'optimisation difficiles, " dit Jeffrey Chou, co-auteur principal d'un article sur ce travail publié dans Nature's Rapports scientifiques . "Il est composé de composants électroniques standard, nous permettant de faire évoluer notre ordinateur rapidement et à moindre coût en tirant parti de l'industrie des puces électroniques existante. »

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 emprunter à travers un certain nombre de villes, commençant et finissant par le même. Cela peut sembler simple avec seulement quelques villes, mais le problème devient exponentiellement difficile à résoudre à mesure que le nombre de villes augmente, enliser 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 des drogues, planifier les expéditions, réduire les interférences sur les réseaux sans fil, et beaucoup plus.

« On sait depuis très longtemps que les ordinateurs numériques sont fondamentalement mauvais pour résoudre ce type de problèmes, " dit Suraj Bramhavar, également co-auteur principal. « De nombreux algorithmes qui ont été conçus pour trouver des solutions doivent faire un compromis entre la qualité de la solution et le temps. Trouver la solution optimale absolue prend un temps déraisonnable lorsque la taille des problèmes augmente. » Trouver de meilleures solutions et le faire en beaucoup moins de temps pourrait permettre aux industries d'économiser des milliards de dollars. 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 les objectifs de la manière la plus efficace et la plus distribuée. Ce principe peut être observé dans la synchronie de la nature, comme des cellules cardiaques battant ensemble ou des bancs de poissons se déplaçant comme un seul. De la même manière, si vous placez deux horloges à pendule sur la même surface, peu importe quand les pendules individuels sont mis en mouvement, ils finiront par se bercer 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, mis en place de telle manière que l'énergie peut être transférée entre eux.

"Nous avons essentiellement construit une électronique, version programmable de cette [configuration d'horloge] à l'aide d'oscillateurs non linéaires couplés, " Chou dit, montrant une vidéo YouTube de métronomes affichant un phénomène similaire. "L'idée est que si vous mettez en place un système qui encode le paysage énergétique de votre problème, alors le système va naturellement essayer de minimiser l'énergie en se synchronisant, et ce faisant, décidera de la meilleure solution. Nous pouvons alors lire cette solution."

Le prototype du laboratoire est une sorte de machine d'Ising, un ordinateur basé sur un modèle en physique qui décrit un réseau d'aimants, chacun d'eux a une orientation magnétique de "tournage" qui ne peut pointer que vers le haut ou vers le bas. L'orientation finale de chaque rotation dépend de son interaction avec toutes les autres rotations. Les interactions individuelles de spin à spin sont définies avec un poids de couplage spécifique, qui dénote la force de leur connexion. Le but d'une machine d'Ising est de trouver, étant donné un réseau de force de couplage spécifique, la bonne configuration de chaque tour, haut ou bas, qui minimise l'énergie globale du système.

Mais comment une machine d'Ising résout-elle un problème d'optimisation ? Il s'avère que les problèmes d'optimisation peuvent être mappés directement sur le modèle d'Ising, de sorte qu'un ensemble de tours avec certains poids de couplage puisse représenter chaque ville et les distances entre elles dans le problème du voyageur de commerce. Ainsi, trouver la configuration de spins la plus basse énergie dans le modèle d'Ising se traduit directement par 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 d'une difficulté prohibitive lorsque les problèmes atteignent même des tailles modestes.

Dans les années récentes, il y a eu des efforts pour construire des machines quantiques qui correspondent au modèle d'Ising, dont le plus notable est celui 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'ils fonctionnent à des températures cryogéniques.

Le système du laboratoire effectue une recherche similaire, mais le fait en utilisant de simples oscillateurs électroniques. Chaque oscillateur représente un spin dans le modèle d'Ising, et prend de même une phase binarisée, où 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 pour résoudre un problème d'optimisation, le problème est d'abord mappé sur le modèle d'Ising, le traduisant en poids de couplage programmables reliant chaque oscillateur.

Avec les poids d'attelage programmés, les oscillateurs sont autorisés à fonctionner, comme le bras de pendule de chaque horloge étant libéré. Le système se détend alors naturellement jusqu'à son état d'énergie minimale globale. 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 a fonctionné contre plus de 2, 000 problèmes d'optimisation aléatoires, il est venu à la bonne solution 98 pour cent du temps.

Précédemment, des chercheurs de l'Université de Stanford ont fait la démonstration d'une machine d'Ising qui utilise des lasers et de l'électronique pour résoudre les 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 peut être difficile et coûteux à étendre à des tailles plus grandes. L'objectif de trouver une alternative plus simple a enflammé les recherches du laboratoire.

Mise à l'échelle

Le circuit oscillateur individuel que l'équipe a utilisé dans sa démonstration est similaire aux circuits trouvés à l'intérieur des téléphones portables ou des routeurs Wi-Fi. Un ajout qu'ils ont fait est une architecture crossbar 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 à fabriquer et peut permettre une connectivité complète à des milliers d'oscillateurs, " dit Chou. Un système entièrement connecté lui permet d'être facilement mappé à une grande variété de problèmes d'optimisation.

"Ce travail du Lincoln Laboratory fait un usage innovant d'une architecture crossbar dans sa construction d'une machine d'Ising analogique-électronique, " dit Peter McMahon, un professeur adjoint de physique appliquée et d'ingénierie à l'Université Cornell qui n'était pas impliqué dans cette recherche. « Il sera intéressant de voir comment les futurs développements de cette architecture et de cette plate-forme fonctionneront. »

Le prototype de la machine d'Ising du laboratoire utilise quatre oscillateurs. L'équipe élabore actuellement 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 y arriver, dire, 500 nœuds, il y a une chance que nous puissions commencer à concurrencer les ordinateurs existants, et à 1, 000 nœuds, nous pourrions peut-être les battre, " dit Bramhavar.

L'équipe voit clairement la voie à suivre pour passer à l'échelle, car 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'ingénierie électrique de premier cycle typique et ont été achetées en ligne pour environ 20 $.

"Ce qui m'excite, c'est la simplicité, " Bramhavar ajoute. " Les ordinateurs quantiques devraient démontrer des performances étonnantes, mais les défis scientifiques et techniques nécessaires pour les étendre sont assez difficiles. Démontrant même une petite fraction des gains de performances envisagés avec les ordinateurs quantiques, mais en utilisant du matériel de l'industrie électronique existante, serait un grand pas en avant. Exploiter le comportement naturel de ces circuits pour résoudre de vrais problèmes présente une alternative très convaincante pour ce que pourrait être la prochaine ère de l'informatique."

Cette histoire est republiée avec l'aimable autorisation de MIT News (web.mit.edu/newsoffice/), un site populaire qui couvre l'actualité de la recherche du MIT, innovation et enseignement.