Verkehrsflussoptimierung mit einem D-Wave Quantum Annealer

Durch Barrieren

Christian Seidel, Florian Neukart, Gabriele Compostella

Seit Kurzem sind erste Quantencomputer erhältlich. Noch sind sie zu schwach und die Algorithmen zu wenig automatisiert. Tests ergeben allerdings, dass sie bestimmte Aufgaben besser lösen als klassische Rechner. So etwa in einem VW-Projekt zur Verkehrsflussoptimierung.

In immer kürzeren Abständen finden sich Meldungen in der Presse, dass Quantencomputer die Welt verändern würden. Mit ihnen ließe sich Verschlüsselung knacken oder es ließen sich neue Medikamente dank Proteinfaltung rasch erforschen und entwickeln. Kurzum: Die enorme Rechenleistung von Quantencomputern löse die komplexesten Aufgaben. Tatsächlich kommen nach und nach erste Quantencomputer aus den Laboren auf den Markt. Aber wie leistungsfähig sind diese heute bereits?

In den 1980er-Jahren machte neben anderen Richard Feynman den Vorschlag, quantenmechanische Fragestellungen mit eigens dafür geschaffenen Quantencomputern zu lösen, und veröffentlichte dazu ein Grundsatzpapier ([a], siehe ix.de/ix1802094). Sie sollten für die Berechnung quantenphysikalische Effekte, etwa Superposition und Verschränkung (siehe Glossar), ausnutzen. Von diesem direkten Weg versprach sich die Forschung eine deutliche Effizienzsteigerung.

Vom klassischen Computer zum Quantencomputer

Anders als klassische Computer rechnet ein Quantencomputer nicht mit Bits, sondern mit Quantenbits oder Qubits. Realisieren lassen sie sich auf unterschiedliche Weise: durch Spinpolarisation in Ionenfallen, Quantenpunkten, Photonen oder mittels Superconducting Quantum Interference Devices (SQUIDs). Für Qubits gelten quantenmechanische Prinzipien wie Verschränkung oder Superposition. In Superposition kann ein Qubit bis zu seiner Messung gleichzeitig die Werte 0 und 1 haben.

Bisher haben sich zwei Quantencomputermodelle herausgebildet: adiabatische Quantencomputer und (universelle) Quantengattercomputer. Adiabatische Quantencomputer, auch Quantum Annealer genannt, implementieren eine Berechnung durch die adiabatische Entwicklung eines quantenmechanischen Systems. Die Initialisierung der Qubits erfolgt in der minimalen Energiekonfiguration, die durch den sogenannten initialen Hamilton-Operator festgelegt wird. Darauf folgt die Entwicklung des Systems hin zum Problem-Hamiltonian, dessen Grundzustand die Lösung abbildet.

Der minimale Energiezustand, den das System bei adäquater Darstellung findet, ist der Output des Rechenvorgangs und somit die optimale Lösung. Dieser Ansatz eignet sich besonders für Optimierungsprobleme. Weitere Anwendungsbereiche sind Sampling und maschinelles Lernen, sofern sich die Fragestellung als Energiewertproblem darstellen lässt. Darunter fallen Mustererkennung, Spracherkennung, Prognosemodelle, Clustering oder Computer Vision.

Adiabatische Quantencomputer sind grundsätzlich polynomiell gleichwertig zum Quantengattermodell: Problemstellungen können gleich effizient auf einem adiabatischen Quantencomputer wie auf einem Quantengatter-Rechner verarbeitet werden [b]. Ein Beispiel sind die Computer von D-Wave, die jedoch nur auf Optimierungs- und Sampling-Aufgaben ausgelegt sind.

Das Quantengattermodell auf der anderen Seite gilt häufig als das Modell des zukünftigen Universalquantencomputers schlechthin, denn damit lassen sich beliebige Algorithmen implementieren und nicht nur reine Optimierungsprobleme. Ist die Frage mittels Qubits formuliert, werden diese der Reihe nach über die Gatter manipuliert. Die Berechnung endet in einer Messung, die zur Folge hat, dass die Superposition der Qubits in eine einzige Bitsequenz und somit den reinen Zustand kollabiert. Für dieses Modell existieren seit den 90er-Jahren erste Algorithmen wie Shor zur Primfaktorzerlegung oder Grover zur Datenbanksuche. Firmen wie IBM, Google, Intel, Rigetti und andere arbeiten aktuell an der Entwicklung eines Gate-Model-Quantencomputers.

