Fügen Sie einfach Laser hinzu, um die schwierigsten Optimierungsaufgaben zu lösen

Ein seltsames Gerät, das als Ising Optical Machine bekannt ist, kann den Flugverkehr kontrollieren und der NFL helfen, Spiele zu planen.

Im vergangenen Jahr konnte ein Ausfall des Verteilungssystems zwischen Mitarbeitern von American Airlines zu einer Unterbrechung des Flugplans von Tausenden von Flügen während der Ferienzeit führen. Der Fehler ermöglichte es den Piloten, Flüge abzulehnen, ohne durch einen anderen Piloten ersetzt zu werden, und etwa 15.000 Flüge wurden bedroht. Und obwohl es der Fluggesellschaft gelungen ist, das Problem rechtzeitig zu verfolgen und die Mitarbeiter zu verteilen , wurde dieses Durcheinander zu einer Erinnerung daran, wie sehr wir bei der Organisation des Arbeitsplans einer Vielzahl von Diensten und Funktionen von Computern abhängig sind, von denen unsere Community jetzt vollständig abhängt.

Beispielsweise verfügen alle großen Fluggesellschaften über ausgefeilte Algorithmen zur Grafikoptimierung, mit denen Piloten und Flüge verglichen werden. Und obwohl der Vorfall mit American Airlines nicht direkt durch den Fehler des Algorithmus aufgetreten ist, könnte das Ergebnis ähnlich sein. Eine solche Ablehnung würde zu Hunderttausenden von Menschen in einer schwierigen oder sehr unbequemen Situation führen, während die Fluggesellschaft nach einem Ausweg aus der Situation suchte.

Der Triumph der algorithmischen Wissenschaft und des Moore'schen Gesetzes besteht darin, dass wir uns jetzt vielen komplexen Optimierungsaufgaben nähern können, einschließlich Bereichen wie Transport, Logistik und Terminplanung. Der größte Teil der modernen Welt wird ohne diese Algorithmen nicht normal funktionieren können: Jährlich werden 50.000 Frachtschiffe transportiert, 25.000 TWh Strom werden erzeugt, und Router transportieren 1 Zettabyte Verkehr durch sich selbst. All dies würde viel weniger effizient funktionieren. Unternehmen arbeiten jedoch häufig mit suboptimalen Lösungen, da die Fristen knapp sind und keine verfügbaren Computerressourcen zur Verfügung stehen. Darüber hinaus gibt es noch viele Möglichkeiten, die Methoden zu verbessern, mit denen wir die meisten Optimierungsprobleme lösen.

Angesichts der Bedeutung der Optimierung und der Tatsache, dass die Ära stabiler und bedeutender Verbesserungen der Prozessorgeschwindigkeit zu Ende zu gehen scheint, begannen die Forscher, die Frage zu untersuchen, ob speziell für die Optimierung entwickelte Maschinen unsere Fähigkeit zur Lösung komplexer Probleme erheblich verbessern können.

Ein vielversprechender Ansatz ist die Entwicklung optischer Maschinen zur Optimierung. Eine Gruppe von Wissenschaftlern der Stanford University (zu der auch der Autor des Artikels gehört) unter der Leitung von Yoshihik Yamamoto hat diese Studien vor sieben Jahren begonnen. Jetzt wird dieses Thema von mehreren Gruppen von Wissenschaftlern sowie Forschern aus den HP- und NTT- Labors untersucht. Nach Jahren der Arbeit wächst das Vertrauen, dass mindestens eine dieser Gruppen eines Tages in der Lage sein wird, eine Maschine zu entwickeln, mit der wir einige der schwierigsten Optimierungsprobleme lösen können, die die moderne Industrie lösen muss.


Die Aufgabe des Verkäufers: Die Komplexität von Aufgaben wie das Finden des kürzesten Wegs zwischen mehreren Punkten nimmt mit der Anzahl der Punkte zu. Das Modellieren unter dem Deckmantel von Ising-Optimierungsproblemen kann helfen, sie schneller zu lösen.

