Quantencomputer machen sich auf, die Welt zu verändern! Ihre Funktionsweise birgt großes Potential, ist aber bisweilen nicht sehr intuitiv. Doch anhand anschaulicher Beispiel lässt sich auch für die Welt des Quantum Computing ein Gespür entwickeln. Dieses wird zur Notwendigkeit, wenn die Disruption durch den Einsatz von Quantencomputern beginnt.

1. Motivation

Digitale Geschäftsmodelle hängen oft an speziellem Wissen über das eigene Produkt. Durch globale Verfügbarkeit über das Internet treten digitale Unternehmen meist in Konkurrenz mit Unternehmen aus aller Welt. Und viele Mitbewerber können eine Auswahl an Musik-Streams anbieten, oder eine Navigation durch die Rush Hour, oder sogar eine Cloud-Lösung für Berechnungen in einer Smart Factory.

Die Differenzierung auf dem Markt der Zukunft erfolgt über die spezielle Auslegung und aktuelle Anpassung auf den Kunden: Welche Musik will meine Kundin jetzt am liebsten hören? Welche Route führt am schnellsten durch die Staus? Oder wie arbeiten die Produktionsmaschinen am effizientesten zusammen?

Der Mathematiker nennt diese Fragen Optimierungsprobleme. Und die Welt ist voll davon. Wenn LKWs beladen werden, wenn Flugzeuge auf Gates verteilt werden, oder wenn moderne Verkehrsführung geplant wird: Jedes Mal versuchen wir, ein Optimierungsproblem zu lösen.

Der Informatiker beschäftigt sich dann mit den Algorithmen, die das möglichst gut und möglichst schnell schaffen. Doch die Theorie sagt uns: Für viele hoch relevante Probleme besteht wenig Hoffnung mit allen bekannten Methoden. Diese Probleme haben von sich aus eine zu hohe Komplexität. Klassische Computer können hier zwar meist eine passable Lösung approximieren, aber auch das kostet oft viel Rechenleistung und ist oft schwer parallelisierbar. Spezielle Hardware (wie Digital Annealer) kann momentan zu einem Geschwindigkeitsschub führen, leidet jedoch aus Prinzip an denselben Schwächen wie der Standardrechner aus dem nächsten Rechenzentrum.

2. Quantum Speedup

Darum liegt die Hoffnung hier auf einer neuartigen Herangehensweise: Quantencomputer nutzen fundamental andere Methoden zur Berechnung von Ergebnissen, indem sie Phänomene der Quantenmechanik ausnutzen, die für unsere Intuition zunächst seltsam wirken können. (Keine Sorge, den ersten Quantenphysikern ging es genauso!) Durch die Nutzung dieser Effekte verspricht man sich für viele Anwendungsfälle eine deutliche Steigerung der effektiven Rechenleistung, einen sogenannten Quantum Speedup.

Doch wie funktioniert dies? Der erste wichtige Effekt in der Quantenwelt ist die Superposition. Während ein klassisches Bit nur einen der beiden Zustände 0 oder 1 annehmen kann, kann ein Qubit (kurz für quantum bit) beide Zustände 0 und 1 gleichzeitig annehmen – zumindest so lange niemand zu genau nachsieht. Man könnte sagen das Universum reagiert bei Quanten erst auf Nachfrage. Fragt man jedoch nicht nach, bleiben beide Optionen eine Möglichkeit und es kann auf beiden Zuständen 0 und 1 gleichzeitig gerechnet werden. Man spart sich so natürlich, einmal die Option 0 und dann nochmal die Option 1 nacheinander durchzugehen. Populär geworden ist dieser Effekt durch die Metapher von Schrödingers Katze. Wichtig ist hier, wie die Superposition aufgelöst wird: Sobald wir nachmessen, also beim Universum nachfragen, ob unser Qubit nun 0 oder 1 ist, entscheidet sich das Universum für eine dieser Varianten und bleibt dabei. Wir können nicht mehr rekonstruieren, wie der Zustand vor dem Messen ausgesehen hat.

