Quantencomputer und Optimierung

<< >>

Die Optimierung ist ein breites Anwendungsfeld für Computer im Allgemeinen. Schon in den 1990er Jahren zeichnete sich ab, dass die Optimierung auch ein vielversprechendes Anwendungsgebiet für Quantencomputer sein könnten.

Optimierungsprobleme zeichnen sich formal so aus, dass eine „Kostenfunktion“ gegeben ist. Eine Lösung des Problems optimiert diese Kostenfunktion. Neben den exakten Lösungen sind auch Lösungsnäherungen von Interesse, die das Problem besser optimieren als eine Reihe anderer Kandidaten aber vielleicht nicht die beste Lösung sind.

Optimierungsprobleme sind für Quantencomputer auch deshalb von Interesse, weil viele Problemfamilien für Optimierung bekannt sind, die erwiesener Maßen nur mit viel Anfwand auf einem herkömmlichen Computer zu lösen sind.

Einstufung der Quanten-Algorithmen für Optimierung

Auch für die Optimierung stufe ich die Algorithmen nach Adam Boulands Beispiel in zwei Kriterien ein, die ich auch in anderen Artikeln auf quantencomputer-info.de verwende:

  1. Beschleunigung: Der Grad an Beschleunigung gegenüber herkömmlichen Computern (bzw. die Beschleunigung gegenüber den besten bekannten Algorithmen für herkömmliche Computer für dieselbe Anwendung)
  2. Verfügbarkeit: Der Zeitpunkt, wann dieser Algorithmus vermutlich verfügbar sein wird

Verfügbarkeit

Beschleunigung

Kurzfristig (NISQ)

Langfristig

Riesig

(exponentiell)

Moderat

(z.b. quadratisch)

Grover

Unbekannt

QAA

QAOA

 

Optimierung mit dem Grover-Algorithmus

Der Grover-Algorithmus ist ein Urgestein der Quantencomputer-Forschung. Für einen Quanten-Algorithmus ist er „einigermaßen verständlich“. Wegen seiner universellen Anwendungen habe ich ihm einen einen eigenen Beitrag auf quantencomputer-info.de gewidmet, unter anderem auch wegen der so grundlegenden Fragestellungen, ob ein Quantencomputer die schwierigen NP-Probleme effizient lösen kann.

Da auch Optimierungsprobleme dazugehören, können wir den Grover-Algorithmus hier ebenfalls auflisten. Er ist im Prinzip ein Suchalgeorithmus, der alle möglichen Lösungskandidaten durchprobieren kann.

Tatsächlich erzielt der Grover-Algorithmus nur eine moderate, quadratische Beschleunigung gegenüber herkömmlichen Suchalgorithmen. Ich erläutere in meinem Spezial-Artikel, dass vermutlich keine schnelleren Suchalgorithmen mit einem Quantencomputer möglich sind. Aus diesem Grund geht die Quantencomputer-Forschung davon aus, dass die schwierigen NP-Probleme mit einem Quantencomputer nicht generell effizient gelöst werden können.

Auf der anderen Seite können selbst quadratische Beschleunigung einen gewaltigen Vorteil bringen. Für herkömmliche Computer wurde in der Vergangenheit z.B. der Algorithmus „Schnelle Fourier-Transformation“ entwickelt. Er beschleunigt die „Normale Fourier-Transformation“ ebenfalls quadratisch. Was es damit auf sich hat, ist an dieser Stelle unwichtig. Was ich aber bemerkenswert finde, ist der Titel den die Schnelle Fourier-Transformation für diese moderate Beschleunigung bekommen hat: „The most important numerical algorithm of our lifetime“ i.

Wie fast alle Quanten-Algorithmen mit aktuell erwiesener Beschleunigung gegenüber herkömmlichen Computer, ist der Grover-Algorithmus vermutlich zu umfangreich für die NISQ-Quantencomputer der nächsten Generationen.

QAA: Optimierung und dem Quantum Adiabatic Algorithm

Der Quantum Adiabatic Algorithm basiert auf dem Adiabatischen Theorem der Quantenmechanik, das noch aus den Anfangszeiten der Quantenmechanik stammt ii. Das Theorem sagt Folgendes aus:

Wir präparieren ein Quantensystem derart, dass es die Quantenversion von einem Optimierungsproblem mit einer bekannten Lösung ist. Die Qubits sind so eingestellt, dass sie der bekannten Lösung in Bit-Darstellung entsprechen. Wenn wir das Quantensystem „adiabatisch“ also langsam ändern, entspricht es jetzt einem neuen Optimierungsproblem. Im Weiteren nenne ich diesen Verlauf den „adiabatischen Pfad“. Die Qubits werden sich dadurch ebenfalls ändern. Die Clou des Adiabatischen Theorems ist, dass die geänderten Qubits jetzt die Lösung des geänderten Problems darstellen iii! Sie müssen nur noch ausgemessen werden, um die Lösung in Bit-Darstellung zu erhalten.

Dabei ist es unerheblich, wie stark wir das Problem ändern. Es kommt lediglich darauf an, dass wir das System langsam ändern. Das Theorem sagt auch aus, wie langsam man das System ändern müsste. Und gerade das könnte sich in der Anwendung als Problem erweisen.

Der Quantum Adiabatic Algorithm ist untrennbar mit dem Quanten Annealer von D-Wave verbunden. D-Waves Annealer ist eine Hardware-Version des Quantum Adiabatic Algorithm. Er ist speziell auf diesen einen Algorithmus abgestimmt und funktioniert dort genauso wie ich es oben beschrieben habe. Andere bekannte Quanten-Algorithmen können allerdings nicht auf ihm ausgeführt werden.

Universelle Quantencomputer, wie die Quantencomputer von Google, IBM, Rigetti und Alibaba können andererseits prinzipiell sowohl den Quantum Adiabatic Algorithm als auch andere Algorithmen ausführen. Hier wird der Quantencomputer allerdings nicht wirklich zeitlich verändert. Stattdessen wird ein Quantenschaltkreis konstruiert, der diese zeitliche Veränderung simuliert. Und tatsächlich ist der Quantum Adiabatic Algorithm auf einem universellen Quantecomputer eine Anwendung der dynamischen Quantensimulation, also der Hamiltonischen Simulation (s.o.). Aus diesem Grund kann der Quantum Adiabatic Algorithm in absehbarer Zeit nur in abgewandelter Form auf einem NISQ-Quantencomputer ausgeführt werden. Diese abgewandelte Form ist gerader der QAOA, den ich weiter unten vorstellen werden.

Auf D-Waves Quanten Annealer kann der Quantum Adiabatic Algorithm allerdings schon heute ausgeführt werden. Wie erfolgreich gegenüber herkömmlichen Optimierungsmethoden dies dort möglich ist, muss erst die Anwendung zeigen.

D-Wave sieht die Anwendungen für den eigenen Quanten Annealer übrigens wesentlich vielfältiger. Tatsächlich gibt es diverse D-Wave-Kunden, die den Quantum Adiabatic Algorithm für andere Anwendungsfelder wie der Künstlichen Intelligenz, Simulation von Quantensystemen, … eingesetzt haben iv.

QAOA: Optimierung mit dem Quantum Approximate Optimization Algorithm

Im Jahr 2014 stellten Edward Farhi et al vom Massachusetts Institute of Technology / MIT einen neuen Algorithmus für Optimierung vor, der speziell für die Quantencomputer der NISQ-Arä abgestimmt ist v vi .

Die Funktionsweise des Quantum Approximate Optimization Algorithm / QAOA ist sehr ähnlich wie die des VQE, der zufälligerweise im selben Jahr vorgestellt wurde, und den ich Ihnen oben beschrieben habe. Der QAOA ist ebenfalls ein Quanten-klassischer Hybrid-Algorithmus:

  1. Die Qubits werden so eingestellt, dass sie einen Kandidaten für die Lösung des Optimierungsproblems darstellen.
  2. Mit diesem Kandidaten ermittelt der Quantencomputer die Kostenfunktion des Problems. Mit einem Quantencomputer sollte dies effizient durchführbar sein. Da diese Messung immer auch eine Sache von Wahrscheinlichkeiten ist, wird sie mehrmals durchgeführt und der beste Wert verwendet.
  3. Über einen herkömmlichen Computer wird ein neuer Kandidat für die Lösung des Problems anhand des bisherigen Optimierungsverlaufs berechnet.

Farhi et al geben darüber hinaus genaue Strategien vor, wie die Kandidaten für die Lösung zu finden sind. Und darin ähnelt der Quantum Approximate Optimization Algorithm / QAOA wiederum dem Quantum Adiabatic Algorithm vii: Die Kandidaten für die Lösung werden derart mit Quantengattern manipuliert, dass sie am Ende nichts anderes sind als eine Stückelung des adiabatischen Pfades für das Problem mit einem universellen Quantencomputer. Wie wir weiter oben gesehen haben, garantiert der Quantum Adiabatic Algorithm, dass dieses Verfahren immer zu der Lösung des Problems führt, falls wir die Stückelung nur extrem detailliert wählen.

Farhi argumentiert nun wie folgt: Selbst wenn wir die Stückelung nur sehr grob wählen, können wir versuchen sie über klassische Methoden zu optimieren. Dafür müssen wir nur prüfen, ob die optimierte Stückelung bessere Kostenwerte im Quantencomputer liefert als die vorherige. So gelangen wir vielleicht nicht zu der besten Optimierung aber zumindest zu einer besseren Lösung. Deshalb nennt Farhi den Quanten-Algorithmus auch „approximate algorithm“. Ein weiterer Vorteil von Farhis Methode ist, dass diese Lösungskandidaten vermutlich effizient auf einem NISQ-Quantencomputer erzeugt werden können.

Ob der QAOA eine Beschleunigung gegenüber herkömmlichen Computern erzielt, ist derzeit noch nicht erwiesen. Allerdings stellte Edward Farhi direkt mit der ersten Veröffentlichung eine bestimmte Klasse von kombinatorischen Optimierungsproblemen vor, die sich mit seinem Algorithmus effizienter lösen lassen als durch den besten Algorithmus für herkömmliche Computer. Mit diesem Ergebnis erzielte er große Aufmerksamkeit viii. Eine Gruppe namhafter Informatiker nahm darauhin Farhis Ideen als Vorlage und entwickelten einen neueren noch schnelleren klassischen Algorithmus für diese Problem-Klasse.

Nichts destotrotz werden große Hoffnungen in den QAOA gesetzt. Die Anwendungen für den QAOA werden weiterhin ausgiebig untersucht ix. Auf dem Portal arxiv.org für Vorveröffentlichungen zähle ich zwischen Dezember 2018 und Juli 2019 23 Fachartikel zum Thema QAOA.Tendenz steigend.

Fußnoten

iii Tatsächlich erfordert das Adiabatische Theorem zusätzlich, dass es eine „Energielücke“ zwischen dem ursprünglichen Problem und dem finalen Problem gibt. Das werde ich hier allerdings nicht weiter ausführen. U.a. steuert diese Energielücke die Zeitspanne, die man für den Quantum Adiabatic Algorithm einplanen muss.

iv https://www.youtube.com/watch?v=UywYeMl30EM: Vortrag von Bo Ewald, President von D-Wave, auf der Konferenz „Quantum For Business 2018“, über die vielfältigen Projekte von D-Waves Kunden.

v https://arxiv.org/abs/1411.4028: „A Quantum Approximate Optimization Algorithm“, Fachartikel von Edward Farhi, Jeffrey Goldstone und Sam Gutman

vi https://www.youtube.com/watch?v=J8y0VhnISi8: „A Quantum Approximate Optimization Algorithm“, Vortrag von Edward Farhi zum Fachartikel

vii Dasselbe Autorenteam (Edward Farhi, Jeffrey Goldstone und Sam Gutman) war übrigens knapp 15 Jahre vorher maßgeblich daran beteiligt, dass der Quantum Adiabatic Algorithm und dadurch auch das Konzept des Quanten Annealers eine größere Aufmerksamkeit in der Forschergemeinde bekam. z.B. https://arxiv.org/abs/quant-ph/0104129: „A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem“ zusammen mit weiteren Autoren.

viii https://www.scottaaronson.com/blog/?p=2155: „Quantum computing news items“ Blogeintrag von Scott Aaronson über den QAOA, der so viel Aufmerksamkeit unter Informatikern erregte, dass diese einen neuen effizienteren, klassischen Algorithmus entwarfen.

ix https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf: Eine schöne Übersicht finden Sie im Artikel „An Introduction to Quantum Optimization Approximation Algorithm“ von Wang und Tauqir

Anwendungen für Quantencomputer

<< >>

Erste Anwendungen: Ein goldenes Zeitalter für Quantencomputer?

Glaubt man Seth Lloyd vom Massachusetts Institute of Technology / MIT, steht die Quantencomputer-Szene gerade kurz vor einem goldenen Zeitalter. Seth Lloyd bezeichnet sich selbst als „Quantum Mechanic“, ist einer der Gründerväter der Quantencomputer-Forschung und seit über 25 Jahren ein führender Theoretiker in dem Bereich. Nebenbei sind seine Vorlesungen und Vorträge einfach immer sehr unterhaltsam i (Gerne gibt Lloyd z.B. die steile These zum besten, dass der Finanzcrash von 2009 durch die verkopften Transaktions-Algorithmen von einem Haufen arbeitsloser Superstring-Theoretikern verursacht wurde, und dass dass die Forscher für Quantencomputer die Sache mit der Weltwirtschaft jetzt zu Ende zu bringen werden).

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 der erste Quanten-Algorithmus von David Deutsch vorgestellt, der für eine spezielle Aufgabe weniger Rechenschritte benötigte, als ein herkömmlicher Computer. In den Jahrzehnten seitdem wurde eine Vielzahl an faszinierenden Quanten-Algorithmen für viele Anwendungen entwickelt, die die herkömmlichen Programme für dieselbe Anwendung meilenweit hinter sich lassen und exponentielle Rechenbeschleunigungen erzielen können.

Diese existieren aber bislang nur auf dem Papier. Was bislang fehlte war die zugehörige Hardware.

Letztere ist langsam verfügbar. Diverse Tech-Firmen arbeiten an Cloud-Angeboten für ihre Quantencomputer. An öffentlichen Einrichtungen wird die Forschung an größere 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 ii).

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.

Laut Seth Lloyd ist die Situation mit den ersten Quantencomputern heute sehr ähnlich. Sie sind aufwendig im Betrieb, besitzen nur wenige Dutzend Qubits und sind besonders noch sehr fehleranfällig. Aber sie können genutzt werden. Das öffnet die Tür erstmals praktische Erfahrungen mit der neuen Technologie zu sammeln.

Viele Algorithmen und Anwendungen für herkömmliche Computer wurden eben über solche Erfahrungen entwickelt. Wir können erwarten, dass dies für Quantencomputer auch zutreffen wird. Erste Kandidaten für solche heuristische Methoden gibt es bereits.

NISQ: Die ersten Generationen von Quantencomputern

Anlässlich seiner Keynote-Rede zu der Konferenz „Quantum Computing For Business 2017“ fand John Preskill vom California Institute of Technology (Caltech) einen passenden Begriff für die erste Ära von Quantencomputern: „Noisy intermediate scale quantum computer“ NISQ iii. John Preskill ist einer der führenden Kopfe hinter der Quantencomputer-Entwicklung und trifft in seinen Vorträgen oft den Nagel auf den Kopf: „Fehleranfällige, mäßig skalierte Quantencomputer“.

Damit meint Preskill Quantencomputer mit etwa 50 – wenigen 100 Qubits. Insbesondere sind die Quantencomputer der NISQ-Ära nicht in der Lage eines der Kernkonzepte für Quantencomputer umzusetzen: Die Quanten-Fehlerkorrektur für die äußerst störanfälligen Qubits. Ohne die Quanten-Fehlerkorrektur können Quantencomputer keine umfangreichen Quanten-Algorithmen ausführen. Und das betrifft aktuell fast alle Quanten-Algorithmen. Die Fehlerrate von aktuellen Quanten-Gattern, also elementaren Qubit-Schaltungen, liegt bei 1:100 bis zu 1:1000. Das liegt um viele Größenordnungen über der Fehlerrate von herkömmlichen Computern.

Die ersten Anwendungen von NISQ-Quantencomputer müssen diese Einschränkungen also berücksichtigen.

Anwendungen für Quantencomputer: Eine Einstufung der Algorithmen

Ein Jahr nach Preskills Vortrag hielt Adam Bouland an gleicher Stelle einen sehr guten Vortrag auf der Konferenz „Quantum Computing For Business 2018iv. Darin stellte er verschiedene bekannte Quanten-Algorithmen für diverse Anwendungen vor. Bouland stufte die Algorithmen in zwei Kriterien ein:

  1. Beschleunigung: Der Grad an Beschleunigung gegenüber herkömmlichen Computer (bzw. die Beschleunigung gegenüber den besten bekannten Algorithmen für herkömmliche Computer für dieselbe Anwendung)
  2. Verfügbarkeit: Der Zeitpunkt, wann dieser Algorithmus vermutlich verfügbar sein wird

Verfügbarkeit

Beschleunigung

Kurzfristig (NISQ)

Langfristig

Riesig

(exponentiell)

Moderat

(z.b. quadratisch)

Unbekannt

 

Diese Einteilung finde ich so sinnvoll, dass ich sie für diesen Artikel ebenso verwenden werde. Genauso werde ich einige Inhalte aus seinem Vortrag übernehmen.

Anwendungen für Quantencomputer: Eine Übersicht

Quantencomputer werden in absehbarer Zukunft vermutlich nur für besonders rechenintensive Probleme eingesetzt werden, deren Lösungen aber besonders wertvoll sein können. Zu den absehbaren Anwendungen zählen zum Beispiel:

  1. Simulationen für Natur- und Ingenieurswissenschaften (Physik, Materialforschung, Quanten-Chemie, Quanten-Biologie)
  2. Optimierung (Logistik, Finanzwirtschaft, …)
  3. Lineare Algebra / Künstliche Intelligenz
  4. IT-Beratung
  5. Kryptographie
  6. Energieeinsparung

Diese werde ich im Folgenden genauer vorstellen.

Quantencomputer Anwendung: „Simulationen für Naturwissenschaften“

Verfügbarkeit

Beschleunigung

Kurzfristig (NISQ)

Langfristig

Riesig

(exponentiell)

Hamiltonische Simulation

Moderat

(z.b. quadratisch)

Unbekannt

VQE

 

1982 beendete der geniale Richard Feynman einen berühmten Aufsatz mit den ebenfalls berühmten Worten: „Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy.“ v .

Hamiltonische Simulation

1996 bewies Seth Lloyd, dass jede solcher Simulationen prinzipiell und effizient mit einem Quantencomputer durchgeführt werden können vi. Diese Art von Berechnungen werden „Hamiltonische Simulationen“ genannt. Sie berechnen die Dynamik, also den zeitlichen Verlauf, von beliebigen Quantensystemen, welche generell durch den sogenannten Hamilton-Operator charakerisiert sind (daher der Name). Hamiltonische Simulationen gehören zu den schwersten Berechnungen, die ein Quantencomputer effizient durchführen kann. Herkömmliche Supercomputer können dies erwiesenermaßen genau nicht.

Hinter vielen möglichen Anwendungen für Quantencomputer stehen noch offene Fragezeichen, inwieweit bekannte Einschränkungen und Nebenbedingungen in der Praxis einmal überwunden werden können. Es herrscht aber generelle Einigkeit, dass die sagenumwobenen Heilsversprechen von Quantencomputern auf jeden Fall für die Hamiltonische Simulation zutreffen werden.

Anwendung: Synthetisierung von Ammoniak

Eine spannende Anwendung für die Hamiltonische Simulation, die bereits im Detail auf ihre Anwendbarkeit untersucht wurde, ist die „Synthetisierung von Ammoniak“:

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 über die Hamiltonische Simulation dazu allerdings in der Lage vii. Allerdings wohl leider nicht in der NISQ-Ära.

VQE: Variational Quantum Eigensolver

Die Anwendung „Hamiltonische Simulation“ übersteigt also wohl die Möglichkeiten für Quantencomputer der NISQ-Ära. Gibt es andere mögliche Anwendungen für Quantensimulationen, die auf der aktuellen Hardware umgesetzt werden können?

Eine wichtige Fragestellung für Quantensysteme ist die Frage nach den nach den Bindungsenergien des Systems und den Atom- bzw. Molekül-Orbitalen.

2014 wurde der neue Quanten-Algorithmus „Variational Quantum Eigensolver“ von Peruzzo und McClean vorgestellt viii ix. Er wurde speziell für die Quantencomputer der NISQ-Arä konzipiert. VQE ist im Grunde ein Optimierungs-Algorithmus und insbesondere ein Quanten-klassischer Hybrid-Algorithmus:

  1. Die Qubits werden so eingestellt, dass sie einen Orbital-Kandidaten darstellen.
  2. Mit diesem Kandidaten ermittelt der Quantencomputer die Bindungsenergie des Moleküls. Mit einem Quantencomputer sollte dies effizient durchführbar sein. Da diese Messung immer auch eine Sache von Wahrscheinlichkeiten ist, wird sie mehrmals durchgeführt und der kleinste Wert verwendet.
  3. Über einen herkömmlichen Computer wird ein neuer Orbital-Kandidat anhand des bisherigen Optimierungsverlaufs berechnet x.
  4. Jetzt beginnt der Algorithmus wieder bei Schritt 1. Diesmal mit dem neuen Orbital-Kandidaten. Der Algorithmus endet dann, wenn z.B. die niedrigste Bindungsenergie gefunden wurde.

Der Grundgedanke des Variational Quantum Eigensolver ist, dass ein Quantencomputer in der Lage ist auch kompliziert verschränkte Quantenzustände herzustellen und mit ihnen zu rechnen. Und gerade solche Orbitale liegen in Molekülen vor. Für einen herkömmlichen Computer wird dies normalerweise schnell exponentiell zu aufwendig.

Dadurch dass der Variational Quantum Eigensolver über die Optimierung sowieso ständig nachjustiert, ist der Algorithmus auch einigermaßen immun gegen Schaltungs- und Qubit-Fehler.

Der Variational Quantum Eigensolver hört sich in der Theorie sehr erfolgversprechend an. Tatsächlich kann aktuell aber niemand mit Sicherheit sagen, ob der VQE tatsächlich eine Beschleunigung bringt, geschweige denn, dass diese beziffert werden könnte. Hier müssen noch viele Erfahrungswerte gesammelt werden. So zeigt sich z.B. dass nicht jeder klassische Optimierungs-Algorithmus im Schritt 3 gleich gut für den Variational Quantum Eigensolver geeignet ist xi