Denken Sie an das klassische Verkäuferproblem, bei dem der Verkäufer von Stadt zu Stadt zieht und Waren verkauft. Er will keine Zeit und kein Geld mit Benzin verschwenden. Dies ist eine Optimierungsaufgabe, deren Zweck es ist, den kürzesten Weg für den Verkäufer zu finden, da er einmal zu jedem Punkt gelangen muss und am Ende der Reise dorthin zurückkehren möchte, wo er begonnen hat.

Für fünf Städte ist das Problem einfach gelöst. Sie kann einfach unter Berücksichtigung aller 12 Pfade berechnet werden . Wenn der Verkäufer jedoch beabsichtigt, 50 Städte zu besuchen, ist die Suchmethode, die alle möglichen Pfade berücksichtigt, unerträglich - es gibt mehr dieser Pfade als die neue Dekillion oder 10 ⁶⁰ - Eins und 60 Nullen.

Mögliche Lösungen für dieses Problem können uns durch Algorithmen gegeben werden, die unterschiedliche Bypass-Pfade und vernünftige Näherungen verwenden. Aber selbst die besten von ihnen können den leistungsstärksten Computer zum Nachdenken bringen. In einem aktuellen Beispiel versuchte die Waterloo University aus Kanada , den kürzesten Weg zwischen fast 50.000 Städten in den Vereinigten Staaten zu finden, die im nationalen Register historischer Orte eingetragen waren, und die Richtigkeit ihrer Entscheidung zu beweisen. Zu diesem Zweck verwendete er 310 leistungsstarke Prozessoren, die 9 Monate lang ohne Unterbrechung arbeiteten.

Die Optimierung umfasst jedoch viel mehr Aufgaben als nur die Verkäuferaufgabe. Eine weitere Herausforderung ist die Planung. Zum Beispiel muss die National Football League in den Vereinigten Staaten jährlich mehrere hundert Spiele planen und gleichzeitig versuchen, Tausende von Regeln einzuhalten, die es beispielsweise Teams verbieten, mehr als drei Spiele hintereinander auf ihrem eigenen Feld zu spielen. Um dieses Problem zu lösen, verwendete die NFL 2017 einen Cluster von 400 Computern .


Ising-Optimierung : Bei diesem Ising-Problem ist die Energie des Systems geringer, wenn die Spins seiner Elektronen in Richtungen gerichtet sind, die den Spins der Nachbarn entgegengesetzt sind. Systeme, die den Zustand mit minimaler Energie im Ising-Modell finden können, können dazu beitragen, die Lösung komplexer Optimierungsprobleme zu beschleunigen.

Fertigungsunternehmen müssen die Maschinenwartung planen. Universitäten brauchen einen Stundenplan. Postdienste müssen Zustellrouten planen. Großstädte wie Peking oder Tokio würden gerne lernen, wie man die Ströme von Millionen von Autos, die während der Hauptverkehrszeiten versuchen, durch ihre Straßen zu fahren, effektiv verwaltet. Diese Aufgaben können Hunderte oder Tausende von Ereignissen umfassen, die geplant werden müssen. In vielen Fällen sind praktische Lösungen immer noch nicht verfügbar, da sie zu viel Computerzeit oder zu viele Computer erfordern.

Seit vielen Jahren versuchen Forscher, spezielle Maschinen zur Lösung von Optimierungsproblemen zu entwickeln. Mitte der 1980er Jahre schlugen David Tank, der damals bei AT & T Bell Labs arbeitete, und John Hopfield, beide bei AT & T Bell und Caltech, vor, analoge elektronische Schaltkreise zu verwenden, die neuronale Netze darstellen, um Optimierungsprobleme wie das Problem des Handlungsreisenden zu lösen. Ihre Arbeit führte zu jahrzehntelanger Forschung auf diesem Gebiet. Dann, 1994, entdeckte Leonard Edleman von der University of Southern California, dass DNA theoretisch zur Lösung solcher Probleme verwendet werden kann. Seine Idee führte zu einer ähnlichen Flut von Forschungen. Diese Versuche, radikal neue und effektive Ansätze zur Lösung von Optimierungsproblemen zu entwickeln, haben jedoch zu praktischen Alternativen zu herkömmlichen Computern und Technologien geführt, die bis heute die Hauptwerkzeuge zur Lösung solcher Probleme sind.

