Pour résoudre les tâches d'optimisation les plus difficiles, ajoutez simplement des lasers

Un étrange appareil connu sous le nom de Ising Optical Machine est capable de contrôler le trafic aérien et d'aider les matchs de la NFL.

L'année dernière, une défaillance du système de distribution entre les employés d'American Airlines pourrait entraîner une interruption du calendrier de milliers de vols pendant la période des fêtes. L'erreur a permis aux pilotes de refuser des vols sans être remplacé par un autre pilote, et environ 15 000 vols ont été menacés. Et bien que la compagnie aérienne ait réussi à suivre le problème à temps et à répartir les employés , ce gâchis est devenu un rappel de la façon dont nous dépendons des ordinateurs pour organiser l'horaire de travail d'un grand nombre de services et de fonctions, dont notre communauté dépend désormais complètement.

Par exemple, toutes les grandes compagnies aériennes disposent d'algorithmes sophistiqués d'optimisation graphique qui comparent les pilotes et les vols. Et bien que l'incident avec American Airlines ne se soit pas produit directement par la faute de l'algorithme, le résultat pourrait être similaire. Un tel refus entraînerait des centaines de milliers de personnes dans une situation difficile ou très gênante alors que la compagnie aérienne cherchait une issue à la situation.

Le triomphe de la science algorithmique et de la loi de Moore est que nous pouvons désormais aborder de nombreuses tâches d'optimisation complexes, y compris des domaines tels que le transport, la logistique et la planification. La plupart du monde moderne ne pourra pas fonctionner normalement sans ces algorithmes: chaque année, 50 000 cargos transportent des marchandises, 25 000 TWh d' électricité sont générés et les routeurs transportent 1 zettaoctet de trafic par eux-mêmes. Tout cela fonctionnerait beaucoup moins efficacement. Cependant, les organisations travaillent souvent avec des solutions sous-optimales en raison de délais serrés et du manque de ressources informatiques disponibles. De plus, il existe encore de nombreuses possibilités d'améliorer les méthodes que nous utilisons pour aider à résoudre la plupart des problèmes d'optimisation.

Étant donné l'importance de l'optimisation et le fait que l'ère des améliorations stables et majeures de la vitesse du processeur semble toucher à sa fin, les chercheurs ont commencé à étudier la question de savoir si des machines spécialement conçues pour l'optimisation pouvaient améliorer considérablement notre capacité à résoudre des problèmes complexes.

Une approche prometteuse est le développement de machines optiques conçues pour l'optimisation. Un groupe de scientifiques de l'Université de Stanford (qui comprend l'auteur de l'article), dirigé par Yoshihik Yamamoto, a commencé ces études il y a sept ans. Ce sujet est maintenant étudié par plusieurs groupes de scientifiques, ainsi que par des chercheurs des laboratoires HP et NTT . Après des années de travail, il est de plus en plus sûr qu'au moins un de ces groupes pourra un jour créer une machine qui pourra nous aider à résoudre certains des problèmes d'optimisation les plus difficiles que l'industrie moderne doit résoudre.


La tâche du vendeur: la complexité des tâches telles que trouver le chemin le plus court entre plusieurs points augmente avec le nombre de points. Les modéliser sous couvert de problèmes d'optimisation Ising peut aider à les résoudre plus rapidement.

Rappelez-vous le problème classique du vendeur, dans lequel le vendeur se déplace de ville en ville, vendant des marchandises. Il ne veut pas perdre de temps et d'argent en essence. Il s'agit d'une tâche d'optimisation, dont le but est de trouver le chemin le plus court pour le vendeur, étant donné qu'il doit se rendre une fois sur chaque point, et à la fin du voyage, il veut retourner là où il a commencé.

Pour cinq villes, le problème est résolu simplement. Il peut être calculé simplement en considérant les 12 chemins . Cependant, si le travailleur acharné a l'intention de visiter 50 villes, la méthode de recherche qui considère tous les chemins possibles sera insupportable - il y aura plus de ces chemins que le nouveau décillion , soit 10 ⁶⁰ - un et 60 zéros.

Des solutions possibles à ce problème peuvent nous être données par des algorithmes qui utilisent différents chemins de contournement et des approximations raisonnables. Mais même les meilleurs d'entre eux peuvent faire réfléchir l'ordinateur le plus puissant. Dans un exemple récent, l'Université de Waterloo au Canada a tenté de trouver le chemin le plus court entre près de 50 000 villes des États-Unis qui figuraient sur le registre national des lieux historiques et de prouver l'exactitude de sa décision. Pour ce faire, il a utilisé 310 processeurs puissants qui ont fonctionné sans s'arrêter pendant 9 mois.