Um den VQE-Algorithmus hat Google das Opensource-Framework „OpenFermion“ für Quantenchemie erstellt. Jarrod McClean, einer der Entwickler des Variational Quantum Eigensolvers, wurde mittlerweile von Google angeworben. Es zeigt sich, dass die Tech-Riesen vermehrt gerade mit solchen Wissenschaftlern eng zusammenarbeiten, die sich einen Namen für Anwendungen von NISQ-Quantencomputern gemacht haben.

Quantencomputer Anwendung: „Optimierung“

Der Optimierung widme ich auf quantencomputer-info.de einen eigenen Artikel. Deshalb stelle ich die drei Algorithmen hier nur in Kürze vor:

Verfügbarkeit

Beschleunigung

Kurzfristig (NISQ)

Langfristig

Riesig

(exponentiell)

Moderat

(z.b. quadratisch)

Grover

Unbekannt

QAA

QAOA

 

Anwendung des Grover-Algorithmus

Der Grover-Algorithmus ist ein universeller Suchalgorithmus, der sämtliche Lösungskandidaten ausprobiert und testet, ob sie das Problem lösen. Daran können Sie sehen, dass der Grover-Algorithmus ein unheimlich breites Feld an Anwendungen besitzt, unter anderem bei Optimierungsproblemen.

Der Grover-Algorithmus besitzt eine quadratische Beschleunigung gegenüber herkömmlichen Suchalgorithmen. In der Anwendung benötigt er aber wohl zu viele Quantengatter, weshalb er wohl nicht für Quantencomputer der NISQ-Arä verwendet werden kann.

Anwendung des QAA – Quantum Adiabatic Algorithm

Grundlage des QAA ist das Adiabatischen Theorem der Quantenmechanik aus dem Jahr 1928.

Der Quantum Adiabatic Algorithm wird hardwareseitig durch den Quanten Annealer von D-Wave realisiert und kann dort bereits heute schon eingesetzt werden. Aus diesem Grund ordne ich ihn als „kurzfristig verfügbar“ ein.

Auf universellen Quantencomputern ist der Quantum Adiabatic Algorithm eine Anwendung der Hamiltonischen Simulation (s.o.). Deswegen wird der QAA auf NISQ-Quantencomputern zunächst nur in einer abgewandelten Form eingesetzt werden. Ein Beispiel hierfür ist gerade der QAOA:

QAOA: Quantum Approximate Optimization Algorithm

Wie der Quantum Variational Eigensolver ist der Quantum Approximate Optimization Algorithm ein Quanten-klassischer Hybrid-Algorithmus:

  1. Die Qubits werden so eingestellt, dass sie einen Kandidaten für die Lösung des Optimierungsproblems darstellen.
  2. Mit diesem Kandidaten ermittelt der Quantencomputer die Kostenfunktion des Problems. Mit einem Quantencomputer sollte dies effizient durchführbar sein. Da diese Messung immer auch eine Sache von Wahrscheinlichkeiten ist, wird sie mehrmals durchgeführt und der beste Wert verwendet.
  3. Über einen herkömmlichen Computer wird ein neuer Kandidat für die Lösung des Problems anhand des bisherigen Optimierungsverlaufs berechnet.

Das Team um Edward Farhi gibt außerdem vor, wie die Lösungskandidaten ermittelt werden. Sie sind nichts anderes als eine Parametrisierung des adiabatischen Pfades im QAA. Nach Farhi ist das ein Indiz dafür, dass dieser Lösungsansatz zum Ziel führt.

Quantencomputer Anwendung: „IT-Beratung“

Aktuelle Quantencomputer sind noch nicht in der Lage interessante Anwendungen zu ermöglichen. Das könnte sich sogar noch in der NISQ-Ära ändern und möglicherweise sehr abrupt. Es gibt Hinweise, dass auch für Quantencomputer eine Art „Moores Law“ zutreffen könnte xii, das die Beschleunigungszyklen von herkömmlichen Computern lange Zeit zutreffend beschrieb. Mögliche Quanten-Algorithmen hierfür habe ich Ihnen in diesem Artikel vorgestellt. Firmen, die auf Highend-Algorithmen angewiesen sind, können sich in der Regel nicht erlauben, eine Entwicklung mit so viel Potential zu verpassen. Um aber auch nur erste Gehversuche in der Quantencomputer-Welt zu machen, ist allerdings so spezielles Knowhow notwendig, dass selbst Firmen mit viel IT-Erfahrung ohne Unterstützung nicht aus den Startlöchern herauskommen werden. Dazu müssen Sie sich zwingend mit der aktuellen Forschung zu den jeweiligen Quanten-Algorithmen auseinandersetzen, die ich z.B. in diesem Artikel vorgestellt habe.

Die Hersteller der Quantencomputer wissen das natürlich und begleiten hier durch die ersten Gehversuche. D-Wave betreute bis Ende 2018 etwa 150 Kundenprojekte. Zusätzlich haben sich zwei Startups einen Namen gemacht, die sich darauf spezialisieren, den zukünftigen Markt für Softwarelösungen herstellerunabhängig auszuloten und Knowhow im Quantencomputing zu entwickeln und zu bündeln: Die Vancouver Firma 1QBit und QCWare aus dem Silicon Valley.

Ich gehe davon aus, dass sowohl die Kunden als auch die nordamerikanischen Firmen früher oder später erkennen, dass sie auch auf IT-Beratung in Deutschland bzw. Europa angewiesen sind:

  • Für Einführungsveranstaltungen, um überhaupt einen Eindruck von der Technologie und den aktuellen Möglichkeiten zu vermitteln
  • Als Schnittstelle zwischen Hersteller und Kunden, die beide Sprachen spricht und besser verfügbar sind
  • Als Experte um Projekte direkt eigenverantwortlich auf den Cloudangeboten umzusetzen

Fußnoten

i https://www.youtube.com/watch?v=5xW49CzjhgI: Vortrag von Seth Lloyd „The Future of Quantum Computing“.

ii 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.

iii https://arxiv.org/abs/1801.00862: „Quantum Computing in the NISQ era and beyond“, Vortragvorlage von John Preskill zur Konferenz „Quantum Computing For Business“ in 2017.

iv https://www.youtube.com/watch?v=PJRatgm8sL0: „The Quantum Algorithms: The NISQ Landscape“, Vortrag von Adam Bouland auf der Konferenz „Quantum for Business 2018“

vhttps://people.eecs.berkeley.edu/~christos/classics/Feynman.pdf: „Simulating Physics with Computers“ Artikel von Richard Feynman

vi https://science.sciencemag.org/content/273/5278/1073: „Universal Quantum Simulator“, Artikel von Seth Llyod

vii http://www.pnas.org/content/early/2017/06/30/1619152114: Wissenschaftlicher Artikel u.a. von Krysta Svore, Matthias Troyer (Microsoft) „Elucidating reaction mechanisms on quantum computers“

viii https://www.youtube.com/watch?v=w7398u8G588: Vortrag von Jarrod McClean: „Quantum Computation for the Discovery of New Materials and […]“

ix https://arxiv.org/abs/1509.04279: „The theory of variational hybrid quantum-classical algorithms“ Fachartikel von Jarrod McClean et al.

xDie Orbital-Kandidaten sind dafür über vorher festgelegte Kriterien parametrisiert. z.B. : Drehe Qubit 1 um Winkel 1, drehe Qubit 2 um Winkel 2, verschränkte Qubit 5 und Qubit 6 um den Faktor 3, … Diese Parameter (Winkel 1, 2, …) werden im weiteren Verlauf anhand von klassischen Algorithmen weiter optimiert (z.B. „Gradient Descent“, Nelder und Mead‘s „Simplex-Verfahren“, …).

xi https://quantumcomputing.stackexchange.com/questions/6562/how-to-implement-nm-algorithm-for-variational-quantum-eigensolver: Antwort von Jarrod McClean zu dem Thema „Optimierer für den VQE“ auf Quantum Computing Stack Exchange

xii https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/: Artikel „Does Neven’s Law Describe Quantum Computing’s Rise?“ auf Quantamagazin, das Quantencomputern sogar eine Turbo-Version von Moores Law in Aussicht stellt, weil jedes weitere Qubit die Leistungsfähigkeiten eines Quantencomputers sowieso bereits verdoppelt (zumindest auf dem Papier). Ähnlich geht Bo Ewald von D-Wave davon aus, dass die Anzahl von Qubits in D-Waves Quanten Annealer alle zwei Jahre verdoppelt werden kann: https://www.youtube.com/watch?v=UywYeMl30EM

Der unglaubliche Quantencomputer einfach erklärt

<<   >>

Durch Quantencomputer wird die rätselhafte Quantenmechanik dafür genutzt, um völlig neuartige berechnende Systeme bereit zustellen. Deshalb besitzen Quantencomputer Eigenschaften die schier unglaublich wirken: So steigert sich die Leistungsfähigkeit eines Quantencomputers zum Beispiel „exponentiell“, also quasi explosionsartig, mit zunehmender Größe. Im Folgenden erkläre ich Ihnen in einfachen Worten, diese besonderen Eigenschaften eines Quantencomputers.

Der Paukenschlag: Der Shor-Algorithmus

Im Jahr 1994 hatte der Mathematiker Peter Shor vom renommierten Massachusetts Institute of Technology / MIT die Idee seines Lebens. Eine Idee, die eine neue Ära einleiten würde.

Shor untersuchte ein neues Verfahren, um eine ganze Zahl in Primzahlen zu zerlegen. Diese Primzahlfaktorisierung ist eine extrem aufwendige Angelegenheit. Um sehr großen Zahlen in Primzahlen zu zerlegen, brauchen selbst sehr leistungsstarke Supercomputer mehrere Jahre. i

Unter anderem deshalb wird sie für die sichere Datenverschlüsselung im Internet verwendet. Es ist zwar sehr einfach selbst große Zahlen aus bekannten Primzahlen zusammenzusetzen (z.B. 7×13×13×17×53 = 1065883). Da die Umkehrung aber nahezu unmöglich ist, ist die Verschlüsselung im Internet bombensicher.

Eigentlich!

Shor fragte sich, ob man das neue Verfahren nutzen könnte, um neue Algorithmen für die Primzahlzerlegung zu erstellen. Irgendwann erinnerte er sich an eine Pflichtvorlesung über Quantenmechanik, die er seinerzeit als Mathematik-Student noch am California Institute of Technology (Caltech), hatte hören müssen. Ihm kam die grandiose Idee, dass das Verfahren ungleich schneller zum Ziel führen könnte, wenn man zur Berechnung nicht einen herkömmlichen Computer, sondern einen Quantencomputer verwenden würde. Er tüfftelte ein Jahr an seinem Quanten-Algorithmus und kam am Ende tatsächlich zu dem gewünschten Ergebnis ii.

Shors Algorithmus schlug ein wie eine Bombe. Bis zu diesem Zeipunkt, war es noch niemanden gelungen einen Quantencomputer zu konstruieren. Der Shor-Algorithmus war aber der erste Beweis, wie ungeheuer leistungsstark ein Quantencomputer sein und welche gesellschaftlichen Auswirkungen er haben würde. Shors Algorithmus löste einen regelrechten Boom in den Quantencomputer-Szene aus.

Ein Quantencomputer macht sich die außergewöhnlichen Eigenschaften der atomaren Welt zu nutze, um über spezielle Quantenprogrammen, den Quanten-Algorithmen, ganz neue Dimensionen in der Rechengeschwindigkeit zu erzielen. Das Wort „außergewöhnlich“ ist hierbei wohl noch untertrieben. Die Quantenwelt ist eine rätselhafte Welt mit schon fast magischen Eigenschaften.

Um einen Eindruck davon zu bekommen, was das Besondere an einem Quantencomputer ist, müssen wir uns erst einmal anschauen, wie ein herkömmlicher Computer funktioniert.

Einfach erklärt: Wie funktioniert ein herkömmlicher Computer?

Nehmen wir Ihren Computer, mit dem Sie diese Zeilen lesen. Er steuert Informationen in Form von Nullen und Einsen über Bits bzw. Bytes an. Die Zahl „71“ wird z.B. durch die Bit-Reihe „0100 0111“ dargestellt und der Buchstabe „J“, per Konvention, durch die Bit-Reihe „100 1010“. Ihr Computer merkt sich, ob eine Bit-Reihe eine Zahl, einen Buchstaben, ein Bild oder Musik darstellt. Die Bits selbst existieren in Form von Milliarden elektrischer An / Aus – Schalter, den Transistoren. Zusammen bilden sie den Arbeitsspeicher Ihres Computers. Ein guter herkömmlicher Computer besitzt etwa 16 * 8 Milliarden Bits oder anders ausgedrückt: 16 Gigabyte. Ein Computerprogramm manipuliert diese Bits in einzelnen Rechenschritten über die elementarsten Bausteine der menschlichen Logik: UND-Verknüpfungen, ODER-Verknüpfungen, NICHT-Verknüpfungen. Diese Verknüpfungen werden auch „Gatter“ genannt (englisch gates). Eine NICHT-Verknüpfung kehrt ein einzelnes Bit z.B. in sein Gegenteil um: NICHT 0 = 1, NICHT 1 = 0 .

Über geschickte elektrische Schaltungen, dem Datenbus, ist Ihr Computer in der Lage jedes der unzähligen Bits im Arbeitsspeicher gezielt anzusteuern, auszulesen oder mit neuen Werten zu überschreiben. Ein Rechenschritt sieht dann zum Beispiel so aus:

„Lese den Wert des Bits mit der Adress-Nummer 1543216 und den Wert des Bits mit der Adress-Nummer 6543 aus und verknüpfe beide Werte mit einem UND-Befehl. Speicher das Ergebnis im Bit mit der Adress-Nummer 789874“. Durch eine geschickte Hintereinanderreihung dieser elementaren UND-, ODER-, NICHT-Verknüpfungen ist Ihr Computer zum Beispiel in der Lage zwei Zahlen miteinander malzunehmen. Nach jedem einzelnen dieser Rechenschritte schreibt Ihr Computer die Zwischenergebnisse wieder in den Arbeitsspeicher hinein und ruft sie von dort wieder für den nächsten Rechenschritt auf. Das Programm für das Mal-Nehmen sieht unnötig umständlich und mechanisch stupide aus. Da Ihr Computer aber in der Lage ist Milliarden von Rechenschritten pro Sekunde auszuführen ist er jedem Menschen am Ende in solchen Aufgaben gigantisch überlegen.

Die Qubits einfach erklärt

Ein Quantencomputer steuert im Gegensatz dazu die Informationen nicht über einfache An / Aus-Schalter an, also den herkömmlichen Bits, sondern über sogenannte „Qubits“ (für Quanten-Bits). In einem Qubit sind die Werte 0 / 1 bzw. An / Aus gleichzeitig in einer überlagerten Form vorhanden. Das sieht auf den ersten Blick vielleicht harmlos aus. Tatsächlich ist diese Überlagerung eines der großen Rätsel der Quantenmechanik. Als Konsequenz ersann der österreichische Nobelpreisträger Erwin Schrödinger vor fast hundert Jahren sein berühmtes Gedankenexperiment „Schrödingers Katze“: Eine Katze, die zusammen mit einem Qubit überlagert ist. Das Qubit schaltet einen Giftcocktail ein, sobald es den Wert 1 hat. Wenn das Qubit aber gleichzeitig den Wert 0 und den Wert 1 besitzt, so Schrödinger, müsste die Katze ebenfalls gleichzeitig tot und lebendig sein.

Die zweite so außergewöhnliche Eigenschaft von Qubits ist die Folgende. Selbst kleinste Mengen an Qubits in einem Quantencomputer können eine riesige Anzahl von Informationen gleichzeitig aufnehmen und verarbeiten: iii

  • 1 Qubit entspricht 2 herkömmlichen Bits
  • 2 Qubits entsprechen 4 herkömmlichen Bits
  • 10 Qubits entsprechen 16 herkömmlichen kilo-Byte
  • 20 Qubits entsprechen 16 herkömmlichen Mega-Byte
  • 30 Qubits entsprechen 16 herkömmlichen Giga-Byte
  • 31 Qubits entsprechen 32 herkömmlichen Giga-Byte

Jedes weitere Qubit verdoppelt also die Anzahl von gleichzeitig verwendbaren Informationen! Die Leistungsfähigkeit eines Quantencomputers steigt also exponentiell! Und so geht’s weiter:

  • 45 Qubits entsprechen in etwa der Speichergröße des größten aktuellen, herkömmlichen Supercomputers
  • 50 Qubits, die „Quanten-Überlegenheit“-Grenze: Die, zumindest theoretische, Grenze an dem ein Quantencomputer gewisse Berechnungen durchführen kann, die mit keinem der aktuellen Supercomputern durchführbar wären. iv Die Tech-Riesen liefern sich um genau diese Grenze gerade das große Wettrennen.
  • 250 Qubits: Die absolute Grenze die überhaupt machbar wäre für herkömmliche Computer. Um die Speichergröße eines 250 Qubit-Quantencomputers zu erreichen, müsste ein herkömmlicher Computer jedes Atom im Universum als herkömmliches Bit verwenden.

Das wirkt unglaublich. Ist es auch!

Und nun bedenken Sie mal, dass die Quantencomputer-Branche das Ziel hat irgendwann einmal Quantencomputer mit Millionen von Qubits zu bauen!

Quantencomputer einfach erklärt: Quantenparallelismus, Superposition

Der Clou bei diesen ungeheuren Zahlen ist aber tatsächlich Folgender: Nehmen wir nochmal das Beispiel mit dem Mal-Nehmen. Ihr herkömmlicher Computer nimmt zwei Zahlen, in Form von zwei Bit-Reihen im Arbeitsspeicher, führt das festgelegte Programm von einzelnen Rechenschritten aus und erhält am Ende eine Zahl in Form von einer Bit-Reihe.

Ein Quantencomputer nimmt im Gegensatz dazu für eine Aufgabe zwei Qubit-Reihen, speichert die Zwischenergebnisse wieder in Qubits und erhält am Ende das Ergebnis in Form einer Qubit-Reihe v. Da in einer Qubit-Reihe aber riesige Mengen von Informationen gleichzeitig enthalten sein können (s.o.), kann der Quantencomputer das Programm letztendlich gleichzeitig mit einer riesigen Menge von Zahlen ausführen. Dies ist der Quantenparallelismus. Normalerweise spricht man aber von der „Superposition“.

Tatsächlich gibt es diese Form von Überlagerung öfter in der Natur und nicht nur in der Quantenmechanik vi. Was den Quantenparallelismus so besonders macht ist die Tatsache, dass nur wenige Qubits so unvorstellbar große Datenmengen überlagern können. Die Qubits werden nämlich nicht nur einzeln überlagert, sondern der gesamte Verbund an Qubits. Und gerade dabei erhöht sich die Anzahl von möglichen Kombination so rasant. Für drei Qubits werden also z.B. bis zu acht mögliche Bit-Zustände gleichzeitig verwendet (das entspricht 2³): Nämlich 000, 100, 001, 101, 011, 111, 010 und 110.

Einsteins spukhafte Verschränkung

Das vorangegangene Beispiel hat eine bizarre Konsequenz. Albert Einstein höchstpersönlich sagte sie 1935 in einem berühmten Aufsatz voraus: Die „Quanten-Verschränkung“ (engl. „entanglement“, er selbst bezeichnete das Phänomen auch „spukhafte Fernwirkung“). Wir können zwei Qubits (oder auch mehrere Qubits) derart überlagern, dass wir sie nicht mehr als einzelne Qubits erkennen können. Stattdessen bilden sie eine völlig neuartige, einheitliche Zustandsform. Sie erscheinen „verschränkt“: Eine Messung am ersten Qubit hat sofort Auswirkungen auf das zweite Qubit.

Ziel von Einsteins Arbeit war es tatsächlich, der Quantenmechanik einen grundlegenden Denkfehler nachzuweisen. Laut Einstein müsste diese Einheit bestehen bleiben, selbst wenn die beiden Qubits Lichtjahre voneinander entfernt wären. Deshalb sprach er von Fernwirkung. Das Verrückte dabei ist: Alle Experimente deuten daraufhin, dass es genauso ist. Die Fernwirkung ist real in der Quantenwelt.

Solche verschränkte Zustandsformen gibt es nirgendwo sonst in den Naturwissenschaften. Vielleicht bis auf eine Ausnahme: Ein sogenanntes astronomisches „Wurmloch“, das zwei schwarze Löcher über eine Distanz von vielen Lichtjahren miteinander verbinden kann, als eine Art Hyper-Schnellstraße. Die Frage, wie diese beiden Phänomene zusammenhängen ist tatsächlich Gegenstand aktueller Forschung in der theoretischen Physik.

Aber: Jede Messung zerstört die Quanteneigenschaften

Die enorme parallele Rechenleistung eines Quantencomputers hat leider einen großen Haken: Sie funktioniert nur solange der Quantencomputer perfekt von seiner Umgebung isoliert ist und die höchst fragilen Qubits ungestört sind. Indem wir am Ende allerdings das Ergebnis des Quantenprogramms aus den Qubits auslesen, tun wir aber genau das. In diesem Moment „zerfallen“ die gleichzeitig vorhandenen Werte und übrig bleibt nur ein einziger Wert der darüber hinaus auch noch zufällig gewählt wird. Dieser Zerfall ist als „Kollaps der Wellenfunktion“ bekannt und ist noch so ein Mysterium der Quantenwelt. Er war der Grund, warum manche Physiker, unter ihnen selbst Albert Einstein, die Quantentheorie zwar schätzten und vorantrieben aber im Grunde ablehnten: „Gott würfelt nicht“.

Und jetzt? Was ist überhaupt gewonnen, wenn am Ende doch nur alles vom Zufall abhängt?

Jetzt kommt das Aber: Die Wahrscheinlichkeiten, mit denen die verschiedenen Werte am Ende ausgelesen bzw. gemessen werden, können wir beeinflussen. Die Kunst eines Quantenprogramms besteht unter anderem darin, die Qubits so zu manipulieren, dass das gesuchte Ergebnis am Ende am Wahrscheinlichsten gemessen wird. Bis dahin, also während er noch von seiner Umgebung isoliert ist, kann dann die enorme Rechenkraft des ungestörten Quantencomputers genutzt werden.

Quantengatter einfach erklärt: Die Bausteine der Quantenprogramme

Auf einem Quantencomputer können wir nicht einfach dieselben Algorithmen laufen lassen, die auf einem herkömmlichen Computer funktionieren. Stattdessen müssen wir für Quantencomputer vollkommen neue und fremdartige Quanten-Algorithmen konstruieren.

