Vorglühen für Optimierungsaufgaben Was ist Quanten-Annealing?

Quantencomputing nutzt Quantenzustände subatomarer Partikel, um Rechenoperationen durchzuführen und/oder Daten zu speichern. Unter dem Oberbegriff Quantencomputing werden derzeit mehrere verschiedene Ansätze zusammengewürfelt. Einer davon ist Quanten-Annealing (englisch: Quantum Annealing).

Anbieter zum Thema

DataCore Software GmbH

Fujitsu Technology Solutions GmbH

Insider Research

Quantum-Annealing ist eine Klasse von algorithmischen Methoden und metaheuristischen Tools zur Lösung von Optimierungsproblemen, welche sich die Quantenfluktuation zu Nutze machen, um das globale Minimum einer gegebenen Zielfunktion näherungsweise zu suchen. (Eine Quantenfluktuation ist das zeitweilige Erscheinen von energetischen Teilchen aus dem leeren Raum.)

Beim Durchforsten des Suchraums dieser Aufgabenstellungen macht sich Quanten-Annealing die Quanten-Überlagerung zu Nutze. Das System durchläuft hierbei eine zeitabhängige Entwicklung, bei der sich die Amplituden der Kandidatenzustände in Abhängigkeit von der Stärke des Querfelds ändern, was das Quanten-Tunneling ermöglicht. Als Resultat eines adiabatischen Prozesses wird eine Hamiltonsche Gleichung gefunden, deren Grundzustand die Lösung der Annealing-Aufgabe darstellt.

Quanten-Annealing bietet Laufzeitvorteile für harte Optimierungsprobleme, welche durch raue Energielandschaften gekennzeichnet sind. Quanten-Annealing übertrifft die Leistung von simuliertem Annealing bei Problemen von ab etwa 1.000 binären Variablen. (Bei simuliertem Annealing handelt es sich um ein heuristisches Approximationsverfahren zur Lösung von Optimierungsproblemen, die so komplex sind, dass sie das Ausprobieren aller Möglichkeiten sowie mathematische Optimierungsverfahren ausschließen).

Quanten-Annealing wird hauptsächlich für kombinatorische Optimierungsprobleme verwendet. Eine geeignete Aufgabenstellung verfügt idealerweise über einen diskreten Suchraum und viele lokale Minima (im Fachjargon „rugged energy landscape“).

Ein Quantum-Annealer spielt seine Stärken bei Problemen aus, für die es in einer „felsigen“ Energielandschaft potenziell viele brauchbare Lösungen gibt und bereits irgendeine beliebige davon — also ein lokales statt des absoluten Minimums der Optimierungsfunktion — ein zufriedenstellendes Resultat darstellt. Diese Art eines Quantencomputers löst bereits heute kombinatorische Optimierungsprobleme im Bereich der Verkehrsflussoptimierung, zum Beispiel im Volkswagen-Konzern, sowie in der Materialforschung für die Luft- und Raumfahrt, etwa bei Airbus, der NASA und bei Lockheed Martin.

Quantum-Annealing

Der Begriff „Annealing“, auf Deutsch „Glühen“, zieht eine Analogie zum Glühvorgang in der Stahlindustrie. Dieses mehrstufige Verfahren der Metallverarbeitung besteht aus den Phasen „Anwärmen“, „Halten“ und „Abkühlen“. Im Quantencomputing lässt sich diese Bezeichnung auf die Vorgänge zurückführen, welche auf ein einzelnes Qubit angewendet werden, um seinen quantenmechanischen Zustand zu beeinflussen.

Das Elektron eines Qubits hat eine Ladung und einen Elektronenspin: Das Teilchen schwingt zwischen zwei Positionen (0 und 1) um die eigene Achse hin und her und erzeugt dabei ein variables Magnetfeld; so kann sich ein Qubit gleichzeitig in diesen zwei Zuständen befinden. Bei dieser Eigenschaft handelt es sich um die Quanten-Überlagerung (in englisch: quantum superposition).

Im Zuge des Quanten-Annealing-Verfahrens wechselt jedes Qubit von der Quanten-Überlagerung in einen klassischen Zustand: Er nimmt entweder den Wert 0 oder 1 ein. Durch die Zufuhr von Energie lässt sich dieser Prozess beeinflussen.

Zur Durchführung von Berechnungen mit vielen Qubits müssen sich diese Elemente ununterbrochen in voneinander abhängigen Superpositionen befinden, also in einem so genannten „quantenkohärenten“ Zustand, in dem die Qubits miteinander verschränkt sind. Die Änderung eines Qubits beeinflusst dann nämlich zugleich den Zustand aller anderen damit verschränkten Qubits.

Verschränkte Systeme verhalten sich über beliebige Entfernungen so, als ob sie miteinander verbunden wären. So legt beispielsweise eine Messung des Spins des einen Elektrons den Spinzustand des anderen fest. Falls das Ergebnis der Messung des ersten Teilchens beispielsweise Spin-up ergibt, so ist das zweite im Zustand Spin-down (je nach Art der Verschränkung möglicherweise auch umgekehrt). Ein verschränkter Zustand lässt sich nicht faktorisieren.

Quantencomputer nutzen dieses Phänomen der Qubits für Rechenoperationen, zum Beispiel im Rahmen der Kryptographie, und die „Teleportation“ von Quantengattern - erstmals 2018 als möglich nachgewiesen.

