Im Anschluss ihres Erasmus-Auslandsjahr in Lyon hat sich Alexandra Krause als angehende Physikerin in den Bereich der Quanteninformatik vertieft. Dazu hat sie im Rahmen der Gulasch Programmiernacht (GPN16) des Entropia e.V. in der Hochschule für Gestaltung und dem ZKM in Karlsruhe über Quantum Speedup (video) vorgetragen und Zeit gefunden, uns auch im Podcast etwas über das Thema zu erzählen.

Im Gegensatz zur klassischen Physik gelten in der Quantenmechanik eigene Regeln: So geht es hier um Teilchen in der Größenordnung von Atomen, wo die Begriffe Teilchen und Welle verschwimmen und der quantenmechanische Zustand unbeobachtet nur noch als Zustandsgemisch beschrieben werden kann.

Genau diese Eigenschaft will man sich beim Quantencomputer zu Nutze machen, wo gegenüber dem klassischen digitalen Computer, der immer auf einzelnen festen Zuständen in Bits mit Logikgattern rechnet, der Quantenrechner pro Schritt in Qubits auf allen Zuständen gleichzeitig operiert. Das eigentliche Ergebnis erhält man dort erst bei der Messung, wodurch sich der reine Zustand des Quantensystems einstellt.

Der Grover-Algorithmus ist eine bekannte Anwendung für einen Quantencomputer, der Datenbanken schneller als klassische Verfahren durchsuchen kann. Der Shor-Algorithmus kann hingegen mit einer Quanten-Fouriertransformation in polynomialer Zeit Zahlen in ihre Primfaktoren zerlegen kann. Damit werden viele assymetrische Kryptoverfahren wie das RSA-Verfahren obsolet, da sie auf der Schwierigkeit der klassischen Faktorisierung basieren. Shor hat in der gleichen Publikation auch ein Verfahren zur effizienten Berechnung von diskreten Logarithmen auf Quantencomputern veröffentlicht, so dass auch Kryptoverfahren auf elliptischen Kurven durch Quantencomputer gebrochen werden, die neben dem RSA-Verfahren Basis für viele Kryptowährungen sind.

Zum jetzigen Zeitpunkt ist es der Experimentalphysik noch nicht gelungen, allgemeine Quantensysteme in einer Größe zu erschaffen, die für sinnvolle Anwendungen der Verfahren erforderlich wären. Die Schwierigkeit liegt darin, den Quantenzustand einzelner Qubits von der Umwelt abzukoppeln und nur für die Berechnung zu verwenden, wenn doch alles in der Umgebung in Bewegung ist. In der Größe weniger Qubits, die allgemeine Quantencomputer bisher erreichen konnten, wurden Zahlen wie 15 und 21 erfolgreich faktorisiert.

Eine Hoffnung besteht hier auf dem adiabatischen Quantencomputer auf Basis adiabatischen Theorems, der von der Firma D-Wave Systems gebaut, und 2011 mit unvergleichlich vielen 128 Qubits auf den Markt gebracht wurde. Das Problem ist dabei, dass adiabatischen Quantencomputer im normalen Arbeitszustand keine universellen Quantencomputer sind, und hauptsächlich Optimierungsprobleme lösen können.

Universelle Quantencomputer können im Circuit model anschaulich jedes herkömmliches Programm abbilden: Jedes klassische Logik-Gatter kann durch Hinzufügen weiterer Ausgänge reversibel werden, und dann als eine unitäre Abbildung oder Matrizen im Quantencomputer realisiert werden. Unitäre Abbildungen sind lineare Abbildungen mit der Eigenschaft, dass sie das komplexe Skalarprodukt zweier Vektoren nach der Abbildung erhalten, d.h. Vektoren behalten die gleiche Länge, und zwei Vektoren behalten den gleichen Winkel zueinander. Der Nachteil des reversiblen Ansatzes ist jedoch, dass dafür womöglich viele Bits benötigt werden, wenn man die Abbildungen nicht zuvor zusammenfassen kann.

Theoretisch kann der adiabatische Quantencomputer auch universell sein, nur ist dazu ideal eine ungestörte Umgebung Voraussetzung, was in Realität nicht erreicht werden kann. Es verbleiben Optimierungsprobleme, die über den Hamiltonoperator abgebildet werden können: physikalische Prozesse möchten den energetisch niedrigsten Zustand zu erreichen. Ein Beispiel sind hier Minimalflächen, wie sie von Seifenhäuten und Seifenblasen angenommen werden- und auch zum Bau des Olympiageländes in München genutzt wurden. Im Schülerlabor für Mathematik in Karlsruhe kann man auch viele Experimente dazu durchführen.

Wenn man ein Optimierungsproblem lösen möchte, so sind lokale Minima ein Problem- in ihrer Umgebung erscheinen sie als Lösung, sie sind es jedoch insgesamt betrachtet nicht. Eine Möglichkeit die lokalen Minima zu umgehen ist das Verfahren des Simulated Annealing. Hier wird durch externe Störquellen begünstigt, dass lokale Minima verlassen werden, um das globale Minimum zu erreichen. In Quantensystemen spielt hier beim Quantum Annealing zusätzlich der Tunneleffekt eine besondere Rolle, wodurch die Störung noch leichter von lokalen Minima hinweg streut. Dadurch ist das Quantum Annealing prinzipiell und aus der Theorie schneller- oder zumindest nicht langsamer- als das Simulated Annealing.

Dabei ist das Quantum Annealing natürlich nur auf einem Quantencomputer effizient umsetzbar. Das ist dabei ein Beispiel für eine Quantensimulation auf einem Quantencomputer in dem Forschungsfeld, das sich mit der Abbildung und Simulation von Quantensystemen befasst.