Dafür verwendet ein Quantencomputer in jedem Rechenschritt ebenfalls elementare Logik-Bausteine, den „Quantengattern“ (engl. quantum gates). Diese spiegeln allerdings nicht unsere normale, Alltagslogik wieder, sondern die Quantenlogik: Somit heißen die elementaren Bausteine nicht mehr UND, ODER oder NICHT. Stattdessen verwendet ein Quantencomputer Logik-Bausteine die z.B. Hadamard, X, S, T, Z, Controlled NOT oder Controlled Z heißen. Diese Quantengatter ähneln in ihrer Funktionsweise weniger den bekannten Bausteine unserer Alltagslogik als vielmehr Drehungen in einem riesigen abstrakten „Hyperraum“. Die Qubits bilden in ihrer Gesamtheit einen einzelnen Zeiger in diesem Raum, der durch jedes einzelne Quantengatter gedreht wird.

Diese grundlegende Fremdheit gegenüber unserer Alltagslogik ist der Grund, warum ein Quantenprogramm nur für Kenner von Quanten-Algorithmen entziffert und verstanden werden kann.

Für alle Darstellungen von Quantengatter-Schaltungen verwende ich auf „quantencomputer-info“ den exzellenten Quantencomputer-Simulator „Quirk“:

http://algassert.com/quirk

Quirk ist öffentlich erreichbar und kann direkt im Browser ausprobiert werden.

In jedem Bereich der herkömmlichen Programmierung existiert eine lebhafte IT-Szene im Internet, die die weitere Entwicklung stark beeinflusst: Seien es Server, Netzwerke. Datenbanken, Internet, Programmierung, … Die IT-Szene für Quantenprogrammierung sitzt hauptsächlich noch in den Forschungseinrichtungen von Universitäten und hauptsächlich in den Spezialabteilungen von Google, IBM, Microsoft & Co und einigen Startups für Quantencomputer. Seit dem Frühjahr 2018 gibt es zwar das neue Diskussionsforum „Quantum Computing Stack Exchange“ vii, dass sich sehr lebhaft und inhaltlich hochwertig entwickelt. Wichtige Ergebnisse werden trotzdem weiterhin über komplizierte wissenschaftliche Arbeiten veröffentlicht.

Die wohl folgenreichste dieser Veröffentlichung war gerade der Algorithmus von Peter Shor aus dem Jahr 1994, der in der Lage ist, die als sicher geglaubte Datenverschlüsselung im Internet zu knacken. Mittlerweile wurden andere, rasend schnelle und vermutlich auch interessantere Quanten-Algorithmen konstruiert.

Beispiel von der Quirk-Homepage: Schematischer Aufbau des Shor-Algorithmus.

Alle Anbieter von Quantencomputern haben mittlerweile Programmierschnittstellen entwickelt. Über diese Schnittstellen können die Quanten-Programme entweder per Simulator auf dem eigenen PC oder vom eigenen PC aus per Fernsteuerung auf dem Cloud-Quantencomputer des Herstellers ausgeführt. Der folgende Programmauszug zeigt Googles Beispiel zum Shor-Algorithmus in Googles eigener Programmierschnittstelle „Cirq“.

An diesen Beispielen erkennen Sie übrigens auch, wie sehr die Quanten-Programmierung noch in den Kinderschuhen steckt. Alle Programme werden aktuell noch in einer Art „Maschinencode für Quantencomputer“ geschrieben und sind entsprechend schwer zu entziffern. In den kommenden Jahren und Jahrzehnten wird sich die Quanten-Programmierung also auch in dieser Hinsicht weiterentwickeln müssen. Die Softwareentwicklung für herkömmliche Digitalcomputer hat es uns vorgemacht. So sind im Laufe der Zeit immer intuitivere Programmiersprachen entstanden, die den eigentlichen Maschinencode immer besser abstrahieren.

Finde das Pik As! Ein Quanten-Algorithmus einfach erklärt

Um Ihnen einen Eindruck von der Andersartigkeit der Quanten-Algorithmen zu vermitteln, versuchen wir mal folgendes Problem zu lösen:

Wir mischen ein Kartenspiel mit 52 Karten gut durch und breiten die 52 Karten wahllos und verdeckt vor uns aus. Die Aufgabe soll heißen: Finde das Pik As!

Mit unsere Alltagslogik und für jeden herkömmlichen Computer ist der beste Algorithmus für die Lösung sehr einfach und offensichtlich:

  1. Nimm irgendeine Karte
  2. Drehe sie um und prüfe: Ist es das Pik As?
    • Falls ja: Fertig!
    • Falls nein: Lege die Karte zur Seite und beginne wieder bei 1.

Im Schnitt brauchen wir für die Lösung ½ * 52 = 26 Durchläufe. Kein einzelner Mensch und kein einzelner Prozessor-Kern kann diese Aufgabe schneller durchführen!

Der Prozessor eines Quantencomputers kann dies sehr wohl. Wegen des Quantenparallelismus kann sich der Quantencomputer alle Karten gleichzeitig ansehen und sie prüfen. Er kann sich die gesuchte Karte aber leider nicht so einfach herausfischen. Stattdessen muss er die falschen Karten nach und nach „ausblenden“ und das Pik As nach und nach weiter „einblenden“. Am Ende bleibt dann nur noch das Pik As übrig.

Der Algorithmus hierfür ist der berühmte Grover-Algorithmus. Ich werden ihn in einem späteren Beitrag im Detail vorstellen. Dabei werden Sie auch erkennen wie ungemein wichtig und tiefgreifend diese auf den ersten Blick banale Fragestellung ist. Leicht abgewandelt könnte die Aufgabe etwa auch heißen: Finde die kürzeste Route von allen möglichen Routen. Für unser Kartenbeispiel angewandt, funktioniert der Grover-Algorithmus sinngemäß wie folgt:

  1. Überführe alle Karten (als Bitmuster in den Qubits dargestellt viii) in einen gleichmäßig überlagerten Quantenzustand. Dies ist jetzt ein einzelner Zustand an dem alle Karten gleich beteiligt sind. Diesen Zustand können Sie sich als einen einzelnen Zeiger in einem riesigen, abstrakten Raum mit 52 Dimensionen bzw. Richtungsachsen „vorstellen“. Wobei: versuchen Sie es gar nicht erst. Mehr als drei Dimensionen können wir uns sowieso nicht vorstellen: oben/unten, links/recht, vorne/hinten. Jede der 52 Richtungsachsen entspricht einer bestimmten Karte. Das gesuchtes Pik As ist eine dieser Achsen. Unser überlagerter Zustand zeigt vollkommen schräg in diesen Raum hinein und ein bißchen in jede der 52 Richtungen.
  2. Der Quantencomputer prüft jetzt in welche Richtung das Pik As liegt. Diese Prüfung ist im Prinzip ein einfaches Unterprogramm, man nennt sie trotzdem etwas geheimnisvoll: Das „Orakel“. Bildlich gesprochen dreht der Quantencomputer mithilfe des Orakels den Zeiger in die Pik As – Richtung. Er kann ihn aber leider nur um in einen kleinen Winkel drehen. Dieser Winkel ist umso kleiner, je mehr Karten geprüft werden müssen. Der Zeiger ist nach der Prüfung keine gleichmäßige Überlagerung mehr. Er zeigt jetzt etwas mehr in die Pik As – Richtung als in die Richtungen der anderen Karten.
  3. Schritt 2. müssen wir jetzt mehrmals hintereinander ausführen. Der Wissenschaftler Lov Grover hat 1996 nachgewiesen, dass der Zeiger nach 52 7.2 Prüfungen in die Richtung des Pik As gedreht wurde. Nach 7 Prüfungen messen wir also die Qubits aus und erhalten die Bit-Darstellung des Pik As.

Folgendes Beispiel zeigt den Grover-Algorithmus für zwei Qubits.

Quantenkomplexität einfach erklärt

Vor einem halbem Jahrhundert begannen Computerwissenschaflter damit, Probleme in Klassen zu unterteilen, je nachdem wie schwierig es ist eine Lösung zu finden. Die Probleme, die relativ effektiv mit einem herkömmlichen Computer gelöst werden können, nannten sie P-Probleme.

Als die ersten Konzepte für Quantencomputer erarbeitet wurden, fügte man die Problem-Klasse BQP hinzu. Dies sind die Probleme, die relativ effektiv mit einem Quantencomputer gelöst werden können.

Mittlerweile weiss man, dass es einen grundlegenden Unterschied zwischen diesen beiden Klassen gibt. Ein Quantencomputer ist prinzipiell in der Lage wesentlich mehr Probleme effektiv zu lösen als ein herkömmlicher Computer. Ein Beispiel hierfür ist die Zerlegung in Primzahlen mit dem Shor-Algorithmus.

Dass aber selbst ein Quantencomputer seine Grenzen hat, wird im folgenden Diagramm deutlich. Es zeigt den Zusammenhang der wichtigen Problem-Klassen, den die meisten Computerwissenschaflter aktuell vermuten:

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

Fußnoten

ii https://www.scottaaronson.com/blog/?p=208: Eine allgemeinverständliche Beschreibung des Shor-Algorithmus auf Scott Aaronsons Blog. Scott Aaronson ist einer von mehreren namhaften Computerwissenschafltern, die mittlerweile im Bereich der Quantencomputer forschen.

iii https://www.youtube.com/watch?v=O_RlktWkSdg: Vortrag von Matthias Troyer (mittlerweile bei Microsoft angestellt) u.a. „Transforming Machine Learning and Optimization through Quantum Computing“

iv https://arxiv.org/abs/1203.5813: wissenschaftliche Arbeit von John Preskill „Quantum computing and the entanglement frontier“

v http://cds.cern.ch/record/722038/files/0403048.pdf: Aufsatz von G. Florio, D. Picca „Quantum implementation of elementary arithmetic operations“. Falls Sie sich den Aufsatz ansehen erkennen Sie auch direkt wie absolut anders ein Quanten-Algorithmus aussieht. Das liegt u.a. an den Quantengattern.

vi Tatsächlich gilt das Superpositionsprinzip auch in der Elektrodynamik und somit auch in der Elektronik. In den herkömmlichen Computern wird dies aber gerade gewollt ausgehebelt, um das digitale Verhalten der herkömmlichen Computer überhaupt erst zu ermöglichen. Möglich machen dies ausgerechnet die nichtlinearen An/Aus-Schaltelemente auf Basis der Quantentechnologie: Die Transistoren. Diese sind tatsächlich nur in einem reinen Quantensystem linear.

viii Natürlich kann ein Quantencomputer nicht mit Karten arbeiten. Stattdessen weisen wir jeder Karte ein bestimmtes Bit-Muster aus 0en und 1en zu. Entsprechend heißt dann die richtige Aufgabe: „Finde das Bit-Muster für das Pik As in den Qubits“. Die gleichmäßige Überlagerung aller Bit-Muster ähnelt dadurch dem wahllosen und verdecktem Ausbreiten der Spielkarten. Unser einfaches Beispiel mag auf den ersten Blick unlogisch aussehen, weil wir nach einem Bit-Muster suchen, das wir vorher festgelegt haben. Bedenken Sie aber, dass man den gleichen Quanten-Algorithmus z.B. auch dafür verwenden kann, um die kürzeste Route aus allen möglichen Routen zu suchen.

Die Quanten-Überlegenheit

<<     >>

Die Quanten-Überlegenheit ist der nächste große Meilenstein in der Entwicklung aktueller Quantencomputer. Die Quanten-Überlegenheit soll den Punkt in der Computer-Geschichte markieren, an dem ein Quantencomputer erstmals nachweislich alle herkömmlichen Supercomputer für ein bestimmtes Problem überflügelt.

John Preskill vom California Institute of Technology (Caltech), einer der führenden Wissenschaftler in der Quantencomputer-Szene, hatte die Schallmauer für die Quanten-Überlegenheit bzw. die „Quantum Supremacy“ 2012 berechnet i. Ab einer Quantencomputergröße von 49 oder 50 Qubit sollte ein Quantencomputer in der Lage sein gewisse Berechnungen schneller auszuführen als jeder herkömmliche Supercomputer.

Preskill gab aber keine Vorgaben, wie nützlich diese Berechnungen für uns sein müssten. Stattdessen legte er die Grenze der Quanten-Überlegenheit wohl auch deshalb fest, um der Quantencomputer-Szene ein Nahziel zu geben. Und so gesehen hatte er damit auch Erfolg: Die Tech-Riesen Google, IBM, Intel & Co, sowie D-Wave stehen aktuell im Wettrennen, wer als erster die prestigeträchtige Quanten-Überlegenheit erreicht hat.

Für Google war der Nachweis für das Jahr 2017 fest angepeilt, allerdings verfehlten sie dieses Ziel. Alle Zeichen deuten darauf hin, dass der Nachweis der Quanten-Überlegenheit trotzdem kurz bevor steht. Google, Intel und IBM haben jeweils eigene „Quanten-Überlegenheit-fähige“ Quantencomputer im Testbetrieb.

Bei dem Nachweis der Quanten-Überlegenheit geht es zunächst eher um ein „Proof of Concept“. Ein Beweis, dass die prinzipielle Überlegenheit der Quantencomputer nicht nur auf dem Papier existiert, sondern real erzielt werden kann. Ein besonders vielversprechendes Forschungsgebiet hierfür sind chaotische Quantensysteme.

Klassische chaotische Systeme, wie das Wetter, gehören zu den rechenintensivsten Problemen überhaupt. Chaotische Quantensysteme toppen dies noch: Selbst kleine Systeme können nicht mehr mit herkömmlichen Supercomputern simuliert werden, weil das Problem nicht vereinfacht werden kann, wie es bei anderen Quantenproblemen teilweise möglich ist.

Im Gegensatz dazu sind Quantencomputer für das Problem ein natürliches Terrain. Besonders die Gruppe um John Martinis bei Google steckt große Erwartungen in die Ausarbeitung ii. Sie nennen es: Sampling von Zufallsschaltungen. Das Interesse erscheint auf der einen Seite arg akademisch. Auf der anderen Seite wäre der Nachweis, dass die Quanten-Überlegenheit nicht nur auf dem Papier existiert, ein echter Meilenstein. Vergleichbar vielleicht mit dem experimentellen Nachweis der Bellschen Ungleichungen 1982, die zum ersten Mal bewiesen, dass die Quantenmechanik nicht mit unentdeckten, klassischen Mitteln erklärt werden kann.

Das Interesse an dem Sampling-Thema bekam 2018 durch den namhaften Computerwissenschaftler Scott Aaronson von der University of Texas eine ungewöhnliche Wendung. Aaronson überraschte die Fachwelt mit einem Artikel über das Sampling von Zufallsschaltungen iii. Darin skizziert er ein Protokoll für „quantenzertifizierte“ Zufallszahlen, das speziell für die erste Generation von Quanten-Überlegenheit-fähigen Quantencomputer zugeschnitten ist.

Zufallszahlen sind für viele Algorithmen und für viele Bereiche in der Informatik essentiell wichtig: Besonders für die Kryptographie. Nicht zuletzt im NSA-Skandal wurde offensichtlich, dass kompromittierte Zufallszahlen für die Übertragungssicherheit ein reales Problem sind. Quantenzertifizierte Zufallszahlen besitzen die erstaunliche Eigenschaft, dass diese nachweislich echte Zufallszahlen sind, selbst wenn das erzeugende System unsicher und der Herausgeber nicht vertrauenswürdig ist.

John Preskill selbst, der die Quanten-Überlegenheit-Grenze 2012 erdacht hatte, wird gerne als „geläuterter Teilchenphysiker“ bezeichnet: Früher beschäftigte er sich mit der Physik der Teilchenbeschleunigern und der Kosmologie. Einem breiteren Publikum wurde er bekannt durch eine berühmte Wette mit dem legendären Physiker Stephen Hawking über das Informationsparadoxon von Schwarzen Löchern. Eine Wette, die er übrigens Jahre später gewann. So erhielt er von Hawking eine Ausgabe von „Total Baseball, The Ultimate Baseball Encyclopedia“ iv.

Laut Preskill gibt es in der Physik diverse Grenzbereiche: Die Stringtheorie, die Physik der Gravitationswellen, die Physik der schwarzen Materie und der schwarzen Energie im Weltall, die Physik der allerkleinsten Elementarteilchen und deren Grundkräfte. Preskill erkannte um die Jahrtausendwende, dass sich ein weiteres Grenzgebiet in der Physik abzeichnete: Die Quantenkomplexität. Also die Art wie Information in komplex verschränkten Quantenzuständen kodiert ist v. Die Quantenkomplexität manifestiert sich in den Quantencomputern und wird durch diese tatsächlich greif- und kontrollierbar.

So sattelte Preskill vor gut 20 Jahren auf die Quanteninformationstheorie um und ist seitdem eine der treibende Kräfte und ein Aushängeschild der Quantencomputer-Szene. Passenderweise heißt seine Position am Caltech „Richard P. Feynman Professor of Theoretical Physics“. Somit ist Preskill quasi auch der offizielle Nachfolger des legendären Urvaters der Quantencomputer.

i https://arxiv.org/abs/1203.5813: wissenschaftliche Arbeit von John Preskill „Quantum computing and the entanglement frontier“

ii https://arxiv.org/abs/1608.00263: wissenschaftliche Arbeit von John Martinis et al „Characterizing Quantum Supremacy in Near-Term Devices“

iii https://simons.berkeley.edu/talks/scott-aaronson-06-12-18: Vortrag „Quantum Supremacy and its Applications“ von Scott Aaronson zu seinem Protokoll für „quantenzertifizierte“ Zufallszahlen

v https://www.youtube.com/watch?v=MuklWupCvWU: Vortrag von John Preskill “Quantum Information and Spacetime”

Welche Quantencomputer gibt es jetzt schon?

<<     >>

Im Folgenden geben ich Ihnen einen Überblick, welche Quantencomputer bereits heute schon existieren und welche konkreten Pläne Industrie und Forschung für die Zukunft verfolgen. Diesen Artikel aktualisiere ich regelmäßig und halte Sie über die aktuellen Entwicklungen in der Quantencomputer-Industrie auf dem Laufenden.

D-Waves adiabatischer Quantencomputer

DWave Quantencomputer

Bild-Urheber: D-Wave Systems, Inc., Bild-Lizenz https://creativecommons.org/licenses/by/3.0/deed.de, unverändert

D-Wave präsentierte im Jahr 2011 also seinen ersten Quantencomputer mit sage und schreibe 128 Qubits! Zur Erinnerung ist hier nochmal der Vergleich zwischen Qubits und klassischen Bits aus meinem letzten Aritkel:

  • 1 Qubit entspricht 2 herkömmlichen Bits
  • 2 Qubits entsprechen 4 herkömmlichen Bits
  • 10 Qubits entsprechen 16 herkömmlichen Kilo-Byte
  • 45 Qubits entsprechen in etwa der Speichergröße des größten aktuellen, herkömmlichen Supercomputers
  • 50 Qubits, die vermutete „Quanten-Überlegenheit“-Grenze

Die Nachricht über D-Waves Quantencomputer sah also auf den ersten Blick so aus, als wäre damit der Durchbruch erzielt worden. Was in diesen Nachrichten etwas unterging, aber was allen Kennern der Thematik klar war, war Folgendes: Der Quantencomputer von D-Wave-Systems war und ist streng genommen „nur“ ein Quanten-berechnendes System für spezielle Zwecke. Es nutzt zwar auch die Quantenmechanik mittels Qubits für Berechnungen, es ist aber kein sogenannter „universeller“ Quantencomputer mit dem die üblichen Quantenprogramme ausgeführt werden können. Insbesondere nicht der Shor-Algorithmus oder der Surface-Code für die Quantenfehlerkorrektur, die ich beide in den letzten Beiträgen kurz vorgestellt habe. Der Quantencomputer von D-Wave-Systems ist für Optimierungsaufgaben vorgesehen, also einem sehr wichtigen Aufgabengebiet für Computer. Der Computer von D-Wave ist ein sogenannter „Quantum Annealer“ (oft auch etwas ungenauer als „adiabatischer Quantencomputer“ bezeichnet). Er verlagert das Prinzip der sogenannten „simulierten Abkühlung“ (engl. simulated annealing) in die Quantenwelt. i ii

Das Prinzip der „simulierten Abkühlung“ ist eine ziemlich brillante Rechentechnik für herkömmliche Computer, die insbesondere in der künstlichen Intelligenz eingesetzt wird. Interessanterweise stammt die Vorlage dazu wiederum aus der Physik bzw. der Metallurgie: Durch das Erhitzen eines Materials und späterer kontrollierter Abkühlung werden die Eigenschaften des Ausgangsmaterials (z.B. die Festigkeit) optimiert: Das Material kann aus einem Zustand mit schlechtem, lokalem Optimum in einen Zustand mit gutem, globalem Optimum gelangen. Dabei springt es bei diesem Vorgang nach und nach über alle lokalen Täler und findet irgendwann den höchsten Berg, also das globale Optimum.

 


Quelle: https://de.wikipedia.org/wiki/Datei:Hill_Climbing_with_Simulated_Annealing.gif

Die Quantenversion dieses Prinzips simuliert im Gegensatz dazu keine langsame Abkühlung. Stattdessen startet ein adiabatischer Quantencomputer zunächst auf der „grünen Wiese“ und schaltet das tatsächliche Optimierungsproblem, also die eigentliche Berg-Tal-Charakteristik, langsam dazu. Ein adiabatischer Quantencomputer überbrückt die Optimierungstäler ebenfalls. Allerdings führt er keine thermischen Sprünge aus, sondern „tunnelt“ durch Quantenfluktuationen in das globale Optimum iii. Ein „Quantum Annealer“ wiederum ist ein adiabatischer Quantencomputer unter realen Bedingungen (z.B. unter Temperatureinflüssen und nicht perfekt isoliert). Da sich hierfür noch kein deutscher Begriff durchgesetzt hat, verwende ich übrigens lieber den üblichen englischen Begriff.

Um dieses Verhalten in seinem Quantenrechner abzubilden, benutzt D-Wave nicht den universellen Satz an Logikbausteinen, um die Qubits miteinander zu verschalten (also z.B. Hadamard, X, Y, Z, CNOT). Stattdessen verwendet D-Wave einen analogen Satz von Quantenbausteinen, die gerade für die adiabatische Quantenprogrammierung notwendig sind iv. Interessanterweise wurde mittlerweile in der Theorie nachgewiesen, dass auch mit den Logikbausteinen für adiabatische Quantenprogrammierung ein universeller Quantencomputer simuliert werden kann. Dies gilt allerdings nur unter perfekten Bedingungen. Die realen „Quantum Annealer“ sind hierzu wohl nicht in der Lage.

