Adiabatische Quantencomputer

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