Quantencomputing ohne Quantenmechanik?

Von Ulrich Trottenberg und Bernhard Thomas

Bild: interactive.quantumnano.at

Quantencomputing ist ein heißes Thema - in Universitäten,  Forschungszentren,  in den großen IT-Firmen, in der internationalen und nationalen Forschungsförderung - und mittlerweile auch in der Politik. Das geht so weit, dass uns führende Personen der Öffentlichkeit, die sonst mit ihren schwachen mathematischen Leistungen und ihrem mathematischen Desinteresse kokettieren, uns das Quantencomputing mit seinen großartigen, revolutionären Möglichkeiten „erklären“.

Auf der anderen Seite haben uns die bedeutendsten Physiker des letzten Jahrhunderts erklärt, dass man die Quantenmechanik - also die physikalische Basis des Quantencomputing – wenn überhaupt,  nur mathematisch verstehen kann: Zentrale Phänomene der Quantenmechanik, insbesondere die Superposition und die Verschränkung,  entziehen sich der Anschauung und stehen in (scheinbarem) Widerspruch zur physikalischen Alltagserfahrung.  Selbst Albert Einstein bezeichnete das Phänomen der Quanten-Verschränkung  als spukhafte Fernwirkung, der ebenfalls geniale Physiker Richard Feynman formulierte pointiert: „Man kann sicher sagen, niemand versteht die Quantenmechanik.“  Und Erwin Schrödinger,  einer der Begründer der Quantenmechanik, versuchte mit seinem berühmten Katzen-Paradox in einem oft missverstandenen Gedankenexperiment die Übertragung quantenmechanischer Phänomene auf die Alltagswelt ad absurdum zu führen (Siehe "Schrödingers Katze" bei Wikipedia).

Bild: scratchpost.dreamhosters.com

 

Und die echten Experten des Quantencomputing? Was sagen die? Da überwiegen in der Tat die optimistischen Einschätzungen (nicht nur bei denen, die von den Forschungsmilliarden gefördert werden). Sie gehen z. B. davon aus, dass man mit Quantencomputern - bei einer Reihe wichtiger Anwendungen - viel, viel schneller, „exponentiell“ schneller rechnen kann als mit herkömmlichen Computern, dass man mit Quantencomputern Probleme lösen kann, die als praktisch unlösbar gelten, fast jeden Verschlüsselungscode knacken kann usw. .

Aber es gibt auch die Skeptiker, die noch einen weiten Weg vor sich sehen bis zu einer praktischen Realisierung großer, leistungsfähiger Quantencomputer. Ein Argument der Skeptiker ist auch, dass mit Quantencomputern erzielte Ergebnisse in aller Regel nur mit einer gewissen Wahrscheinlichkeit „richtig“ sind und dass man möglicherweise die Rechnungen sehr häufig  wiederholen muss, um die Ergebnisse abzusichern.

Schließlich die Algorithmen, die Software? Gibt es die denn schon? Kann man die entsprechenden Algorithmen verstehen? Die Interscience Akademie für Algorithmik hat den Versuch gemacht, Quanten-Algorithmen verständlich zu machen mit nicht mehr als Schulmathematik (Unterstufe / Mittelstufe). Daraus ist eine Serie von 16 Blogs entstanden, eingeleitet durch den Artikel "Quanten-Computing für die Schule - Echt jetzt?". Das geht ohne die Quantenmechanik zu bemühen – und auch ohne die quantenmechanische Mathematik (wie Hilberträume, partielle Differentialgleichungen, Tensoren, Matrizen und Vektoren usw.) zu verwenden. Was vorausgesetzt wird, ist ein bisschen Schulmathematik, einfaches Grundverständnis für klassische Computer; nützlich beim Ausprobieren, aber nicht notwendig, sind elementare Programmierkenntnisse.

Viel Spaß beim Quantencomputing!

Bild: www1.wdr.com

 


Quanten-Computing für die Schule - Echt jetzt?

Von Bernhard Thomas und Ulrich Trottenberg

 

Kann man Quanten-Computing als Thema im Schulunterricht behandeln? Die erste schnelle Antwort wird sein: sicher nicht! Die physikalischen Grundlagen, die Mathematik dazu übersteigt unsere Vorstellungskraft und jegliches Wissen, das man im Rahmen von Schule vermitteln bzw. erwerben kann, sei es im Physikunterricht, in Mathematik oder im Informatikunterricht. Andererseits hört und liest man seit einiger Zeit viel über das Potenzial zukünftiger Quantencomputer - übertroffen nur noch von der Diskussion über Künstliche Intelligenz.

Dem Quanten-Computing, genauso wie dem "klassischen" Computing, liegen Algorithmen zugrunde. Wenn wir uns auf das Algorithmische des Quanten-Computing beschränken, kann es uns dennoch gelingen - etwa im Rahmen des Informatikunterrichts - auch Algorithmen aus der "Quanten-Welt" (Qubit-Algorithmen) kennen zu lernen, zu verstehen und sogar zu konstruieren. Und, was das Ganze besonders spannend macht, auch auf den ersten echten Quantencomputern laufen zu lassen! Auch bei herkömmlichen Computern verstehen wir ja die Physik nicht wirklich, können aber dennoch schon Grundschülerinnen und Grundschülern erklären, wie man grafische Programme erstellt, die dann auf Computern oder kleinen Robots laufen. (Siehe Open Roberta, Calliope, Scratch usw.)

Die Q Blog-Serie der Interscience Akademie für Algorithmik

Unsere Q Blog-Serie ist primär gedacht als Information, Material und Anregung für Lehrpersonen oder interessierte Schülerinnen und Schüler. Es gibt aber auch einiges für jeden zu entdecken, der immer schon einmal wissen wollte, was das Besondere an den geheimnisvollen Qubit-Algorithmen und ihren viel gerühmten Eigenschaften ist. Denn tatsächlich - einiges ist anders als man es von herkömmlichen Algorithmen gewohnt ist.

Schulwissen

Wir werden sehen, dass wir uns in dieser Serie auf allgemeines Schulwissen beschränken können. D.h. wir kommen zum Einen ohne Kenntnisse  der Quantenphysik aus, wenngleich die meisten Ideen und Konzepte der  Quanten-Informatik und der Qubit-Algorithmen aus der Quantenphysik abgeleitet sind, und zwar insbesondere aus der Mathematik der Quantenphysik. Dort haben sie auch ihre Entsprechung, sogar ihre Umsetzung, in Form von Quanten-Computern. Der Respekt vor diesem immensen mathematisch-naturwissenschaftlichen Wissen seit den Anfängen des letzten Jahrhunderts kann nicht groß genug sein, Respekt gebührt vor allem denen, die sich seit etwa den 1980er Jahren mit der informatischen Bedeutung der Quantenphysik befasst haben und befassen. Auch hier ist der Schatz an dokumentiertem Wissen heute unüberschaubar. Was aber nicht bedeutet, dass man aus Ehr-Furcht davor keinen Zugang zu diesen Dingen finden kann.

Zum anderen wollen wir ohne die "höhere Mathematik" auskommen. Wir verzichten auf Hilbert-Räume, Vektoren und Matrizen, Tensor-Rechnung, komplexe Zahlen, partielle Differentialgleichungen - das übliche Handwerkszeug professioneller Quanten-Mathematiker und-Informatiker. Was wir verwenden, ist bewusst eher mittleres Schul-Niveau: die Darstellung von Punkten im Koordinatensystem, den Einheitskreis im Koordinatensystem, ab und an den "Pythagoras", Prozentrechnung und relative Häufigkeiten, auch mal den Sinus oder Cosinus, wenn's hoch kommt -  und was wir brauchen, ist Offenheit für neue Entdeckungen.