Aus technischen Gründen kann D-Wave noch nicht alle Qubits miteinander verschalten. Stattdessen ordnet D-Wave die Qubits in einem sogenannten „Chimera-Graphen“ an, in denen jedes Qubit mit insgesamt 6 Nachbar-Qubits verschaltet werden kann v. Diese Einschränkung reduziert die Anzahl der tatsächlich verfügbaren Qubits in der Praxis teils deutlich. Tatsächlich gilt dieser Sachverhalt für alle derzeitigen Quantencomputer. Der Quantencomputer-Szene fehlt derzeit noch ein Datenbus für Qubits. Bei adiabatischen Quantencomputern, wie D-Waves Quantencomputer, fällt dies aber besonders auf.

Im Laufe der Jahre hat D-Wave seine Palette an „Quantum Annealer“ erweitert. Mittlerweile bieten sie ein Modell mit 2048 Qubits an. Google, die NASA und Lockheed haben bisher D-Wave-Modelle im Werte von mehreren Millionen Dollar gekauft. Interessanter ist für einen größeren Kundenkreis wohl eher das Cloud-Angebot von D-Wave vi.

Um eigene Quantenprogramme zu erstellen bietet D-Wave eine spezielle Software-Palette an. Für die größte Flexibilität gibt es eine „SAPI“, die über Standardwerkzeuge für herkömmliche Computer angesprochen werden kann (z.B. über RESTful Services, Python, C/C++). Ein Beispiel-Programm für die Benutzung der „SAPI“ finden Sie z.B. hier.

Aufbauend darauf stellt D-Wave das Programm „qbsolv“ bereit. Sie können „qbsolv“ als Open Source Software von GitHub vii herunterladen. „qbsolv“ zerlegt ein allgemeines „QUBO“-Optimierungsproblem automatisch in kleinere Häppchen und bildet diese auf die Chimera-Struktur des jeweils verwendeten Quantenrechners ab. In mehreren Durchläufen versucht „qbsolv“ das Ergebnis immer weiter zu verbessern viii.

Um das Potential der eigenen Hardware weiter auszuloten hat D-Wave die Expertin für Experimentelle Algorithmen Catherine McGeoch angestellt. Sie untersucht, ob die aktuellen Quantencomputer von D-Wave bereits die „Quanten-Überlegenheit“ nachweisen. Tatsächlich gestaltet sich dieser Nachweis schwieriger als vermutet. Die Quantenprogramme der Testaufgaben erreichen erstaunlich schnelle Näherungswerte für die besten Lösungen. Diese verbessern sich aber nicht mehr, wenn die Quantenprogramme länger laufen. D-Wave vermutet, dass dies ein Zeichen dafür ist, dass die Qubits noch nicht perfekt isoliert sind, und die Logikbausteine noch kleine Fehler aufweisen könnten. ix

Ähnliche Untersuchungen führten Google und die NASA durch, nachdem sie ihren D-Wave Quantencomputer gekauft hatten. Im Jahr 2015 veröffentlichten sie ihr viel beachtetes Resultat: Für sehr spezielle Optimierungsaufgabe gelangte der Quantencomputer von D-Wave 100 Millionen mal schneller zum Ergebnis als ein leistungsstarker herkömmlicher Computer! x xi

Diese Ergebnisse wurden aber später kritisiert xii xiii. Tatsächlich gibt es Stimmen, die das Konzept von D-Wave grundsätzlich anzweifeln, da in der Theorie noch nicht bewiesen wurde, ob die „Quantum Annealer“ wirklich einen prinzipiellen Vorteil gegenüber herkömmlichen Supercomputern haben.

Das Wettrennen um den Nachweis der „Quanten-Überlegenheit“ ist also noch offen xiv.

Googles supraleitender Quantencomputer „Bristlecone“

2013 gründete Google das Quantum AI Lab. Das Quantum AI Lab ist ein Team, das von dem langjährigen Google-Mitarbeiter Hartmut Neven geführt wird. Es sollte zunächst die Möglichkeiten untersuchen, D-Waves neue Hardware für die künstliche Intelligenz zu nutzen. xv

Als sich abzeichnete, dass der Quantencomputer von D-Wave noch gewisse Einschränkungen hatte, beschloss Google einen eigenen, universellen Quantencomputer zu bauen.

2014 startete das Google Quantum AI Lab eine Koorperation mit dem bekannten Physiker John Martinis von der University of California, Santa Barbara. Er sollte den Bau des Quantencomputers leiten.

Anders als D-Waves adiabatischer Quantencomputer ist Googles Quantencomputer in der Lage, jedes Quantenprogramm auszuführen. Solche universellen Quantencomputer laufen auch unter weiteren Namen: „Gate-based Quantencomputer“, „Circuit-Quantencomputer“, „Digitaler Quantencomputer“. Alle Bezeichnungen meinen dasselbe.

John Martinis ist einer der führenden Wissenschaftler in der Konstruktion von Qubits auf Basis der Supraleiter-Technologie. xvi Die Supraleiter-Technologie ist einer der zwei aussichtsreichsten Kandidaten um verlässliche Quantencomputer zu bauen. xvii

Diese gründen letztendlich auf einfachen integrierten Schaltkreisen, die somit auf einen herkömmlichen Chip platziert werden können. Die Schaltkreise werden enorm heruntergekühlt bis fast zum absoluten Temperatur-Nullpunkt und erhalten so supraleitende Quanteneigenschaften. Dort fließt der Strom widerstandsfrei gleichzeitig in beide Umlaufrichtungen. In dem man bewusste Lücken in jeden Schaltkreis einbaut, sogenannte „Josephson Junctions“, ist es möglich den Quantenschaltkreis zu einem einzigen Qubit zu reduzieren.

Über ausgeklügelte Bestrahlungen im Mikrowellen-Bereich werden die Supraleiter-Qubits so manipuliert, das man am Ende die Quantengatter Hadamard, X, Y, Z und CNOT erhält.

Googles Labor hat unter John Martinis Leitung seit einiger Zeit Erfahrungen mit einem 9-Qubit-Quantencomputer gesammelt. Dort sind die Qubits wie an einer Perlenschnur aufgereiht. Entsprechend können nur die beiden direkt benachbarten Qubits miteinander verschaltet werden. Googles und Martinis Ziel ist es die Technik hinter dem 9-Qubit-System zu größeren Quantencomputer auszubauen.

Google hatte für Ende 2017 fest das prestigeträchtige Ziel der „Quanten-Überlegenheit“ angepeilt. Also dem ersten Quantencomputer, der in der Lage ist gewisse Berechnungen schneller auszuführen, als jeder herkömmliche Supercomputer. Google konnte das ehrgeizige Ziel zwar nicht halten, gab aber bekannt, dass ein „Quanten-Überlegenheit-Quantencomputer“ mit dem Namen „Bristlecone“ seit Anfang 2018 im Testbetrieb sei. xviii

Im März 2018 überraschte Google auf der jährlichen Konferenz der American Physical Society mit näheren Informationen zu Bristlecone. xix

Google benennt die Anzahl von Qubits in Bristlecone mit 72 Qubits!

Dies würde einen gigantischen Entwicklungssprung gegenüber anderen Quantencomputern bedeuten. Die Speichergröße eines 72-Qubit Quantencomputers entspricht dem 100 millionenfachen des größten herkömmlichen Supercomputers!

Ein Fernziel für Quantencomputer ist es, dass alle Qubits über einen Quanten-Datenbus miteinander verschaltet werden können. Dies erreicht auch Google mit Bristlecone noch nicht. Alle aktuelle, universelle Quantencomputer haben die gemeinsame Einschränkung, dass nur die nächstbenachbarten Qubits miteinander verschaltet werden können. Um auch entferntere Qubits effektiv miteinander rechnen zu lassen, sind zusätzlich Tauschoperationen notwendig (auch „Swaps“ genannt), die die Quantenprogramme zusätzlich aufblähen und verkomplizieren xx. In Googles Bristlecone sind die Qubits nicht mehr in Reihe, sondern quadratisch angeordnet. Dieses Design verbessert zumindest die Verschaltung der Qubits untereinander.

Google konnte nach eigenen Angaben die niedrigen Fehlerraten des 9 Qubit-Quantencomputers auch in Bristlecone beibehalten. Die Quanten-Theoretiker des Tech-Riesens haben ein eigenes generisches Benchmarksystem entwickelt, über den die Qualität des Quantencomputers überprüft werden kann. Außerdem soll Bristlecone in der Lage sein den Surface-Code zur Quanten-Fehlerkorrektur zu testen.

Nach einer generellen Testphase wird Google Bristlecone in einem Cloud-Angebot bereitstellen. Martinis geht davon aus, dass sich die verwendete Technologie auf bis zu 1000 Qubits skalieren lässt! Dabei weist er immer wieder auf weitere Knackpunkte hin: Die Qualität der Qubits, d.h. die Anfälligkeit für Rechenfehler, wird für alle Quantencomputer am Ende eine ebenso große Rolle spielen, wie die Anzahl der Qubits selbst. Falls in den zukünftigen Cloud-Angeboten die Rechenzeit auf den Quantencomputern den Kunden in Rechnung gestellt wird, dürfte überdies auch die Schnelligkeit der Quantengatter, also der Logikbausteine, wichtig werden. Eine weitere praktische Einschränkung wird in Zukunft das Einrichten des Quantenprogramms auf dem Quantencomputer sein: Wir sind es gewohnt, dass wir in herkömmlichen Cloud-Angeboten direkt mit den Servern der Anbieter kommunizieren. Das ist für Quantencomputer zunächst alles andere als selbstverständlich. xxi xxii

Neben der Weiterentwicklung der eigenen Hardware, untersucht Googles Quantum AI Lab weiterhin die Anwendungsmöglichkeiten von heutigen und von zukünftigen Quantencomputern. xxiii xxiv Ein Bereich, den Google softwaretechnisch und auch personell forciert ist die Simulation von chemischen Prozessen mittels Quantencomputern xxv. Dafür hat Google mit „Cirq“ eine Erweiterung für die beliebte Programmiersprache ein Python veröffentlicht, über die umfangreiche Quantenprogramme erstellt werden können xxvi. Ein weiterer geplanter Eckpfeiler von Googles Softwareportfolio sind Quantenalgorithmen für Optimierungsaufgaben. Beide diese Eckpfeiler teilen die Eigenschaft, dass sie Quanten-klassische „Hybrid-Algorithmen“ sind. Über Näherungsverfahren werden dabei schrittweise die Stärken von sowohl Quantencomputern als auch klassischen Computern ausgenutzt. Diese Verfahren haben den bestechenden Vorteil, dass sie anscheinend immun gegen die Fehlerraten der aktuellen Quantencomputern sind.

IBMs universeller Quantencomputer

IBM ist der Tech-Riese, der von Anfang stark im Bereich Quantencomputer engagiert war. Was den zählbaren Erfolg angeht, war IBM z.B. Google bis jetzt eine ganze Körperlänge voraus. Das würde sich allerdings wohl ändern, wenn Googles Bristlecone verfügbar ist. Wir können also gespannt sein, wie das Wettrennen weitergeht …

Bereits im Mai 2016 startete IBM ein überraschendes Cloud-Angebot: In der IBM Quantum Experience stellte IBM den eigenen 5 Qubit Quantencomputer für die Öffentlichkeit zur Verfügung.

https://quantumexperience.ng.bluemix.net/

Wie Googles Quantencomputer ist IBMs Quantencomputer ein universeller Quantencomputer. IBMs Quantencomputer basiert ebenfalls auf der Supraleitertechnologie. Als Schnittstelle zum Anwender dient ein grafischer „Quantum Composer“, über den Quantenprogramme erstellt werden können. Mittlerweile bietet IBM zusätzlich die Entwickungsungebung Qiskit, ebenfalls auf Basis von der Programmiersprache Python, an xxvii. Die Quantenprogramme der Cloud-Nutzer stellt IBM in eine Warteschlange, die nach und nach auf der Hardware ausgeführt wird. Mittlerweile benötigt man dafür allerdings ein Credit-Konto. Wem das zu umständlich ist, kann die Quantenprogramme zunächst auf einem 20 Qubit-Simulator ausführen.

Die Quantencomputer auf der IBM Quantum Experience haben sich seit der ersten Veröffentlichung auch weiterentwickelt. Ein 20 Qubit-Quantencomputer, auf dem die Qubits quadratisch angeordnet sind, steht einem engeren Anwenderkreis zur Verfügung. Ein etwas älteres Modell mit 16 Qubits, die in Reihe angeordnet sind, steht der Allgemeinheit zur Verfügung. Ende 2017 erklärte IBM, dass ein neuer Quantencomputer mit 50 Qubit in Arbeit ist. Auf diesem wäre also die Quanten-Überlegenheit, zumindest theoretisch, ebenfalls nachweisbar.

Die Infrastruktur von IBM ist gut dokumentiert und insbesondere bietet IBM einen sehr guten Userguide an, der aber leider einiges an Vorwissen in Linearer Algebra und komplexen Zahlen voraussetzt. Mittlerweile gibt es in einem eigenen Forum eine erste Community. Eine Vielzahl von Beispielprogramme stellt IBM über „Github“, dem frei zugänglichen Cloudspeicher für beliebige Software-Projekte, zur Verfügung. Hierbei setzt IBM von Anfang an auf „Jupyter Notebook“, dass sich in der Wissenschaftswelt immer mehr zum Standard entwickelt xxviii. IBM wirbt damit, dass eine Reihe von wissenschaftlichen Veröffentlichungen über die IBM Quantum Experience entstanden sind.

Microsofts topologischer Quantencomputer

Microsoft ist ebenfalls schon seit Jahren engagiert im Bereich Quantencomputer. Für seine eigene Hardware hat Microsoft sich die Messlatte sehr, sehr hoch gehangen. Microsoft versucht direkt einen Quantencomputer der nächsten oder übernächsten Generation zu konstruieren: Einen topologischen Quantencomputer. Die topologischen Quantencomputer wurden erst 1997 von dem theoretischen Physiker Alexei Kitaev vorgeschlagen. Also jenem Kitaev, der unter anderem durch seinen topologischen Surfacecode für die Quanten-Fehlerkorrektur bekannt ist.

Sie ahnen es wahrscheinlich: Ein topologischer Quantencomputer besitzt eine eingebaute Quanten-Fehlerkorrektur. Eine Eigenschaft, die andere im Bau befindliche Quantencomputer auf viele Jahre nicht besitzen werden. Das Herzstück der topologischen Quantencomputer sind sogenannte „Majorana-Quasiteilchen“, mit denen man ein einzelnes Qubit räumlich in die Länge ziehen kann. Die Quanteninformation in einem Qubit ist damit nicht mehr in einem einzelnen Punkt im Raum lokalisiert und kann nur noch über koordinierte Aktionen auf ganze Raumbereiche verändert oder ausgelesen werden. Das ganze Konzept der topologischen Quantencomputer ist so neu, dass die ersten Hinweise für Majorana-Quasiteilchen vor gerade mal zehn Jahren gefunden wurden.

Für das sehr ambitionierte Ziel hat Microsoft unter anderen den wohl namhaftesten Wissenschaftler auf dem Gebiet angeheuert: Michael Friedmann, US-amerikanischer Mathematiker und Träger der Fields Medaille, also jenem „Nobelpreis für Mathematik“. Im Gegensatz zum Nobelpreis, wird die Fields Medaille nur alle vier Jahre verliehen. Friedmann hat seine großen Erfolge in dem Bereich der Topologie erzielt und fing um das Jahr 2000 an, sich mit dem Thema topologische Quantencomputer zu befassen.

https://www.microsoft.com/en-us/quantum/

Es ist nicht leicht Details über den aktuellen Entwicklungsstand von Microsofts Hardware zu erfahren. Aktuell testet Microsoft mit Expertenteams, die über den gesamten Globus verteilt sind, geeignete Materialien für die topologischen Qubits. Es ist schon erstaunlich, dass Microsoft solch eine technologische Wette mit ungewissen Erfolgsaussichten eingeht. Microsoft wird damit über viele Jahre den anderen Tech-Riesen hinterherhinken. Das würde sich aber schlagartig ändern, falls Microsoft sein Ziel erreichen sollte. Dies würde Microsoft vermutlich sofort an die Spitze der Quantencomputer-Szene katapultieren. xxix xxx

Parallel zur der Entwicklung des eigenen Quantencomputers verstärkt Microsoft, genauso wie Google und IBM, die Bemühungen die Infrastruktur und Anwendungsmöglichkeiten von Quantencomputern weiter auszubauen. Dazu stellte Microsoft mehrere namhafte Forscher für Quantenalgorithmen ein.

Im Herbst 2017 veröffentlichte Microsoft die Erweiterung „Q#“ xxxi für seine bekannte Programmierumsprache „C#“ mit denen Quantenprogramme erstellt und auf herkömmlichen Computern simuliert werden können. Diese lief zunächst nur auf Microsoft‘s Entwicklungsumgebung „Visual Studio“ und damit nur unter Windows. Mittlerweile entwickelt sich Microsoft aber immer mehr weg von dem reinen Windows-Anbieter zu einem Cloud-Anbieter. Seit Anfang 2019 gibt es deshalb „Q#“ und „C#-core“ auch unter Mac OS und Linux. Auch Microsoft setzt dabei ebenso auf Python und Jupyter Notebook. Seit Mai 2019 ist Q# sogar Open Source. Microsofts Cloud-Umgebung „Azure“ wird übrigens derart unterstützt, dass dort Simulationen mit noch mehr Qubits ausgeführt werden können.

Auch Microsoft baut beständig sein Softwareportfolio für Quantenprogramme aus. Wie bei Google ist auch hier die Quanten-Chemie ein Schwerpunkt.

Neben diesen umfangreichen Bibliotheken sind im Microsoft Quantum Development Kit auch eine Vielzahl von Beispielprogrammen enthalten, die aber wieder einiges an Vorwissen im Bereich Quantencomputing voraussetzen: Im „Hello World“-Einsteigerprogramm setzt Microsoft beispielsweise ein bekanntes Protokoll für die Quantenteleportation um xxxii xxxiii.

Ohne gute Vorkenntnisse sind diese Programme also ziemlich nichtssagend.

Alibabas Quantencomputer in der Cloud

Im März 2018 betrat der chinesische Tech-Riese Alibaba überraschend den Quantencomputer-Ring. Alibaba verblüffte die Öffentlichkeit, dass der eigene supraleitende 11-Qubit Quantencomputer ab sofort öffentlich verfügbar ist xxxiv xxxv. Bis dahin brachte man Alibaba eher nicht mit Quantencomputern in Verbindung. Ein Grund für den schnellen Erfolg wird hier wohl auch die Kooperation mit der der Chinesischen Akademie der Wissenschaften sein. Alibaba kommt damit zugute, dass China sich in einem gewaltigen Kraftakt gerade zu einer digitalen Großmacht aufschwingt. Im Rahmen dieser Maßnahme fördert China die Technologien für Quanteninformation mit einem Budget von 10 Milliarden Dollar xxxvi!

Rigetti Computing‘s Quantencomputer: Ein David unter vielen Goliaths

In 2013 verließ Chad Rigetti das Quantencomputer-Team bei IBM und gründete Rigetti Computing. Über mehrere Finanzierungsrunden konnte er genug Investoren für seine Pläne für einen neuen Global Player im Quantencomputer-Markt gewinnen. Mittlerweile besitzt die Firma ein üppiges Kapitalpolster. Im Juni 2017 startet Rigetti Computing das eigene Quantencomputer-Cloudangebot xxxvii. Der aktuelle universelle Quantencomputer von Rigetti besitzt 14 Qubits auf Supraleiter-Basis.

Im August 2018 veröffentlichte Rigetti Computing seine Pläne, in den nächsten zwölf Monaten einen 128-Qubit Quantencomputer funktionsfähig zu haben xxxviii.

Wie alle anderen Quantencomputer-Konkurrenten richtet sich Rigetti als „Fullstack“-Anbieter aus: Also als ein Anbieter der von der Hardware über die Cloudangebote und den Programmierschnittstellen bis hin zu Highlevel-Anwendungen die gesamte Quantencomputer-Palette anbietet. Auch Rigetti setzt als Programmierschnittstelle auf eine Python-API mit dem Namen „Forest“. Als Anwendungsbeispiel für ihr Komplettpaket geben sie etwa die Simulation von Bindungsenergien in Atomenkernen an xxxix.

Intel, EU, Xanadu, Softwareanbieter: Noch weitere Wettstreiter sind in den Startlöchern …

Anfang 2018 kündigten IBM und Google also an einen Quantencomputer im Testbetrieb zu haben, der fähig sein könnte die Quanten-Überlegenheit nachzuweisen. Etwa zeitgleich kam dieselbe Meldung auch von Intel xl. Die Entwicklung Intels erfolgt in Koorperation mit der TU Delft in den Niederlanden. Seit dieser ersten Meldung ist es allerdings ziemlich ruhig geworden um Intels Quantencomputer-Ambitionen.

Wesentlich mehr Aufmerksamkeit, zumindest hierzulande, bekam das Flagship Programm der EU xli. Im Rahmen des European Quantum Flagship fördert die EU seit Oktober 2018 die Quanten-Technologien mit 1 Milliarde Euro in den nächsten 10 Jahren. Zu diesen Technologien zählen Quantensensoren, die Quantenkommunikation … und ein Quantencomputer xlii:

Zehn europäische Partner aus Forschung und Industrie haben sich im Projekt OpenSuperQ xliii zusammengeschlossen. Ziel des Projektes ist die Entwicklung eines öffentlich zugänglichen Quantencomputers mit 100 Qubits bis Ende 2021, ebenfalls auf Supraleiter-Basis. Das Team – mit Partnern aus Deutschland, Spanien, Schweden, Schweiz und Finnland – wird vom dem Physiker Frank Wilhelm-Mauch von der Universität des Saarlanders geführt. Der Quantencomputer OpenSuperQ selbst soll am Ende im Forschungszentrum Jülich stehen.

Einen ganz anderen und sehr spannenden Ansatz verfolgt die kanadische Startup-Firma Xanadu xliv. Mittlerweile haben Sie sicher erkannt, dass supraleitende Qubits der Standard für die aktuellen Quantencomputer sind. Die Quantenprozessoren sind dabei also integrierte Schaltkreise und bauen damit auf bekannte und sehr bewährte Methoden für herkömmliche Chip-Technologien auf. Im Gegensatz dazu setzt Xanadu für seinen Quantencomputer auf eine sehr neue aber schnell wachsende Technologie, die sich „Integrated Photonics“ nennt xlv. Die integrierten Schaltkreise hierbei sind keine elektrischen, sondern optische Schaltkreise. Optische Quantensysteme basieren auf Licht und haben damit den Vorteil, dass sie weniger anfällig gegen Umgebungseinflüsse sind. Somit arbeiten sie fehlerfreier als elektrische Systeme. Entsprechend schwieriger ist es allerdings auch optische Systeme gezielt zu manipulieren. Insbesondere können die Informationsträger für optische Quantencomputer, nämlich die Photonen bzw. Lichtteilchen, nicht miteinander wechselwirken.

