Skip to main content
Blogbeitrag

Quo vadis Quantencomputing?

Quantencomputing verspricht nichts Geringeres als die Etablierung eines neuen Ansatzes Berechnungen durchzuführen. Dieser soll den Vorstoß in neue Anwendungsgebiete der Informatik erlauben, umgesetzt durch Computer, die auf den Gesetzen der Quantenmechanik beruhen. Zum Einsatz kommen sollen Algorithmen für dieses neue Berechnungsmodell, die mit ihrer Leistungsfähigkeit Problemstellungen adressieren, deren praktische Lösbarkeit bisher außer Reichweite lag. Wie steht es um diese Vision und wo stehen und gehen wir auf dem Weg dorthin?

Nach wegbereitenden Resultaten wie dem No-Cloning-Theorem in den 1960er und 1970er Jahren, existiert die explizite Formulierung des Konzepts eines Quantencomputers seit den 1980er Jahren. Es geht zurück auf Ideen von Paul Benioff und Richard Feynman. Sie sahen in diesen Maschinen vor allem das Potenzial, Simulationen quantenmechanischer physikalischer Systeme gegenüber „klassischen Computern“ (damit bezeichnen wir hier heutige Rechner sowie äquivalente Rechenmodelle wie Turingmaschinen) zu beschleunigen. Nach einigen eher akademischen Problemen, deren theoretische Lösung mit dem Quantencomputing-Paradigma beginnend mit dem Algorithmus von Deutsch demonstriert wurde, fand die Thematik in den 1990er Jahren mit den Arbeiten von Peter Shor und Lov Grover große Beachtung. Mit Quantenalgorithmen für das Faktorisierungsproblem und die sogenannte unstrukturierte Datenbanksuche gab es nun bereits zwei Beispiele für Verfahren, die einer Lösung mit klassischen Computern allem Anschein nach überlegen sind und einen exponentiellen bzw. polynomiellen Speed-up gegenüber etablierten Verfahren bieten. Darüber hinaus stellen sie für erstere der genannten Problemstellungen die Sicherheit der Public-Key-Infrastruktur in Frage und riefen damit sogar Geheimdienste auf den Plan. 