Zugegeben, wir werden damit nicht die gesamte Quanten-Informatik und ihr algorithmisches Instrumentarium darstellen können. Aber wir werden mit unseren Mitteln die Grundprinzipien von Qubits und Qubit-Algorithmen verstehen, einfache bis namhafte komplexere Algorithmen kennenlernen und dabei viele der mit Qubits verbundenen Begriffe und Eigenschaften entmystifizieren. Und auch der korrekte, sinnvolle Sprachgebrauch der Qubit-Welt will eingeübt werden.

Entdecken statt Auswendiglernen

Auch in der Darstellung des Themas Qubit-Algorithmen gehen wir einen etwas anderen Weg. Statt mit den üblichen Definitionen loszulegen, gehen wir hier auf Entdeckungstour. Unter anderem die grundlegenden Modelle – vom Bit bis zum Qubit – entwickeln wir anhand von “virtuellen Experimenten”. Die allerdings nichts mit Quantenphysik zu tun haben. Natürlich "lernt" man dabei auch Neues, das man sich merken sollte - aber dafür gibt es Beispiele "zum Anfassen", damit das leichter fällt.

Qubits oder Quanten?

Warum sprechen wir von Qubit-Algorithmen und nicht von Quanten-Algorithmen? Qubits sind die "Objekte" der Quanten-Informatik und der Algorithmen, die wir hier besprechen. Man kann sie erst einmal als Entsprechung zu klassischen Bits verstehen. Sie sind im Prinzip völlig unabhängig von dem, was "Quanten" bedeutet - bis auf die Tatsache, dass man sie am besten auf sogenannten Quanten-Computern  implementiert, die Qubits und die Qubit-Algorithmen. Solange man sich also mit den Objekten nur algorithmisch beschäftigt, spielen Quanten im physikalischen Sinne keine Rolle. So auch in unserer Blog-Serie. Zugegeben, die Bezeichnung Qubit ist natürlich eine Zusammenfügung aus Quantum und Bit.

Quanten dagegen sind ein physikalisches Konzept. Wen das nicht interessiert, kann diesen Absatz ab hier überspringen. Man kann auch ohne dieses Wissen alles Weitere verstehen, da sind wir sicher.

Ein Quant bezeichnet ursprünglich die kleinste Einheit einer physikalischen Wirkung (Wikipedia: Plancksches Wirkungsquant). Max Planck erkannte, dass in der physikalischen Welt alle Veränderungen in "Sprüngen" von mindestens Quantengröße vor sich gehen - wenn man genau genug hinschaut. (Der viel zitierte "Quantensprung" ist also eigentlich die kleinste Veränderung, die man erwirken kann.)

Im atomaren und sub-atomaren Bereich der Physik gibt es vielfältige Abläufe, die in diesem Sinne "gequantelt" von statten gehen. Wenn zum Beispiel ein Elektron auf ein niedrigeres Energieniveau zurück fällt, gibt es Energie von der Größe eines Vielfachen des Planckschen Quants ab und das in Form eines Lichtteilchens (Photon). Üblicherweise werden daher auch diese "Energiepakete" als (Licht-)Quanten bezeichnet. Typisch für ein Photon ist, dass es je nach experimenteller Bedingung ein - im Sinne makroskopischer Phänomene - teilchenartiges oder ein wellenartiges Verhalten zeigt. Auch andere physikalische Objekte, wie z.B. ein Elektron, kann dieses Verhalten zeigen, weshalb man sie ebenfalls als physikalische Quantenobjekte oder -systeme auffasst bzw. verwendet.

Das Verhalten von Quantenobjekten lässt sich durch eine (mathematische) Zustandsbeschreibung charakterisieren (Quantenzustand), etwa durch mathematisch anspruchsvolle partielle Differentialgleichungen (z.B. die Schrödinger-Gleichung). Damit lassen sich bestimmte Quanteneigenschaften erklären und durch einen Mess-Prozess bestimmen.

Grundlage für allgemeine Quanten-Computer, auf denen wir Qubit-Algorithmen ablaufen lassen können, sind Quantensysteme, also physikalische Systeme, bei denen sich Zustandsänderungen mittels Quanten vollziehen. Für die Realisierung von Qubits verwendet man Systeme mit Quanteneigenschaften, die grundsätzlich zwei gegensätzliche Ausprägungen haben, und deren allgemeiner Zustand als Überlagerung dieser beiden Ausprägungen dargestellt werden kann (Superposition genannt).

Eine weitere Besonderheit, die wir auch bei den Qubit-Algorithmen verwenden, ist, dass man den Quantenzustand eines Systems nicht wissen kann - prinzipiell nicht! Was man tun kann, ist, ein Quantensystem messen und aus den Messergebnissen gewisse Rückschlüsse auf den Zustand ziehen. Quantenphysiker können aber durchaus Quantenzustände "herstellen", durch physikalische Operationen und durch Überprüfung mit Messungen. Allerdings kann man ein Quantensystem nicht zweimal messen; nach dem ersten Messen ist es nicht mehr in dem Zustand, in dem es bei der Messung war. Schlimmer noch, bei den meisten Messungen am irgendwie "gleich hergestellten" Quantenzustand bekommt man unterschiedliche Ergebnisse! Wenn die Messung aber vielfach wiederholt wird, kann man allerdings eine Häufigkeitsverteilung der Ergebnisse erstellen und daraus so etwas wie die Wahrscheinlichkeit für die einzelnen Ergebnisse ableiten. Der Quantenzustand "äußert" sich dann per Messungen in Form einer Wahrscheinlichkeitsverteilung für die möglichen Ergebnisse. Höchst eigenartig - aber darauf basiert letztlich das Besondere an Qubits und Qubit-Algorithmen - sie sind eine Abstraktion des Geschehens bei bestimmten physikalischen Quantensystemen. Und darauf wollen wir uns hier beschränken.

Ein faszinierendes und auch für den Physik-Laien gut verständliches Video findet man hier. Es demonstriert physikalisch die auch in der Qubit-Algorithmik wichtigen Begriffe Superposition und Verschränkung sehr anschaulich anhand von Photonen-Experimenten.

Hier endet der "Quanten-Absatz".

Qubit Prinzipien

Das Ungewöhnliche an Qubits lässt sich durch zwei, drei Grundprinzipien beschreiben:

Erstens, ein Qubit, oder auch ein Qubit-System, hat Zustände, die sich nicht direkt zeigen, sondern nur indirekt, wenn man sie misst. Dabei kann es durchaus sein, dass verschiedene Zustände gleiche Messergebnisse liefern.

Zweitens, es gibt Zustände, deren Messung nicht ein eindeutiges Ergebnis liefern - wie 0 oder 1 beim "Messen" normaler Bits (z.B. Lesen, Ausdrucken, Verrechnen). Ihr Messergebnis kann nur durch feste Wahrscheinlichkeiten für verschiedene mögliche Ereignisse (z.B. 0 oder 1) charakterisiert werden. Das ist eine Besonderheit, die wir am besten durch eine einfache Analogie verdeutlichen.

Man stelle sich vor: In einem Pausenraum stehen zwei Getränkeautomaten. Der eine Automat ist ein Becher-Automat. D.h. wenn man C oder L drückt und Geld einwirft, fällt ein Becher und wird mit Cola, bzw. Limo gefüllt. Außerdem gibt es die Taste H (für Halbe-Halbe), damit bekommt man eine Mischung halb Cola, halb Limo, also so etwas wie Mezzomix. Insgesamt also: drei Tasten, drei Getränke. Der andere Automat gibt nur Getränke in Flaschen aus. C und Geldeinwurf: eine Flasche Cola, bei L eine Flasche Limo. Und jetzt kommt's: Was, wenn man H wählt? Nicht etwa eine Flasche Mezzomix, sondern Cola! Beim nächsten Mal: wieder Cola. Also sind C und H einfach zwei Tasten für Cola? Beim nächsten Mal H gibt es eine Limo. Der nächste bekommt wieder eine Cola, die nächsten Schüler Limo, Limo, Cola usw. jeweils ein Flasche. Also drei Tasten, zwei "Outputs"? Die Schüler finden das krass und kaufen nur noch H - wegen des Überraschungseffekts. Ein Schüler kommt auf die Idee zu zählen. Über die ganze Pause hinweg zählt er 14 mal Cola und 16 mal Limo. Aha, das ist es also, was H bedeutet: Cola und Limo-Flaschen werden (zufällig) in etwa der Hälfte aller Käufe ausgegeben.