Jedes Qubit in einem Quantencomputer kann mit den anderen Qubits des Systems verschränkt sein. Die Verflechtung von Quantenzuständen erhöht exponentiell die Anzahl von Nullen und Einsen, die ein Array von Qubits gleichzeitig verarbeiten kann.

Doch es hapert noch an der Umsetzung: In aktuellen Implementierungen ist die Superposition so zerbrechlich, dass zufällige Wechselwirkungen eines einzelnen Qubits mit den Molekülen seiner unmittelbaren Umgebung das gesamte Netzwerk der verschränkten Qubits in dem System zusammenbrechen lassen oder abtrennen kann.

Die Funktionsweise eines Quanten-Annealers

Das Lösen von Problemen mit einem Quanten-Annealer kann als ein Versuch betrachtet werden, den tiefsten Punkt in einer Landschaft aus Gipfeln und Tälern zu finden. Jede mögliche Lösung wird den Koordinaten in der Landschaft zugeordnet, und die Höhe der Landschaft ist die „Energie“ (der „Kostenpunkt“) der Lösung an diesem Ort.

Das Ziel besteht hierbei darin, den tiefsten Punkt oder Punkte auf der Karte zu finden und die Koordinaten auszulesen, da dies die niedrigste Energie also die (beinahe) optimale Lösung für das Problem ergibt. (Es ist die „beinahe“ optimale Lösung, nicht zwangsweise das globale Minimum.)

Phänomena der Quantenphysik wie das Quantentunneling ermöglichen es dem Quanten-Annealer, diese Landschaft auf eine Weise zu erkunden, die mit klassischen Systemen noch nie möglich war.

Quanten-Tunneling in einem Quanten-Annealer

Quantentunneling lässt sich am besten durch eine Analogie zu einem Bieber beschreiben, der in einer Landschaft voller Seen und Hügel zur tiefsten Schlucht durchdringen möchte. Der Bieber kann überirdisch laufen, tauchen und direkt durch die Hügel „tunneln“. Das Tunneln ist energieintensiv, aber Raubtier-sicher. So tunnelt der Bieber gerne direkt durch die Hügel hindurch, muss sich jedoch zwischendurch von dem Buddeln erholen, indem er sich auf seinem Weg zur tiefsten Schlucht der Unterwasser-Landschaft in einer lokalen Schlucht versteckt.

So etwa verläuft auch thermisch angeregtes Quanten-Tunneling in einem Quanten-Annealer:

• Im ersten Schritt nimmt das System Energie aus dem Thermalbad auf.

• Als Nächstes macht es sich Quanten-Tunneling zu Nutze, um den Übergang zwischen dem Eintritts- und dem Austrittspunkt zu vollziehen.

• Im dritten Schritt entspannt sich das System auf ein lokales Minimum durch die Abgabe der Energie zurück ans Thermalbad.

Adiabatische Quanten-Annealer

Der Adiabaten-Ansatz der Quantenmechanik besagt, dass der Zustand eines quantenmechanischen Systems die gesuchte Problemlösung in guter Annäherung findet, wenn der sogenannte Energieoperator gemäß einer Formel „langsam genug“ geändert wird.

Die bisher erfolgreichste Implementierung eines Quanten-Annealers, die D-Wave-Maschine von D-Wave Systems, macht sich in ihrer QPU — Quantum Processing Unit — das adiabatische Theorem der Quantenmechanik zu Nutze.

Die Aufgabe der QPU besteht darin, ein Ising-Problem zu lösen (eine quadratische uneingeschränkte binäre Optimierungsaufgabe). Jedes Qubit repräsentiert hierbei eine Variable. Die Koppler zwischen Qubits (die programmierbaren induktiven Verbindungen zwischen Qubits) repräsentieren die Kosten, die mit den Qubit-Paaren verbunden sind. Bei der QPU handelt es sich um nichts anderes als eine physische Implementierung eines ungerichteten Graphen mit Qubits als Scheitelpunkten und Kopplern als Kanten dazwischen.

Beim Quanten-Computing auf der Basis des adiabatischen Theorems wird ein Rechenproblem kodiert, indem ein System langsam vom Grundzustand einer einfachen anfänglichen Hamiltonschen Gleichung zur Lösung der finalen Hamiltonschen Gleichung geführt wird. Der Reiz dieses Ansatzes liegt in der Kombination von Einfachheit und Allgemeinheit.

Prinzipiell lässt sich jedes Optimierungsproblem für einen adiabatischen Quanten-Annealer aufarbeiten. In der Praxis sind mögliche Anwendungen aber durch begrenzte Konnektivität zwischen Qubits, verfügbare Interaktionen und auch durch Quanten-Rauschen eingeschränkt.

Die geringste 2-Zustands-Recheneinheit einer QPU (Quantum Processing Unit) von D-Wave Systems ist der sogenannte Qubit.

Anders als ein klassisches Bit kann ein Qubit neben den Zuständen 0 und 1 dank der Quantenüberlagerung beliebige Werte dazwischen erfassen (Engl. „quantum superposition“).

*Das Autoren-Duo

Die Autoren des Artikels, Anna Kobylinska und Filipe Pereira Martins arbeiten für McKinley Denali Inc. (USA).

(ID:45639860)