Was optische Quantencomputer außerdem so besonders macht: Sie sind das Mittel der Wahl für „CV-Quantencomputing“ (CV steht für „Continuous Variable“). Im CV-Quantencomputing sind die zentralen Informationseinheiten nicht Qubits, sondern „Qumodes“. Im Gegensatz zu Qubits können Qumodes nicht nur zwei Werte gleichzeitig annehmen, sondern im Prinzip beliebig viele und sogar Werte in einem kontinuierlichen Spektrum. CV-Quantencomputer besitzen einen ganz eigenen Satz von Quantengattern xlvi als den Satz, den ich Ihnen auf „quantencomputer-info“ vorgestelle. Auf der einen Seite können auf CV-Quantencomputer „analoge“ Probleme vermutlich besser abgebildet werden (z.B. Probleme aus der Physik, Chemie oder Biologie). Auf der anderen Seite können alle Berechnungen für Qubit-Quantencomputer auch mit CV-Quantencomputern durchgeführt werden xlvii … zumindest theoretisch.

Neben den großen Quantencomputer- und Fullstack-Anbietern wurden in den letzten Jahren eine Reihe kleinerer Firmen gegründet, die sich darauf spezialisieren, den zukünftigen Markt für Softwarelösungen auszuloten und Know-How im Quantencomputing zu entwickeln und zu bündeln.

Die Vancouver Firma 1QBit xlviii war eine der ersten Firmen dieser Art. Das Startup QCWare xlix aus dem Silicon Valley ist unter anderem Organisator der Konferenz „Quantum For Business“. Beide Firmen entwickeln eigene Cloudlösungen, die darauf abzielen die Komplexität von Quantencomputern und die Eigenheiten der jeweiligen Quantencomputer-Hardware zu abstrahieren.

Fußnoten

i https://arxiv.org/abs/1611.04471: wissenschaftliche Arbeit von T. Albash, D. A. Lidar „Adiabatic Quantum Computing“

iii Die Grundlage zu diesem Prinzip ist bereits seit den Gründerzeiten der Quantenmechanik bekannt https://de.wikipedia.org/wiki/Adiabatisches_Theorem_der_Quantenmechanik

iv Dieser Satz von speziellen Quantenbausteinen wird auch „Ising-Modell“ genannt. Das Ising-Modell vereinfacht die Wechselwirkungen in komplexen Quantensystemen so geschickt, dass es in der theoretischen Physik gerne als vereinfachtes Modell für zu komplizierte Systeme verwendet wird.

v https://www.nature.com/articles/srep37107/figures/1: Jedes Qubit ist in einer Chimera-Zelle enthalten. Die benachbarten Zellen können miteinander verschaltet werden. Jede Chimera-Zelle besteht aus zwei 4er-Reihen von Qubits. Darin kann jedes Qubit einer Reihe mit jedem Qubit der Nachbarreihe verschaltet werden: Ein sogenannter „complete bipartite graph“. https://arxiv.org/abs/1508.05087: Durch den Fertigungsprozess können nur etwa 95% der Qubits wirklich verwendet werden. Im Anhang A wird dies im Detail sehr anschaulich dargestellt.

vi https://cloud.dwavesys.com: Aktuell ist der Kundenkreis hierfür allerdings nur sehr eingeschränkt. D-Wave hat allerdings angekündigt sein Cloud-Angebot in 2018 für die breite Öffentlichkeit zugänglich zu machen: https://www.cnbc.com/2018/02/23/d-wave-is-raising-money-to-bring-quantum-computing-to-public-cloud.html

ix https://www.youtube.com/watch?v=y8gPz8sc7tY: Vortrag von Catherine McGeoch – „Quantum Annealing: Theory and Practice“

xi https://arxiv.org/abs/1512.02206: wissenschaftliche Arbeit von S. Mandrà, H. Katzgraber, C. Thomas „The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)“

xiii https://www.youtube.com/watch?v=O_RlktWkSdg: Vortrag von Matthias Troyer (mittlerweile bei Microsoft angestellt) u.a. „Transforming Machine Learning and Optimization through Quantum Computing“

xiv https://quantumcomputing.stackexchange.com/questions/171/is-there-proof-that-the-d-wave-one-is-a-quantum-computer-and-is-effective: Sehr interessante Beiträge auf Quantumcomputing Stack-Exchange zum Thema „Is there proof that the D-wave (one) is a quantum computer and is effective?“

xx https://arxiv.org/abs/1805.12570: Fachartikel von S. Herbert „On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity“

xxiii https://research.google.com/pubs/pub45919.html: Nature-Artikel von Google „Commercialize Quantum Technologies in Five Years“

xxviii „Jupyter Notebook“ läuft im Browser ab. Ein Entwickler kann dadurch den Programmcode und die Programmausgabe ganz „Internet-like“ in erklärende Texte, Formeln, Grafiken und Tabellen einbetten.

xxx https://arxiv.org/abs/1501.02813: „Majorana Zero Modes and Topological Quantum Computation“, Fachartikel von Michael Freedman et al.

xxxii https://www.youtube.com/watch?v=v7b4J2INq9c: Demovideo von Krysta Svore (Microsoft) „Microsoft Quantum Development Kit: Introduction and step-by-step demo“

xxxiii https://de.wikipedia.org/wiki/Quantenteleportation: Die Wiki-Doku zur Quantenteleportation. Einen besseren Eindruck von dem Algorithmus bekommt man über das Beispiel auf der Quirk-Homepage: http://algassert.com/quirk

xxxv http://quantumcomputer.ac.cn/index.html: Interessanterweise ist das Cloudangebot von Alibaba nicht so einfach über Google auffindbar. Ein Schelm werde Böses dabei denkt … 🙂

xxxvii https://www.rigetti.com: Homepage der Firma Rigetti Computing.

xxxix https://arxiv.org/abs/1801.03897: „Cloud Quantum Computing of an Atomic Nucleus“ Fachartikel

xli https://qt.eu/: Homepage des EU Flagship-Programms

xliii http://opensuperq.eu/: Homepage des EU-Projektes OpenSuperQ

xliv https://www.xanadu.ai: Homepage der kanadischen Firma Xanadu

xlv https://arxiv.org/abs/1607.08535: „Why I am optimistic about the silicon-photonic route to quantum computing“, Artikel von Terry Rudolph

xlvi https://strawberryfields.readthedocs.io/en/stable/introduction.html: Dokumentation von Xanadus Software-API „Straberryfields“, mit einer Einführung zu CV-Quantencomputing.

xlvii https://arxiv.org/abs/quant-ph/0008040: „Encoding a qubit in an oscillator“, Fachartikel von Daniel Gottesman, Alexei Kitaev und John Preskill

xlviii https://1qbit.com/: Homepage der kanadischen Firma 1QBit

xlix https://qcware.com: Homepage der US-Firma QCWare

Der Grover-Algorithmus und die Suche nach dem heiligen Gral


<<

Der Quantenparallelismus öffnet den Quantencomputern Türen zu völlig neuen Rechenwegen. Die Vermutung liegt nahe, dass sie dadurch Grenzen der Berechenbarkeit für herkömmliche Computer spielend überflügeln können. Im Folgenden stelle ich Ihnen den berühmten Grover-Algorithmus für Quantencomputer im Detail vor. Er ist in der Lage sämtliche „Nadel im Heuhaufen“-Probleme drastisch schneller zu lösen, als ein herkömmlicher Computer. Dabei gehe ich auch kurz auf die Komplexitätstheorie ein, einem faszinierenden Teilgebiet der Informatik, und zeige Ihnen inwiefern selbst der Grover-Algorithmus an seine Komplexitätsgrenzen stößt.

Der Quantenparallelismus

Quantencomputer ermöglichen eine völlig neue Form des parallelen Rechnens: Dem Quantenparallelismus. Dadurch ist ein Quantencomputer in der Lage dasselbe Quantenprogramm für eine Vielzahl von Werten gleichzeitig durchzuführen, prinzipiell sogar für alle Werte die der Computer überhaupt darstellen kann. Dem Quantenparallelismus liegt ein Grundprinzip der Quantenmechanik zu Grunde: Dem sogenannten „Superpositionsprinzip“. D.h. jeder Quantencomputer besitzt den Quantenparallelismus automatisch von Grund auf.

Auf den ersten Blick besitzt der Quantenparallelismus ein unglaubliches Potential. Und seit den allerersten Anfängen der Quantencomputer fragen sich Wissenschaftler, ob sie damit sogar in der Lage sind den heiligen Gral der Computerwissenschaften zu finden: Einen einfachen Weg, um alle überhaupt möglichen „NP-Probleme“ zu lösen.

Die NP-Probleme der Informatik

In den 1960er Jahren fingen Computerwissenschaftler an Probleme in verschiedene Klassen zu unterteilen, je nachdem wie aufwendig sie zu lösen sind. Die Komplexitätsklasse $ P $ enthält grob gesprochen alle Probleme, die sich mithilfe eines herkömmlichen Computers relativ einfach lösen lassen. Genauer gesagt: mit „polynomialem Rechenaufwand“ i. Demgegenüber steht z.B. die Komplexitätsklasse $ NP $. Diese enthält alle Probleme, die sich zwar nicht einfach lösen lassen, deren Lösung man aber mithilfe eines herkömmlichen Computers einfach überprüfen kann, und zwar wieder mit polynomialem Aufwand. Jetzt sind gerade viele bedeutende Probleme der Informatik und Mathematik NP-Probleme. Ein Beispiel für ein NP-Problem ist etwa die bereits erwähnte 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 Komplexitätstheorie ist ein sehr breites Teilgebiet der Informatik. Und in ihrem Zentrum steht eine alles überstrahlende Frage: Ist $ P = NP $ ? D.h. lassen sich diese schwierigen Probleme am Ende nicht doch einfach lösen? ii

Diese Frage ist so etwas wie der „Heilige Gral“ der Computerwissenschaften. Sie wurde u.a. im Jahr 2000 in die exklusive Liste der sieben Millennium-Probleme von offenen Rätseln in der Mathematik aufgenommen, deren Klärung eine enorme Tragweite hätte (nebenbei ist jedes Millenium-Problem mit einem Preisgeld von einer Millionen Euro dotiert). Falls $ P = NP $ wahr wäre, könnten wir beispielsweise mathematische Intuition mit einem Computer automatisieren iii. Diverse andere offene Probleme der Mathematik könnten so z.B. ebenfalls gelöst werden. Für die Wissenschaft als Ganzes hätte dies vermutlich monumentale Auswirkungen.

Allerdings gehen die meisten Experten davon aus, dass $ P = NP $ leider nicht wahr ist und dass sich die NP-Probleme nicht einfach mit einem herkömmlichen Computer lösen lassen.

Aber jetzt kommen die Quantencomputer ins Spiel. Für diese haben die Komplexitätstheoretiker eine neue Klasse von Problemen eingeführt: $ BQP $. Dies sind grob gesprochen wieder alle Probleme, die sich einfach mit einem Quantencomputer lösen lassen. Die Frage ist jetzt: Wenn schon nicht $ P = NP $ ist, ist dann wenigstens $ NP $ in $ BQP $ enthalten? Sind die NP-Probleme also leicht mit einem Quantencomputer zu lösen?

Der Quantencomputer: Die ultimative Brute Force – Lösung ?

Wie verhält es sich also mit den Quantencomputern und den NP-Problemen? Auf den ersten Blick scheint der Quantenparallelismus hierfür zu schön um wahr zu sein. Warum?

Die NP-Probleme sind ja gerade die Probleme, deren Lösung man einfach überprüfen kann. Und mit einem Quantencomputer können wir uns alle möglichen Lösungskandidaten prinzipiell gleichzeitig vornehmen und testen, ob sie das Problem lösen. Violà, wir haben einen ultimativen NP-Cruncher bzw. den ultimativen „Brute Force“ – Algorithmus gefunden, also einen Algorithmus der „brachial“ einfach alle möglichen Kombinationen ausprobiert.

Leider ist das nur auf den ersten Blick so einfach.

Tatsächlich vermuten die Komplexitätstheoretiker eher folgende Zusammenhänge zwischen den Klassen $ P $, $ NP $ und $ BQP $.

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

Das Diagramm zeigt den Zusammenhang der Komplexitätklassen, den die meisten Wissenschaftler vermuten iv. Der vollständigkeithalber sei erwähnt: „PSPACE“ sind die Probleme, für die der Speicherbedarf des Lösungsprogramms polynomial ansteigt, deren Laufzeit aber beliebig lang sein darf und evtl. nie endet. „NP complete“ sind die NP-Probleme, die repräsentativ für alle anderen NP-Probleme sind: Wenn man davon nur eines einfach lösen könnte, kann man alle anderen NP-Probleme auch einfach lösen, und entsprechend hätte man P = NP bewiesen.

Die Suche nach einem NP-Cruncher demonstriert sehr schön wie vielschichtig das Thema Quantencomputer ist und dass selbst die erstaunlichen Quantencomputer ihre Grenzen haben. Ich habe es deshalb ausgewählt, weil man an ihm die vielen Facetten der Quanten-Algorithmen ideal für Einsteiger verdeutlichen kann.

Der Grover-Algorithmus

Der Grover-Algorithmus wurde 1996 von dem indischen Informatiker Lov Grover gefunden. Er ist einer der Standard-Beispiele, die man als erstes lernt, wenn man sich näher mit Quanten-Algorithmen beschäftigt. Unter anderen auch, weil er so vielfältig einsetzbar ist. Normalerweise bekommt man erklärt, dass der Grover-Algorithmus für das komplette Durchsuchen einer Datenbank mittels eines sogenannten „Orakels“ verwendet wird, anders ausgedrückt: Um die Nadel im Heuhaufen zu finden. Dahinter verbirgt sich aber gerade auch die NP-Problematik: Zum einen haben wir eine riesige Menge an Lösungskandidaten, die unsere „Datenbank“ ist. Zum anderen haben wir eine einfache Prüfroutine, nämlich das „Orakel“, mit der wir feststellen können, ob ein Lösungskandidat tatsächlich eine Lösung ist v.

Wir wissen, dass ein Quantencomputer in der Lage ist alle Lösungskandidaten gleichzeitig durch die Prüfroutine durchzujagen. Die echten Lösungen werden dabei von der Routine erkannt. Die vertrackte Frage ist nun: Was bringt uns das eigentlich? Am Ende müssen wir ein Ergebnis messen, und wir erinnern uns, dass das bei Quantencomputern immer eine Sache der Wahrscheinlichkeit ist. Und dabei stören jetzt die falschen Lösungskandidaten wieder und verringern die Wahrscheinlichkeit die echte Lösung zu messen. Wir müssen es also irgendwie hinbekommen, dass der Quanten-Algorithmus die falschen Lösungskandidaten in den Qubit-Speicherregistern weitestgehend unterdrückt und am Ende die echte Lösung mit einer hohen Wahrscheinlichkeit gemessen wird. In dem wir die Prozedur dann mehrmals wiederholen wird aus der Wahrscheinlichkeit dann immer mehr Gewissheit.

Und das ist gerade die Herausforderung an den Quanten-Algorithmen: Die gewünschte Lösung muss zu einer globalen Eigenschaft der Qubit-Register werden. Als Hilfsmittel hat man dafür die Quantengatter, deren Arbeitsweise zwar genau bekannt ist, die aber leider alles andere als intuitiv und einfach sind.

Ein Qubit und einfache Quantengatter

In meinen Beitrag Das Qubit und ein Magier bei „Britain Has Got Talent“ hatte ich schon die Zeigerbilder verwendet mit denen wir uns die verschiedenen Zustände eines Qubits vorstellen können. Das Qubit ist dann ein Zeiger auf der Kreislinie in diesem Bild. Ich hatte schon im letzten Beitrag erwähnt, dass diese Beschreibung nur ein vereinfachtes Bild eines tatsächlichen Qubits ist vi. Um den Grover-Algorithmus zu verstehen, reicht es aber tatsächlich aus.

Folgendes Zeigerbild zeigt ein Qubit, dass gleichzeitig im Zustand |0und im Zustand |1⟩ ist.

Das Besondere an diesem Bild ist außerdem, dass die Zustände |0und |1⟩ gleichmäßig überlagert sind. Es ist zu gleichen Teilen sowohl |0als auch |1⟩. Ein Qubit im Zustand |0gelangt in diesen Zustand der gleichmäßigen Überlagerung, indem es in dem einfachen Zeigerbild um 45° gedreht wird. Diese Drehung wird durch das Hadamard-Quantengatter H durchgeführt.

|qubit= H |0

Ein anderes Gatter ist das X – Quantengatter. Es spiegelt das aktuelle Qubit an der Winkelhalbierenden, also gerade am Zustand H |0⟩. Oder anders betrachtet: Das X-Gatter tauscht den Zustand |0und den Zustand |1gegeneinander aus.

X |0= |1und X |1= |0

Geometrische Anschauung für den Grover-Algorithmus

Das Schöne am Grover-Algorithmus ist auch, dass man ihn an einem einfachen geometrischen Zeigerbild erklären kann.

Wenn wir uns dafür ein ganzes Register mit N Qubits anschauen, so verhalten sich die Zustände in diesem Register auch wieder wie ein einziger Zeiger. Der Zeiger dreht sich allerdings nicht mehr in einer 2 dimensionalen Ebene, sondern in einem $ 2^N $ dimensionalem Raum! Jede Achse in diesem Raum entspricht einer anderen Kombination von 0en und 1en in dem Qubitregister: Eine Achse entspricht zum Beispiel der Kombination 10001101100, eine andere Achse entspricht der Kombination 00001101100, wieder eine andere Achse entspricht einer ganz anderen Kombination 11011010111 und so weiter. Zum Glück können wir diesen $ 2^N $ dimensionalen Raum für den Grover-Algorithmus wieder auf eine 2 dimensionale Ebene vereinfachen.

Dazu konstruieren wir drei Zeiger, die auf einer Kreislinie in einer Ebene liegen. Der erste Zeiger ist einfach: Nehmen wir mal an die erste Kombination 10001101100 löst das NP-Problem. Das wissen wir am Anfang natürlich noch nicht, wir könnten die Kombination auch „Lösung“ nennen. Die zugehörige Achse wird jetzt unsere Y-Achse.

Der zweite Zeiger zeigt in die Richtung der „gleichmäßigen Überlagerung“. Das ist gerade der Zeiger, der entsteht, wenn auf alle Qubits jeweils ein Hadamard-Quantengatter angewendet wird. Für ein Qubit hatten wir gerade gesehen, dass ein Hadamard-Quantengatter den Qubit-Zeiger so dreht, dass beide Zustände $ \rvert 0 \rangle $ und $ \rvert 1 \rangle $ gleichmäßig überlagert werden und gleichzeitig vorhanden sind. Wenn wir jeweils ein Hadamard-Gatter auf jedes Qubit anwenden bedeutet das, dass alle möglichen Zustände des ganzen Quantencomputers gleichmäßig überlagert sind. Das ist also genau die Situation, die wir für unseren Brute-Force-Plan benötigen: Wir haben alle möglichen Kombinationen von 0en und 1en, und somit die gesamte Menge an Lösungskandidaten, gleichzeitig im Zugriff.Nennen wir diesen Zeiger der gleichmäßigen Überlagerung $ \rvert S \rangle $.

Alle Achsen in dem $ 2^N $ dimensionalem Raum, und somit alle Kombinationen von 0en und 1en, haben den gleichen kleinen Anteil an $ \rvert S \rangle $. Da $ \rvert S \rangle $, wie jeder Zeiger auf der Kugeloberfläche in dem $ 2^N $ dimensionalen Raum, die Länge 1 hat, ist der Anteil von jedem Qubit-Zustand an $ \rvert S \rangle $ nur ein kleiner Bruchteil von 1. Zunächst würde man vermuten dieser Bruchteil wäre $ 1/2^N $, da es $ 2^N $ Kombinationen gibt. Dies ist aber nicht so: Aufgrund des Satzes von Pythagoras vii ist der kleine Bruchteil die Wurzel davon, und zwar $ 1/ \sqrt{2^N} $. Und somit zeigt der Zeiger der gleichmäßigen Überlagerung zu diesem kleinen Bruchteil auch in Richtung unseres Lösungszeigers $ \rvert 10001101100 \rangle $. Insbesondere wird dieser Bruchteil also schnell kleiner je größer N wird. Das Wurzelzeichen wird sich später übrigens als der Clou für den Grover-Algorithmus herausstellen!

Jetzt zum dritten Zeiger, den wir $ \rvert s \rangle $ nennen wollen: Der entsteht, wenn wir aus der gleichmäßigen Überlagerung $ \rvert S \rangle $ den kleinen $ \rvert 10001101100 \rangle $ – Anteil herausrechnen. $ \rvert s \rangle $ zeigt damit genau in X-Richtung. $ \rvert S \rangle $ und $ \rvert s \rangle $ liegen also nah beieinander. Der Winkel der sie trennt ist gerade $ 1/ \sqrt{2^N} $ viii. Das der Winkel zwischen $ \rvert S \rangle $ und $ \rvert s \rangle $ so klein ist, wird uns am Ende noch mächtig ärgern!

Wenn wir uns das Diagramm ansehen können wir erkennen, was der Grover-Algorithmus leisten muss:

Wir nennen den aktuellen Zustand des Quantencomputers einfach $ \rvert x \rangle $. Er wird normalerweise eine Überlagerung von verschiedenen anderen Zuständen sein. Am Anfang starten wir mit dem Zustand der gleichmäßigen Überlagerung, also $ \rvert x \rangle = \rvert S \rangle $. Wir müssen jetzt eine Reihe von Quantengattern derart zusammenschalten, dass $ \rvert x \rangle $ nach und nach in die Richtung unserer Lösung $ \rvert 10001101100 \rangle $ zur Y-Achse gedreht wird.

Im Folgenden erfahren Sie zunächst, was es mit dem Zeiger $ \rvert s \rangle $ auf sich hat.

Das Orakel: Eine einfache Spiegelung

Schauen wir uns an wie ein Quantengatter den Zustand der gleichmäßigen Überlagerung verändert. Dank des Superpositionsprinzip wissen wir: Ein Quantengatter verändert eine Überlagerung von Zuständen derart, dass wir danach eine Überlagerung von veränderten Zuständen haben: z.B.

$ X ( \rvert 0 \rangle – \rvert 1 \rangle ) = X \rvert 0 \rangle – X \rvert 1 \rangle = \rvert 1 \rangle – \rvert 0 \rangle $

Das gleiche gilt natürlich immer noch, wenn wir mehrere Quantengatter miteinander kombinieren. Das Orakel ist insbesondere auch einfach eine Zusammenschaltung von mehreren Quantengattern. Nennen wir es O.