Der zweite Automat ist ein "Qubit-Cola-Limo-Automat": Mit Taste C gibt's Cola, mit L gibt's Limo und mit H gibt's ... wir haben's gesehen.

Drittens, und dann reicht es erst einmal, man kann alle diese Zustände "herstellen". D.h. es gibt Qubit-Operationen (ähnlich wie Bit-Operationen), die einen Zustand in einen nächsten überführen. Und mit solchen kann man alle Qubit-Zustände erreichen, sogar determiniert.

Aus Qubits und solchen Operationen werden Qubit-Algorithmen aufgebaut - die Messungen nicht zu vergessen.

Spannend! Mit Qubit-Algorithmen auf echten Quantenrechnern experimentieren

Seit etwa 2017 gibt es von IBM die in der Cloud verfügbare Umgebung IBM Q Experience. Sie umfasst den Zugang zu realen Quanten-Computern, QC-Simulatoren und Programmierumgebungen. Besonders motivierend ist die Möglichkeit, kleine Qubit Algorithmen grafisch zu erstellen (mit dem Circuit Composer). Für fortgeschrittene Qubit-Algorithmen bietet sich ein mit Python verwendbares Paket für Qubit-Programmierung an (das Qiskit). In dieser Blog-Serie beschränken wir uns auf den IBM Q Composer zur Illustration und beim Experimentieren mit Qubit-Algorithmen. Programmieren ist keine Voraussetzung für diese Q-Serie. Wer aber Spaß daran hat, kann viele interessante Dinge mit dem Composer oder in der Kombination von Python und Qiskit ausprobieren - ebenfalls direkt in der IBM Q Experience Cloud (via Browser). *)

Auch Google hat eine sehr leistungsfähige QC-Umgebung in der Cloud verfügbar gemacht (Google Cirq). Sie bietet ähnliche Möglichkeiten zur Qubit-Programmierung wie die IBM Umgebung und kann hier als Alternative zur IBM Q Experience durchaus in Betracht gezogen werden. Microsoft bietet mit Azure Quantum eine Entwicklungsplattform mit der Programmierumgebung QDK (Quantum Developer Kit) und Simulatoren. Die Quantum-Hardware wird über Azure von Partnern integriert.

Es folgt eine Übersicht über die einzelnen Abschnitte der Q-Serie, nummeriert von Q1 bis Q16.

 

Qubit-Algorithmen für die Schule - die Q-Serie

Q1 Etwas ist anders! - Qubit-Algorithmen

Die An-Moderation.

Q2 Etwas ist anders! - Hello Qubit World

Wir machen uns damit vertraut, wie ein Qubit-Algorithmus "aussieht", auch wenn wir die Details jetzt noch nicht verstehen. Jedenfalls schon ganz schön exotisch.

Q3 Vom Bit- zum Qubit-Modell

Wir entdecken das Bit neu als "kleinen Bruder" des Qubits. Wir finden eine Black Box mit der Bezeichnung BIT vor, experimentieren damit und machen uns so ein BIT-Modell. Am Ende finden wir eine Blue Box mit der Aufschrift ZBIT vor.

Q4 ZBIT – unterwegs zum Qubit-Modell

Wir experimentieren mit der ZBIT-Box und stellen fest, dass sie sich an einer Stelle ganz anders verhält als die BIT-Box, nämlich zufällig! Damit sind wir schon auf dem halben Weg zum Qubit. Wir untersuchen die Blue Box und machen uns ein Modell, das wie eine ZBIT-Box funktionieren soll. Stellen allerdings fest, dass das im ersten Anlauf nicht richtig klappt.

Q5 Ein verbessertes ZBIT-Modell

Wir entwickeln ein Modell für ZBIT, das passt. D.h. man kann die Experimente damit nachvollziehen und erklären. Und Voraussagen machen, die wir durch Experimente mit der Blue Box bestätigen können. Bis hierhin haben wir auch schon einiges an abkürzenden Schreibweisen verwendet, die später auch als Gerüst für die Beschreibung von Qubit-Algorithmen dienen. Wir haben auch gelernt, dass "Messen" eine wichtige Rolle spielt, um Aussagen über den Zustand eines ZBIT-Modells zu machen.

Q6 Zwischenspiel - ZBIT-Spielereien

Namen sind Schall und Rauch. Nicht wie sie heißen, macht Zustände zu ZBIT-Zuständen, sondern wie man sie verwendet. Wir spielen ein wenig herum mit verschiedenen Möglichkeiten ein ZBIT-Modell zu beschreiben: vom Basketball-Spiel über die Grafik aus Q2 (Hello Qubit-World) bis zu Punkten im x-y-Koordinatensystem.

Q7 Qubit - Ein Modell für Qubit Algorithmen

Mit der Grey Box QBIT lernen wir das Verhalten von Qubits kennen und verstehen. Die "Experimente" sind vielfältiger, damit auch ihre Beschreibung als elementare Algorithmen. Die QBIT-Zustände haben wir aber schon am Ende der ZBIT-Spielereien richtig als Punkte im x-y-Koordinatensystem dargestellt. Das ZBIT ist tatsächlich schon ein vereinfachtes Qubit - mit seinen Zuständen, Operatoren und Messvorschriften.

Q8 Fingerübungen - Einfache Qubit Algorithmen ausprobiert

Einfache 1-Qubit und erste 2-Qubit Operationen werden vorgestellt in Form einer einfachen symbolischen Notation und als Gates (Gatter) in Composer Circuits (Schaltkreise). Wir lernen die Wirkung und das Zusammenwirken von einigen Gates verstehen, darunter ein erstes Controlled Gate, CNOT, dessen Wirkung auf einen Qubit-Zustand vom Zustand eines anderen Qubit abhängt. Gelegentlich verwenden wir alternativ zur Koordinatendarstellung auch die |0>, |1> Form (Ket-Notation) zur Kennzeichnung von Zuständen.

Q9 Verschränkung und andere 2-Qubit Phänomene

Wir probieren weitere einfache 2-Qubit Algorithmen aus und erklären die Zustandsabfolge und die Messergebnisse. Wir stoßen dabei erstmalig auf die Verschränkung von 2-Qubit-Zuständen und den Kickback-Effekt, beides wichtige Elemente in Qubit-Anwendungen.  Die Wirkung von Gates und die Zustandsabfolgen werden berechenbar durch einfache Formeln auf Basis der Zustandskoordinaten.

Q10 Qubit-Algorithmen - Hinter die Kulissen geschaut

"Hinter die Kulissen schauen" heißt, die Effekte der Zwei- und Mehr-Qubit Algorithmen durch Zustandsübergänge und Messungen zu erklären.  Mittels Koordinatendarstellung und Gate-Formeln. Bei dieser Gelegenheit lernen wir noch einige weitere Gates aus dem Repertoir der Qubit-Algorithmik und des Composers kennen. Unter anderem das über 3 Qubits wirksame Toffoli Gate.

Q11 3-Qubit Circus

Mit mehr Qubits werden Qubit-Algorithmen vielfältiger - aber auch komplizierter zu verfolgen. Wir konstruieren und analysieren einige 3-Qubit Circuits. Auch bei 3-Qubit-Systemen gibt es den Effekt der Verschränkung, sogar noch vielfältiger.

Q12 Ein echter Quanten-Würfel in 3 Qubits