Mais l'optimisation implique bien plus de tâches que la simple tâche de vendeur. Un autre défi est la planification. Par exemple, la National Football League aux États-Unis doit planifier chaque année plusieurs centaines de matchs, tout en essayant de respecter des milliers de règles, qui, par exemple, interdisent aux équipes de jouer plus de trois matchs sur leur propre terrain d'affilée. Pour résoudre ce problème, en 2017, la NFL a utilisé un cluster de 400 ordinateurs .


Optimisation d'Ising : dans ce problème d'Ising, l'énergie du système est plus faible lorsque les spins de ses électrons sont dirigés dans des directions opposées aux spins des voisins. Les systèmes qui peuvent trouver l'état avec une énergie minimale dans le modèle Ising peuvent aider à accélérer la solution de problèmes d'optimisation complexes.

Les entreprises manufacturières doivent planifier la maintenance des machines. Les universités ont besoin d'un calendrier. Les services de messagerie doivent planifier les itinéraires de livraison. Les grandes villes, comme Pékin ou Tokyo, aimeraient apprendre à gérer efficacement les flux de millions de voitures essayant de traverser leurs rues aux heures de pointe. Ces tâches peuvent inclure des centaines ou des milliers d'événements qui doivent être planifiés et, dans de nombreux cas, les solutions pratiques ne sont toujours pas disponibles, car elles nécessitent trop de temps ou trop d'ordinateurs.

Depuis de nombreuses années, les chercheurs tentent de créer des machines spéciales pour résoudre les problèmes d'optimisation. Au milieu des années 1980, David Tank, qui travaillait alors dans les laboratoires AT&T Bell, et John Hopfield, tous deux travaillant chez AT&T Bell et Caltech, ont suggéré d'utiliser des circuits électroniques analogiques représentant des réseaux de neurones pour résoudre des problèmes d'optimisation tels que le problème du voyageur de commerce. Leurs travaux ont donné lieu à des décennies de recherche dans ce domaine. Puis, en 1994, Leonard Edleman de l'Université de Californie du Sud a découvert qu'en théorie, l'ADN peut être utilisé pour résoudre des problèmes de ce type. Son idée a donné lieu à une vague de recherches similaire. Cependant, ces tentatives pour développer des approches radicalement nouvelles et efficaces pour résoudre les problèmes d'optimisation ont conduit à des alternatives pratiques aux ordinateurs et technologies conventionnels, qui restent aujourd'hui les principaux outils pour résoudre ces problèmes.

Les tentatives de création de machines optiques spéciales capables de résoudre des problèmes d'optimisation se sont concentrées sur l'un de ces problèmes, connu sous le nom d'optimisation Ising. Elle a été nommée d'après le physicien Ernst Ising, le célèbre ouvrage sur le modèle des moments magnétiques et son explication des transitions entre les différents états magnétiques. Il s'avère que de nombreux problèmes d'optimisation courants, notamment la planification et la recherche de chemins, peuvent facilement être transformés en problèmes d'optimisation Ising.

Pour comprendre comment le modèle d'Ising est lié à l'optimisation, vous devez commencer par l'utiliser en physique pour comprendre le magnétisme. Considérez une barre magnétique conventionnelle. En utilisant le modèle d'Ising, on peut imaginer une barre magnétique, comme un réseau tridimensionnel d'atomes, dans lequel chacun des atomes lui-même est une barre magnétique. Les électrons dans les atomes ont une propriété appelée spin. Les spins des électrons de valence - situés sur les enveloppes extérieures de l'atome - sont dirigés vers le haut ou vers le bas. La direction des spins détermine la magnétisation du matériau. Si tous les dos sont dirigés vers le haut, le matériau est magnétisé. S'il est abaissé, le matériau est également magnétisé - uniquement avec la polarité opposée. Si les dos sont mélangés, le matériau n'est pas magnétisé.

Ces spins interagissent également les uns avec les autres. Dans une barre magnétique, « l'énergie totale » de deux électrons voisins est plus faible si leurs spins sont alignés - c'est-à-dire qu'ils sont dirigés dans la même direction. Inversement, leur énergie totale est plus élevée si les spins sont multidirectionnels.