Seither ist der Quantenalgorithmen-Zoo (https://quantumalgorithmzoo.org/) bereits in den 2000er Jahren erheblich angewachsen und adressiert eine ganze Reihe von Problemtypen und Problemstellungen. Im Kern vieler Algorithmen stecken dabei die Ideen der beiden Pioniere in der einen oder anderen Form – etwa die Quanten-Fouriertransformation. Eine hervorragende Übersicht zu diesen nun quasi schon „klassischen“ Themen des Quantencomputings und der Quanteninformation findet man etwa im Standardwerk von Michael A. Nielsen und Isaac L. Chuang. Die meisten dieser Verfahren haben gemein, dass sie einen universellen und fehlerkorrigierten Quantencomputer benötigen, um praktisch zu skalieren bzw. zu funktionieren. 

Etwa das Jahr 2010 markiert ein Umdenken hin zu praktischeren Problemstellungen, die insbesondere in den Bereichen Optimierung und Maschinelles Lernen, aber auch bei der Simulation physikalischer Systeme zu finden sind. In diese Zeit fällt – nach ersten Implementierungen um die Jahrtausendwende – die verstärkte praktische Entwicklung von Quantenrechnern, beginnend mit Quantenannealern als Implementierungen des Adiabatischen Quantencomputing-Modells, und ab etwa 2015 zunehmend durch Implementierungen des immer stärker fokussierten Gate-Modells. 

Angewandtes Quantencomputing. Die heute oft genannten Rechner, vertreten etwa mit dem IBM Q System, der Implementierung von Rigetti oder auch dem Sycamore-Prozessor von Google, sind allesamt Vertreter dieses Rechenmodells. Im Jahr 2018 prägte John Preskill für die mit diesen Maschinen andauernde Phase den Begriff NISQ-Ära des Quantencomputings („Noisy Intermediate-Scale Quantum“). Er bezeichnet damit Quantenrechner mit 50–100 Qubits und nur begrenzten Möglichkeiten zur Fehlerkorrektur. Diese erlauben eine Ausführung beliebig tiefer Schaltkreise zwar noch nicht, können aber für bestimmte Aufgaben die Leistung klassischer Computer bereits übertreffen – wie etwa jener für die Quantensupremacy-Demonstration im Oktober 2019 eingesetzte 53-Qubit Prozessor von Google. Dennoch wurde die Informatik-Welt dadurch noch nicht tiefgreifend verändert. Eine synthetische Aufgabe konnte in 200 Sekunden mittels Sycamore-Chip gelöst werden, anstelle – je nach Lesart in 10000 Jahren (Aussage Google) oder 2,5 Tagen (Aussage IBM) – bei Ausführung auf dem zu dieser Zeit leistungsfähigsten klassischen Supercomputer Summit von IBM. Dies markiert also immerhin einen Speed-up um den Faktor 1080 bis 1,578 Mrd.

Die NISQ-Ära hat auch auf algorithmischer Seite verstärkte Anstrengungen hervorgebracht – etwa verschiedene Verfahren des überwachten Lernens und der kombinatorischen Optimierung für diese Maschinen, die Entwicklung verschiedener Frameworks zur Implementierung der Algorithmen und erste anwendungsorientierte Fachbücher zur Thematik (vgl. Maria Schuld und Francesco Petruccione zum überwachten Lernen und Jack D. Hidary zu Anwendungen des Quantencomputings).

Hybride Algorithmen für Maschinelles Lernen und Optimierung. Die heutigen Algorithmen ordnen sich dabei in das Schema der sogenannten hybriden quanten-klassischen Algorithmen bzw. variierbaren Schaltkreise ein. Hierbei wird ein nicht allzu tiefgeschichteter parametrierter Quantenschaltkreis durch einen klassischen Rechner unter Variation dieser Parameter iterativ mehrfach ausgeführt. Der klassische Anteil des Algorithmus optimiert dabei die Ausgabe des Quantenschaltkreises bezüglich einer Zielfunktion – etwa mittels Gradientenabstieg oder unter Anwendung anderer klassischer Optimierungsverfahren.

Nach diesem Prinzip arbeiten die derzeit vielversprechendsten Algorithmen – z.B. VQE (Variational Quantum Eigensolver), verschiedene QNN-Varianten (Quantum Neural Network) oder auch QAOA (Quantum Approximate Optimization Algorithm), und bedienen mit Simulation, Maschinellem Lernen und kombinatorischer Optimierungdrei potenzielle Anwendungsgebiete moderner Quantenalgorithmen. Die Leistungsfähigkeit klassischer Algorithmen auf diesen Gebieten wird dabei am ehesten bei der Simulation physikalischer Systeme erreicht, da der Ressourcenverbrauch zur Simulation von Quantensystemen mit klassischen Rechnern unter Anwendung aktueller (und wohl auch künftiger) Verfahren exponentiell wächst.

Für Optimierungsverfahren und ML-Algorithmen ist die Leistungsfähigkeit gegenwärtiger Implementierungen i.d.R. noch nicht in die Nähe klassischer Verfahren gelangt, aber die Liste der verfügbaren Algorithmen ist bereits lang. Sie beinhaltet neben den schon genannten Verfahren Quantenvarianten von SVMs, PCA, Boltzmann-Maschinen, Reinforcement Learning, Bayesscher Inferenz, Convolutional NN oder Rekurrenten NN, die unter Nutzung quantenspezifischer algorithmischer Strategien wie z.B. Amplitudenverstärkung gegenüber ihren klassischen Verwandten gemäß theoretischer Analysen eine polynomielle oder gar superpolynomielle Beschleunigung realisieren.

Potenziale und Grenzen. Erhebliche Potenziale des Quantencomputing-Ansatzes und der entsprechenden Algorithmen bestehen in eben diesen Verbesserungen des Laufzeitverhaltens und der Speicheranforderungen von Algorithmen. Darüber hinaus kommen einige Arbeiten zu dem Ergebnis, dass Quantenverfahren auch andere Vorzüge gegenüber klassischen Algorithmen haben können, beim Maschinellen Lernen etwa in puncto Generalisierungsfähigkeit.

Die Vorteile von Quantenverfahren basieren im Wesentlichen auf der Nutzung der Ressourcen Superposition und Verschränkung als grundlegende Eigenschaften der Quantenwelt, zu denen es bei den Berechnungsmodellen klassischer Computer keine Äquivalente gibt. Gute Quantenalgorithmen nutzen diese Eigenschaften geschickt aus, um Quantenzustände – also den Speicherzustand des Quantencomputers – so zu manipulieren, dass das Ergebnis der gewünschten Rechnung möglichst zügig erzeugt wird, was bei vielen Verfahren übrigens nur mit einer bestimmten Wahrscheinlichkeit gelingt: Quantencomputing ist inhärent probabilistisch. Die Komplexitätsklasse der Probleme, für deren Lösung es einen effizienten Quantenalgorithmus gibt, heißt BQP (Bounded Error Quantum Polynomial Time) – die Klasse der Probleme, die auf einem Quantenrechner mit Fehlerwahrscheinlichkeit höchstens 1/3 in Polynomialzeit lösbar sind. BQP enthält die klassischen Komplexitätsklassen P, da Quantencomputer klassische Rechner effizient simulieren können, und BPP (Bounded Error Probabilistic Polynomial Time) – das „klassische Äquivalent“ zu BQP – jedoch nach allem was wir wissen und annehmen (etwa P≠NP) nicht die Klasse der NP-vollständigen Probleme. Diese bleiben also auch für Quantencomputer „schwierig“.

Weiterhin ist bekannt, dass BQP in der Klasse PSPACE der klassisch mit einem polynomiellen Platzbedarf lösbaren Probleme enthalten ist, und der Beweis dessen durch die Simulation eines Quantenschaltkreises mit einem klassischen Rechner macht direkt klar, dass Quantencomputer die Klasse der entscheidbaren Sprachen nicht erweitern, da sie eben allesamt von klassischen Rechnern simuliert werden können; vermutlich aber eben nicht alle auch effizient. Somit sind die Grenzen des Quantencomputing-Ansatzes in Bezug auf Effizienz und Berechenbarkeit in diesem Rahmen „grob“ abschätzbar. Was bleibt sind signifikante Vorteile für Quantenrechner bei der Anwendung auf Probleme wie die Faktorisierung natürlicher Zahlen, die – vermutlich – nicht in BPP, wohl aber in BQP liegen. Weitere relevante Vertreter dieser Problemklasse gilt es zu identifizieren. Klar ist auch, dass diese Komplexitätsbetrachtungen polynomielle Speed-ups unberücksichtigt lassen, diese also generell erlauben, was praktisch dann erheblichen Vorteilen entsprechen kann. 

Für einige Verfahren des Maschinellen Lernens werden wie beschrieben Speed-ups unterschiedlichen Ausmaßes erwartet. Bei Problemstellungen der Optimierung geht man von ähnlichen Resultaten aus. Komplexitätsbetrachtungen des Quantencomputings sind heute in vielen Details untersetzt, vgl. etwa https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q. Beachten Sie z.B. das spannende Resultat MIP*=RE einer neuen Charakterisierung der Menge der rekursiv aufzählbaren Sprachen von Ji et al. vom Januar 2020 (https://arxiv.org/abs/2001.04383).

Quantenhardware und Quantenvolumen. Kaum betrachtet wurde in dieser kurzen Einstimmung bisher das Thema Quantenhardware. Fakt ist, dass die Entwicklung von Quantenhardware große Fortschritte macht und auch weiterhin erwarten lässt. Prinzipiell verdoppelt sich – von Verlusten durch Fehlerkorrektur usw. einmal abgesehen – die Leistung eines Quantencomputers mit der Hinzunahme eines einzelnen weiteren Qubits. Eine Größe, die die Leistungsfähigkeit von Quantenrechnern repräsentieren soll und neben der Anzahl der Qubits auch Fehlerraten, die Konnektivität zwischen Qubits sowie darüber hinausgehende Parameter einbezieht, ist das sogenannte Quantenvolumen. Dessen exponentielles Wachstum soll das Moorsche Gesetz ablösen. IBM strebt eine jährliche Verdopplung dieser Leistungskenngröße an. Beim 28-Qubit-Rechner IBM Raleigh liegt sie derzeit bei 32 (Stand Januar 2020); Honeywell beansprucht ein Quantenvolumen von 64 für den eigenen Quantenrechner (Stand Juni 2020).

Es findet also ein spannendes Rennen statt. Neben den genannten Protagonisten gibt es eine Reihe weiterer, die ebenfalls an eigenen Quantenmaschinen arbeiten. Mit der Weiterentwicklung der Hardware (vgl. neben den genannten Unternehmen auch Microsoft, AQT, Xanadu, etc.), der Algorithmen wie oben beschrieben, der Programmiersprachen (etwa Python, Q# oder Silq) und der Software-Frameworks (z.B. Cirq, Qiskit, PennyLane, TensorFlow Quantum) werden Quantenrechner aller Voraussicht nach weiterhin zügig an Leistung gewinnen und damit immer relevanter werden und – so zumindest die Erwartung – Bereiche der Überlegenheit gegenüber klassischen Rechnern immer deutlicher markieren.

GI-Arbeitskreis „Quantencomputing“. Das ist Grund genug für die GI, das Thema auch in unserer Fachgesellschaft intensiver zu betrachten und einen Arbeitskreis „Quantencomputing“ ins Leben zu rufen.

Wir laden Sie herzlich zum Austausch im Rahmen dieses AK ein – diejenigen, die sich ebenfalls mit dem Thema Quantencomputing auseinandersetzen oder dies vorhaben, sind aufgerufen, sich bei Prof. Dr. Jörg Lässig (joerg.laessig@iosb-ast.fraunhofer.de), Fraunhofer IOSB-AST und Hochschule Zittau/Görlitz zu melden. Wir danken ihm für die Zusammenstellung des vorliegenden Artikels. Feedback, Ideen und Anregungen zum Thema sind ausdrücklich erwünscht.