Mit diesem Abschnitt und den folgenden stellen wir Qubit-Algorithmen vor, die man (fast) als praktische Anwendungen sehen kann. Der erste ist ein normaler 6-flächiger Würfel, der, wenn er auf einem realen Quantencomputer ausgeführt wird, einen echten Zufallswürfel darstellt, der nach den Gesetzen der Quantenphysik prinzipiell nicht vorausberechenbar ist. Hilfestellung für die Idee dieses 3-Qubit Algorithmus liefert eine 3-Qubit-Verschränkung, der sog. W-Zustand, den wir hier näher untersuchen.

Q13 Superdichte Codierung und Quanten-Kommunikation

Wir konstruieren und untersuchen Qubit-Algorithmen, mit denen man prinzipiell mehr Bits in weniger Qubits codieren und übertragen kann. Also z.B. 2 Bits in einem Qubit. Das Modell der superdichten Quanten-Kommunikation ist zwar ungewöhnlich aber mit unseren Mitteln leicht nachvollziehbar. Auch hier spielt wieder die Verschränkung eine Rolle. Das Verfahren funktioniert auch in Realität. Quanten-Kommunikation hat man schon über hunderte von Kilometern getestet,

Q14 Quanten-Teleportation

Während Quanten-Kommunikation die Übertragung von Bits mittels verschränkter Qubits ermöglicht, bedeutet Quanten-Teleportation (trotz dieses SciFi Wortes) das Übertragen eines Qubit-Zustands auf ein anderes, entferntes Qubit mittels Bit-Information, die zuvor aus Messungen gewonnen wurde. Wir konstruieren, anlaysieren und diskutieren den Quanten-Teleportations-Algorithmus.

Q15 Ein Geheimnis mit einer Frage rauskriegen - Bernstein-Vazirani-Algorithmus

Wir stehen vor der Aufgabe, eine geheime Bit-Kette herauszufinden, etwa einen Code oder den Weg durch ein Labyrinth. Wir probieren es mit klassischen (Bit-)Algorithmen, die typischerweise immer eine gewisse Anzahl von "Fragen" benötigen, und schließlich mit einem Qubit-Algorithmus, der das mit nur einer "Frage" schafft. Wir haben damit ein erstes Beispiel für einen Beschleunigungseffekt durch Qubit-Parallelismus. Wir untersuchen, wie das geht und warum das geht und wie man das allgemein verwenden kann.

In diesem Abschnitt führen wir auch die Qubit-Programmierung mittels Qiskit ein. Ein Link verweist auf ein vollständiges, lesbares Qiskit/Python-Programm.

Q16 Was man so liest

Hier diskutieren wir den Sprachgebrauch und einige typische Aussagen, wie sie in den Medien zum Thema Quantencomputing immer wieder auftauchen. Was ist gemeint, was ist dran, wie muss man das verstehen und - was steckt eigentlich dahinter? Wir tun dies auf der Basis des erworbenen Verständnisses aus dieser Q-Serie.

QX Etwas ist anders - und es gibt noch viel mehr

Es ist zu erwarten, dass sich weitere interessante Ideen und Algorithmen ergeben, die sich auf der Ebene "Schulwissen" ebensogut darstellen lassen, wie die bisherigen Beispiele, auch wenn sie vielleicht noch etwas komplizierter werden.  Nur was man erklären kann, hat man verstanden. Ideen können gerne auch aus Kommentaren und Mitteilungen zu dieser Blog-Serie kommen. Die würden wir in weiteren Blog-Abschnitten unter QX aufnehmen.

Und hier beginnt die Q-Serie.

 

*) Update Aug. 2020: Das Erscheinungsbild der IBM Quantum Experience Umgebung hat seit etwa August 2020 ein Update erfahren. Insbesondere das User Interface des Circuit Composers hat sich etwas verändert. Es gibt mehr vordefinierte Gates, ein paar andere Voreinstellungen und Farben. Mit Blick auf die Beispiel-Circuits in der Blog-Serie haben sich aber im Wesentlichen nur die Farben der Gates geändert. Interessant ist auch, dass auf der Oberfläche nicht nur der Circuit dargestellt wird, sondern auch gleich die Ergebnisse von Messungen, sowie andere interessante Informationen, auf die wir in den Blogs nicht eingegangen sind. Dazu gehört auch, wenn man es richtig versteht, eine Darstellung der aktuellen Zustandssuperposition (Statevector), also die n-Qubit Basiszutände mit ihren Koeffizienten (Amplituden genannt).

 

Dank

Unser Dank geht unter anderem an Dr. Roman Wienands für die Antworten auf viele algorithmische Detailfragen. Dr. Wienands und der Zweitautor führen übrigens seit vielen Jahren sehr erfolgreich Seminare zu "Algorithmen im Schulunterricht" für die Lehrerausbildung am Mathematischen Institut der Universität zu Köln durch. Seit einiger Zeit auch zu Themen aus der Künstlichen Intelligenz und dem Quantencomputing.

Der Zweitautor hat darüber hinaus die Kapitel der Q-Serie als Diskussionspartner intensiv begleitet, die Texte akribisch durchgesehen und, natürlich, viele Fehler und einige Unverständlichkeiten gefunden.

Zu diesem Einführungstext wird es ein Companion-Text geben, der die gesellschaftlichen und bildungspolitischen Aspekte des Quanten-Computing sowie dessen erwartete Möglichkeiten beleuchtet.

Kontakte

Prof. Dr. Ulrich Trottenberg: ulrich.trottenberg@interscience.de

Dr. Bernhard Thomas: bernhard.thomas@interscience.de


Q15 Ein Geheimnis mit einer Frage rauskriegen - Bernstein-Vazirani-Algorithmus

In diesem Abschnitt wollen wir heraus finden, was es mit Quanten-Parallelismus und der viel zitierten Super-Beschleunigung von Quanten-Algorithmen auf sich hat.  Wir bleiben dabei wieder auf dem Boden der Qubits und werden hier insbesondere wieder von einem Effekt Gebrauch machen, den wir in Q9 schon kennen gelernt hatten, dem (phase) Kickback.

Zur Lösung einer Aufgabe kann es durchaus verschiedenene Algorithmen geben und diese können sich darin unterscheiden, wieviel Aufwand es macht, um die Aufgabe zu lösen. Den Aufwand misst man meist in der benötigten Anzahl von Rechenschritten, Funktionsauswertungen, Entscheidungen usw. und charakterisiert den algorithmischen Aufwand dann in Bezug auf die "Größe" der Aufgabe. Bei einer Sortieraufgabe kann diese z.B. die Anzahl n der zu sortierenden Dinge sein.

Denken wir uns z.B. ein einfaches "binäres" Labyrinth. D.h. es gibt einen Eingang, danach gibt es Verzweigungen, bei denen man links oder rechts gehen kann und nach n Verzweigungen kommt man an eine Tür. Alle Türen bis auf eine, dem Ausgang, sind verschlossen. Eine naive Methode, das Labyrinth zu "knacken" wäre, immer vom Eingang loszulaufen und alle möglichen Wege auszuprobieren, bis man an den Ausgang kommt. Und irgendwann erwischt man ja den richtige Weg. Dieser nicht-so-clevere Algorithmus kann also die Aufgabe lösen. Aber wie hoch ist der Aufwand? Wenn man Glück hat, ist schon der erste Weg der richtige, wenn man Pech hat, der letzte. Also: schlimmstenfalls muss man 2^n Wege ausprobieren.

Orakel und Geheimnisse

Ein Orakel ist etwas, das ein Geheimnis kennt und das man dazu befragen kann. Zum Beispiel das Ergebnis eines WM-Fussballspiels. In der Qubit-Welt wird ein Orakel etwas abstrakter verstanden, als Black-Box oder eine Funktion mit unbekannten Größen (dem Geheimnis), die man durch Berechnung der Funktionswerte (Antworten) für verschiedene Eingabewerte (Fragen) herausfinden will. So kann man  die Aufgabe "Gleichungen mit zwei Unbekannten" auch als Orakel auffassen, was bei vielen auch im übertragenen Sinne ein ewiges Orakel ist.