O soll wie folgtdie verschiedenen überlagerten Teilzustände verändern:

  • Wenn eine Kombination von 0en und 1en keine Lösung des Problems ist, wir erinnern uns, dass wir dies für NP-Probleme leicht herausfinden können, bleibt dieser Anteil an der gesamten Überlagerung unverändert. Als Gleichung geschrieben:$ O \rvert 10101010101 \rangle = \rvert 10101010101 \rangle $
  • Wenn eine Kombination von 0en und 1en eine Lösung ist, wird dieser Anteil an der gesamten Überlagerung ins Negative umgekehrt. Als Gleichung geschrieben:$ O \rvert 10001101100 \rangle = – \rvert 10001101100 \rangle $

Wenn wir uns das Zeigerbild ansehen, können wir jetzt Folgendes erkennen:

$ O $ verändert fast alle Anteile an dem Anfangszustand $ \rvert S \rangle $ nicht. Nur der Anteil in die Y-Richtung wird umgekehrt. Das ist aber nichts anderes als eine Spiegelung an der X-Achse, die ja der Zustand $ \rvert s \rangle $ ist.

Zunächst haben wir dadurch nichts gewonnen, weil der Zeiger $ \rvert x \rangle $ sich noch nicht näher an $ \rvert 10001101100 \rangle $, unserer Y-Achse angenähert hat. Deshalb spiegeln wir $ \rvert x \rangle $ nochmal. Diesmal allerdings nicht an $ \rvert s \rangle $, sondern an $ \rvert S \rangle $!

Der aktuelle Zustand des Quantencomputers $ \rvert x \rangle $ ist um einen Winkel näher an die Y-Achse gedreht. Dieser zusätzliche Winkel ist das zweifache von dem kleinen Winkel zwischen $ \rvert S \rangle $ und $ \rvert s \rangle $, also $ 2 / \sqrt{2^N} $.

Zwischenfaszit: Die Stärken und Schwächen des Grover-Algorithmus

Jetzt können wir erkennen, wie es weitergehen muss: Jedes mal wenn wir den aktuellen Zeiger $ \rvert x \rangle $ zuerst an $ \rvert s \rangle $ spiegeln und danach an $ \rvert S \rangle $, dreht sich $ \rvert x \rangle $ um den Winkel $ 2/ \sqrt{2^N} $ näher an $ \rvert 10001101100 \rangle $ heran.

Weil der Winkel leider so klein ist, müssen wir das Ganze ungefährt $ \frac{1}{2} * \sqrt{2^N} $ Mal durchführen.

Damit haben wir tatsächlich schon das Prinzip des Grover-Algorithmus gelöst und damit auch die Antwort auf unsere Brute Force / NP-Cruncher-Frage herausbekommen!

Ein herkömmlicher Computer würde im Schnitt $ \frac{1}{2} * 2^N $ Versuche brauchen, um $ 2^N $ Kombinationen durchzuprobieren und eine Lösung zu erhalten. Ein Quantencomputer braucht mit dem Grover-Algorithmus $ \frac{1}{2} * \sqrt{2^N} $ Versuche. Das ist eine quadratische Beschleunigung!

Wenn also ein herkömmlicher Computer für ein Brute-Force-Problem eine Millionen Rechenschritte benötigen würde, bräuchte ein Quantencomputer nur 1000 Rechenschritte. Das ist schon sehr gut!

Aber leider hatten wir uns mehr davon versprochen: Was stört, ist dass wir immer noch $ \sqrt{2^N}= 2^{\frac{1}{2}N} $ Rechenschritte benötigen. Das ist immer noch mehr als polynomial. Polynomialer Rechenaufwand wäre $ N^{\text{etwas}} $. Damit ist das Problem kein BQP-Problem und ein schwieriges NP-Problem bleibt also auch ein schwieriges Problem für den Grover-Algorithmus, obwohl letzterer es zumindest schneller lösen kann.

Die große Frage ist nun: Ginge das auch besser?

Was so sehr stört ist, dass der Winkel zwischen $ \rvert S \rangle $ und $ \rvert s \rangle $ so klein ist. Dies ist so etwas wie die Quantenversion der Tatsache, dass die gesuchte Kombination 10001101100 eine unter sehr sehr vielen Kombinationen ist. Vielleicht können wir den Grover-Algorithmus z.B. derart ändern, dass wir bei jeder Reflexion an $ \rvert s \rangle $ näher an $ \rvert 10001101100 \rangle $ herankommen.

Tatsächlich wurde eine Grenze für ein Optimum an Verbesserung für den Grover-Algorithmus gefunden. Jeder Algorithmus, der das Orakel $ O $ mehrmals verwendet sieht prinzipiell so aus:

$ … O … O … O … O … $

Die Pünktchen stehen jeweils für irgendeine Schaltung an Quantengattern. Es ist erstaunlich aber man kann tatsächlich prinzipiell beweisen, dass jeder Einsatz eines Orakels in dieser Form den Rest des Quanten-Algorithmus, also die Pünktchen, höchstens quadratisch beschleunigen kann ix. Das zeigt, dass der Grover-Algorithmus tatsächlich optimal ist. Leider.

Natürlich gibt es viele Quanten-Algorithmen, die die besten herkömmlichen Algorithmen exponentiell beschleunigen, wie z.B. der Shor-Algorithmus. Evtl. gibt es sogar doch noch einen ultimativen NP-Cruncher, der auf Quantencomputern mit Polynomialaufwand läuft. Aber die Idee, diesen NP-Cruncher dadurch zu konstruieren, indem man ein Orakel mehrmals hintereinander ausführt, führt leider nicht zum gewünschtem Ziel.

Der Grover-Algorithmus als Quanten-Schaltkreis

Achtung, jetzt wird es ernst!

Bisher hatte ich den Grover-Algorithmus anhand der geometrischen Anschauung erklärt. Jetzt schauen wir uns den Quanten-Schaltkreis für den Grover-Algorithmus auf einem 2 Qubit – Quantencomputer an:

Am Anfang auf der linken Seite ist jedes Qubit im Zustand $ \rvert 0 \rangle $ vorhanden. Anders ausgedrückt: $ \rvert 00 \rangle $. Darauf erzeugen wir den Zustand der gleichmäßigen Überlagerung $ \rvert S \rangle $, in dem wir auf jedes Qubit das Hadamard-Quantengatter anwenden. Die beiden Qubits bilden jetzt eine Überlagerung aus allen möglichen Kombinationen von 0en und 1en.

Danach führen wir das Orakel aus. Das Orakel muss für jedes Problem individuell konstruiert werden, weil die Prüfroutine für Lösungskandidaten natürlich jeweils anders aussieht. Beispiele hierfür gebe ich weiter unten.

Im Gegensatz dazu sieht die Spiegelung an $ \rvert S \rangle $ für jedes Problem gleich aus. Zum Glück kann man sie einfach aus der Spiegelung an der $ \rvert 00 \rangle $ – Achse ableiten.

Letztere ist im inneren Kasten dargestellt:

Zunächst zum Quantengatter ganz in der Mitte. Dieses heißt „Controlled NOT“ bzw. CNOT. Das CNOT-Quantengatter ist so etwas wie eine „Wenn-Dann / If-Then“-Schaltung für Quantencomputer. Es arbeitet so: Falls das obere Qubit

  • den Zustand |0⟩ hat, lässt es das untere Qubit unverändert
  • den Zustand |1⟩ hat, tauscht es die Zustände |0⟩ und |1⟩ um unteren Qubit, führt also ein X – Quantengatter auf das untere Qubit aus.

Das obere Qubit „kontrolliert“ also den X-Tausch im unteren Qubit, deshalb der Name. Normalerweise sind beide Qubits überlagert. In dem Fall tauscht das obere Qubit den überlagerten Zustand des unteren Qubit „ein bißchen und ein bißchen nicht“. Dadurch entsteht so ein berühmt-berüchtigter verschränkter Quantenzustand: Die beiden Qubits sind jetzt so tiefgreifend miteinander verwoben, dass man sie nicht mehr als einzelne Einheiten betrachten kann, sondern nur als Ganzes.

Für den inneren Kasten in unserem Grover-Schaltkreis ist das Entscheidende, dass man das CNOT-Quantengatter auch als Spiegelung auffassen kann. Das verwundert nicht, weil wir oben gesehen hatten, dass das X-Quantengatter unter anderem eine Spiegelung an der Achse $ H \rvert 0 \rangle $ ist. So richtig klar wird es, wenn wir diese Spiegelung auf die Achse des Zustands |11drehen. Das erreichen wir durch die Schaltung $ H CNOT H $ in der Mitte, was man übrigens auch „Controlled Z“ oder CZ nennt. Die CZ-Quantenschaltung arbeitet insgesamt so: Falls das obere Qubit

  • den Zustand |0⟩ hat, lässt es das untere Qubit unverändert
  • den Zustand |1⟩ hat, lässt es den |0⟩ – Anteil des unteren Qubits unverändert und kehrt den und |1⟩ – Anteil ins Negative um.

Oder als Gleichung:

CZ ( |00+ |10+ |01+ |11) = |00+ |10+ |01|11

Das ist aber tatsächlich nichts anderes als eine Spiegelung! Genauso hatten wir nämlich oben auch die Funktionsweise des Orakels erklärt. Jetzt überprüfen wir noch an welcher Achse hier gespiegelt wird. Eigentlich kehrt sich in der Gleichung der |11⟩ – Anteil ins Negative. Nun muss man wissen, dass ein Quantencomputer bei jeder Messung am Ende globale Minuszeichen eines Zustandes ignoriert. Es macht am Ende also keinen Unterschied, wenn wir die komplette Qubit-Überlagerung mit „-1“ mal nehmen:

|00+ |10+ |01|11ist gleichwertig mit

|00 |10|01+ |11

Das macht die Controlled Z – Quantenschaltung also zu einer Spiegelung an der |11⟩ –Achse.

Schauen wir uns noch den Rest von dem inneren Kasten im Quanten-Schaltkreises oben an:

Die beiden unteren X – Quantengatter links und rechts von der Controlled Z – Schaltung $ H CNOT H $ drehen die Spiegelachse von der |11⟩-Achse zunächst auf die |10⟩-Achse. Die beiden oberen X-Quantengatter links und rechts drehen die Spiegelachse weiter auf die |00⟩-Achse.

Soweit zum inneren Kasten. Den Trick mit dem CZ – Quantengatter merken wir uns für später, wenn wir die Spiegelung für das Orakel zu konstruieren.

Die zusätzlichen Hadamard-Quantengatter im äußeren Kasten drehen dann die Spiegelachse $ \rvert 00 \rangle $ auf den Zustand $ \rvert S \rangle $, also ganz analog zu der Gleichung weiter oben $ H \rvert 0 \rangle = \rvert S \rangle $.

Alles verstanden? Ich vermute, jetzt bekommen Sie langsam ein Ahnung, warum Quanten-Algorithmen so kompliziert sind. Und dabei ist der Grover-Algorithmus noch verhältnismäßig einfach 🙂 !

Die Pünktchen im weiteren Verlauf des Quanten-Schaltkreises deuten an, dass danach das Orakel und die Spiegelung an $ \rvert S \rangle $ entsprechend oft wiederholt werden müssen, damit der Lösungszustand verstärkt wird.

Am Ende erfolgt dann die Messung der einzelnen Qubits, die dann die gesuchte Lösung mit hoher Wahrscheinlichkeit ergibt.

Das Beispiel beschreibt den Fall für 2-Qubits. Für mehrere Qubits sieht die Schaltung prinzipiell genauso aus.

Ein Beispiel-Orakel für ein echtes „3SAT“-Problem

Eine der großen Stärken des Grover-Algorithmus ist es, dass er ein sehr universeller Algorithmus ist, den wir für eine riesige Auswahl an Problemen verwenden können. Der Teil des Quanten-Schaltkreises, den ich Ihnen im vorigen Abschnitt vorgestellt habe, sieht dabei für jedes Problem gleich aus. Der Teil des Quanten-Schaltkreises, der speziell für jedes Problem angepasst werden muss, ist das Orakel selbst.

Um einen Eindruck von einem Grover-Orakel zu bekommen stelle ich Ihnen zwei Beispiele vor. Das erste Grover-Orakel gehört zu einem Problem, das so simpel ist, dass ich es „Deppen-Problem“ nenne. Es ist außerdem leider das Standardbeispiel für ein Grover-Orakel, dass in vielen Einführungen für den Grover-Algorithmus herumgeistert. Es ist so einfach, dass man nicht versteht wo überhaupt das Problem ist. In dem „Deppen-Problem“ werden die zwei Bits gesucht, also zwei Zahlen mit Werten 0 oder 1, die folgende Gleichungen erfüllen:

$ X_1 $ = 1

$ X_2 $ = 1

Dieses Problem liefert also seine eigene Lösung gleich mit. Es ist so einfach, dass man den ganzen Sinn und Zweck des Orakels im Grover-Algorithmus nicht richtig verstehen kann. Als Einstieg zeige ich Ihnen trotzdem auch den Quanten-Schaltkreis von diesem Orakel.

Nochmal zur Erinnerung: Wie muss das Orakel O in dem Grover-Algorithmus funktionieren? Das hatte ich oben beschrieben.

O soll wie folgtdie verschiedenen überlagerten Teilzustände von $ O \rvert x\rangle $ verändern:

  • Für alle Kombinationen von 0en und 1en, die keine Lösung sind (also |x = |00, |01 und |10) bleibt der Anteil an der gesamten Überlagerung unverändert. Als Gleichung geschrieben:$ O \rvert x \rangle = \rvert x \rangle $
  • Nur der |11er- Anteil an der gesamten Überlagerung wird ins Negative umgekehrt. Als Gleichung geschrieben:$ O \rvert 11 \rangle = – \rvert 11 \rangle $

Diesen Schaltkreis kennen wir bereits. Es ist gerade die Controlled Z – Quantenschaltung oder CZ, die wir oben kennen gelernt hatten:

Der ganze Grover-Schaltkreis sieht damit so aus:

Kommen wir aber jetzt zu einem vernünftigen Beispiel: Ein 3SAT-Problem.

Zunächst zu den SAT-Problemen bzw. „Boolean Statisfiability“-Probleme: So werden in der Informatik Systeme von Gleichungen mit mehreren Bit-Zahlen genannt. Dabei können die Bit-Zahlen jeweils mit UND, ODER oder NICHT miteinander verknüpft werden. Unser „Deppen-Problem“ ist also auch ein sehr einfaches SAT-Problem. 3SAT-Probleme wiederum sind solche SAT-Probleme, bei denen in jeder Bit-Gleichung nur drei Bit-Zahlen vorkommen dürfen. Zum Beispiel

$ (NICHT \ x_1) \quad ODER \quad (NICHT \ x_3) \quad ODER \quad (NICHT \ x_4)  = 1 $

$ x_2 \quad ODER \quad x_3 \quad (NICHT \ x_4) = 1 $

$ x_1 \quad ODER \quad (NICHT \ x_2) \quad ODER \quad x_4 = 1 $

$ (NICHT \ x_1) \quad ODER \quad X_2 \quad ODER \quad (NICHT \ x_4)  = 1 $

Sie werden mir zustimmen, das Problem sieht schon schwieriger aus. Die Komplexität von 3SAT-Problemen ist sogar amtlich: Sie gehören zu den „NP-Complete“-Problemen: Alle NP-Probleme können in 3SAT-Probleme umgewandelt werden. Könnte man alle 3SAT-Probleme einfach lösen, könnte man alle NP-Probleme einfach lösen x.

Das 3SAT-Orakel, das ich Ihnen hier vorstelle stammt übrigens von Craig Gidney xi, von dem auch der öffentliche Quantencomputer-Simulator „Quirk“ stammt, mit dem ich die Quanten-Schaltkreise auf „quantencomputer-info“ erstelle. Gidney gibt dabei folgenden Tipp, um ein Grover-Orakel zu konstruieren: Überlege Dir zu dem Problem den klassischen Schaltkreis für herkömmlichen Computer. Dann wandel die klassischen Gatter in Quantengatter um.

Unsere vier Gleichungen oben können wir umschreiben in eine Gleichung, die wir zu einem Schaltkreis umwandeln können. Da für Quantencomputer UND-Verknüpfungen handlicher sind als Oder-Verknüpfungen, müssen wir die Gleichungen noch zusätzlich umwandeln. Dabei machen wir uns zunutze, dass z.B. gilt $ (NICHT \ x_1) \quad ODER \quad (NICHT \ x_3) = NICHT( x_1 \quad UND \quad x_3) $.

 

$ NICHT \big( \quad x_1 \quad UND \quad x_3 \quad UND \quad x_4 \quad \big) \quad UND $

$ NICHT \big( \quad (NICHT \ x_2) \quad UND \quad (NICHT \ x_3) \quad UND \quad x_4 \big) \quad UND $

$ NICHT \big( \quad (NICHT \ x_1) \quad UND \quad x_2 \quad UND \quad (NICHT \ x_4) \big) \quad UND $

$ NICHT \big( \quad x_1 \quad UND \quad (NICHT \ x_2) \quad UND \quad x_4 \big) \quad UND $

$ = 1 $

Danach schreiben wir die Gleichungen als Tabelle um und zwar in derselben gedrehten Sichtweise, wie auch unser Quanten-Schaltkreis ausgerichtet sein wird.

Gleichung 1

Gleichung 2

Gleichung 3

Gleichung 4

Bit 1

Bit1

NICHT Bit1

Bit1

Bit 2

NICHT Bit 2

Bit2

NICHT Bit2

Bit 3

Bit3

NICHT Bit3

Bit3

Bit 4

Bit4

Bit4

NICHT Bit4

Im Quanten-Schaltkreis verwenden wir für jedes Bit natürlich ein Qubit. Jede Gleichung wird durch ein mehrfaches UND-Quantengatter dargestellt. Die schwarzen Kreise bedeuten, dass das Qubit so wie es ist UND-verknüpft wird. Die weißen Kreise bedeuten, dass das Qubit vor der UND-Verknüpfung mit einem X-Gatter NICHT-verknüpft wird. Das Ergebnis jeder Gleichung wird in einem zusätzlichen „Ancilla“-Qubit hinterlegt. Am Ende werden alle diese Ancilla-Qubits mit einem mehrfachen NICHT-UND-Gatter verknüpft, genauso wie es unser 3SAT-Problem verlangt. Das Endergebnis hinterlegen wir in einem zusätzlichen Qubit. Immer wenn dieses Qubit den Zustand |1 besitzt, sind alle unsere Gleichungen erfüllt. In allen anderen Fällen ist das letzte Qubit im Zustand |0.

Am Ende müssen wir uns noch um unser Orakel kümmern: Immer wenn eine Bit-Kombination alle Gleichungen erfüllt, soll sich der Teil der Überlagerung ins Negative umkehren und ansonsten so bleiben wie er ist. Oder anders ausgedrückt, immer wenn das Qubit für das Endergebnis im Zustand |1 ist, soll sich der Teil an der Gesamt-Überlagerung |xins Negative umkehren. Wenn das Endergebnis-Qubit im Zustand |0 ist, soll der Teil der Gesamt-Überlagerung |xso bleiben wie er ist. Das Quantengatter, das sich genauso verhält, nennt man Z-Quantengatter.

Z |0= |0und Z |1= – |1

In unserem vereinfachten Zeigerbild für Qubits ist das eine Spiegelung an der |0⟩ – Achse:

Die Schaltung oben ist allerdings wieder eine starke Vereinfachung. Für jede der 4 Bit-Gleichungen ist nur ein Quantengatter dargestellt. Tatsächlich müssten hierfür wieder eine Vielzahl zusätzlicher CNOT- und weitere Quantengatter verwendet werden. Aber das ist tatsächlich „nur“ noch eine Fleißarbeit xii.

Fußnoten

i Polynomialer Rechenaufwand bedeutet Folgendes: Je komplexer das Problem wird, desto mehr nimmt natürlich die Zeit zu um die Lösung zu finden. Polynomialer Rechenaufwand bedeutet nun, dass die Anzahl der Rechenschritte um die Lösung zu finden nach einer Potenzregel zunimmt. Wenn N die Komplexität des Problems ist, so nimmt der Rechenaufwand dann grob gesehen wie N oder N² oder N³ oder N⁴, …. zu. Um z.B. eine Person unter N=1000 Personen zu finden, benötigt man im Mittel ½ * N Versuche. Probleme bei denen der Aufwand mehr als polynomial zunimmt, wären etwa Probleme deren Lösungsaufwand explosionsartig bzw. exponentiell zunimmt z.b. $ 2^N $. Solche Probleme sind eher charakteristisch für NP-Probleme.

ii Eine sehr schöne Einführung in die Komplexitätstheorie bekommen Sie auf Scott Aaronsons Website zu seinem Buch „Quantum Computing Since Democritus“: https://www.scottaaronson.com/democritus/lec6.html. Scott Aaronson ist einer der führenden Quanteninformatiker und ein fesselnder Didakt.

iii Mathematische Beweise sind insbesondere auch Kandidaten für NP-Probleme. Einen fertigen Beweis zu verifizieren ist, zumindest für Fachleute, gut machbar. Die Kunst ist es einen Beweis für ein Problem zu finden. So formulierte beispielsweise Pierre de Fermat seine berühmte Vermutung an + bn = cn in den 1650er Jahren. Trotz intensivsten Bemühungen von führenden Mathematikern wurde der Beweis hierfür erst 1994 von Andrew Wiles mithilfe von modernsten Methoden der arithmetischen Geometrie gefunden.

iv Tatsächlich ist das Diagramm über die Zusammenhänge zwischen P, NP, BQP und PSPACE fast komplett unbewiesen. Wirklich bewiesen wurde zuletzt allerdings die Vermutung, dass es BQP-Probleme gibt, die weder in P noch in NP liegen. Nebenbei wurde damit auch bewiesen, dass PSPACE und NP nicht gleich sind. Lesen Sie hierzu auch den Artikel auf Quantamagazine https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/

v Der Begriff „Orakel“ hat für die Computerwissenschaften eine noch speziellere Bedeutung, was für den Grover-Algorithmus aber nicht wichtig ist.

vi Das exakte Bild eines Qubits ist das einer Kugeloberfläche. Die Zustände |0und |1⟩ müssen wir dann an Nord- und Südpol einzeichnen. Um von der Kreislinie zur Kugeloberfläche zu gelangen, muss ein zusätzliche Winkel verwendet werden, der auch „Phase“ genannt wird.