Der zweite wichtige Effekt nennt sich Verschränkung und basiert auf der Superposition. Wir starten also mit zwei Qubits, deren genauen Zustand wir noch nicht nachgemessen haben. Wir können dennoch auf ihnen rechnen: Dabei verschieben wir die Wahrscheinlichkeit, dass sich das Qubit im Zustand 0 oder 1 befindet, in eine Richtung. Ein Beispiel: Wir wollen die kürzeste Fahr-Route zur gegenüberliegenden Seite des Häuserblocks vor uns berechnen. Dazu können wir zuerst links und dann rechts abbiegen, oder eben zuerst rechts und dann links. Beides sind valide Lösung dieses Optimierungsproblems. Aber rechts und dann rechts Fahren würde uns völlig in die falsche Richtung schicken. Wenn wir nun die Lösung mit einem Quantencomputer berechnen, könnten wir (bevor wir messen) eine Superposition der beiden Lösungen als Ergebnis bekommen. Zum Speichern nutzen wir zwei Qubits und so könnte „01“ für „links, dann rechts“ und „10“ für die Lösung „rechts, dann links“ stehen. Wenn wir nun zunächst nur das erste Qubit messen, könnte uns das Universum sowohl eine 0 als auch eine 1 nennen, da beide Möglichkeiten eine Lösung darstellen. Sobald wir das erste Qubit aber gemessen haben, wüssten wir sofort, dass das zweite Qubit das genaue Gegenteil ist. Tatsächlich befindet sich dann nach der Messung des ersten Qubits auch das zweite Qubit nicht mehr in einer Superposition. Man könnte sagen, das Universum merkt sich die Abhängigkeiten zwischen den Qubits, auch wenn wir deren Werte noch gar nicht nachgefragt haben. Diesen Zustand der Abhängigkeit nennt man dann Verschränkung. Und er bleibt unabhängig von räumlicher Nähe oder Distanz erhalten. Einstein nannte den Effekt deshalb zweifelnd „spukhafte Fernwirkung“.

3. Quantum Annealing

Als Beispiel für die grundlegenden Quanteneffekte haben wir nun schon ein kleines Optimierungsproblem besprochen, nämlich das Finden einer Fahr-Route. Tatsächlich sind Quantenmaschinen für solche Aufgaben besonders geeignet. Eine spezielle Technik namens Quantum Annealing ist sogar nur auf die Lösung von Optimierungsproblemen spezialisiert.

Stellen wir uns hierfür den Bau eines Einfamilienhauses vor. Wir haben ein bestimmtes Budget, das wir ausgeben können. Nun gibt es eine große Anzahl an Entscheidungen, die wir treffen können: Wie viele Zimmer soll es geben? Wird ein Kamin benötigt oder nicht? Wie soll die Ausstattung der Küche aussehen? Und sollen die Rollläden händisch zu bedienen sein oder automatisch oder vielleicht gar nicht existieren? Für jede dieser Fragestellungen gibt es zahlreiche mögliche Entscheidungen und einige getroffene Entscheidungen bedingen auch weitere Fragen. Nun wird unter den scheinbar unendlich vielen Möglichkeiten diejenige Konstellation gesucht, die uns am besten gefällt. Diese Konstellation nennen wir die optimale Lösung bezogen auf die gegebene Fragestellung. Die optimale Lösung und alle weiteren Lösungen können wir uns als einen Ort innerhalb einer hügeligen Landschaft vorstellen. Je tiefer dieser Ort liegt, desto besser die Lösung. Im Gegensatz zu Tälern repräsentieren Orte auf Bergen schlechte Lösungen.  Die Frage ist nun, wie wir das tiefste Tal in dieser durchaus riesengroßen Landschaft finden. Denn wenn man sich durch das Gelände bewegt und in einem Tal umringt von Bergen steht, dann kann man schwer erkennen, dass man sich im tiefsten Tal befindet.

Quantum Annealing ist nun eine Technik, mit der genau dieses Problem angegangen werden kann. Wir versuchen die optimale Lösung zu finden und verwenden dabei einen weiteren Quanteneffekt, nämlich das Tunneling. Wie bereits beschrieben kann es beim Durchwandern der Landschaft passieren, dass man in einem Tal landet, das allerdings nicht das tiefste Tal ist. Wir haben eine gute Lösung gefunden, aber eben nicht die beste Lösung. Nun muss der Algorithmus schaffen, dass wir aus dem Tal herausklettern, um weiter die Ortschaft zu erkunden. Das Entkommen des Tals kann durchaus mit viel Kraftaufwand verbunden sein, so dass es in der Tat so ist, dass viele Algorithmen in diesem sogenannten lokalen Minimum stecken bleiben. Quantum Annealing ist nun mittels des Tunnelings in der Lage, Berge zu überwinden, nicht indem geklettert wird, sondern indem ein Tunnel gegraben wird.  Für ein Quantum ist dieser Tunnel viel einfacher zu nehmen, als über die Spitze des Berges zu wandern. Auf der anderen Seite kann die Suche nach einem besseren Tal fortgesetzt werden.