Damit ist der adiabatische Quantencomputer auf eine kleinere Klasse von lösbaren Problemen beschränkt, jedoch soll er dieses mit einer erheblichen höheren Anzahl von Qubits durchführen können- zur Zeit der Aufnahme waren dies mit dem D-Wave Two etwa 512 Qubits. Die Frage, ob diese adiabatischen Quantencomputer mit dieser großen Anzahl von Qubits wirklich als Quantencomputer arbeiten, wurde wissenschaftlich diskutiert:

Im Artikel Evidence for quantum annealing with more than one hundred qubits legen die Autoren dar, dass der betrachtete adiabatische Quantencomputer starke Anzeichen für die tatsächliche Umsetzung des Quantum Annealing zeigt. In wie weit jedoch nun eine quantenbedingte Beschleunigung feststellen ist, diskutieren T. Rønnow und Mitautoren in der Arbeit Defining and detecting quantum speedup. Sie erhielten das ernüchternde Ergebnis, dass eine Beschleunigung durch Nutzung des betrachteten Quantensystems nicht eindeutig nachgewiesen werden konnte. Dagegen argumentierten V. Denchev et al. in What is the Computational Value of Finite Range Tunneling?, dass eine 100'000'000-fache Beschleunigung mit hoher Wahrscheinlichkeit gegenüber einem Einprozessor-System nachgewiesen werden kann.

Ein Problem bei der Analyse ist, dass die betrachteten Algorithmen für den Quantencomputer in den Bereich der probabilistischen Algorithmen fallen, die Ergebnisse also eine Fehlerwahrscheinlichkeit besitzen, die durch mehrfache Ausführung verringert werden kann. In der Kryptographie werden probabilistische Primzahltests sehr häufig eingesetzt, die auch in diese Klasse der Algorithmen fallen. So wurde im ersten Paper das Verhalten des Quantencomputers in einer Vielzahl von Versuchen mit simulierten Algorithmen verglichen und mit hoher Wahrscheinlichkeit festgestellt, dass der D-Wave-Rechner tatsächlich den Quantum Annealing Algorithmus ausführt.

Über den D-Wave-Rechner ist bekannt, dass die einzelnen Qubits durch supraleitende Ringe abgebildet sind und die beiden Stromlaufrichtungen die superpositionierten Zustände darstellen. Die Kopplung zwischen Qubits und nach außen erfolgt durch Spulen, die über die entstehenden Magnetfelder mit den Strömen in den Ringen interagieren. Die Kopplung zwischen Qubits wird damit durch die parametrisierte Kopplung der Spulen realisiert.

Für klassische Algorithmen und parallelisierte Computersysteme beschreibt der Begriff des Speedup die Effizienzsteigerung durch Nutzung einer erhöhten Parallelisierung. Je nach Algorithmus gibt es nach Amdahls Gesetz logische Grenzen, wo weitere Parallelisierung keine Gewinn mehr erzielt. Entsprechend besteht der Wunsch den Begriff des Quantum Speedup analog zu definieren und nachzuweisen: Diesen Ansatz verfolgten T. Rønnow und Mitautoren und definierten verschiedene Klassen von Quantum Speedup, wobei der adiabatische D-Wave Quantencomputer für sie nur Anzeichen für ein potentielles Speed-up ergab. Das ist ein ernüchterndes Ergebnis, wobei die Autoren klar weiteren Forschungsbedarf sahen.

Hier war das Paper von V. Denchev und Mitautoren eine große Überraschung, wo dem D-Wave 2X Rechner mit hoher Wahrscheinlichkeit eine Beschleunigung von 10^8 nachgesagt wurde. Neben den Annealing-Verfahren kam hier auch Quantum Monte Carlo zum Einsatz. Im Ergebnis erhielten sie für die Annealing-Verfahren ein asymptotisches Speed-Up, das sich für größere Problemstellungen einstellt, für Quantum Monte Carlo eine von der Problemgröße unabhängige Beschleunigung gegenüber einem klassischen Single-core Rechner.

Diese Aussagen trafen aber schnell auf Widerstand und den Nachweis, dass ein im Paper betrachtetes Problem mit anderen Algorithmen teilweise auf einem klassischen Rechner vielfach schneller gelöst werden kann als auf dem Quantencomputer.

Literatur und weiterführende Informationen

• S. Boixo, et al.: Evidence for quantum annealing with more than one hundred qubits, Nature Physics 10.3: 218-224, 2014.
• T. Rønnow, et al.: Defining and detecting quantum speedup, Science 345.6195: 420-424, 2014.
• V. Denchev, et al.: What is the Computational Value of Finite Range Tunneling? arXiv preprint arXiv:1512.02206, 2015.
• R. Harris, R., et al.: Compound Josephson-junction coupler for flux qubits with minimal crosstalk, Physical Review B 80.5: 052506, 2009.
• S. Ritterbusch: Digitale Währungen, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 32, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2014. http://modellansatz.de/digitale-waehrungen
• E. Dittrich: Schülerlabor, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 103, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2016. http://modellansatz.de/schuelerlabor
• Bernd Fix: Post-Quantum Krypto, Afra-Berlin.de, Vortrag am 13.12.2013.
• F. Rieger, F. von Leitner: Fnord Jahresrückblick, 32c3, Vortrag am 29.12.2015.
• S. Aaronson: Google, D-Wave, and the case of the factor-10^8 speedup for WHAT? Blog-Post mit Updates 16.5.2013-16.12.2015.
• Quantum Annealing Solver für den Laptop