vii Zur Erinnerung: $ \sqrt{ a^2 + b^2 } = c $, wenn $ a $ und $ b $ senkrecht aufeinander stehen. Wenn jetzt noch mehr senkrechte Achsen dazukommen, erhalten wir $ \sqrt{ a_1^2 + a_2^2 + a_3^2 + a_4^2 + …} = c $. Da die $ 2^N $ $ a $‘s in der gleichmäßigen Überlagerung alle gleich lang sind und $ c $ die Länge 1 hat, bekommen wir $ \sqrt{ 2^N a^2 } = 1 $ was gerade $ a = 1 / \sqrt{2^N} $ ist

viii Da wir die Winkel als Radianten bzw. Kreisbogen messen, müssen wir genau genommen vor alle Winkel noch einen Faktor $ \pi / 2 $ schreiben. Um das ganze Thema nicht noch komplizierter aussehen zu lassen und uns nur das grobe Verhalten des Grover-Algorithmus interessiert, können wir diesen auch weglassen.

ix https://arxiv.org/abs/quant-ph/9701001: Fachartikel „Strengths and Weaknesses of Quantum Computing“. Eine besser verdauliche Variante des Beweises findet man in dem Standard-Lehrbuch „Quantum Computation and Quantum Information“ von Michael Nielsen und Isaac Chuang, oft auch kurz „Mike and Ike“ genannt.

x https://www.scottaaronson.com/democritus/lec6.html: „PHYS771 Lecture 6: P, NP, and Friends“, die 6. Vorlesung aus Scott Aaronson‘s legendären Vorlesungsreihe „Quantum Computing Since Democritus“. Darin beleuchtet Aaronson, einer bekanntesten Theoretiker für Quantencomputer weltweit, viele Grundlagen-Aspekte aus Mathematik, Informatik und Quantenmechanik auf eine erfrischend mitreißende Weise.

xi https://cstheory.stackexchange.com/questions/38538/oracle-construction-for-grovers-algorithm/38551#38551: „Oracle Construction for Grover’s Algorithm“, Thread auf CSTheory- Stackexchange

xii Die Quantengatter für jede Gleichung sind abgewandelte CCCNOT-Schaltungen. Teilweise müssten hier noch X-Gatter für die NICHT-Verknüpfungen in den Gleichungen vorgeschaltet werden. CCCNOT-Schaltungen können über mehrere CCNOT-Schaltungen erstellt werden: https://quantumcomputing.stackexchange.com/questions/2397/implementing-a-cccnot-gate-using-only-toffoli-gates. CCNOT-Gatter wiederum sind die Quantencomputer-Version von klassischen UND-Gattern und werden oft auch Toffoli-Gatter genannt. Ein Toffoli-Gatter kann wiederum über 6 CNOT-Gatter konstruiert werden: https://en.wikipedia.org/wiki/Toffoli_gate

Einleitung: Die Quantenrevolution beginnt

>>

Quantencomputer besitzen das Potential unsere Gesellschaft maßgeblich zu verändern.

Was vor über 30 Jahren als visionäres aber aussichtsloses Vermächtnis eines genialen Physikers begann, wird gerade in diesen Tagen Wirklichkeit.

Ziel meiner Seite „quantencomputer-info“ ist es, umfassend und stets aktuell über die rätselhafte Technologie zu informieren. Alles was Sie dafür mitbringen müssen ist eine ordentliche Portion Neugierde.

Quantencomputer: Ein Informationsvakuum

Der Begriff Quantencomputer taucht regelmäßig in den Technologie-Nachrichten der Mainstream-Medien auf. Die vereinzelten Meldungen die Sie dort finden, können das Thema allerdings nicht annähernd ausreichend vermitteln. Auf der anderen Seite können Sie eine Vielzahl von komplizierten, sehr mathematischen Lehrmaterial von Hochschulen zu Quantencomputern finden. Aktuelle Entwicklungen können Sie hauptsächlich nur in noch viel anspruchsvolleren wissenschaftlichen Fachartikeln verfolgen. Das setzt ein ungeheures Vorwissen in der Quantenmechanik und in Mathematik voraus.

Insbesondere für Entscheider in der Technologiebranche wird allerdings irgendwann in den nächsten Jahren der Zeitpunkt kommen, an denen sie entscheiden müssen, ob ihr Unternehmen in die neue Technologie Quantencomputer investieren sollte. IT-ler müssen für sich persönlich abwägen, ob sie sich auf den beschwerlichen Weg machen sollten, sich Knowhow in dem neuen Bereich Quantencomputer anzueignen, der so komplett anders ist als alles was sie bisher gemacht haben. Und letztendlich werden technikinteressierte Laien mehr über die Technologie wissen wollen, der man wahre Wunder nachsagt.

„quantencomputer-info“ soll dabei helfen dieses Informationsvakuum mit Leben zu füllen. Auf den nächsten Seiten werde ich Ihnen ein relativ genaues Verständnis der Quantencomputer vermitteln. Ich werde die Grundlagen erklären und auch auf Themen aus der aktuellen Entwicklung und Forschung eingehen. Dabei werde ich fast vollständig mathematische Formeln vermeiden und das Wesen hinter den Quantencomputern eher bildlich beschreiben. Anstatt auf Exaktheit lege ich den Fokus auf ein sehr gutes qualitative Verständnis. Deshalb soll diese Seite auch ein sehr guter Ausgangspunkt sein, um in die so ungeheuer komplizierte Materie einzusteigen und dabei den Wald vor lauter Bäumen noch zu sehen. Insbesondere werde ich Ihnen folgende Fragen genauer beantworten:

      • Was genau ist ein Quantencomputer?
      • Wie funktioniert ein Quantencomputer?
      • Warum dieser Hype um Quantencomputer?
      • Was ist die Quanten-Überlegenheit?
      • Was genau ist ein „Qubit“?
      • Wie sehen Quantenprogramme aus?
      • Welche Quantencomputer gibt es jetzt schon und welche wird es demnächst geben?
      • Was sind die absehbaren Anwendungsgebiete für Quantencomputer?

Insbesondere die letzten beiden Punkte werden ich auf „quantencomputer-info“ aktuell halten und auf neue Entwicklungen eingehen.

Eine neue Ära der Technologie-Geschichte

Quantencomputer werden nach und nach das Tor zu einer neuen Welt öffnen. Diese Welt wird so bizarr und anders sein, dass wir erst langsam einen Eindruck davon bekommen, was darin möglich sein wird. Es ist die Welt der Quantenberechenbarkeit und der Quantenkomplexität. Durch die Quantencomputer werden Quanteneffekte für unser Computerzeitalter bzw. für die Ära der Algorithmen erschlossen. Was wird passieren, wenn wir das Tor in das Zeitalter der Quantencomputer betreten? Um einen Eindruck davon zu bekommen, welche Erwartungen viele Experten in diesen Schritt setzen, ist es hilfreich die aktuelle Entwicklung mit der Erschließung der Quantenmechanik für das Industriezeitalter bzw. für die Ingenieurswissenschaften zu vergleichen.

Quantentechnologien wie Halbleiter, Transistoren, Dioden, Laser und viele weitere bilden das Herzstück unserer modernen, technologischen Gesellschaft. In allen möglichen Geräten unseres täglichen Lebens wie den Computern, dem Internet, Smartphones, Fernsehern, … sind sie zu finden. Aber selbst diese bahnbrechenden Technologien sind eher vergleichbar mit der Entwicklung des elektrischen Lichts: Sie sind das Resultat von Quanteneffekten für riesige Massen von Elektronen. Quantencomputer sind so etwas wie die digitale Version der Quantentechnologien: Sie verändern und verzahnen auf filigranste Weise einzelne, elementare Quantenzustände. Die Andersartigkeit der Quantenwelt hat uns die Halbleiter und Laser beschert. Dieselben Quanteneffekte besitzen das Potential das Wesen von grundlegenden Algorithmen und selbst das Wesen unserer Logik komplett umzukrempeln. Wir werden völlig neue und extrem abgekürzte Rechenwege entdecken und beschreiten können, die sonst unmöglich wären.

Seit über zwei Jahrzehnten findet intensive Forschung zu dem Thema Quantencomputer statt. Die auch daraus entstandene Quanteninformationstheorie entwickelt sich immer mehr zu einem der Herzstücke der modernen Physik und ist tief in die Informatik eingedrungen. Erste experimentelle Quantencomputer wurden im Laufe der letzten 20 Jahre in Forschungseinrichtungen gebaut. Längst haben die Tech-Riesen Google, IBM, Microsoft & Co das bahnbrechende Potential der Technologie erkannt und führende Physiker, Informatiker und Mathematiker angeworben, um die Entwicklung der ersten kommerziellen Quantencomputer zu befeuern. Als Resultat stehen jetzt die ersten Quantencomputer in der Cloud.

Verfügbar für jedermann.

Unbemerkt von der breiten Öffentlichkeit liefern sich die Tech-Giganten gerade ein spannendes Wettrennen, welche Gruppe als erstes den nächsten großen Meilenstein erreicht: Der erste Nachweis der „Quantum Supremacy“ oder auf deutsch der „Quanten-Überlegenheit“. Also der erste Quantencomputer, der jeden herkömmlichen Supercomputer für gewisse Berechnungen überflügelt.

Alle Zeichen deuten darauf hin, dass dieser Moment kurz bevor steht.

Quantencomputer: Der einfachste Weg, die Quantenmechanik zu verstehen lernen

Einen weiteren Punkt finde ich persönlich noch wichtig: Ein Quantencomputer ist letztendlich das einfachste Multi-System in der Quantenmechanik. Wenn Sie die Funktionsweise eines Quantencomputers verstanden haben, haben Sie zwischen den Zeilen auch sehr viel über die Quantenmechanik erfahren. Zu grundlegenden Themen der Quantenmechanik ist es dann manchmal nur ein kleiner Schritt. Deshalb werde ich immer wieder auf einige Themen eingehen: Vielleicht haben Sie von dem „Welle-Teilchen-Dualismus“ gehört oder von „Schrödingers Katze“ oder von „Heisenbergs Unschärferelation“, der Existenz von „Paralleluniversen“. Oder was hat die Quantemechanik mit „Wurmlöchern“ im Weltraumzu tun? Wenn Sie die Ausdauer haben, werden Sie hier einiges darüber erfahren.

Ich selbst habe Physik und Mathematik mit Begeisterung studiert. Seit fast 20 Jahren bin ich jetzt als IT-Berater für große Unternehmen tätig. Meine Leidenschaft für die Quantenphysik habe ich dabei nie verloren, und auf den folgenden Seiten werden Sie verstehen warum.

Ich muss Sie warnen. Die Quantenmechanik und somit die Quantencomputer sind auf faszinierende Art und Weise mit Nichts vergleichbar, mit dem Sie sich bisher beschäftigt haben. Um sie zu erfassen ist ein gewisser Aufwand und ein offener Geist notwendig … aber was ich eigentlich sagen will, drückt Morpheus in dem Science-Fiction-Klassiker „Die Matrix“ noch am Besten aus:

„Das ist deine letzte Chance. Danach gibt es kein zurück. Nimm die blaue Pille — die Geschichte endet… Nimm die rote Pille — du bleibst hier im Wunderland und ich werde dir zeigen wie tief das Kaninchenloch reicht.”

Das Qubit und ein Magier bei „Britain Has Got Talent“

<<
>>

In diesem Beitrag erfahren Sie die grundlegenden Eigenschaften eines einzelnen Qubits und der Quantengatter. Da das Qubit das einfachste Quantensystem ist, lernen Sie dabei auch viel über die Quantenmechanik. Danach werden Sie verstehen warum die Quantenwelt und mit ihr die Qubits und die Quantenprogrammierung so faszinierend ist.

Dabei verwende ich keine „Höhere Mathematik“. Ich versuche Ihnen aber das Wesen der Gleichungen bildlich zu erklären. Damit werden Sie in der Lage sein selbst einen Eindruck davon zu bekommen was Physiker meinen, wenn sie z.B. sagen „Das Elektron ist sowohl Teilchen als auch Welle“.

Ein Magier bei „Britain Has Got Talent“

Fountain Studios, London, 26.5.2014:

Der 25 jährige Kanadier Darcy Oake betritt die Bühne der beliebten Talent-Show „Britain‘s Got Talent“. Was er im Begriff ist zu zeigen wird die Jury und sämtliche Zuschauer buchstäblich aus den Socken hauen.

In der Mitte der Bühne steht ein Gerüst mit einem Podest. Darcy Oake steigt auf eine Stahltreppe nach oben. Dort angekomment erklärt er dem Publikum, was wir schon vermuten: Von diesem Podest wird er nun verschwinden. Der Clou dabei ist Folgendes: dabei zeigt er auf einen Mann, der eine große Kamera geschultert hat und langsam über die Bühne wandert .Alles wird aus verschiedenen Blickwinkeln mitgefilmt und auf einer großen Leinwand live gezeigt.

Es geht los. Während der Kameramann um das Podest wandert sehen wir das Videobild von Darcy Oake, der sich auf dem Podest auf einen Stuhl setzt und sich ein riesiges Tuch über seinen Kopf zieht. Der Kameramann läuft auf der Bühne um das Gerüst herum. Kein Trick ist erkennbar. Wir sehen nur das flatternde Tuch und darunter die Männergestalt von Darcy Oake. Plötzlich fällt das Tuch auf dem Podest zu Boden und Darcy Oake ist … natürlich verschwunden. Aber jetzt kommt das Unglaubliche: Ein Assistent geht hinüber zum Kameramann, der immer noch mitten auf der Bühne steht. Der Assistent nimmt ihm die große Kamera aus den Händen und dreht sie herum. Jetzt sehen wir das Gesicht des Kameramannes auf der Leinwand. Es ist … Darcy Oake. Unglaublich.

Sie sollten sich selbst ein Bild davon machen. Der Trick und auch die Reaktion der Jury darauf sind einfach saucool. Hier geht’s zum Video:

https://www.youtube.com/watch?v=C5N0MDF1CYQ

Was ich so faszinierend an dem Trick finde: Für eine kurze Zeitspanne hat es Darcy Oake so aussehen lassen, als wäre er zweimal gleichzeitig vorhanden gewesen auf der Bühne: Ein Ich als Zauberer auf dem Podest und ein zweites Ich als Kameramann neben dem Podest. Erst als der Assistent das Geheimnis lüftet, wird allen Zuschauern klar, wer er jetzt ist.

Es gibt noch einen anderen Grund, warum ich den Trick so wunderbar finde: Was ich gerade beschrieben habe ist genau das was ein Qubit in der Quantenwelt ausmacht. Darcy Oake verhält sich in seinem Trick also genauso wie ein Qubit.

Warum meine ich das?

Das Qubit

Ein Qubit ist die einfachste Zustandsform der Quantenphysik. Ein binärer Quantenzustand der genau zwei Zustände besitzt. Meistens werden sie mit 0 und 1 bezeichnet, manchmal als „up“ und „down“, es ist ganz egal. Soweit unterscheidet sich ein Qubit nicht von einem Bit in einem herkömmlichen Computer ist. Letzteres ist ein elektronischer Schalter, der zwei Werte haben kann: An oder aus. Dies wird normalerweise durch die Zahlen 1 und 0 symbolisiert. Das Bit hat also entweder den Wert 1 oder den Wert 0.

Und das ist genau der Unterschied und das Unerklärbare an einem Qubit. Genau wie Darcy Oake in seinem Zaubertrick nimmt das Qubit beide „Ich-Zustände“ gleichzeitig ein. Im Laufe der Zeit „pendelt“ das Qubit bildlich gesprochen zwischen diesen Zuständen hin und her: Mal ist es mehr 1, mal ist es mehr 0. Und damit meine ich nicht, dass das Qubit z.B. mal den Wert 0.321, also näher bei 0, und mal den Wert 0,7681, also näher bei 1, hat. Nein: Es gibt wirklich nur die Werte 0 und 1, und beide in einer gemischten oder auch überlagerten Form.

Diese überlagerte Form lässt sich vereinfacht mit einem Zeiger auf einer Kreislinie vergleichen, wie ich es in dem Diagramm unten aufgezeichnet habe. Der Qubit-Zeiger pendelt entlang der Kreislinie. Die zwei gleichzeitig vorhandenen Ich-Zustände sind die x-Achse und die y-Achse des Diagramms. Die aktuellen x- und die y-Werte der Zeigerspitze (also die Ordinate und die Abszisse) sind ein Maß für die Wahrscheinlichkeit in diesem Moment den Zustand zu messen.

 

 

 

 

 

 

 

 

Die Stellung der Achsen „Kameramann“ und „Zauberer auf dem Podest“ haben übrigens nichts mit den tatsächlichen Positionen auf der Bühne zu tun. Das vereinfachte Zeigerbild zeigt an, welche Überlagerung das Qubit in einem abstrakten Parameterraum besitzt. Nebenbei: Diese spezielle Art von Raum wird „Hilbertraum“ genannt, benannt nach dem deutschen Mathematiker David Hilbert, dem vielleicht wichtigsten Mathematiker des 20. Jahrhunderts i.

Natürlich gibt es in der Quantenphysik für das Qubit eine exakte mathematische Beschreibung. Die am Anfang ungewöhnliche Schreibweise lautet:

|qubit⟩ = 0.500 * |0⟩ + 0.866 * |1⟩

Die Schreibweise mit den |0und |1 soll klar machen, dass es sich hierbei nicht um Zahlen, sondern um Zustände, also Objekte handelt. Wir hätten auch schreiben können |Kameramannfür|0und |Zauberer auf dem Podestfür|1⟩.

Nur die roten Dinger vor den Zuständen sind echte Zahlen. Die Zahlen sind ein Maß dafür, wie wahrscheinlich im Moment der Zustand |0⟩ oder |1⟩ gemessen werden würde. Im Laufe der Zeit, also während der Pendelbewegung, verändern sich die Zahlen nach einem genau bekannten Gesetz, der sogenannten „Schrödingergleichung“. Während eines Quantenprogramms werden diese roten Zahlen durch einen festen Satz von Quantengattern, den Grundbausteinen der Quantenprogramme verändert.

Wenn Sie genau hinsehen, bemerken Sie, dass die „Wahrscheinlichkeiten“ 0.500 und 0.866 nicht zusammen 1 ergeben (was in der normalen Wahrscheinlichkeitsrechnung 100% entsprechen würde). Der Grund: An der Gleichung oben gibt es ein paar mathematische Gemeinheiten, die die Sache noch einiges ungewöhnlicher machen ii. Das exakte Zeigerbild für ein Qubit werde ich in einem späteren Beitrag beschreiben iii. Für die Themen, die ich in diesem Beitrag beschreibe, reicht die vereinfachte Sichtweise aber schon ganz gut aus.

Nehmen wir als Beispiel ein Qubit, das im Zustand |0⟩ beginnt und dann in den Zustand |1übergeht.

|qubit⟩ = |0⟩

 

 

 

 

|qubit⟩ = 0.707 * |0⟩ + 0.707 * |1⟩

 

 

 

 

|qubit⟩ = |1⟩

 

 

 

 

Die „Pendelbewegung“ geht solange weiter, bis wir das Qubit tatsächlich messen und es in Interaktion mit seiner Umgebung treten muss. In diesem Moment entscheidet sich das Qubit für einen der beiden Ich-Zustände. Und zwar entscheidet es sich um so mehr für den Zustand, in dessen Richtung das Pendel vorher ausgeschlagen hat.

Dieses Verhalten des Qubits mag vielleicht auf den ersten Blick zwar etwas verwirrend aber doch irgendwie banal aus. Tatsächlich ist dieses Verhalten aber absolut unglaublich. Dieses Verhalten eines Qubits, und natürlich auch jedes anderen Quantenzustandes, ist einer der Gründe warum die Quantenwelt auch über 100 Jahren nach ihrer Entdeckung vielleicht das größte Rätsel der Naturwissenschaften ist:

Es ist als würde die Natur in ihren kleinsten, atomaren Strukturen Darcy Oakes Magie mit den beiden Ich-Zuständen ausführen, die gleichzeitig auf der Bühne sind.

Allerdings nicht als Trick, sondern in echt.

Der „Welle-Teilchen-Dualismus“

Was ich gerade beschrieben habe nennt man auch den „Welle-Teilchen-Dualismus“ der Quantenmechanik: Ein Qubit nimmt mehrere Zustände gleichzeitig ein, wie eine Welle. Bei jeder Messung, die wir durchführen, verhält es sich aber wie ein normales Teilchen und wir messen nur noch einen einzigen Zustand.

Die Sache mit der Welle kommt so ins Spiel: Ein Qubit besitzt nur zwei Zustände. Normalerweise besitzt ein Quantenobjekt wesentlich mehr Zustände und oft sogar unendlich viele! Für ein Elektron sind dies z.B. die Orte sein, an dem es sich aufhalten kann. Unser vereinfachtes Zeigerbild passt dann trotzdem noch. Nur besitzt das Diagramm dann nicht mehr nur zwei Achsen, sondern eine Achse für jeden möglichen Zustand. Also sehr sehr viele Achsen, die senkrecht aufeinander stehen. Gegebenenfalls auch unendlich viele Achsen. Natürlich kann man sich das nicht mehr vorstellen, weil wir uns nur einen Zeiger in einem Diagramm mit höchstens drei Achsen vorstellen können. In der Mathematik kann man solche Systeme mit unendlich vielen Dimensionen trotzdem exakt berechnen. Dieser Zweig der Mathematik wird „Funktionalanalysis“ genannt iv. Den Zeiger können wir dann immer noch auf die gleiche Weise schreiben. Jetzt allerdings mit mehr Zuständen.

|elektron = 0.0134 * |Ort 1 + 0.0136 * |Ort 2 + 0.0137 * |Ort 3 + 0.0137 * |Ort 4 +

….

+ 0.0317 * |Ort 10000 + 0.0316 * |Ort 10001 + 0.0315 * |Ort 10002 +

….

Daraus können wir uns jetzt unsere Welle zusammenbauen: Dazu reihen wir blauen Orts-Zustände wie eine Perlenschnur in der x-Achse aneinander. Die roten Wahrscheinlichkeits-Zahlen zeichnen wir als Pendelausschlag an diesem Ort auf der y-Achse ein. Heraus bekommen wir gerade das Bild einer Welle.

Das sollte Sie aber nicht in die Irre führen. Das Elektron ist keine Welle. Das Elektron ist wie dieser blaue Zeiger in einem Diagramm, dessen Zeigerspitze immer an einer bestimmten Stelle in dem abstrakten Hilbertraum mit den vielen senkrechten Achsen steht. Nur die Wahrscheinlichkeiten kann man so darstellen, dass sie aussehen wie eine Welle.

Der „Welle-Teilchen-Dualismus“ hat für Elektronen erstaunliche Konsequenzen: Es gibt dieses berühmte „Doppelspalt-Experiment“ in dem ein einzelnes Elektron durch zwei benachbarte Spalte gleichzeitig fliegt und auf eine Art Leinwand trifft. Dort heben sich die Wahrscheinlichkeiten komplett auf oder verstärken sich. Das Elektron „interferiert“ also mit sich selbst v.