Machine optique Ising: un oscillateur paramétrique optique (OPO) avec rétroaction de mesure peut résoudre les problèmes d'optimisation exprimés sous la forme du modèle Ising - un ensemble de spins d'électrons et leur influence les uns sur les autres. Les phases des impulsions optiques dans OPO représentent des spins, et l'effet est introduit dans un réseau de portes programmables par l'utilisateur ( PPM ). Il faut effectuer une centaine de passages dans le système avant que les impulsions de l'OPO ne deviennent suffisamment puissantes pour apporter une solution au problème.

Dans le modèle d'Ising, nous résumons l'énergie des interactions entre les spins de chaque paire d'électrons dans un ensemble d'atomes. Comme la quantité d'énergie dépend de l'alignement ou non des spins, l'énergie totale de l'ensemble dépend de la direction de tous les spins du système. Ainsi, la tâche générale de l'optimisation Ising est de déterminer dans quel état les spins doivent être afin de minimiser l'énergie du système.

Dans le modèle le plus simple, on pense que seuls les spins adjacents interagissent. Cependant, dans le problème général d'optimisation d'Ising, tout spin peut interagir avec n'importe quel autre, quelle que soit la distance, et le signe et la force de ces interactions peuvent être uniques pour chaque paire de dos. Dans une formulation aussi généralisée, ce problème est très difficile à résoudre - tout comme le problème d'un vendeur visitant des centaines de milliers d'acheteurs potentiels. Si nous pouvons trouver un moyen de résoudre rapidement les problèmes d'optimisation d'Ising, et un moyen de parler du problème du voyageur de commerce et des problèmes similaires de la même manière que les problèmes d'Ising, nous pourrons peut-être résoudre ces problèmes aussi rapidement. L'énergie minimale du système dans le problème d'Ising représentera l'itinéraire le plus rapide entre les villes, la solution la plus efficace pour emballer un cargo ou tout autre problème d'optimisation dont nous avons besoin.

Alors, comment convertissez-vous le chemin d'un vendeur ambulant en dos? La tâche principale est d'établir la conformité: nous devons présenter notre problème d'optimisation sous une forme dans laquelle une machine conçue pour résoudre les problèmes d'optimisation d'Ising peut le résoudre. Vous devez d'abord comparer le problème d'optimisation initial - par exemple, trouver un moyen pour le vendeur d'aspirateurs - avec un ensemble de spins, et déterminer comment les spins s'influencent mutuellement. Grâce aux études menées au cours des dernières décennies en informatique et en recherche opérationnelle , une comparaison de divers problèmes d'optimisation avec les formes d'Ising est généralement connue .

Cependant, il est difficile de travailler avec des atomes individuels et les spins de leurs électrons, nous nous sommes donc concentrés sur la création d'une machine qui implémente le modèle d'Ising en utilisant des impulsions de lumière au lieu de spins d'électrons. Le problème d'Ising est comparé aux impulsions et aux interactions entre eux. Le résultat est évalué en termes d'énergie totale du problème et un état avec une énergie minimale est considéré comme la solution optimale. Cette décision est ensuite traduite dans un langage qui a du sens pour la tâche d'origine - par exemple, de la manière la plus courte d'un vendeur.

L'OPO, un appareil de type laser, est la clé de la capacité de notre prototype à faire correspondre les spins aux impulsions lumineuses. Mais OPO, contrairement à un laser conventionnel, produit une lumière qui est exactement en phase, ou exactement en antiphase, à une lumière de base. C'est exactement ce qui est nécessaire pour représenter les états binaires du spin, de haut en bas. On peut imaginer un spin dirigé vers le haut comme un état dans lequel la lumière de l'OPO est en phase avec celle de base, et vice versa, un spin dirigé vers le bas correspond à la lumière en antiphase.

Il existe plusieurs façons de créer une machine Ising à l'aide d'OPO. Les groupes de NTT, Caltech, Cornell et Columbia, entre autres, ont des approches différentes. Le prototype de la machine Ising, présenté pour la première fois à Stanford dans une expérience menée par Alireza Marandi (qui travaille maintenant à Caltech), a utilisé une technologie avec laquelle nous continuons de travailler: le multiplexage temporel multiplexé et la connexion optique.

Regardons ce terme difficile. Nous commençons avec une source laser pulsée. La source envoie simultanément des impulsions lumineuses de plusieurs picosecondes dans deux directions. La première impulsion devient fondamentale; il se divise et suit deux chemins différents.