Nach dieser sehr bildlichen Erklärung der Funktionsweise eines Quantum Annealers stellt sich natürlich die Frage, wie wir ein Optimierungsproblem auf eine solche Maschine transportiert bekommen. Dazu muss das Problem in eine bestimmte Form gebracht werden, der sogenannten Quadratic Unconstrained Binary Optimization, kurz QUBO. Diese Formulierung, oder besser Denkweise, wollen wir auch anhand eines konkreten Beispiels erklären:

Angenommen wir sind der Betreiber eines Flughafens und möchten die ankommenden Flugzeuge am besten auf die Gates verteilen. Und nehmen wir an, unser Flughafen hat nur zwei Gates (A und B) und wird auch nur von zwei Flugzeugen angeflogen (1 und 2). Dies ist natürlich ein viel zu kleines Beispiel, soll aber die Funktionsweise erläutern. Darüber hinaus gibt es unterschiedliche Anforderungen, nämlich: Am Liebsten soll das grüne Flugzeug 1 am grünen Gate A landen und entsprechend das blaue Flugzeug 2 am blauen Gate B. Eine weitere Anforderung ist, dass es keine Unfälle geben soll, also das Anlegen von zwei Flugzeugen an einem Gate soll verhindert werden. Nun gibt es mehrere Konstellationen, wie die Flugzeuge an die Gates gelotst werden können. Flugzeug 1 an Gate A und Flugzeug 2 an Gate B (beste Lösung), Flugzeug 1 an Gate B und Flugzeug 2 an Gate A (gute Lösung). Ferner gibt es die Möglichkeiten, dass Flugzeug 1 an Gate A und auch Flugzeug 2 an Gate A ankommt oder eben beide Flugzeuge an Gate B. Diese sollen schlechte Lösungen sein.

Nun wird eine sogenannte QUBO-Matrix ausgefüllt, in der die gegebenen Sachverhalte eingetragen werden. Der Clou ist dann, dass mittels Quantum Annealing die beste Lösung ermittelt werden kann. Das Befüllen der Matrix würde wie folgt verlaufen: Angenommen Flugzeug 1 parkt an Gate A; diesen Zustand finden wir generell super und belegen ihn mit einem niedrigen Wert wie -2 (zur Erinnerung: das Tal ist die beste Lösung). Wenn dem so ist, wenn also Flugzeug 1 an Gate A parkt, dann kann nicht gleichzeitig auch Flugzeug 1 an Gate B sein. Das ist unmöglich und wird mit einem hohen Wert wie etwa +5 bestraft. Immer noch gegeben die Annahme, dass sich Flugzeug 1 an Gate A befindet, so darf Flugzeug 2 sich nicht auch an Gate A befinden. Auch dieser Zustand wird mit einem hohen Wert wie +5 bestraft. Zuletzt ist unter der Annahme, dass Flugzeug 1 sich an Gate A befindet die Möglichkeit gegeben, dass Flugzeug 2 sich an Gate B befindet. Dieser Zustand ist generell gut und wird mit dem Wert -2 belohnt. Nun können wir annehmen, dass der Zustand eintritt, dass Flugzeug 1 an Gate B landet. Dieser Zustand ist nicht katastrophal, auch nicht super, sondern gut. Von daher wird ein niedriger Wert von -1 vergeben. Gegeben diese Annahme, dann ist es möglich, dass sich Flugzeug 2 an Gate A begibt. Ebenso ist dies in Ordnung und wird mit -1 belohnt. Wenn bei der Annahme, dass sich Flugzeug 1 an Gate B befindet, die Tatsache hinzukommt, dass Flugzeug 2 sich ebenfalls an Gate B befindet, so ist dies ein Unfall und zu vermeiden. Es wird der Wert +5 vergeben. Die dritte Zeile vertritt die Annahme, dass Flugzeug 2 an Gate A landet, was in Ordnung ist (-1). Wenn diese Annahme wahr ist, dann kann Flugzeug 2 sich nicht auch gleichzeitig an Gate B befinden (+5). Schließlich ist es möglich, dass Flugzeug 2 sich an Gate B befindet, was sehr gut ist (-2).