Der abstrakte Hilbertraum hat übrigens die interessante Eigenschaft, dass er die Entfernungsinformationen der Orte komplett auflöst: Im Hilbertraum stehen alle Ortszustände als eigene Achse senkrecht aufeinander. Die Zeigerspitze ist von jedem Ort „gleichweit entfernt“. Nämlich höchstens um eine 90°-Drehung. Oder anders ausgedrückt: Um von hier bis ins Sternbild Alpha Centauri zu springen, muss das Elektron im Hilbertraum nur eine 90°-Drehung durchführen. Das gleiche gilt für einen Mikro-Sprung von einem Atom zum nächsten.

Ich finde das faszinierend. Vielleicht ist genau das, die richtige Sicht auf unser Universum und unsere Vorstellung von Entfernung kommt nur durch Nebeneffekte zustande vi.

Die Grundidee eines Quantenprogramms

Jetzt werden Sie vielleicht sagen: Moment mal, die Argumentation ist zu dämlich! Das Qubit soll zwei Ich-Zustände zugleich einnehmen, obwohl das eigentlich unmöglich ist. Und wenn wir versuchen genau das zu beobachten, verschwindet der Effekt wieder. Wer soll das denn glauben ?!

Nun ja, viele Physiker wollten das am Anfang auch nicht glauben. Aber viele Experimente haben nachgewiesen, dass in der kurzen unbeobachteten Zeitspanne zwischen zwei Messungen, etwas ungeheuer Merkwürdiges passieren muss, das sich nur durch diese Art von Ich-Überlagerung erklären lässt.

Und dieses ungeheuer Merkwürdiges kann genutzt werden, um neue Arten von Berechnungen auszuführen:

Nehmen wir nochmal das Zauberer-Beispiel. Angenommen Darcy Oake muss eine Aufgabe lösen, die er niemals alleine lösen könnte. Zum Beispiel soll er die Rechenaufgabe 16 – 7 nur mit seinen Fingern lösen. Nur mal angenommen ihm geht es so, wie meinem kleinen Sohn und er kann sie wirklich nicht anders lösen als die Zahlen mit seinen 10 Fingern abzuzählen. Da die Aufgabe aber mit einer Zahl größer als 10 zu tun hat, ist sie für ihn eigentlich nicht lösbar. Jetzt startet er einfach seinen Trick. Er zaubert sein zweites Ich auf die Bühne. Zusammen lösen sie die Aufgabe mit ihren vier Händen. Am Ende zeigen jeweils beide Ichs die Zahl 9 mit Fingern in die Luft. Jetzt ist es egal welches der beiden Ich-Zustände von Darcy Oake am Ende gemessen wird und übrig bleibt. Er hat also die „unmögliche“ Aufgabe gelöst.

Das ist natürlich ein blödes Beispiel. Aber ich hoffe, Sie verstehen worauf ich hinaus will. Natürlich hat ein Qubit keine Finger. Für ein einzelnes Qubits muss man eher eine Frage stellen, die mit Ja oder Nein beantwortet werden kann. Ausserdem sind die beiden Ich-Zustände eines einzelnen Qubits nicht unabhängig voneinander, wie Sie am Zeigerbild oben sehen können. Richtig rechnen kann man erst mit mehreren Qubits.

Das bringt uns sofort zu der Frage: Wie könnte man denn mit einem Qubit rechnen?

Dafür muss man verstehen, wie man ein Qubit überhaupt verändern kann. Das führt uns direkt zu den „Quantengattern“ für Quantencomputer. Im Detail erfahren Sie das in den nächsten Beiträgen auf Quantencomputer-Info. Wenn Sie ausschließlich an der Quantenprogrammierung interessiert sind, können Sie den Rest dieses Beitrags also überspringen. Im Rest dieses Beitrages bekommen Sie von mir ein paar Erläuterungen und Hintergründe zu den Quantengattern, die Ihnen dabei helfen sollten ein besseres Verständnis dafür zu entwickeln.

Der Elektronen-Spin: Die Mutter aller Qubits

Um die Unregelmäßigkeiten in Strahlungs-Experimenten von Atomhüllen zu erklären, schlugen mehrere Physiker Ende der 1920er Jahren vor, dass jedes Elektron einen inneren Drall besitzen müsste: Der Elektronen-Spin. Der Eigendrall dieses Spins dürfte nur zwei mögliche Werte besitzen: „Wert ½, die Drehachse zeigt nach oben“ oder „Wert -½, die Drehachse zeigt nach unten“. Anders ausgedrückt: |up oder |down oder noch einfacher: |0 oder |1 . Der Elektronen-Spin ist als das allererste qubit-artige System in der Quantenmechanik.

Der österreichische Physiker Wolfgang Pauli untersuchte daraufhin die quantenmechanischen Gesetze nach denen sich das Spin-Qubit verändern kann. Die Grundbausteine, die er dafür fand wurden deshalb nach ihm benannt: „Die Paulimatrizen“. Alle anderen Qubits gehorchen auch den Paulimatrizen. Die Spin-Qubits haben aber die interessante Eigenschaft, dass sie eine Raumrichtungen auszeichnen, nämlich der Drehachse des Eigendralls. Und deshalb lassen sich die Paulimatrizen für Spin-Qubits, sehr schön anschaulich beschreiben.

Im Zentrum steht unter anderem die Frage: Wie dreht sich ein Spin-Qubit im Raum? Sie werden sehen, die Antwort ist absolut erstaunlich!

Wie dreht sich ein Spin-Qubit im Raum?

Nehmen wir erst mal einen ganz normalen Gegenstand. Angenommen Sie sitzen einem Bürostuhl gegenüber. Wenn Sie den Bürostuhl drehen scheint es so als ob er seine Form verändert. Natürlich macht er das nicht. Er sieht einfach aus jeder Blickrichtung anders aus. Dabei kommt es noch darauf an um welche Achse Sie den Bürostuhl drehen: Wenn Sie der Sitzfläche eine halbe Umdrehung versetzen sehen Sie die Rückseite des Bürostuhls. Wenn Sie die halbe Umdrehung anders durchführen, z.B. indem Sie ihn kopfüber drehen, sehen Sie auch die Rückseite. Allerdings ist der Bürostuhl jetzt auch noch auf den Kopf gestellt.

Gilt das gleiche für ein Spin-Qubit? Sieht es aus jeder Blickrichtung anders aus, je nachdem wie wir es drehen?

Ja, es sieht aus jeder Blickrichtung anders aus.

Bevor ich das genauer erkläre, müssen wir das Beispiel vom Zauberer und der Bühne noch etwas verfeinern.

Ich hatte Ihnen im vorangegangenen Abschnitt erklärt, dass ein Qubit ein Quantenzustand aus zwei überlagerten Zuständen ist, die es auf geheimnisvolle Weise beide gleichzeitig einnimmt. Im Zauberer Beispiel waren das die beiden Ich-Zustände „Kameramann“ und „Zauberer auf dem Podest“, die auf magische Weise gleichzeitig auf der Bühne vorhanden waren. Wir können uns das Qubit als gedankliches Pendel vorstellen, dass zwischen diesen beiden Ich-Zuständen hin- und herpendelt. Je mehr das Pendel in die Richtung eines Ich-Zustandes ausschlägt, um so wahrscheinlicher wird dieser Ich-Zustand am Ende gemessen. Vor der Messung sind trotzdem beide Ich-Zustände gleichzeitig vorhanden. In unserem Beispiel vom Zauber könnten wir uns diese Wahrscheinlichkeiten so vorstellen: Je unwahrscheinlich z.B. der Zustand „Kameramann“ wird, um so durchsichtiger wird er. Ist der Kameramann komplett ausgeblendet, ist die Wahrscheinlichkeit den Zustand „Kameramann“ zumessen gleich Null Prozent. Ist er vollkommen eingeblendet messen wir den Kameramann mit 100%-iger Wahrscheinlichkeit. Dazwischen sind alle Wahrscheinlichkeitswerte erlaubt. Wir wollen uns die Wahrscheinlichkeiten für die Ich-Zustände also so vorstellen, als wären wir ein Videotricktechniker, der an einem Ein-/Ausblende-Regler für Darcy Oake herumspielt. An dem Zeigerbild oben erkennen wir außerdem: Wenn wir den Zustand „Kameramann“ langsam ausblenden, blenden wir den Zustand „Zauberer auf dem Podest“ automatisch ein.

 

 

 

 

 

 

 

Ist der Zeiger um 45° gedreht sind der „Kameramann“ und der „Zauberer auf dem Podest“ gleich stark eingeblendet. Es gibt ein haufig benutztes Quantengattern, dass sich vereinfacht betrachtet ganz ähnlich verhält. Das „Hadamard“-Quantengatter oder einfach „H“. Was ich gerade bildlich beschrieben habe schreibt man in der Quantenmechanik:

H |0⟩ =0.707 * |0⟩ + 0.707 * |1⟩

Das Hadamard-Quantengatter ist ein sehr oft verwendeter Baustein in Quantenprogammen. Wenn man es z. B. auf alle Qubits in einem Quantencomputer anwendet, belegt es den Speicher in dem Quantencomputer mit allen verfügbaren Werten gleichzeitig.

Das X-Quantengatter: Die Drehung auf der Bühne

Jetzt zur Drehung im Raum.

Das vertrakte dahinter ist, dass das Zeigerbild unseres Qubits nur zwei Achsen besitzt. Der Raum hat aber drei Dimensionen. Tatsächlich steckt dahinter ein altes mathematisches Rätsel: Wie kann ich einen Zeiger mit zwei Komponenten verändern, so dass diese Transformation eine Drehung im Raum darstellt. Das ist knifflig, weil das Ganze eindeutig sein muss. An der Veränderung des Zeigers muss ich eindeutig ablesen können, wie das Qubit im Raum gedreht wurde. Andersherum muss eine bestimmte Drehung im Raum den das Qubit immer auf dieselbe Art und Weise ändern. Das Ganze muss zumindest für kleine Drehungen gelten. Ein Teilgebiet der Mathematik beschäftigt sich mit solchen Fragen: Die „Darstellungstheorie“. Das Problem wurde tatsächlich 50 Jahre vor der Entdeckung der Quantenmechanik von dem Mathematiker William Clifford gelöst. Die endgültige Lösung für das Problem werde ich erst im nächsten Beitrag vorstellen. Unser Beispiel mit dem vereinfachten Zeigerbild können wir aber jetzt schon verwenden, um einen besseren Eindruck von den Quantengattern H, X, Y und Z zu bekommen. Später werden wir dieses Bild dann verfeinern.

Nehmen wir zwei Assistenten, die auf der linken Seite der Bühne stehen und sich den Zaubertrick zunächst nur anschauen. Beide stehen am Anfang nebeneinander. Nehmen wir als Beispiel an, das dass der Zeiger des Kameramann – Zauberer auf dem Podest – Qubits am Anfang auf „Zauberer auf dem Podest“ steht. D.h. er ist komplett sichtbar und der Kameramann ist komplett unsichtbar.

Jetzt geht der erste Assistent langsam gegen den Uhrzeigersinn vorne um die Bühne herum. Während er läuft sieht er, dass der Kameramann langsam sichtbar und der Zauberer im Kasten immer mehr ausgeblendet wird. Für ihn ist es, als würde durch sein Laufen ein magischer Schieberegler verschoben, der beide Zauberergestalten videotechnisch ein- und ausblendet.

Der erste Assistent ist jetzt so weit gegangen, dass er vorne auf der Bühne und direkt vor dem Zauberer-Qubit steht. Der zweite Assistent steht immer noch links neben dem Qubit. Der gelaufene Assistent sieht Folgendes: Der Kameramann ist jetzt genauso eingeblendet, wie der Zauberer auf dem Podest und letzterer ist also entsprechend ausgeblendet. Wenn Sie sich an das Beispiel mit dem 45°-Winkel erinnern, werden Sie erkennen, dass der erste Assistent durch sein Laufen also ein Hadamard-Quantengatter auf das Qubit ausgeführt hat.

Jetzt geht der erste Assistent langsam weiter gegen den Uhrzeigersinn vorne um die Bühne herum. Der Kameramann wird weiter eingeblendet, während der Zauberer auf dem Podest weiter ausgeblendet wird. Als er auf der anderen Seite der Bühne, der rechten Seite, angekommen ist stoppt er. Was sieht er jetzt? Der Kameramann ist komplett eingeblendet und der Zauberer auf dem Podest ist komplett ausgeblendet. Wenn er jetzt das Zauberer-Qubit messen würde, würde er immer den Kameramann messen.

Aber was sieht der zweite Assistent, der die ganze Zeit auf der linken Seite der Bühne stehengeblieben ist? Für ihn hat sich die ganze Zeit nichts geändert: Nur der Zauberer auf dem Podest ist zu sehen und der Kameramann ist komplett unsichtbar. Wenn der zweite Assistent also das Zauberer-Qubit messen würde, würde er immer den Zauberer auf dem Podest messen. Also genau das Gegenteil von dem ersten Assistenten.

So sieht also ein Qubit aus den verschiedenen Blickrichtungen aus.

Die Drehung um 180° auf der Bühne hat übrigens auch einen festen Namen: X-Quantengatter. Also ein weiterer Baustein der Quantenlogik.

Was ich gerade bildlich beschrieben habe schreibt man in der Quantenmechanik:

X|0⟩ = |1⟩ und X|1= |0

Das X- Quantengatter in einem Quantencomputer ist also das Gegenstück zu einem NICHT-Gatter in einem herkömmlichen Computer: Es kehrt jeden Zustand in sein Gegenteil um.

Wenn wir das X- Quantengatter mit einem Hadamard-Quantengatter wie oben kombinieren bekommen wir:

X*H |0⟩    = X* (0.707 * |0⟩ +0.707 * |1⟩ )

= X * 0.707 |0+X * 0.707|1

= 0.707 * X|0+0.707 * X|1

= 0.707 * |1+ 0.707 * |0

Die Quantengatter verändern also nur die blauen Zustände und nicht die roten Zahlen. Das Gleiche gilt für das Plus-Zeichen. Haben Sie die Rechnung verstanden? Herzlichen Glückwunsch! So sehen die Rechnungen in der Quantenmechanik aus (meistens allerdings ein bisschen komplexer). An dieser kleinen Rechnung können Sie übrigens auch schon verstehen, wieso es den Quantenparallelismus gibt. Warum erkläre ich Ihnen gleich im Anschluss.

In der Quantencomputer-Programmierung verwendet man für solche Rechnungen üblicherweise auch Quanten-Schaltungsdiagramme:

 

 

Die 50%-Anzeige ist kein zusätzliches Quantengatter und soll nur verdeutlichen, dass am Ende beide Zustände |0und|1⟩ mit gleicher Wahrscheinlichkeit gemessen werden würden.

Der Grund für den Quantenparallelismus

Wir haben gerade gesehen, dass die beiden Quantengatter X und H nur die blauen Qubit-Zustände verändern und die einfachen roten Zahlen übersehen. Sie übersehen auch das Plus-Zeichen dazwischen. Das ist eine Eigenschaft die alle Operationen der Quantenmechanik und somit auch alle Quantengatter besitzen. In unserer Erfahrungswelt sind wir auf die Messungen der Quanten-Systeme angewiesen und zerstören dabei die Überlagerungen der Qubit-Zustände. Ein Quantengatter hat im Gegensatz dazu kein Problem mit den Überlagerungen. Es wirkt auf jeden blauen Qubit-Zustand gleichberechtigt und erhält dabei die Überlagerung (in Form von den roten Zahlen und dem Plus-Zeichen). Ein X-Quantengatter führt z.B. in einem Rechenschritt parallel zwei NICHT-Operationen aus. Dafür müssen wir nichts tun. Die Quantenmechanik leistet das für uns umsonst. Diese Tatsache steckt hinter dem Quantenparallelismus.

Die beschriebene Eigenschaft der Quantengatter nennt man in der Mathematik übrigens „Linearität“. Die algebraischen Berechnungen die man auf diese Weise durchführt nennt man entsprechend „Lineare Algebra“.

Die Geburtstunde der Quantenmenchanik und die „Heisenbergsche Unschärferelation“

Ich hoffe, Sie haben noch etwas Luft für den Rest des Beitrages. An dieser Stelle kann ich es mir nicht verkneifen, noch die Mutter aller Quantenphänome kurz vorzustellen (obwohl dies eher weniger mit Quantencomputern zu tun hat). Über wohl keine Eigenschaft der Quantenmechanik wurde soviel geschrieben und philosophiert wie über die „Heisenbergsche Unschärferelation“. Kommen wir also zur Geburtsstunde der Quantenmechanik:

Helgoland, 1925: Der junge Göttinger Physiker Werner Heisenberg nimmt sich mehrere Wochen Urlaub, um seinen Heuschnupfen auf der Insel Helgoland zu kurieren. Die Wochen wird er nutzen um die offenen Rätsel der Atomphysik zu untersuchen. Im Juni gelingt ihn der Durchbruch und er schreibt einen Aufsatz, der die Wissenschaft revolutionieren wird. Seine neue Theorie, die „Quantenmechanik“ erklärt das Verhalten von Objekten im atomaren Maßstab auf so fundamental neue Weise, dass selbst Heisenberg zunächst zögert die Arbeit zu veröffentlichen. Zurück in Göttingen bespricht er die neuen Erkenntnisse mit seinem erfahrenen Kollegen Max Born. Dieser erkennt sofort die Tragweite der neuen Ideen. Zusammen arbeiten sie, mit Unterstützung von Borns Student Pascual Jordan, die ganze Quantenmechanik in einer Serie von drei Aufsätzen aus vii.

Heisenbergs erste Arbeit wurde später als „magischer Aufsatz“ bezeichnet viii: Zu Heisenbergs Zeit war nur wenig über die Welt der Atome bekannt. Und trotzdem schaffte er es mit nahezu schlafwandlerischer Sicherheit die Grundidee der Quantenmechanik in wenigen Zeilen herzuleiten: Die Umformulierung der Physik über den abstrakten Hilbertraum.

Im zweiten Aufsatz stellte das Team dann die Unschärferelation vor ix:

Um einen Eindruck von der Unschärferelation zu bekommen, kommen wir noch mal auf unser Zauberer-Beispiel zurück. Wir hatten gesehen, dass Darcy Oake die Zustände „Kameramann“ und „Zauberer auf dem Podest“ gleichzeitig besitzt. Angenommen er hat noch zwei andere Zustände „Alt“ und „Jung“, die er ebenfalls gleichzeitig besitzt. Die vier Eigenschaften hängen aber auf überraschende Weise voneinander ab:

„Kameramann“ und „Zauberer auf dem Podest“ hatten wir mit den beiden Achsen im Zeigerdiagramm gleichgesetzt. „Alt“ und „Jung“ sollen auch zwei Achsen in demselben Zeigerbild bekommen. Aber um 45° gedrehte Achsen! Das Thema hatten wir schon mal beim Hadamard-Quantengatter.

Für das Qubit-Beispiel von oben messen die Assistenten also mit fast 100%-iger Wahrscheinlichkeit den Zustand „Jung“ und nur selten den Zustand „Alt“.

Wenn jetzt ein Assistent den Zustand „Jung“ für Darcy Oake misst, dreht er damit das Zauberer-Qubit auf die grüne „Jung“-Achse. Aber was ist mit den Zuständen „Kameramann“ und „Zauberer auf dem Podest“?

Die sind jetzt komplett ungewiss!

Das Zauberer-Qubit steht jetzt genau in der Mitte zu den anderen beiden Achsen „Kameramann“ und „Zauberer auf dem Podest“. Eine Messung ergibt jetzt zu 50% den Kameramann und zu 50% den Zauberer auf dem Podest. Sobald ein Assistent jetzt zum Beispiel den Zustand Kameramann misst, dreht sich das Zauberer-Qubit auf die Kameramann-Achse.

Jetzt ist aber wieder die Messung für „Jung“ und „Alt“ komplett ungewiss!

Was jetzt auch klar wird: Es macht sogar einen Unterschied, ob die Assistenten zuerst die Messung für „Jung“ oder „Alt“ und danach die Messung für „Kameramann“ oder „Zauberer auf dem Podest“ durchführen oder umgekehrt!

Die Heisenbergsche Unschärferelation sagt jetzt Folgendes aus: Das gleiche Prinzip gilt in der Quantenwelt für den Ort und den Impuls, also die Geschwindigkeit, eines Teilchens. Der Ort ist wie die Zustände „Kameramann“ und „Zauberer auf dem Podest“ (nur wieder mit viel viel mehr senkrechten Achsen), der Impuls wie die Zustände „Jung“ und „Alt“. Wenn wir den Ort genau kennen, hat sich der Quanten-Zeiger des Teilchens so in die Mitte der Impuls-Achsen gedreht, dass der Impuls komplett ungewiss geworden ist. Andersherum gilt das Gleiche: Wenn wir den Impuls genau kennen, können wir nichts mehr über den Ort des Teilchens aussagen. Für beide Größen kommen wir an einer Unschärfe nicht vorbei.

Außerdem macht es einen Unterschied, ob wir zuerst den Ort und danach den Impuls messen oder umgekehrt. Die Messungen in der Quantenmechanik kann man also nicht einfach vertauschen und das gleiche kommt heraus. Deshalb nennt man die algebraischen Berechnungen in der Quantenmechanik auch „nichtkommutativ“. Warum die Natur sich gerade so verhält weiss bis jetzt kein Mensch. Aber auf diese Weise können die Physiker das Phänomen exakt beschreiben.

Nur wenn das Diagramm auf die Achsen für „Kameramann“ und „Zauberer auf dem Podest“ ausgerichtet ist, können wir die Wahrscheinlichkeiten für diese Zustände ablesen. Für die Zustände „Jung“ und „Alt“ gilt das zunächst nicht. Dafür müssen wir die Achsen erst auf die Sichtweise für „Jung“ und „Alt“ drehen. Der Wechsel zwischen den verschiedenen Sichtweisen auf ein Qubit oder auch auf ein Elektron nennt man „Basiswechsel“. Der Basiswechsel zwischen Ortsdarstellung und Impulsdarstellung hat einen speziellen Namen: Die „Fouriertransformation“. Ein Kernbaustein des Shor-Algorithmus ist z.B. auch die Fouriertransformation, die auf mehrere Qubits angewendet wird. Im Schaltdiagramm des Shor-Algorithmus auf der Quirk-Homepage unten erkennen Sie das an dem Kürzel „QFT“. Für ein Qubit ist die Fouriertransformation gerade das Hadamard-Quantengatter.