Quantencomputing verspricht eine Erweiterung der bisherigen klassischen Recheneffizienz mit enormem Potenzial. Theoretisch wurde gezeigt, dass Quantencomputer bestimmte Probleme der Informatik, wie das Suchen in großen Datenbanken (Grover-Algorithmus) oder die Primfaktorzerlegung (Shor-Algorithmus), effizienter lösen als klassische Computer. Diese Verfahren erfordern einen sogenannten Gatter-basierten Quantencomputer (mehr Informationen zur Quantenhardware finden Sie im Blogbeitrag „Quantencomputer: Neue Potenziale für Maschinelles Lernen“). Auch kombinatorische Optimierungsprobleme in Form von „Quadratic Unconstrained Binary Optimization“ (QUBO) Problemen lassen sich mithilfe von quantenmechanischen Prinzipien lösen. Computer, welche sich diese Prinzipien zunutze machen, heißen Quantenannealer oder adiabatische Quantencomputer. Für das Lösen wird sich das adiabatische Theorem der Quantenmechanik zunutze gemacht – ein quantenmechanisches System, welches sich in einem Zustand minimaler Energie befindet, verbleibt bei hinreichend langsamer (adiabatischer) Veränderung in einem solchen Zustand. Die Idee besteht nun darin, ein QUBO – also das mathematische Problem, welches man eigentlich lösen möchte – in den Energie-Operator eines quantenmechanischen Systems zu kodieren. Startet man jetzt mit einem einfachen Problem mit bekannter Lösung und überführt dieses adiabatisch in das angestrebte Zielproblem, so erhält man ebenfalls eine Lösung des Zielproblems.
Kodierung
Wenn auch die Berechnungen mithilfe des adiabatischen Prinzips relativ neu sind, ist die Kodierung von Daten und Problemen seit jeher ein fester Bestandteil der Informatik. Bilder, Songs, oder Videos werden als binäre Daten kodiert. Tatsächlich ist die Kodierung eines QUBOs als Hamilton-Operator wesentlich einfacher als die Kodierung eines Songs als MP3 Datei.
Funktionsweise des Quantenannealing. (Links) In der Quantenwelt ist es möglich durch Energiebarrieren hindurch zu „tunneln“, wohingegen die Barriere in der klassischen Physik überwunden werden muss. (Rechts) Durch adiabatische Evolution des Systems bleibt ein Zustand minimaler Energie erhalten.
QUBOs treten in vielen verschiedenen Branchen auf, beispielsweise in:
- Routenberechnungen in der Logistik,
- Portfolioanalysen in der Finanzwirtschaft,
- Virtual Screening in der Herstellung neuer Medikamente in der Pharmaforschung.
Auch im Maschinellen Lernen ist diese Art von Optimierungsproblemen anzutreffen, unter anderem in Clusteringproblemen, Hopfield Netzwerken oder probabilistischen graphischen Modellen. Für mehr Details über Optimierung im Maschinellen Lernen sei hier auf unseren Beitrag „Optimierung im Maschinellen Lernen“ verwiesen.
Obwohl diese theoretischen Ergebnisse äußerst vielversprechend sind, ist aktuelle Quantenhardware noch nicht in dem Stadium, die oben genannten Quantenalgorithmen verlässlich ausführen zu können. State-of-the-art Quantencomputer basieren auf supraleitenden Implementierungen, welche auf Temperaturen von wenigen milli Kelvin heruntergekühlt werden müssen. Diese sind sehr fehleranfällig durch äußere Einflüsse, beispielsweise das Magnetfeld der Erde, weswegen keine beliebig komplexen Algorithmen ausgeführt werden können, im Gegensatz zu einem klassischen Computer. Durch die Kühlung und die Abschirmung ist es somit sehr energieaufwändig solch einen Quantencomputer zu betreiben. Das hat Forschende am Fraunhofer IAIS und am Lamarr-Institut dazu bewegt, den IAIS Evo Annealer zu entwickeln, um schon jetzt für ein zukünftiges fehlertolerantes Quantenzeitalter bereit zu sein.
IAIS Evo Annealer: Hardwaredesign und Eigenschaften
Eine globale Lösung für ein QUBO Problem zu finden ist NP-schwer – es ist kein klassischer Algorithmus bekannt, der jedes QUBO in polynomieller Zeit lösen kann. Dies gilt auch für Quantenannealer – hier kann die Annealing-Zeit, also die Dauer des adiabatischen Prozesses, exponentiell sein. Allerdings sind die QUBOs, die für klassische Rechner schwer sind, nicht unbedingt die gleichen, die für Quantenannealer schwer sind. Daher kann ein Quantenannealer ein schweres QUBO möglicherweise wesentlich schneller lösen als ein klassischer Computer. Daneben gibt es auch effiziente klassische Verfahren, um QUBO Probleme anzugehen. Diese sind jedoch heuristisch und es ist nicht garantiert, dass eine global-optimale Lösung gefunden werden kann. Prominente Beispiele für solche Verfahren sind Simulated Annealing, Tabu Suche und Evolutionäre Algorithmen (EA). EA sind von der Evolution natürlicher Lebewesen inspiriert, dahingehend, dass Mutationen und Rekombinationen auf eine Menge von bisherigen Individuen (bei uns: Lösungen für QUBO Probleme) angewandt werden, um neue (bessere) Lösungen zu erhalten (mehr Informationen hierzu, finden Sie im Blogbeitrag zu „Evolutionäre Optimierung von Quantenschaltkreisen“).
Üblicherweise sind solche Algorithmen in einer Hochsprache implementiert, sodass sie auf einer herkömmlichen CPU ausgeführt werden können. Die Abstraktionsebenen einer solchen Hochsprache führen zu einer hohen Zahl an CPU-Operationen – ein Overhead, der auf einem Quantenannealer nicht existiert. Die Grundidee hinter dem IAIS Evo Annealer ist nun eine „Hardware-Implementierung“ eines EA für QUBO Probleme. Somit emuliert der IAIS Evo Annealer das Verhalten eines Quantenannealers, da der CPU-Overhead umgangen wird. Darüber hinaus wurden einige Komponenten des EA angepasst, um einen Tunneleffekt zu emulieren. Für die Hardware-Implementierung wird ein Field Programmable Gate Array (FPGA) verwendet, welches die Realisierung eigener Chipdesigns erlaubt, ohne die Notwendigkeit einen Chip tatsächlich produzieren zu müssen (mehr Informationen zu FPGAs finden Sie im Blogbeitrag „Wenn Mikrochips Lernen lernen“).
FPGAs
FPGAs werden beispielsweise auch in professioneller Netzwerk-Hardware eingesetzt, um die Funktionalität des Chips zu einem späteren Zeitpunkt ändern zu können, zum Beispiel um eine Sicherheitslücke zu schließen oder um den Funktionsumfang zu erweitern.
Das aktuelle Design des Evo Annealers erlaubt die Bewertung von über 16.000.000 Lösungen pro Sekunde, wobei die Leistungsaufnahme je nach Hardware zwischen 5 und 10 Watt beträgt. Zum Vergleich: Eine gewöhnliche Workstation mit einer GPU verbraucht zwischen 500 und 1000 Watt. Auch wenn hier der Unterschied bereits Faktor 100 beträgt, ist der Abstand zu einem echten Quantenannealer noch wesentlich größer: Geräte der kanadischen Firma D-Wave beispielsweise benötigen ungefähr 16.000 Watt. Die meiste Leistung wird dabei für das Kühlen und das magnetische Abschirmen des Quantenchips benutzt. Aktuell ist der IAIS Evo Annealer in der Lage QUBO Probleme der Größe 2048 zu lösen. Das D-Wave Advantage System ist ausgestattet mit 5600 Qubits, kann hardwarebedingt jedoch nur sehr spezielle QUBOs dieser Größe lösen. Die zugrundeliegende Qubit-Topologie ist kein vollständig zusammenhängender Graph, das heißt nicht jedes Qubit ist direkt mit jedem anderen verbunden. Daher ist die Größe von QUBOs im Allgemeinen auf 180 beschränkt. Der größte verfügbare Gatter-basierte Quantenprozessor von IBM ist mit 127 Qubits ausgestattet, mit welchem sich QUBOs eben dieser Größe lösen lassen.
Aufgrund der überlegenen Problemgröße und des geringen Energieverbrauchs des Evo Annealers, ist dieser sowohl als Brückentechnologie für das Quantencomputing als auch als eigenständiger Hardwarebeschleuniger für QUBOs einsetzbar.
Quantum Readiness
Trotz der beeindruckenden Eigenschaften des Evo Annealers muss klar sein, dass dieser lediglich einen echten Quantenannealer emuliert. Es werden keine quantenmechanischen Effekte ausgenutzt und somit ist auch nicht das volle Potenzial des Quantencomputings nutzbar. Jedoch ist der IAIS Evo Annealer extrem energieeffizient, was eine immer wichtiger werdende Eigenschaft von Hardware darstellt. Darüber hinaus, bereitet er jetzt schon auf das Zeitalter der fehlertoleranten und leistungsstarken Quantencomputer vor, indem bereits formulierte QUBO Probleme auch auf zukünftigen echten Quantenannealern lösbar sind.
Am Fraunhofer IAIS, einem der vier Partner des Lamarr-Instituts, wird diese „Quantum Readiness“ bereits für Use-Cases aus der Wirtschaft eingesetzt. Mit dem IAIS Evo Annealer lässt sich vorab überprüfen, inwiefern sich von Quantencomputing für ein bestimmtes Problem profitieren lässt, ohne auf echte Quantenhardware zurückgreifen zu müssen.
Weitere Informationen zum IAIS Evo Annealer:
https://www.iais.fraunhofer.de/de/geschaeftsfelder/cognitive-business-optimization/quantum-readiness.html