Versuche, spezielle optische Maschinen zu entwickeln, die Optimierungsprobleme lösen können, haben sich auf eines dieser Probleme konzentriert, das als Ising-Optimierung bekannt ist. Sie wurde nach dem Physiker Ernst Ising benannt, der berühmten Arbeit über das Modell magnetischer Momente und deren Erklärung der Übergänge zwischen verschiedenen magnetischen Zuständen. Es stellt sich heraus, dass viele häufig auftretende Optimierungsprobleme, einschließlich der Planung und Suche nach Pfaden, leicht in Ising-Optimierungsprobleme umgewandelt werden können.

Um zu verstehen, wie das Ising-Modell mit der Optimierung zusammenhängt, müssen Sie es zunächst in der Physik verwenden, um den Magnetismus zu verstehen. Betrachten Sie einen herkömmlichen Magnetstab. Mit dem Ising-Modell kann man sich einen Magnetstab als dreidimensionales Gitter von Atomen vorstellen, in dem jedes der Atome selbst ein Magnetstab ist. Elektronen in Atomen haben eine Eigenschaft, die als Spin bezeichnet wird. Die Spins der Valenzelektronen - die sich an den äußeren Schalen des Atoms befinden - sind entweder nach oben oder nach unten gerichtet. Die Richtung der Spins bestimmt die Magnetisierung des Materials. Wenn alle Rücken nach oben gerichtet sind, wird das Material magnetisiert. Wenn unten, wird das Material auch magnetisiert - nur mit der entgegengesetzten Polarität. Wenn die Rücken gemischt werden, wird das Material nicht magnetisiert.

Diese Drehungen interagieren auch miteinander. In einem Magnetstab ist die " Gesamtenergie " zweier benachbarter Elektronen geringer, wenn ihre Spins ausgerichtet sind - das heißt, sie sind in die gleiche Richtung gerichtet. Umgekehrt ist ihre Gesamtenergie höher, wenn die Spins multidirektional sind.


Optische Ising-Maschine: Ein optischer parametrischer Oszillator (OPO) mit Messungsrückkopplung kann Optimierungsprobleme lösen, die in Form eines Ising-Modells ausgedrückt werden - eine Reihe von Elektronenspins und deren Einfluss aufeinander. Die Phasen der optischen Impulse in OPO stellen Spins dar, und der Effekt wird in ein vom Benutzer programmierbares Gate-Array ( PPM ) eingeführt. Es ist notwendig, ungefähr hundert Durchgänge durch das System zu absolvieren, bevor die Impulse im OPO stark genug werden, um eine Lösung für das Problem zu finden.

Im Ising-Modell fassen wir die Energie der Wechselwirkungen zwischen den Spins jedes Elektronenpaars in einer Reihe von Atomen zusammen. Da die Energiemenge davon abhängt, ob die Drehungen ausgerichtet sind oder nicht, hängt die Gesamtenergie des Satzes von der Richtung aller Drehungen des Systems ab. Daher besteht die allgemeine Aufgabe der Ising-Optimierung darin, zu bestimmen, in welchem ​​Zustand sich die Drehungen befinden sollten, um die Energie des Systems zu minimieren.

Im einfachsten Modell wird angenommen, dass nur benachbarte Spins interagieren. Bei dem allgemeinen Ising-Optimierungsproblem kann jedoch jeder Spin unabhängig von der Entfernung mit jedem anderen interagieren, und das Vorzeichen und die Stärke dieser Wechselwirkungen können für jedes Rückenpaar eindeutig sein. In einer solchen verallgemeinerten Formulierung ist dieses Problem sehr schwer zu lösen - genau wie das Problem eines Verkäufers, der Hunderttausende potenzieller Käufer besucht. Wenn wir einen Weg finden, um Ising-Optimierungsprobleme schnell zu lösen und über das Problem des Handlungsreisenden und ähnliche Probleme auf die gleiche Weise wie Ising-Probleme zu sprechen, können wir diese Probleme möglicherweise auch schnell lösen. Die minimale Systemenergie im Ising-Problem stellt die schnellste Route zwischen Städten dar, die effektivste Lösung für das Packen eines Frachtschiffs oder jedes andere Optimierungsproblem, das wir benötigen.