Eine Quantum Annealing Hardware kann nun diese Formulierung entgegen nehmen und diejenige Konstellation von Flugzeugen und Gates herausfinden, die am günstigsten ist. Ein klassischer Algorithmus müsste alle möglichen Gesamtzuordnungen durchgehen, von „kein Flugzeug landet irgendwo“ = ∅ über „beide Flugzeuge landen an Gate A“ = {1A, 1B} und mehr bis zur besten Lösung „Flugzeug 1 an Gate A und Flugzeug 2 an Gate B“ = {1A, 2B}, was relativ viel Zeit benötigt. Der Quantum Annealer ermittelt aus der Matrix sofort die Gesamtzuordnung {1A, 2B} mit dem niedrigsten kombinierten Wert in der Matrix, was gleichzeitig dem tiefsten Tal der Lösungslandschaft und somit der besten Lösung entspricht. Die Aufgabe eines Programmierers ist es nun, das Problem der realen Welt korrekt in ein QUBO zu überführen.

4. Quantum Gate Model

Neben der seit etwa 2010 kommerziell verfügbaren Quantum Annealing Hardware existiert zudem eine weitere Klasse an Quantencomputern, nämlich die, die auf dem sogenannten Quantum Gate Model basieren. Diese Quantencomputer, oft auch universelle Quantencomputer genannt, arbeiten recht ähnlich zu herkömmlichen Rechnern mit klassischer Rechnerarchitektur in dem Sinne, dass es Eingaben, Operationen und Ausgaben gibt. Bei dem zuvor beschriebenen Quantum Annealern hingegen wird lediglich ein Problem als QUBO definiert und einmalig nach der besten Lösung gesucht. Im Quantum Gate Model werden dagegen wie bei klassischen Computern Folgen von Operationen abgearbeitet, wobei die Operationen aber Quanteneffekte verwenden. Durch die Superposition kann ein Quantencomputer sehr viele Zustände oder Möglichkeiten gleichzeitig betrachten und durch die Verschränkung kann eine einzige Operation sehr viele Zustände oder Möglichkeiten gleichzeitig verarbeiten. Diese Kombination verschafft einen sehr mächtigen Vorteil, aber auch einen Nachteil: solche Maschinen sind schwer herzustellen, so dass diese eher einen Forschungsgegenstand darstellen und zunächst im Laborbetrieb verwendet werden.

5. Diskussion

Das Thema Quantum Computing ist aus vielerlei Hinsicht ein enorm spannendes Thema. Zum einen treten wir in die Fußstapfen vieler bahnbrechender Forscher aus den Bereichen Mathematik und Physik, wie etwa Max Planck, Albert Einstein, Niels Bohr und weiteren. Zum anderen erleben wir nahezu wöchentlich neueste physikalische und technische Errungenschaften, die sich um die Quanteneffekte kümmern, die schwer herzustellen und zu kontrollieren sind. Schließlich gibt es viele neuartige Algorithmen seitens der Theoretiker und Mathematiker, die komplett neuartig durchdacht sein müssen, um die speziellen Quanteneffekte auszunutzen. Und genau das bringt die Informatik ins Spiel. Die Informatiker müssen einerseits gewisse physikalische Effekte verstehen, aber gewisse andere Begebenheiten abstrahieren und gegebenenfalls ignorieren. Darüber hinaus müssen die Informatiker mit den enormen Einschränkungen zurechtkommen, die bei der Verwendung von Quantencomputern bestehen. Ein Quantum Annealer kann exakt nur Probleme in einer QUBO-Form lösen, ein Rechner im Quantum Gate Model kann derzeit nur auf eine niedrige zweistellige Anzahl an Qubits zugreifen. Die Technik befindet sich noch in den Kinderschuhen und die Verwendung der Hardware fühlt sich oft wie eine Zeitreise in die Steinzeit an. Jedoch eine Steinzeit, in der es Laserschwerter gibt.

Deshalb ist genau jetzt die richtige Zeit ist, sich mit dieser zukunftsweisenden Technologie auseinander zu setzen! Unternehmen müssen in sich gehen und genau analysieren, wo es Anwendungsfälle gibt, die sich aus schweren Optimierungsproblemen zusammensetzen. Die Mitarbeiter müssen sich auf die Verwendung von Quantencomputern vorbereiten und es muss eine Bereitschaft entwickelt werden, in dieser neuartigen Weise zu denken. Dabei ist die Vernetzung zwischen verschiedenen Firmen und Branchen ebenso wichtig wie die Zusammenarbeit von Industrie und Wissenschaft. Ein Pilotprojekt ist das Quantum Applications and Research Lab (QAR-Lab) an der LMU München. Hier bringen wir unsere Erfahrung in der Umsetzung von QUBO-Problemen mit den Domänenexperten aus Industrie und Wissenschaft zusammen, um frühzeitig Lösungen zu entwickeln, die mit der Quantenrevolution wachsen können. Das große Ziel ist sich heute schon für die Zukunft zu rüsten. Das bedeutet: Become Quantum Ready!