Was können wir von Quantencomputern in den kommenden Jahren erwarten?

Die Andersartigkeit der neuen Rechenwege

Bevor wir uns die ersten praktischen Anwendungsgebiete für Quantencomputer anschauen, sollten wir uns eine generelle Frage stellen.

Ich hatte schon mehrfach betont, dass Quantencomputer in ihrer Andersartigkeit ganz neue Rechenwege ermöglichen werden. Die Frage ist jetzt: Kann man dies präzisieren?

Die Antwort ist: In der theoretischen Informatik beginnt man damit genau dies zu tun.

Vor einem halbem Jahrhundert begannen Computerwissenschaflter damit, Probleme in Klassen zu unterteilen, je nachdem wie schwierig es ist eine Lösung zu finden. Probleme, die herkömmliche Computer mit verhältnismäßig wenig Rechenaufwand lösen können werden beispielsweise $ P $-Probleme genannt. Daneben gibt es Probleme, die nur mit sehr viel Rechenaufwand gelöst werden können, deren Lösungen aber mit wenig Rechenaufwand überprüft werden können. Diese Probleme werden $ NP $-Probleme genannt. Ein Beispiel hierfür ist die Zerlegung in Primfaktoren: Wenn man einmal die gesuchten Primfaktoren $ p $ und $ q $ einer Zahl $ n $ gefunden hat, ist die Überprüfung der Lösung kinderleicht, nämlich gerade $ p*q = n $. Die $ PSPACE $ -Probleme wiederum sind solche Probleme, deren Lösungweg man noch in einem herkömmlichen Computer programmieren kann, eventuell endet das Programm aber nie!

 

 

 

 