Nehmen wir an, es gibt ein Orakel, das den richtigen Weg kennt aber geheim hält. Das Geheimnis ist eine Kette von 0 und 1, wobei 0 für "links abbiegen" steht und 1 für "rechts abbiegen". Die Bit-Kette beschreibt damit den Weg vom Eingang bis zur richtigen Tür, dem Ausgang. Wer die 0-1-Kette kennt, kennt den Weg durch das Labyrinth.

Wie kann man diese Bit-Kette herausfinden?

Das erste Orakel

Man könnte alle möglichen n Bit langen 0-1-Ketten aufschreiben und einzeln dem Orakel vorlegen, bis es eine 1 (für richtig) als Antwort gibt. Das entspricht dem Aufwand unserer Wegsuche am Anfang: schlimmstenfalls müssten wir 2^n mal fragen. Der Algorithmus ist naheliegend und klassisch einfach zu beschreiben:

Für alle 0-1-Ketten der Länge n, von 000...0 bis 111...1, 
vergleiche bit-weise mit der geheimen Bit-Kette. 
Zähle die Übereinstimmungen. Sobald eine 0-1-Kette 
n Übereinstimmungen liefert, ist das Geheimnis gefunden. Ende.

Wir gönnen uns hier den Spaß und die Übung, dieses Vorgehen als einen Qubit-Algorithmus mittels Composer darzustellen. Etwa so:

Hier ist n=4 und die vorgelegte 0-1-Kette ist 1011, generiert mittels X-Gates. Das Orakel ist als Qubit-Orakel konstruiert und für uns nicht sichtbar. (Noch nicht. Weiter unten lüften wir die Abdeckung und sehen, wie das Orakel als Qubit-Algorithmus aussieht.) Qubit q4 übernimmt die "Antwort" des Orakels, das wir durch Messung sichtbar machen. Wenn wir die richtige Bit-Kette als Input vorgelegt haben, bekommen wir hier (zu 100% der Wiederholungen) eine 1 als gemessene Antwort. Für jede andere Bit-Kette dagegen ein "gemischtes" Messergebnis, d.h. eine Häufigkeitsverteilung über 0 und 1.

Wenn wir in diesem Beispiel alle Inputs ausprobieren, finden wir, dass das Geheimnis 0110 ist. Je nachdem, wie wir vorgehen, kann das maximal 2^n = 16 Versuche bedeuten.

Das zweite Orakel

Eine bessere Möglichkeit ist es, alle Bit-Ketten mit nur einer 1 aufzuschreiben und zu fragen, ob es an gleicher Position auch eine 1 in der geheimen Bit-Kette gibt, also eine Art Filterverfahren.

Für alle 0-1-Ketten, die an nur einer Position eine 1 haben 
und sonst 0, multipliziere jedes Bit mit dem entsprechenden Bit 
der geheimen Bit-Kette und bilde die Summe dieser n Produkte. 
Ist das Ergebnis 0, gibt es an der betreffenden Stelle keine 1 
in der geheimen Bit-Kette, sondern eine 0. Und umgekehrt. 
Sind alle n Positionen durchlaufen, hat man die geheime Bit-Kette 
rekonstruiert.

Auch hier gönnen wir uns den Spaß, statt des klassischen Algorithmus ein Qubit-Orakel zu konstruieren.

Viel Neues ist nicht zu sehen, da wir das Orakel wieder geheim halten. Weiter unten sehen wir, wie einfach der Qubit Algorithmus dazu ist. Hier "prüfen" wir das 3. Bit des Geheimnisses mit dem Input 0010. Die Messung von q4 liefert eine 1, wenn an der 3. Position eine 1 steht (hier der Fall). Haben wir das X-Gate für alle 4 Qubits verwendet, haben wir alle 4 Positionen in der geheimen Bit-Kette bestimmt.

Es sind also insgesamt nur n=4 "Fragen" an das Orakel zu stellen, um das Geheimnis aufzudecken - gegenüber 16 beim ersten Algorithmus. Weil 2^n eine Potenz zur Basis 2 ist, bei der n der Exponent ist, spricht man dem zweiten Algorithmus eine exponentielle Verbesserung (Beschleunigung) im Vergleich zum ersten zu: n zu  2^n. Wer sich mit Logarithmen auskennt, kann auch schreiben:  log(n) zu n*log(2).

Beides sind klassische Algorithmen. Das Zweite ist gleichzeitig auch das beste klassische Verfahren, um diese Aufgabe zu lösen. Auch wenn wir sie als Qubit-Algorithmen darstellen, steckt da noch nichts Qubit-Typisches dahinter. Anders wird es mit dem nächsten Verfahren, dem sog. Bernstein-Vazirani-Algorithmus. Der macht u.a. von Superposition und  (phase) Kickback Gebrauch.

Bernstein-Vazirani-Algorithmus

Der Gedanke ist eigentlich ganz einfach: statt das Orakel mit einzelnen Bit-Ketten zu befragen und die Antworten zu notieren, könnten wir doch einen typsichen n-Qubit-Zustand erzeugen, in dem die Zustände |0> und |1> jeweils gleichermaßen vertreten sind, und diesen dem Orakel vorlegen. Das Orakel soll dann entscheiden, "was richtig ist" -  im Vergleich mit dem Geheimnis.

Zugegeben, ganz so einfach ist es nicht - auch wenn man immer wieder liest, dass ein Qubit "0 und 1 gleichzeitig" sein kann. Aber wir können als Input für das Orakel die n Qubits mittels Hadamard-Gates in die bekannte Superposition aus (1,0) und (0,1) versetzen. Damit beginnt der Algorithmus, der Bernstein und Vazirani als Entdecker (1992) zugeschrieben  wird. Im Composer mit n=4 sieht das so aus:

Hier ist q4 wieder ein "Hilfs-Qubit", das, anders als die Input-Qubits, per X-Gate mit (0,1) initialisiert wird (als Ket: |1>). Wie die geheime Bit-Kette hier im Qubit-Orakel angelegt ist, finden wir gleich heraus. Der Algorithmus bringt also zunächst mittels H-Gate alle Qubits in die Hadamard-Superposition. Am Ende werden die Qubits per H-Gates wieder in Basis-Zustände (1,0) oder (0,1) versetzt und gemessen. Das Hilfs-Qubit ist dabei unwichtig, d.h. auf das H-Gate und die Messung kann man verzichten.

Zum Unterschied zu den klassichen Algorithmen wird dem Orakel hier nicht eine Bit-Kette der Länge n als Input vorgelegt, sondern ein n-Qubit-Zustand! Betonung auf  "Zustand" und "ein". Die Antwort des Orakels auf diesen Zustand bewirkt eine Änderung des n-Qubit-Zustands. Werden darauf dann H-Gates angewandt, besteht der Endzustand aus Basis-Zuständen, die durch Messung eine Bit-Kette ergeben. Und diese enstpricht genau dem Geheimnis des Orakels. Kaum zu glauben.

Wenn also die Messung der 4 Qubit-Zustände 0101 ergibt, dann ist das die gesuchte Bit-Kette, die Lösung, der Geheim-Code, der Weg durch's Labyrinth, oder was auch immer das Geheimnis bedeutet.

Vergleichen wir die Anzahl der Fragen, die wir dem Orakel im stellen müssen, so haben wir beim ersten Algorithmus im schlechtesten Fall 16, beim zweiten immer 4 Fragen zu stellen, und beim Bernstein-Vazirani nur eine. Das Verhältnis zum besten klassischen Algorithmus ist also 1 zu n. Wir haben hier also für große n eine erhebliche algorithmische Verbesserung. In Q16 "Was man so liest" werden wir die Bedeutung dieses Effektes noch weiter diskutieren. Hier wollen wir zunächst noch verstehen, wie und wodurch dieser Effekt zustande kommt.