Im Gegensatz zu anderen Anbietern, die auf supraleitende Qubits setzen, verfolgt Microsoft einen komplizierteren Ansatz: den des topologischen Quantencomputers. Die dahinterliegenden Konzepte der Mathematik und Physik wie Quasipartikel und Braids sind hochspannend und Gegenstand aktueller Forschungen. Quasipartikel treten auf, wenn sich Anregungen in komplexen Systemen wie Festkörpern wie schwach interagierende Partikel im freien Raum verhalten. Anyonen sind zum Beispiel zweidimensionale Quasipartikel, deren Weltlinien sich kreuzen und Zöpfe (Braids) in dreidimensionaler Raumzeit formen. Diese Braids wiederum werden als logische Gates im topologischen Quantengatter verwendet. Vorteil eines solchen Quantencomputers wäre eine geringere Fehleranfälligkeit.

Qubits besitzen zwei mögliche Zustände, die in der Literatur oft mit Up und Down bezeichnet werden. Im Gegensatz zu klassischen Bits gilt jedoch: a) Teilchen in Superposition können mehrere Zustände gleichzeitig einnehmen. b) Sind zwei Teilchen verschränkt, ergibt sich durch die Messung des einen automatisch der Zustand des anderen. c) Quanten können mit einer endlichen Wahrscheinlichkeit durch Hindernisse tunneln und so klassisch nicht erlaubte Zonen erreichen (Abb. 1).

Denn: Auch beim Quantencomputer können Fehler entstehen, die die Rechenoperation beeinflussen. Zudem ist er ein probabilistisches System. Was geschieht, wenn in einem Quantenschaltkreis eine Störung vorliegt? Ein klassischer Computer kann mit seinem Binärsystem den Wert 1 bei einer Spannung von beispielsweise 3 Volt und den Wert 0 mit keiner Spannung darstellen. Liegt auf einem Schaltkreis nun lediglich eine Spannung von 2,3 Volt an, lässt sich dies leicht korrigieren. Eine Regel „Spannungen größer als 1,5 Volt werden zum Wert 1, kleiner zum Wert 0“ ist schnell implementiert. Da Effekte wie Interferenz Bitflips verursachen und damit die Berechnung negativ beeinflussen können, ist eine Fehlerkorrektur notwendig. Dafür müssen aber zusätzliche Qubits bereitstehen. So können mehrere physische Qubits zu fehlerkorrigierten logischen Qubits zusammengeschlossen werden, die dann die Rechenoperationen durchführen. Das verringert aber die Zahl der auf dem Chip adressierbaren Qubits.

Superposition ist sowohl bei Quantum-Annealing-Systemen als auch bei Gate-Model-Quantencomputern der wichtigste Effekt. Dank ihr evaluiert ein Quantenprozessor in einem einzigen Aufruf alle Konfigurationen und damit alle möglichen Lösungen eines Problems. Ein klassischer Algorithmus muss sich trotz Parallelisierung mit sequenziellen CPU-Zugriffen zufriedengeben.

Die Kunst bei der Implementierung von Qubits ist es, die Superposition so lange wie möglich aufrechtzuerhalten. Äußere Einflüsse wie Temperaturschwankungen oder selbst das Magnetfeld der Erde können je nach Beschaffenheit der Qubits eine Dekohärenz auslösen. Deshalb ist meist eine starke Abschirmung der Quantum Processing Units (QPU) erforderlich.

Der zweite relevante Quanteneffekt ist die Verschränkung. Zwei verschränkte Qubits beeinflussen sich wechselseitig. Das ist unabhängig davon, ob sich beide im selben Raum oder ob sich eines auf der Erde und das andere in der Andromeda-Galaxie befindet. Der Vorgang der Verschränkung legt die Informationseigenschaft der beiden Qubits fest, also beispielsweise den Status 0 oder 1. Das gilt es zu beachten, denn später findet kein Informationsaustausch mehr statt. Wird also ein Qubit gemessen, ist gleichzeitig der Zustand der verschränkten Qubits fixiert. Diese von Einstein noch verächtlich „spukhafte Fernwirkung“ genannte Eigenschaft ist ein wichtiger Bestandteil eines Quantencomputers.

Der dritte Effekt ist das Tunneling. Jede potenzielle Lösung weist eine spezifische Energie auf. Hohe Energien repräsentieren suboptimale Lösungen und jene mit niedrigen Energien nähern sich dem Optimum an. Die Lösungen bewegen sich sinnbildlich in einer hügeligen Landschaft mit Bergen und Tälern. Im tiefsten Tal befindet sich das Energieminimum, also die optimale Lösung. Die Herausforderung liegt darin, dieses tiefste Tal zu finden. Dank Tunneling richtet sich das System stets zum Energieminimum aus. Zustände tunneln durch die Energiebarrieren, also die Hügel der Landschaft, egal an welcher Stelle der Ausgangspunkt ist. Auch einige herkömmliche Algorithmen, wie der Bergsteigeralgorithmus, die Tabusuche oder Simulated Annealing, versuchen mit unterschiedlichen Techniken, das globale Minimum zu finden. Sie laufen jedoch Gefahr, in einem Tal stecken zu bleiben – einem lokalen Minimum –, das zwar tief ist, aber nicht das tiefste. Die optimale Lösung bleibt bei zeitkritischen Problemen oftmals verborgen.