(Quelle: https://en.wikipedia.org/wiki/File:BQP_complexity_class_diagram.svg)

Sie können sich vorstellen, dass diese Themen ungemein tiefgreifend sind. Sie präzisieren, was wir uns unter „Berechenbarkeit“ und „Komplexität“ vorstellen müssen.

In diese Thematik passt unsere Frage über die Andersartigkeit der Quantencomputer ideal hinein:

Deshalb haben Wissenschaftler für Quantencomputer vor 30 Jahren eine neue Klasse eingeführt: $ BQP $ sind die Probleme, die ein Quantencomputer mit verhältnismäßig wenig Rechenaufwand lösen kann. Das Diagramm oben zeigt die Zusammenhänge zwischen den Problemklassen $ P $, $ NP $ und $ BQP $, die die meisten Wissenschaftler vermuten ⁱ. Sie können also erkennen, dass Quantencomputer wahrscheinlich viel mehr Probleme effizient lösen können als herkömmliche Computer, insbesondere einige der „Mega-Probleme“ in PSPACE. Sie erkennen aber auch, dass selbst Quantencomputer vermutlich ihre Grenzen haben werden.

Eine wichtige Tatsache wird in diesem Diagramm allerdings nicht deutlich: Probleme die ein Quantencomputer nur mit viel Aufwand lösen kann, die also nicht in BQP liegen, sind auf herkömmlichen Computern noch wesentlich aufwendiger zu lösen. D.h. selbst bei den schwierigen NP-Problemen haben die Quantencomputer einen Geschwindigkeitsvorteil. Den Quanten-Algorithmus hierfür nennt man „Grover-Algorithmus“. Ihn werde in einem eigenen Beitrag im Detail vorstellen. Dann kommen wir auch wieder auf das Diagramm oben zu sprechen.

So, genug der Theorie. Kommen wir zu konkreten Problemen und konkreten Quantenprogrammen.

Ein goldenes Zeitalter für Quantencomputer

Glaubt man Seth Lloyd vom Massachusetts Institute of Technology / MIT, erlebt die Quantencomputer-Szene gerade so etwas wie ein goldenes Zeitalter. Seth Lloyd bezeichnet sich selbst als „Quantum Mechanic“, ist einer der Gründerväter der Szene und seit über 25 Jahren ein führender Theoretiker in dem Bereich. Nebenbei sind seine Vorlesungen und Vorträge einfach ziemlich witzig. So gibt er gerne die Legende zum besten, dass der Finanzcrash von 2009 durch die verkopften Transaktions-Algorithmen von einem Haufen arbeitsloser Physiker für Superstring-Theorie verursacht wurde. Augenzwinkernd fügt er dann hinzu, dass die Quanten-Informationstheoretiker dadurch angespornt sind die Sache mit der Weltwirtschaft jetzt zu Ende zu bringen. Mit noch fieseren Algorithmen ⁱⁱ.

Lloyd erzählt, dass die Forschung an Quantencomputern gerade mal mit einer handvoll Wissenschaftlern begann. Heute sind es Zehntausende, die die Entwicklung in dem Bereich regelrecht beflügeln. Im Jahr 1985 wurde das erste Quantenprogramm von David Deutsch vorgestellt, das für eine spezielle Aufgabe weniger Rechenschritte benötigte, als ein herkömmlicher Computer. In den Jahrzehnten seitdem wurde eine Vielzahl an faszinierenden Quantenalgorithmen entwickelt, die die herkömmlichen Programme für dieselbe Aufgabe meilenweit hinter sich lassen und exponentielle Rechenbeschleunigungen erzielen können.

Was bislang fehlte war die zugehörige Hardware.

Diese ist langsam verfügbar. Die Tech-Riesen arbeiten an Cloud-Angeboten für ihre Quantencomputer. Zahlreiche Startup-Firmen entwickeln Quantencomputern mit Dutzenden von Qubits. An öffentlichen Einrichtungen wird die Forschung an größeren und verlässlicheren Quantencomputern ebenfalls weiter vorangetrieben.

Lloyd vergleicht die aktuelle Entwicklung mit der Gründerzeit der ersten Digitalcomputer. Das Konzept für die herkömmlichen Digitalcomputer wurde in den 1930er Jahren von Claude Shannon in seiner Masterarbeit, ebenfalls am MIT, vorgestellt. Die Arbeit von Shannon wurde später als die „einflussreichste Masterarbeit des 20. Jahrhunderts“ bezeichnet. Das Hauptwerk von Shannon sollte später allerdings die moderne Informationstheorie werden, die er im Alleingang entwickelte und die auch die Vorlage für die Quanten-Informationstheorie wurde. Claude Shannon war ohne Zweifel einer der prägendsten Wissenschaftlern des 20. Jahrhunderts. Konrad Zuse entwickelte während des 2. Weltkriegs erste Prototypen. Bis in die 1950er Jahre waren mehrere erste Computermodelle verfügbar. Diese waren sehr limitiert, riesengroß und fehleranfällig, Aber allein diese Verfügbarkeit legte den Grundstein für die Entwicklung einer Vielzahl von grundlegenden Algorithmen, die auch heute noch verwendet werden. Die Informatikgeschichte ist voll von Beispielen über Algorithmen, die praktisch sehr erfolgreich waren (oder noch erfolgreich sind), ohne dass man zunächst den Grund für den Erfolg theoretisch begründen konnte. Das „Simplex-Verfahren“ ist so ein Beispiel. Und sehr aktuell gilt dies auch für die „Deep-Learning Netze“, die das Herzstück der künstlichen Intelligenz bei Google, Amazon, den autonomen Autos & Co bilden.

Die Situation mit den ersten Quantencomputern ist heute sehr ähnlich. Sie sind aufwendig im Betrieb, besitzen nur wenige Dutzend Qubits und sind besonders noch sehr fehleranfällig. Aktuell sind alle Quantencomputer den herkömmlichen Computern in ihrer Rechengeschwindigkeit weit unterlegen. Überhaupt werden die herkömmlichen Computer selbst in der Quantencomputer-Ära weiterhin für die normale Rechenarbeit benötigt. Quantencomputer werden vermutlich nur für besonders rechenintensive Probleme eingesetzt werden, deren Lösungen aber besonders wertvoll sein werden. Viele interessante Quanten-Algorithmen dafür können allerdings nur unzureichend auf der aktuellen Hardware umgesetzt werden ⁱⁱⁱ. Dieses Bild ändert sich aber laufend:

Im Laufe dieses Jahres werden wohl die ersten Quantencomputer verfügbar sein, die die Grenze von 50 Qubits, der Grenze der Quanten-Überlegenheit, durchbrechen werden. Und in der nächste Phase der Entwicklung werden Quantencomputer konstruiert werden, die 50 Qubits bis zu wenigen hundert Qubits leistungsstark sind. Diese werden noch nicht in der Lage sein umfangreiche Quantenprogramme auszuführen, da mit dieser Anzahl von Qubits noch keine Quanten-Fehlerkorrekturen möglich sind. Aber wenn die Fehleranfälligkeit der einzelnen Rechenschritte in heutigen Größenordnungen bleibt, dürften die Quantenprogramme bis zu mehrere hundert Rechenschritte mit tolerierbaren Fehlerraten durchführen können. Und mit solchen Quantencomputern sollten wir in der Lage sein bereits außergewöhnliche Dinge berechnen zu können.

Erste Anwendungsgebiete zeichnen sich ab

Den Shor-Algorithmus werden wir sicherlich noch eine längere Zeit nicht für Zahlen von interessanter Größe ausführen können, da hierfür die Quanten-Fehlerkorrektur und eher viele tausend Qubits und Millionen von Quantengattern notwendig wären. Es gibt aber andere leistungsstarke Quantenalgorithmen, die bereits in der Generation von Quantencomputern mit bis zu wenigen hundert Qubits einsatzfähig sind.

Folgende zentrale Einsatzfelder und Business Cases zeichnen sich für die Quantencomputern der nächsten Jahren ab: ^{iv v vi}

 

• Grundlagenforschung in der Physik
• Materialforschung- und -entwicklung
• Chemische Forschung, Quantenchemie
  • Pharmazeutische Forschung
• Bigdata (z.B. Google, Amazon, Netflix)
• Künstliche Intelligenz und Maschinenlernen
• Finanzwirtschaft
• Logistik
• Assistentensysteme (z.B. Kranheitsdiagnose)
• Simulationen von Quantensystemen
• Energieeinsparung
• IT-Beratung zur Quantencomputer-Technologie für Kunden

In den nächsten Abschnitten werden Sie mehr über die Quanten-Algorithmen zu diesen Einsatzfeldern erfahren.

Optimierungsaufgaben: Quantum Variational Eigensolver

Materialforschung, chemische Forschung, Logistik, Finanzwirtschaft, IT-Beratung

Für die kommende Generation der Quantencomputer, der Quanten-Überlegenheit-Computer, zeichnet sich ein Lösungsverfahren für Optimierungsaufgaben ab, dass teilweise Quantencomputer und teilweise herkömmliche Computer verwendet. Das Verfahren hat den Vorteil, dass die praktischen Einschränkungen der jungen Quantencomputer ausdrücklich berücksichtigt werden. Unter anderem scheint es immun gegenüber Rechenfehlern der Quantencomputern zu sein.

Das Verfahren kann auch zur Simulation von Quantensystemen in der Chemie und Materialforschung verwendet werden und ist dort unter dem Namen „Quantum Variational Eigensolver (QVE)“ bekannt ^vii.

Jarrod McClean, einer der Entwickler des Quantum Variational Eigensolver – Algorithmus, zitiert hierfür z.B. folgendes interessante Anwendungsbeispiel ^viii: Im Jahr 1913 wurde das Haber-Bosch-Verfahren zur Synthetisierung von Ammoniak zum ersten Mal großindustriell eingeführt. Seitdem ist es das weltweit dominierende Verfahren für die Herstellung von Düngemitteln. Es benötigt allerdings eine Hitze von 400° Celsius und einen Druck von 200 Bar. Etwa 1-2% des weltweiten Energiebedarfs wird jährlich nur in das Haber-Bosch-Verfahren gesteckt.

Pflanzen und Pilze hingegen synthetisieren Ammoniak bei 20° Celsius und einem Druck von 1 Bar, dem Atmosphärendruck. Forscher konnten die zentralen Reaktionen hierfür zwar lokalisieren allerdings nicht detailliert verstehen. Die notwendigen Quantensimulationen sind schlichtweg zu komplex, als das sie von einem herkömmlichen Supercomputer berechnet werden könnten.

Quantencomputer wären dazu allerdings in der Lage ^ix. Dafür ist McClean maßgeblich für Google an der Entwicklung des OpenSource-Frameworks „OpenFermion“ beteiligt ^x. Ziel von OpenFermion ist es Molekül-Eigenschaften zu berechnen, in dem es ein chemisches Problem in die Welt der Quantencomputer übersetzt. Der Anwender braucht im Prinzip also keine Kenntnisse in der Quantenprogrammierung.

IT-Beratung für Quantencomputer

McClean ist übrigens mittlerweile angestellt beim Google Quantum AI Lab. Es zeigt sich das Tech-Riesen wie Google und Microsoft gezielt auch die theoretischen Wissenschaftler aus der öffentlichen Forschung anheuern, die sich durch Anwendungsmöglichkeiten der nächsten Quantencomputer-Generation hervorgetan haben. Dies kann zum einen mit dem Nachweis der Quanten-Überlegenheit zusammenhängen: Um sie nachzuweisen benötigt man sowohl die Quantencomputer-Hardware als auch einen geeigneten Quanten-Algorithmus.

Zum anderen bauen die Konzerne damit auch spezialisierte und hochkarätige Knowhow-Einheiten auf, die in Zukunft als Schnittstelle zwischen Kunden und der neuen Technologie dienen können. Erste Beispiele solcher Kooperationen gibt es bereits ^xi.

Diesen Business Case im Umfeld der der nächsten Quantencomputer erwähnt das Google Quantum AI Lab übrigens selbst ausdrücklich. ^xii

Lineare Algebra: QRAM, Matrix Inversion, Quantum principal component analysis

Materialforschung, chemische Forschung, Logistik, Finanzwirtschaft, Maschinenlernen, Bigdata

Der Shor-Algorithmus ist das bekannteste und ein leicht verständliches Beispiel, wie ein Quantenprogramm unsere Gesellschaft verändern kann. Der wirtschaftliche Nutzen für Unternehmen durch den Shor-Algorithmus sähe allerdings wahrscheinlich eher bescheiden aus.

Ganz anders ist das im Falle der „Linearen Algebra“. Sie ist vielleicht das Grundwerkzeug der Mathematik. So unglaublich viele Probleme und Aufgaben in der Forschung, Wirtschaft und Industrie lassen sich mit ihrer Hilfe lösen. Die Quantenmechanik selbst ist zum Beispiel ein riesiges Lineare-Algebra-Problem.

Seth Lloyd und andere haben mittlerweile Quantenalgorithmen für die Lineare Algebra entwickelt, die ein gigantisches Verbesserungspotential gegenüber herkömmlichen Methoden besitzen (QRAM ^xiii, Matrix Inversion ^xiv).

Sie könnten vielleicht zu dem „Killer-Feature“ der Quantencomputer werden.

Ein Beispiel hierzu: Netflix verwendet für die Film-Empfehlungen an seine Kunden einen Algorithmus der auf der sogenannten „Principal Component Analysis“ der künstlichen Intelligenz basiert. Diese erweitert des Prinzips des „Starren Körpers“ aus der klassischen Mechanik auf beliebige Datenstrukturen. In der Mechanik betrachtet man einen festen Körpern von beliebiger Form als Ansammlung von sehr, sehr vielen einzelnen Massepunkten. Das Prinzip des „Starren Körpers“ besagt, dass dieser Körper in Summe dann immer drei feste Drehachsen besitzt. Dreht sich der Körper um eine dieser Achsen, gibt es keine Umwucht und die Drehung sieht wie beim Kreisel immer gleichmäßig aus. Der Ort jedes einzelnen Massepunktes lässt sich dann durch seine Drehachsen-Anteile beschreiben. Die Drehachsen selbst lassen sich mithilfe der Linearen Algebra aus der Statistik aller Punkte berechnen.

Die Principal Component Analysis übersetzt dieses Prinzip in die Datenstrukturen des Big Datas. Aus den Nutzungsdaten aller Netflixkunden kann eine Art Starrer Körper berechnet werden. Dieser Datenkörper ist nun nicht mehr dreidimensional, sondern lebt in einem hochdimensionalen Datenraum. Der starre Datenkörper besitzt auch feste „Drehachsen“, den „Components“. Das Nutzungsverhalten eines einzelnen Kunden lässt sich wiederum vollständig durch die Components beschreiben. Die Components, die den größten Anteil am Nutzungsverhalten eines einzelnen Kunden haben, sind dann die „Principal Components“ des Kunden. Dieser erhält dann die entsprechenden Empfehlungen (z.B. „Komödien aus den 1990er Jahren“).

Die Berechnungen müssen riesige Datenmengen in einem hochdimensionalen Datenraum bewältigen. Netflix braucht dafür einen vollen Tag.

Die Principal Component Analysis könnte durch einen Quantencomputer exponentiell beschleunigt werden.

Es könnte sein, dass die neuen Algorithmen von Seth Lloyd und anderen noch zu anspruchsvoll für die kommende Generation von Quantencomputern sind. Aber wie John Preskill in seiner Keynote für die Konferenz „Quantum to Business“ im Dezember 2017 erklärte: „Wir werden es ausprobieren und herausfinden“. Mit den kommenden Quantencomputern werden wir die ersten ernsthaften Gehversuche mit den Quantenalgorithmen machen. Unsere Erfahrungen mit den herkömmlichen Digitalcomputern haben gezeigt: Es ist wahrscheinlich, dass wir ganz neue Wege finden werden, die theoretisch jetzt noch nicht absehbar sind.

Fußnoten