iX 2/2018
S. 94
Wissen
Quantum Computing
Aufmacherbild

Verkehrsflussoptimierung mit einem D-Wave Quantum Annealer

Durch Barrieren

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.

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.

Kommentare lesen (4 Beiträge)