Das Orakel und das Phase Kickback

Den zentralen Trick dieses Algorithmus wollen und können wir bereits am einfachsten Problembeispiel verstehen: einer geheimen Bit-Kette der Länge 1. (Dieser Trick ist sehr verständlich dargestellt von M. Treinish in seinem Vortrag "Open Source Quantum Computing" . Als Youtube video: https://youtu.be/th4TDYX6xoc - 2019, englisch.)

In Q9 hatten wir den (Phase) Kickback Effekt schon demonstriert. Das Composer-Diagramm sah so aus (s. Abb. links). Es erinnert, zumindest am Anfang, an das vorige Composer Diagramm, allerdings mit nur einem Input-Qubit und ohne das zweite H-Gate beim Hilfs-Qubit.

Wir haben inzwischen gelernt, die Zustandsänderungen im Algorithmus zu verfolgen, so dass wir den Effekt des Kickback nachvollziehen können. Wir bezeichnen die Koordinaten der Qubit-Zustände von q0 und q1 mit (x,y) bzw. (u,v). Die Ausgangszustände sind (x,y) = (1,0) und (u,v) = (0,1) (nach dem X-Gate).

(u,v)⊗(x,y) ux uy vx xy Koordinaten q1,q0
Kets |00> |01> |10> |11>
(0,1)⊗(1,0) 0 0 1 0
H(0,1)⊗H(1,0)=1/2(1,-1)⊗(1,1) 1 1 -1 -1 (Vorfaktor 1/2)
CNOT q0-q1 (vertauscht uy,vy) 1 -1 -1 1 =1/2(1,-1)⊗(1,-1)
1/2(1,-1)⊗H(1,-1)=1/√2(1,-1)⊗(0,1) 0 1 0 -1 =H(0,1)⊗(0,1)

Der Zustand von q0 ist damit (x,y) = (0,1), der von q1 ist H(0,1), also unverändert. Qubit q1 hat auf diese Weise seinen Ausgangszustand (0,1) auf q0 übertragen (q1 kicked back). DIe Messung für q0 ergibt eine 1. Und das liegt letztlich an dem CNOT. Würden wir dieses weg lassen,  gäbe es die Vertauschung von uy und vy nicht. Die H-Gates auf der q0-Linie würden sich aufheben, der Zustand von q0 bliebe unververändert,  der von q1 bliebe H(0,1). Die Messung von q0 würde 0 ergeben.

In der Ket-Darstellung sehen die Zeilen 4 und 5 wie folgt aus
(|0>+|1>)(|0>-|1>) = |00>-|01>+|10>-|11> ---CNOT---  |00>-|01>+|11>-|10> = (|0>-|1>)(|0>-|1>)
Das erinnert an die Binomischen Formeln: Links die 3., rechts die 2. Das CNOT verändert die Dritte in die Zweite.

Jetzt bemerken wir Folgendes:
Eine Kickback-Struktur zwischen Input-Qubit und Hilfs-Qubit wird vom Bernstein-Vazirani-Algorithmus offenbar als 1 erkannt, eine fehlende als 0. Wenn der Algorithmus also eine n lange geheime Bit-Kette  mit Hilfe eines n-Qubit-Zustands erkennen soll, muss man nur entsprechende Kickback-Strukturen (d.h. die CNOT-Gates) hintereinander schalten. Und zwar so, das die Position einer 1 im Geheimnis dem Control-Qubit entspricht.

Hier ist das Beispiel mit "aufgedecktem" Orakel. Das Geheimnis ist 0101 (oben ist  rechts) und wird korrekt gemessen bei einem Durchlauf mit dem Simulator.

Einsatz eines echten Quanten-Computers: IBMQX2

Bisher haben wir die Qubit-Algorithmen immer auf dem Q-Simulator ablaufen lassen. Zeit für einen echten Quanten-Computer!

Wir lassen den gleichen Composer Circuit für den Bernstein-Vazirani-Algorithmus nun auf dem IBM-Quanten-Computer IBMQX2 laufen.

Die Anzahl Wiederholungen (number of shots) konnte beim Simulator auf 1 gesetzt werden, da wir erwarten konnten, dass das Ergebnis zu 100% genau eine Bit-Kette liefert. Wird stattdessen ein Quantum-Device verwendet, muss man damit rechnen, dass aufgrund von Dekohärenz-Effekten das Ergebnis eines einzelnen Durchlaufs "gestört" ist. Mit z.B. n_shots=1024 wird das Programm 1024 Mal wiederholt und man kann aus der Häufigkeit der Ergebnisse die richtige Antwort erschliessen. Es ist, als müssten wir das Orakel mehrfach befragen, weil es die Antwort immer "leicht verwirrt" gibt. (Ein typischer Diskussionspunkt, wenn es um die (theoretische) "Quanten-Beschleunigung" geht.)

Hier zunächst das Ablaufprotokoll:

Und hier das Ergebnis der 1042 Durchläufe auf dem ibmqx2:

Wir sehen hier, dass das bei weitem häufigste Messergebnis die Bit-Kette 0101 ist, die wir als gefundenes Geheimnis akzeptieren. Sie stimmt auch mit dem Ergebnis des Simulators überein. Mit geringen Anteilen werden aber auch alle anderen möglichen 4-Bit-Ergebnisse gemessen, ein Effekt, der (zur Zeit) bei echten Quanten-Computern auftritt und kompensiert werden muss. Um diese "Unsicherheit" zu eliminieren, bleibt uns hier (in dieser Blog-Serie) nur die Wiederholung.

Die ersten beiden Algorithmen "aufgedeckt"

Und da wir gerade dabei sind, decken wir auch die Orakel der beiden klassischen Algorithmen auf:

Der zweite Algorithmus (blau), der mit n Fragen ebenfalls das Geheimnis 0101 findet. Als Input wird in der Abbildung per q2 das 3. Bit (von rechts) geprüft.

 

 

 

 

Und hier der erste Algorithmus (pink):Das Orakel des ersten Algorithmus soll ja beantworten, ob die Zustände des n-Qubit-Inputs der geheimen Bit-Kette entsprechen oder nicht. Was wir hier sehen, ist eine naive Methode, diese Antwort über das Hilfs-Qubit q4 zu generieren: Das Orakel "zählt" die Anzahl der Übereinstimmungen durch "Drehungen" (cRz - Controlled Rz) des Hilfs-Qubit-Zustands um einen (kleinen) Winkel, hier pi/6. Am Ende wird der Zustand um das n-Fache des Winkels "zurückgedreht" (Rz-Gate). Waren alle n Inputs "richtig", führt das Zurückdrehen das Hilfs-Qubit auf den Basiszustand zurück. Ansonsten auf einen Superpostionszustand. Im Beispiel sind die Zustände der Input-Qubits gerade so, dass alle mit der im Orakel angelegten Bit-Kette 0110 übereinstimmen. Das Messergebnis (wiederholte Durchläufe) ist 1 zu 100%.

(Anm.: Das Rz- und cRz-Gate haben wir bisher nicht behandelt, weil wir im Wesentlichen ohne dem auskommen. Wir kennen das Z-Gate. Rz und Controlled Rz erzeugen winkelabhängig "Teilschritte" von Z in Form von Drehungen. Um sie in unserem Circuit wirksam zu machen, müssen wir vorher den Basis-Zustand von q4 mit dem H-Gate transformieren - und am Ende rück-transformieren. Etwas kompliziert, aber es funktioniert. Alternativ kann man auch ein "controlled Ry" durch eine Kombination von mehreren Gates implementieren, was hier aber unnötig unübersichtlich würde.)

Wie geheim ist geheim?

Im Composer Diagramm zum Bernstein-Vazirani Algorithmus scheint es zunächst etwas unsinnig, das Orakel zu befragen, wenn die "geheime Bit-Kette" im Circuit-Teil für das Orakel doch ganz offensichtlich ist: 1, wo ein CNOT angelegt ist, 0 sonst.

Zum einen ist es immer so, dass, wenn man eine Übereinstimmung von zwei Dingen prüfen will, beides irgendwie "zur Verfügung" haben muß. So auch, wenn man eine unbekannte Bit-Kette durch Inputs herausfinden will. Auch die unbekannte Bit-Kette muß "irgendwie" verfügbar oder überprüfbar vorliegen. Die Form kann beliebig kompliziert sein oder so einfach wie eine klassische binäre Daten-Variable - oder eben ein Teil eine Qubit-Circuits.

Zum anderen kann man sich vorstellen, dass der Orakel-Teil des Circuits "unerkannt" implementiert wird, etwa durch einen Algorithmus außerhalb des eigentlichen Bernstein-Vazirani-Circuits. In der Qubit-Programmierumgebung Qiskit kann man z.B. in einer Funktion eine zufällige Bit-Kette erzeugen, die dann in einen Programmblock für das Orakel umgesetzt wird. Damit ist das Orakel innerhalb des Gesamt-Algorithmus eine Black Box.

Generieren eines zufälligen Orakels - mit Qiskit

Wir zeigen und erklären zum Abschluss diese Aufgabe für eine unbekannte, zufällige Bit-Kette der Länge n= 32 anhand eines vollständigen Python Programms unter Verwendung der Qiskit-Umgebung. Der Algorithmus wird also insgesamt in einer Programmiersprache beschrieben, statt umgangssprachlich oder grafisch per Composer Diagramm. Die Qiskit Ausdrücke entsprechen den Komponenten eines Composer Circuits; man kann sich sogar das Qiskit Programm als Composer Grafik anzeigen lassen. Python/Qiskit Programme kann man am besten als sog. "Notebooks" direkt in der IBM Q Experience Cloud entwerfen und ausführen - auf dem QC-Simulator oder einem realen QC. (Notebooks sind eine Kombination aus Text- und Programm-Teilen. Man kann also im Klartext die "Story" zum Programm in einzelnenen Schritten aufschreiben und dazu die Programm-Teile einfügen. Alles zusammen ist dann ablauffähig. Die Dateiendung der Notbooks ist .ipynb - für iPython NoteBook.) Zum Testen von Teilen oder einzelnen Ideen kann man immer auch auf den Composer zurückgreifen, denn die "Übersetzung" eines Composer Circuits nach Qiskit ist simpel.

Wir empfehlen hiermit auch den Übergang vom Composer (grafisch) zu Qiskit/Python (Programmierung). Mit Qiskit/Python ist man viel flexibler in der Formulierung von Qubit-Algorithmen. Außerdem kann man damit gut die Kombination von konventioneller Algorithmik und Qubit-Algorithmik gestalten, d.h. den Quanten-Computer nur für seine speziellen Stärken einsetzen.

Unter diesem Link: " Bernstein-Vazirani-Algorithmus" kann man das komplette Notebook als html-Datei herunterladen bzw. ansehen. Möchte man mit dem Notebook im IBM-Q Umfeld experimentieren, kann man die Datei in der IBM-Q Umgebung in ein leeres Qiskit-Notebook hineinkopieren (Text-Zellen getrennt von Code-Zellen).

Hier beschreiben wir nur die wesentlichen Teile in Text-Form.

  • Defintion eines Qubit-Systems namens 'circ'  mit n=33 Qubits und Mess-Bits
    • 32 für das Geheimnis und 1 Hilfs-Qubit
  • Die Gates werden je Qubit eingesetzt
    • X-Gate für das Hilfs-Qubit q[32]: circ.x(q[32])
    • H-Gate für alle Qubits von q[0] bis q[32]: circ.h(q[i])
  • Das Geheimnis wird generiert und das Orakel eingefügt
    • Zufällige 0-1-Kette (das Geheimnis) wir erzeugt
    • Für alle Positionen s mit 1 in der Kette wird das entsprechende Qubit mit einem CNOT versehen: circ.cx(q[s],q[32])
  • Die Gates je Qubit werden ergänzt
    • H-Gate für alle Qubits von q[0] bis q[32]: circ.h(q[i])
  • Mess-Operation
    • Messen der Zustände der Qubits: circ.measure(q,c)
    • c enthält die Bit-Ergebnisse (von rechts nach links)
    • Das c-Bit ganz links gehört zum Hilfs-Qubit und wird ignoriert
  • Das Qubit-Programm wird ausgeführt
    • Die "Backend-Maschine" wird aufgerufen (Simulator oder ein realer Quanten-Computer)
    • Die Anzahl Wiederholungen ('shots') wird festgelegt: n_shots=1
    • Das Programm wird gestartet: job=execute(circ, ....)
    • Das (Mess-)Ergebnis wird erstellt: result=job.result()
  • Das Ergebnis 'result' wird aufbereitet
    • Die Ergebnis-Bit-Kette wird als Lösung des Geheimnisses ausgegeben.

Ein Beispiel für die Ergebnis-Ausgabe des Programms:

Anm.: Ergebnisse für Qubits q0 bis q32 werden in der Bit-Kette von rechts nach links geschrieben
      Qubits, die nicht gemessen werden, haben den Messwert 0 per Default

counts:  {'100101100111110100101111010110000': 1}
Gefundenes Geheimnis: 00101100111110100101111010110000
Das Orakel war: [0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]

Mit diesem Ausflug in die Qiskit-QC-Programmierung öffnen wir das Feld für weitere, neue Versuche, Qubit-Algorithmen zu entwerfen, zu realisieren bzw. nachzubauen. Es sei aber noch einmal daran erinnert, dass die Qubit-Welt über das, was wir hier dargestellt haben, hinaus noch weitere mathematische Begriffe und Methoden kennt und verwendet. D.h. nicht alle Algorithmen, die sich in der Literatur oder in Einführungs-Videos finden, sind mit unserer "Schul-Qubit-Toolbox" realisierbar oder verstehbar.

Im nächsten Abschnitt der Blog-Serie wollen wir versuchen zu verstehen, was so alles in den Medien und populärwissenschaftlichen Beiträgen zum Quanten-Computing geschrieben wird. Zu "Was man so liest" geht es hier.

Zum Schluss wieder die Tabellen-Ergänzung mit neuen Begriffen:

Begriff englisch Begriff deutsch Bedeutung
Oracle Orakel Black box, Qubit-Funktion mit (unbekannten) Parametern
Secret Geheimnis (Unbekannte) Parameter des Orakels, meist Bit-Ketten
Exponential improvement Exponentielle Verbesserung Auch als "Beschleunigung" bezeichnet. Aufwand eines Algorithmus im Vergleich zu einem anderen im Verhältnis log(n) zu n, wobei n die "Größe" des Problems kennzeichnet. Auch n zu 2^n.
Number of shots Anzahl Wiederholungen Wiederholungen eines Durchlaufs, um eine statistische Verteilung über die möglichen Messergebnisse (Bit-Ketten) zu erhalten
Decoherence Dekohärenz Ungesteuerter Zerfall von (Mehr-)Qubit-Zuständen auf einem realen physikalischen Gerät (Quanten-Computer)
ibmqx2 ibmqx2 Realer Quanten-Computer, offen zugänglich in der IBM Q Cloud
Rz, cRz Rz, cRz Weiteres Gate bzw. Controlled Gate mit Rotationswirkung
Qiskit Qiskit Q-Bibliothek zur Einbettung in (z.B.) Python. Professionelle Alternative zur grafischen Programmierung mit dem Composer
Notebook Notebook Skripte kombiniert aus aus Text- und Programm-Teilen (Zellen)
Cells Zellen Notebook-Abschnitte, die Text oder Programm-Code enthalten und einzeln oder zusammen ausgeführt werden können
Ancillary Qubit Hilfs-Qubit Extra Qubit, das für den Algorithmus gebraucht wird aber nicht in das (Mess-)Ergebnis eingeht

 


Q1 Etwas ist anders! - Qubit-Algorithmen

Muss ich Quantenphysik kennen, oder verstehen, wie Quantencomputer funktionieren, um mich mit  sog. Quanten-Algorithmen zu beschäftigen?

Sicher nicht! Lass uns deshalb lieber von Qubit-Algorithmen, oder kurz Q-Algorithmen sprechen.  Die Idee der Qubit-Algorithmen gab es schon, bevor die ersten Quantencomputer nutzbar wurden.

Nicht anders als bei den Bit-Algorithmen, den herkömmlichen Algorithmen, die für "normale" Computer programmiert werden. Auch hier verstehen die Wenigsten die zugrunde liegende Physik und viele auch nicht, wie normale Computer funktionieren. Hauptsache, man kann spielen, chatten, Musik hören - ja, und manchmal sogar programmieren.

Allerdings - etwas ist anders bei Q-Algorithmen. Was darauf zurückzuführen ist, dass irgendwo doch die Quantenphysik schon im Hinterkopf war, als  Qubits und Qubit-Algorithmen "erfunden" wurden. Das wollen wir hier heraus finden.

Und es ist echt spannend, dass man heute reale, programmierbare Quantencomputer im Internet (als Cloud Service) frei verwenden kann, z.B. von IBM oder Google. Es ist schon ein etwas anderes Gefühl, ein eigenes kleines Q-Programm auf einem realen Q-Computer laufen zu lassen. Einfacher geht es übrigens mit Q-Computer-Simulatoren, also "Modellen" von Quantencomputern, die auf normalen Computern laufen und so tun, als wären sie QCs. Zum Ausprobieren von Q-Algorithmen perfekt.

Es wird heutzutage in den Medien viel Wunderliches über QCs und Qubit-Algorithmen geschrieben. Wie super-schnell sie sind - genauer, in Zukunft sein werden, welche geheimnisvollen Objekte Qubits sind, die gleichzeitig verschiedene Zustände haben können. Dann ist da von "Schrödingers Katze" die Rede, die gleichzeitig tot und lebendig sein soll - also wohl ein Zombie? (Jedenfalls solange, bis man nachschaut - dann ist sie entweder tot oder lebendig!) Und dass ein Quantencomputer daher doppelt so schnell Lösungen errechnet, wenn man nur ein Qubit hinzufügt. Es ist von der  "Supremacy" von Quantencomputern die Rede, ein Wort, das ausdrücken soll, dass wir bald QCs haben werden, die - bei bestimmten Rechnungen - schneller sein werden als der schnellste Supercomputer.  Und damit z.B. die stärksten heute verwendeten Verschlüsselungen im Nu knacken können.

Wenn wir uns mit Bits und Qubits und Qubit-Algorithmen näher beschäftigen, werden wir sehen, was davon zu halten ist und was dahinter steckt. Wenn man es selbst ausprobiert hat, wird man den Zauber schon verstehen. Wenn man die Katze streichelt, merkt man schon, wie lebendig sie ist.

Als nächstes wollen wir sehen, was ein Qubit bedeutet - oder wir schauen uns erst einmal ein einfaches Beispiel eines Q-Algorithmus an, um einen Eindruck zu bekommen, aber ohne es schon verstehen zu müssen. Am liebsten beides gleichzeitig? Mal sehen, wie die Entscheidung ausfällt.

Fortsetzung folgt - Stay tuned

Übrigens, wer Lust hat, kann Fragen, Ideen, Kommentare oder Diskussionen direkt ins Kommentarfeld unter dem Blog schreiben.

Und hier geht's weiter.


Q2 Etwas ist anders! - Hello Qubit World

Schauen wir uns also als erstes einmal an, wie so ein Qubit-Algorithmus aussieht - auch ohne den schon zu verstehen.

Bekanntlich ist in der Welt der Informatiker, Programmierer, Hacker das erste, was man ausprobiert bei einem neuen System oder einer neuen Programmiersprache, ein "Hello World" zu erzeugen. Das allgemein anerkannte "Hello World" für Quantencomputer sieht allerdings schon etwas ungewöhnlich aus. Es liefert auch nicht die Grußformel, sondern ist nur so etwas wie das einfachste Qubit-Programm. (Natürlich kann man das Ergebnis daraus in der "normalen" Programmierwelt in ein "Hello World" umwandeln.) Wir werden sehen.

Und so sieht es aus, das "Hello World"  der Qubit-Welt:

Sieht eher aus wie ein Ausschnitt aus einer Partitur moderner Musik? Der Vergleich ist gar  nicht so unpassend. Dieser Ausschnitt "orchestriert"  quasi die "Instrumente" eines Quantencomputers, die Qubits.

Am liebsten würde man das Bild sofort erklärt bekommen, aber das heben wir uns für später auf. Man sieht erst mal, ein Q-Algorithmus wird ganz anders dargestellt als üblich. Und dies ist eine einfache Möglichkeit einen Q-Algorithmus als Qubit-Programm grafisch zu beschreiben. (Das ist so ähnlich wie bei Scratch oder Roberta, wo man ein Programm visuell aus einzelnene Bausteinen zusammensetzen kann.) Natürlich kann man statt in der grafischen Form einen Q-Algorithmus auch in Worten beschreiben, wobei man aber sorgfältig mit der Sprache umgehen muss. Oder durch eine Programmiersprache, z.B. Python. Wir probieren das nachher mal.

Versuchen wir mal zu erraten, was die Grafik bedeutet, quasi als Partitur: Es gibt offenbar 2 Instrumente, q1 und q2. Die haben ihre eigene "Linie", auf denen etwas passiert. Klar, das sollen zwei Qubits sein - wobei wir erst in einem späteren Blog erklären, was Qubits sein sollen. Auf den Linien geschieht etwas, nacheinander, mit den jeweiligen Qubits. Was auch immer H macht, es macht es nur mit q1. Danach kommt etwas, dass offenbar q1 und q2 zusammen betrifft.

Am Ende jeder Qubit-Zeile steht eine Art Anzeige-Symbol, wie bei einem Messgerät, mit einem Pfeil nach unten auf die Doppel-Linie C. Tatsächlich, hier wird ein Qubit "gemessen". Und das Messergebnis wird an die C-Linie übertragen. Das "C" steht übrigens für "classical" - nein, nicht "klassische Musik", sondern "klassiches Bit", im Gegensatz zum Quanten-Bit oder Qubit. Danach kommt nichts mehr, es ist Schluß, das "Musikstück" zuende.

Was bedeuten die Zahlen unten auf der C-Linie? Das ist einfach zu erraten: die 2 besagt, dass C die "Messwerte" von 2 Qubits aufnimmt. Die 0, klar, steht für: "Hier kommt der Messwert von Qubit q0." Und die 1 für Messwert von q1 - falls es in einer größeren "Partitur" mal unübersichtlich werden sollte. Und da das C für "classical bit" steht, kann man schon schließen, dass die Messergebnisse herkömmliche Bits sind.

Jetzt wissen wir, was die Teile bedeuten, aber immer noch nicht, was der ganze Qubit-Schaltkreis macht (so nennt man das Gebilde in Anlehnung an herkömmliche elektronische Schaltkreise).

Das liegt daran, dass wir nicht wissen was die beiden blauen Symbole machen. Mal sehen, ob wir das auch noch verstehen können, z.B. indem wir den Hello Qubit World Algorithmus in normaler Sprache formulieren.

Aber jetzt ist es erst mal genug. Pause. Dann weiter lesen.

Cliff-Hanger - Stay tuned

Und hier geht's weiter.