Le second est utilisé comme source d'énergie pour l'OPO: il stimule un cristal dans l'OPO, qui émet des impulsions de photons. Chaque impulsion est transmise à une bobine de câble en boucle optique de plusieurs centaines de mètres de long, selon le nombre d'impulsions dont nous avons besoin. Il y a des centaines, voire des milliers d'impulsions OPO dans cet anneau, et elles se poursuivront en cercle les unes après les autres, passant à travers le cristal encore et encore.


Ci-dessus: L'auteur de l'article et son ancien partenaire de laboratoire, Alireza Marandi, examinent le prototype de l'ordinateur optique d'Ising.
Ci-dessous: la plupart des événements ont lieu à l'intérieur de la bobine de câble optique

Les phases de ces impulsions joueront le rôle des spins du modèle d'Ising. Mais immédiatement après leur création, avant de parcourir plusieurs fois la boucle, ils sont tellement faibles que leurs phases ne sont pas bien définies. La façon dont nous les faisons interagir leur donnera finalement les phases finales et nous donnera la solution à notre problème d'Ising.

Rappelez-vous la lumière de base de la description de l'expérience? À un point de la boucle se trouve un séparateur qui sélectionne une petite partie de chaque impulsion, qui est comparée à l'impulsion de base dans le détecteur homodyne. La tension de sortie du détecteur contient des informations sur la phase et l'amplitude du détecteur. Ce signal est numérisé et introduit dans le PPVM. Dans ce document, le problème d'Ising lui-même est présenté.

Rappelons que résoudre le problème d'Ising signifie trouver l'état d'énergie minimum pour un ensemble de spins dans lesquels les spins interagissent de différentes manières, et ces interactions ajoutent de l'énergie supplémentaire à l'énergie totale du système. En HME, chaque élan dénote un spin. Par conséquent, pour chaque impulsion - et dans notre configuration, nous en avons utilisé 100 -, le PPMM effectue des calculs, qui incluent les mesures enregistrées de toutes les autres impulsions, ce qui, selon le problème d'Ising, devrait affecter le spin considéré. Le processeur applique ensuite les calculs aux réglages du modulateur d'intensité et du modulateur de phase situés sur l'un des trajets de l'impulsion de base. L'impulsion de base modifiée est introduite dans l'anneau du câble à fibres optiques, dans lequel les impulsions OPO espionnent.

Il est essentiel de choisir le bon moment - nous avons besoin de l'impulsion de base combinée pour combiner avec la bonne impulsion OPO. Si c'est fait correctement, les deux impulsions se mélangeront. Selon qu'ils sont en phase ou non, l'impulsion introduite dans le système incline l'impulsion OPO pour représenter un spin dirigé vers le haut ou vers le bas.

Pour chaque impulsion OPO dans la boucle, nous répétons tout ce processus et pour atteindre les états de phase finaux, les impulsions peuvent parcourir des dizaines de milliers de fois sur toute la longueur de la boucle. Après cela, un ordinateur séparé lit un ensemble de phases, les interprète comme des électrons du problème d'Ising avec des spins pointant vers le haut ou vers le bas, puis transforme cela en une solution significative au problème d'optimisation initial que vous devez résoudre.

Dans nos expériences, nous avons d'abord fait un système avec quatre tours, puis avec 16 tours. Les paramètres de la tâche étaient basés sur le matériel dans les installations sous la forme de segments de branchement d'un câble optique d'une certaine longueur. Dans ces expériences, nous avons découvert avec succès des états d'énergie minimale, ce qui nous a motivés à développer cette approche. En 2016, nous avons créé une machine de rétroaction basée sur PPVM capable de résoudre les problèmes d'Ising avec 100 tours. La comparaison de la vitesse de notre installation avec des systèmes spécialisés, y compris l'appareil de « recuit quantique » de la NASA, nous a donné la certitude que les machines Ising OPO peuvent être des optimiseurs efficaces.

Les résultats étaient prometteurs, mais nous avons encore beaucoup à apprendre avant de comprendre si une telle approche optique peut même devancer un processeur conventionnel pour résoudre des problèmes d'optimisation pratiques. Il est possible que la capacité de la machine à résoudre des problèmes puisse être améliorée en utilisant des états quantiques de la lumière, qui sont très difficiles à simuler. Nous approchons seulement la solution de beaucoup de ces questions, et nous prévoyons dans les prochaines années d'étudier l'interaction extrêmement intéressante de la théorie et de l'expérience, en développant ce nouveau type d'ordinateur.