Wie wandelt man den Weg eines reisenden Verkäufers in Rücken um? Die Hauptaufgabe besteht darin, die Konformität herzustellen: Wir müssen unser Optimierungsproblem in einer Form darstellen, in der eine Maschine, die zur Lösung von Ising-Optimierungsproblemen entwickelt wurde, es lösen kann. Zuerst müssen Sie das anfängliche Optimierungsproblem - zum Beispiel einen Weg für den Verkäufer von Staubsaugern finden - mit einer Reihe von Drehungen vergleichen und bestimmen, wie sich Drehungen gegenseitig beeinflussen. Dank Studien, die in den letzten Jahrzehnten sowohl in der Informatik als auch in der Operationsforschung durchgeführt wurden , ist ein Vergleich verschiedener Optimierungsprobleme mit Ising-Formen allgemein bekannt .

Es ist jedoch schwierig, mit einzelnen Atomen und den Spins ihrer Elektronen zu arbeiten. Deshalb haben wir uns darauf konzentriert, eine Maschine zu entwickeln, die das Ising-Modell mithilfe von Lichtimpulsen anstelle von Elektronenspins implementiert. Das Ising-Problem wird mit Impulsen und Wechselwirkungen zwischen ihnen verglichen. Das Ergebnis wird anhand der Gesamtenergie des Problems bewertet, und ein Zustand mit minimaler Energie wird als optimale Lösung angesehen. Dann wird diese Entscheidung in eine Sprache übersetzt, die für die ursprüngliche Aufgabe sinnvoll ist - zum Beispiel auf kürzestem Weg eines Verkäufers.

Der Schlüssel für die Fähigkeit unseres Prototyps, Drehungen an Lichtimpulse anzupassen, ist das OPO, ein laserähnliches Gerät. Im Gegensatz zu einem herkömmlichen Laser erzeugt OPO jedoch Licht, das genau in Phase oder genau gegenphasig zu einem Grundlicht ist. Dies ist genau das, was benötigt wird, um die Binärzustände des Spins nach oben und unten darzustellen. Wir können uns einen nach oben gerichteten Spin als einen Zustand vorstellen, in dem das Licht des OPO mit der Basis in Phase ist, und umgekehrt entspricht ein nach unten gerichteter Spin dem gegenphasigen Licht.

Es gibt verschiedene Möglichkeiten, eine Ising-Maschine mit OPO zu erstellen. Gruppen von NTT, Caltech, Cornell und Columbia verfolgen unter anderem unterschiedliche Ansätze. Der Prototyp der Ising-Maschine, der erstmals in Stanford in einem von Alireza Marandi (die jetzt in Caltech arbeitet) geleiteten Experiment gezeigt wurde, verwendete eine Technologie, mit der wir weiter arbeiten: Multiplex-Zeitmultiplex und optische Verbindung.

Schauen wir uns diesen schwierigen Begriff an. Wir beginnen mit einer gepulsten Laserquelle. Die Quelle sendet simultane Lichtimpulse, die mehrere Pikosekunden dauern, in zwei Richtungen. Der erste Impuls wird grundlegend; es teilt sich und geht zwei verschiedene Wege.

Die zweite wird als Energiequelle für OPO verwendet: Sie stimuliert einen Kristall in OPO, der Photonenimpulse aussendet. Jeder Impuls wird an eine mehrere hundert Meter lange Spule aus optischen Schleifen übertragen, abhängig von der Anzahl der benötigten Impulse. Es gibt Hunderte oder sogar Tausende von OPO-Impulsen in diesem Ring, und sie werden nacheinander in einem Kreis jagen und immer wieder durch den Kristall gehen.


Oben: Der Autor des Artikels und seine frühere Laborpartnerin Alireza Marandi betrachten den Prototyp des optischen Computers von Ising.
Unten: Die meisten Veranstaltungen finden innerhalb der optischen Kabeltrommel statt

Die Phasen dieser Impulse spielen die Rolle der Drehungen des Ising-Modells. Aber unmittelbar nach ihrer Erstellung, bevor sie mehrmals die Schleife durchlaufen, sind sie so schwach, dass ihre Phasen nicht genau definiert sind. Die Art und Weise, wie wir sie interagieren lassen, gibt ihnen letztendlich die letzten Phasen und gibt uns die Lösung für unser Ising-Problem.