Erste Systeme entstanden zunächst überwiegend im universitären Bereich. Im Jahr 2011 brachte das kanadische Unternehmen D-Wave Systems einen sogenannten Quantum Annealer auf den Markt: den D-Wave One mit 128 Qubits. Weitere Firmen wie Google, IBM, Rigetti, Intel und Microsoft ziehen seither nach. Die entstandene Konkurrenz beschleunigt die Entwicklung und macht die Produkte für Forschung und Industrie immer interessanter (siehe Kasten „Vom klassischen Computer zum Quantencomputer“).

Von der Theorie zur Praxis

Quantum-Annealing-Systeme von D-Wave stehen typischerweise im Labor des Unternehmens. Zugriff erfolgt übers Netzwerk (Abb. 2). *Quelle: D-Wave Systems*

Die Autoren dieses Artikels haben es sich zur Aufgabe gemacht, erste Einsatzszenarien an verfügbaren Systemen zu testen. Sie verwenden dafür einen Quanten-Annealer von D-Wave. Die QPU des D-Wave beherbergt Qubits und Couplers – gewichtete Verbindungen zwischen einzelnen Qubits – angeordnet im sogenannten Chimera-Graphen. Die Chimera-Struktur ist ein rechtwinklig verknüpftes Gitter aus bipartiten Graphen, das als Hardwareverbindungsstruktur in Quantum-Annealing-Systemen verwendet wird. Die Wahl einer passenden Graphenstruktur hängt maßgeblich von der Anzahl der physikalisch sinnvoll umsetzbaren Verbindungen ab. Bei magnetischen Qubits etwa ist Interferenz ein Problem, die durch die bei der Kommunikation zwischen einzelnen Qubits entstehenden Magnetfelder verursacht wird.

Der Kern eines D-Wave-Quantenrechners sitzt auf einem Chip. Dieser beherbergt derzeit 2000 Qubits, realisiert als SQUIDs (Abb. 3). *Quelle: D-Wave Systems*

Im aktuellen System sind das etwas über 2000 Qubits. D-Wave verwendet dafür den SQUID-Ansatz. Das Unternehmen fertigt sie aus dem supraleitenden Metall Niobium. Wegen der erforderlichen tiefen Temperatur ist die QPU in ein System aus Kryostaten eingebettet, das sie auf 0,015 K, beziehungsweise -273,135 °C, abkühlt. Jedes Qubit wird über einen Niobium-Ring abgebildet und ist in der aktuellen Architektur mit sechs weiteren Qubits via Couplers verbunden.

Nativ geschieht die Verarbeitung beim D-Wave über ein Ising-Modell, das der statistischen Physik entstammt und Ferromagnetismus abbilden kann. Jeder Gitterpunkt repräsentiert einen magnetischen Moment: +1 oder -1. Die Gesamtenergie besteht aus Beiträgen auf den einzelnen Gitterpunkten und Wechselwirkung zwischen den magnetischen Momenten. Verwandt ist die Quadratic Unconstrained Binary Optimization (QUBO) zur Minimierung quadratischer Polynome über binäre Variablen. Sie lässt sich einfach in einen Hamilton-Operator für das Ising-Modell übersetzen. Für beide Ansätze ist nicht klar, ob klassische Computer sie in endlicher Zeit lösen können. Es handelt sich um sogenannte NP-schwere Probleme. Sie lassen sich leicht ineinander überführen.

Zunächst muss man eine Frage, die man mit der QPU lösen möchte, als QUBO formulieren. Im zweiten Schritt folgt die Abbildung auf die Chimera-Graph-Struktur, das sogenannte Embedding. Das Problem muss sich also auf dem zweidimensionalen, dünn besetzten Chimera-Graphen darstellen lassen. Dort sind die Qubits in Achterblöcken angeordnet und jeweils mit sechs anderen Qubits direkt verbunden. Sie bilden die Knoten des Graphen. Die Verbindungen sind gewichtet.

Reicht die Verknüpfungsdichte der QPU nicht aus, weil die Aufgabe eine höhere Verknüpfung verlangt, lässt sich das über Umwege lösen. Das Zusammenziehen mehrerer Qubits über stark gekoppelte Ketten zu logischen Einheiten (Chaining) erhöht die Verknüpfungsdichte, reduziert allerdings die Anzahl der verfügbaren Qubits. Die durch Chaining gekoppelten Qubits stehen für die weitere Adressierung in derselben Berechnung nicht mehr bereit.