Erinnern Sie sich an das Basislicht aus der Beschreibung des Experiments? An einem Punkt in der Schleife befindet sich ein Splitter, der einen kleinen Teil jedes Impulses auswählt, der mit dem Basisimpuls im Homodyn-Detektor verglichen wird. Die Ausgangsspannung des Detektors enthält Informationen über die Phase und Amplitude des Detektors. Dieses Signal wird digitalisiert und in die PPVM eingespeist. Darin wird das Ising-Problem selbst vorgestellt.

Denken Sie daran, dass zur Lösung des Ising-Problems der Ermittlung des minimalen Energiezustands für eine Reihe von Drehungen erforderlich ist, bei denen Drehungen auf unterschiedliche Weise interagieren. Diese Wechselwirkungen erhöhen die Gesamtenergie des Systems um zusätzliche Energie. In HME bezeichnet jeder Impuls einen Spin. Daher führt das PPMM für jeden Impuls - und in unserem Setup haben wir 100 verwendet - Berechnungen durch, die die aufgezeichneten Messungen aller anderen Impulse enthalten, die gemäß dem Ising-Problem den betrachteten Spin beeinflussen sollten. Der Prozessor wendet die Berechnungen dann auf die Einstellungen des Intensitätsmodulators und des Phasenmodulators an, die sich auf einem der Pfade des Basisimpulses befinden. Der modifizierte Basisimpuls wird in den Ring des Glasfaserkabels eingespeist, in dem die OPO-Impulse snoop sind.

Es ist wichtig, den richtigen Moment zu wählen - wir brauchen den kombinierten Basisimpuls, um ihn mit dem richtigen OPO-Impuls zu kombinieren. Bei korrekter Ausführung mischen sich die beiden Impulse. Je nachdem, ob sie in Phase sind oder nicht, neigt der in das System eingebrachte Impuls den OPO-Impuls, um einen nach oben oder unten gerichteten Spin darzustellen.

Für jeden OPO-Impuls in der Schleife wiederholen wir diesen gesamten Vorgang. Um die endgültigen Phasenzustände zu erreichen, können sich die Impulse zehntausende Male über die gesamte Länge der Schleife bewegen. Danach liest ein separater Computer eine Reihe von Phasen, interpretiert sie als Elektronen aus dem Ising-Problem, wobei die Drehungen nach oben oder unten zeigen, und verwandelt sie dann in eine sinnvolle Lösung für das anfängliche Optimierungsproblem, das Sie lösen müssen.

In unseren Experimenten haben wir zuerst ein System mit vier Drehungen und dann mit 16 Drehungen erstellt. Die Parameter der Aufgabe waren hardwarebasiert in Installationen in Form von Verzweigungssegmenten eines optischen Kabels einer bestimmten Länge. In diesen Experimenten haben wir erfolgreich Zustände minimaler Energie entdeckt, und dies hat uns motiviert, diesen Ansatz zu entwickeln. 2016 haben wir eine PPVM-basierte Feedback-Maschine entwickelt, mit der Ising-Probleme mit 100 Spins gelöst werden können. Der Vergleich der Geschwindigkeit unserer Anlage mit speziellen Systemen, einschließlich des NASA- Quantenglühgeräts , gab uns das Vertrauen, dass die Ising OPO-Maschinen effiziente Optimierer sein können.

Die Ergebnisse waren vielversprechend, aber wir müssen noch viel lernen, bevor wir verstehen, ob ein solcher optischer Ansatz bei der Lösung praktischer Optimierungsprobleme sogar einem herkömmlichen Prozessor voraus sein kann. Es ist möglich, dass die Fähigkeit der Maschine, Probleme zu lösen, durch die Verwendung von Quantenzuständen des Lichts verbessert werden kann, die sehr schwer zu simulieren sind. Wir nähern uns nur der Lösung vieler solcher Fragen und planen, in den nächsten Jahren das äußerst interessante Zusammenspiel von Theorie und Experiment zu untersuchen und diesen neuen Computertyp zu entwickeln.