Naive Bayes Modell löst das Even-Odd Learning Problem
KI im Informatikunterricht
Dieser Beitrag kann als Grundlage für die Einführung des Themas „Künstliche Intelligenz“ im Schulunterricht eingesetzt werden. Er illustriert „Maschinelles Lernen“ anhand einer für die Schüler* einfach verständlichen Aufgabe mittels einer Data Analytics Methode: Naive-Bayes. Die Aufgabe kann mit „Papier und Bleistift“ durchgeführt werden. Die Voraussetzungen beschränken sich auf Erstellen von Tabellen, Auszählen von Häufigkeiten und Berechnung von relativen Häufigkeiten.
Die Blogserie „Six not so easy pieces for AI” (Sechs nicht so einfache Aufgaben für AI) begann in 2019 mit der einfachen Fragestellung, ob AI in der Lage ist, eine der einfachsten „intellektuellen“ Leistungen zu erbringen, nämlich zu lernen, ob eine Zahl gerade oder ungerade ist. (Siehe hier.)
Abstrakte Fragestellung - Allgemeines Schema
Hier bedeuten die einzelnen Attribute des Input-Vektors die Dezimalstellen einer ganzen Zahl, beginnend bei den „Einern“ ganz rechts. Der Wertebereich (Kategorien-Labels) ist jeweils 0,1,…,9. Die Response im Supervised Learning gibt jeweils an, ob die Zahl gerade oder ungerade ist. Die entsprechenden Klassen sind 0 (für Gerade) und 1 (für Ungerade). Im trainierten Zustand gibt R die „Vorhersage“ für eine Testzahl.
Es ist wichtig zu bedenken, dass ein "lernendes KI-System" hier kein Konzept von Zahlen, Dezimalstellen und deren Bedeutung innerhalb einer Zahl (z.B. Einer, Zehner etc.) hat. Die Inputs sind für das System nichts weiter als eine Liste von Ziffern.
Das Training-Szenario
Als Training-Daten wird eine Anzahl von ganzen positiven Zahlen in Form einer Liste der einzelnen Dezimalstellen samt der richtigen Klassifikation in gerade / ungerade vorgegeben.
Als Testdaten werden einzelne Zahlen oder ein Set von Zahlen in dieser Form ohne Klassifikation verwendet. Diese sind nicht in den „Lernvorgang“ eingegangen. Das Ergebnis (Prediction) kann mit dem wahren Wert verglichen werden.
Die ML Methode
Als ML-Methode verwenden wir hier, anders als in der erwähnten Blog-Serie, ein Naive-Bayes Verfahren. Kurz erläutert, wertet das NB-Verfahren die Trainingsdaten aus und bestimmt – mittels der Bayes-Formel - die bedingte Wahrscheinlichkeit dafür, dass, gegeben eine m-stellige Zahl (Input-Vektor), das Ergebnis R=0 ("gerade") ist. Entsprechend für R=1 ("ungerade"):
P(R=0|a0 a1 … am)
Der Input-Vektor ist einfach die Ziffernfolge der Zahl, wobei für die Dezimalstellen untereinander keine Abhängigkeit besteht. (Grundannahme für die Gültigkeit von „Naive“ Bayes.)
Im „gelernten“ Zustand kann das Modell (auch Classifier genannt) für unbekannte Zahlen b = b0 b1 … bm entscheiden, ob diese gerade oder ungerade ist, anhand der berechneten Wahrscheinlichkeiten P(R=0|b) und P(R=1|b) – je nachdem, welche der Wahrscheinlichkeiten größer ist.
(In der Regel reichen wenige Zahlen für das Training aus, sofern man die sog. Glättung im Classifier „ausschaltet“. Die Glättung kompensiert Fälle, in denen eventuell einzelne Werte in den Input-Daten nicht vorkommen (missing data), und sich damit Schwierigkeiten in der Auswertung ergeben können.)
Für unser gerade-ungerade-Lernen Problem zeigt sich, dass die o.a. Wahrscheinlichkeiten P entweder 0.0 oder 1.0 sind. Im Sinne der Blogserie haben wir es hier also mit „starkem Lernen“ zu tun.
Ist das Lernverfahren auch „robust“? In der Blogserie hatten wir damit ein Lernverfahren gekennzeichnet, das ein gewisses Maß an Fehlern in den Trainingsdaten vertragen kann und trotzdem „richtig“ lernt. Und dabei auch die Fehler „richtigstellt“ (im Code-Beispiel: 5% Zufallsstörung)
Da die Input-Werte ganzzahlig (Kategorien) sind (0,..9) und die Response-Klassen ebenfalls (0,1), setzen wir hier die Variante CategoricalNB() aus der scikit-learn Toolbox an.
Outline des Algorithmus „Gerade/Ungerade Lernen“
Als Programm liegt dieses Beispiel als ein Jupyter Notebook vor, ablauffähig und mit kleinen Zwischentexte zur Erläuterung. Wegen Problemen bei der Kompatibilität der Dokumentenformate liegt das Notebook als html-Datei hier: NB_even-odd_problem_notebook
Der übliche, grobe Ablauf ist wie folgt:
- Problem Defintion: Beschreibung der Aufgabe als Text
- Problem-Dimensionen und Datensatzumfang (Code-Zelle)
- Parameter für Problem-Varianten (optional, Code)
- Generierung des Datensets: (Code-Zellen) Inputzahlen per Zufallsgenerator, dargestellt als Liste von Dezimalziffern je Zeile, davon N Zeilen (Matrix-Struktur Nx6). Zugehörige Klassifikation (R-Werte) als Liste von 0 und 1 für jede Matrix-Zeile (Zahl). Beispiel:
- Datenset-Aufteilung Tranings-/Testdaten: z.B. 70% zu 30% (Code)
- Categorical Naive Bayes Modell: Modell-Defintion und Training (g_u_model.fit()) mit den Trainingsdaten (Code)
- Ergebnisse: 7.1Test-Beispiele, 7.2 Genauigkeit der Klassifikation durch das Modell für Trainings- und Testdaten, 7.3 „Innere“ Daten des trainierten Modells (s. Code-Zellen)
- (Optional) Aufgaben-Varianten: 8.1 Verfälschen der Klassifikationen in den Trainingsdaten zur einem kleinen Prozentsatz per Zufall. 8.2 Probieren, Teilbarkeit durch 5 zu lernen. (Code Zellen)
- (Optional) Experimentieren: Teilbarkeit durch 3, 4 o.ä. Warum funktioniert Naiv-Bayes hier nicht?
Links zu NaiveBayes Methoden
https://scikit-learn.org/stable/modules/naive_bayes.html
https://scikit-learn.org/stable/modules/generated/sklearn.naive_bayes.CategoricalNB.html
https://www.analyticsvidhya.com/blog/2017/09/naive-bayes-explained/
Prozente, Prozente! Oder: Prozente lügen nicht
Prozente? Das kann doch jeder!
- 10% Rabatt auf 120 Euro sind 12 Euro, also rabattierter Betrag 108 Euro
- 19% MWSt auf 50 Euro ergeben 59,50 Euro Brutto
- „Wir schenken Ihnen die Mehrwertsteuer!“ Heißt das 9,50 Euro Abzug vom Kaufpreis – oder 19% Abzug?
Da wird’s schon enger. Wenn etwas x = 59,50 Euro kostet und um 19% reduziert wird, errechnet sich der reduzierte Preis als x – x*0,19 = x*(1-0,19) = x*0,81 = 48,20 Euro. Um auf den ursprünglichen Nettopreis zu kommen, muss man x durch (1+0,19) teilen. Also 59,5/1,19 = 50.
Dieser Unterschied von „rauf“ und „runter“ macht schon vielen Schwierigkeiten. In der Schule hatte die Prozentrechnung dafür noch gereicht. Es gibt – gerade in Zeiten von Corona – Unmengen von %-Aussagen. Aber was bedeuten sie?
- Rauf und runter
Was passiert, wenn wir in Folge abwechselnd 20% auf einen Betrag aufschlagen und dann wieder 20% abziehen? Also, beginnend etwa bei 100 Euro:
- Plus 20% ergibt 120 Euro
- Abzüglich 20% ergibt 120 – 24 = 96 Euro
- Plus 20% ergibt 96 + 20%*96 = 96 + 19,20 = 115,20 Euro
- Abzüglich 20%, ergibt 92,16 Euro,
Mathematisch gesehen wird bei „Plus“ der aktuelle Betrag mit (1 + 0,2) multipliziert, beim Abzug mit (1 – 0,2). Bei jedem „rauf und runter“ wird also mit (1+0,2)*(1-0,2) = (1-0,04) = 0,96 multipliziert. Das heißt zum einen, 20% rauf und 20% runter ergibt nicht den Ausgangswert, wie man meinen könnte, sondern einen geringeren Wert. Zum anderen: wenn man das wiederholt macht, wird der Wert jedes Mal um den Faktor 0,96 kleiner. Das ist eine exponentielle Folge, die auf Dauer gegen Null geht.
Wenn man sich fragt, wann der Wert sich auf die Hälfte reduziert hat, muss man schon mit Logarithmen arbeiten, oder aber die Folge „simulieren“. Ergebnis: nach 17 Schritten.
- Exponentielles Wachstum
Mit Prozenten kann man exponentielles Wachstum, oder dessen Gegenteil, erzeugen. Das ist jedem klar, der mal sein Sparguthaben mit Zinseszins gerechnet hat. Kommen auf einen Betrag von, sagen wir, 100 Euro -2% Zinsen – d.h. 2% „Strafzinsen“ - so ist das Resultat 100 – 0,02*100 = 100*(1-0,02) = 100*0,98. Kommen darauf für einen weiteren Zeitraum ebenfalls 2% Strafzinsen, ergibt das 100*0,98*0,98 = 100*0,98² usw.
Wir haben also exponentielles Wachstum, wenn ein Wert „prozentual“ zunimmt, also mit jedem Zeitschritt K zu K‘ = K*q wird, wobei der Prozentsatz p% in q = 1+p/100 verrechnet wird. Nach t Zeitperioden ist ein Anfangswert K0 auf Kt = K0*q t gestiegen – oder gefallen, je nachdem ob q > 1 oder q < 1 ist.
Damit haben wir auch eine einfache Erklärung für den Begriff „exponentiell“: Der Wachstumsfaktor für Kt berechnet sich mit t als Exponent. Bei einem „linearen“ Wachstum hätten wir Kt = K0 + a*t, d.h. t als Faktor der Steigerungsrate (wenn a > 0).
In seinem Blogbeitrag „Exponentielles Wachstum“ (Link) erklärt Ulrich Trottenberg die Bedeutung von Exponentiellem Wachstum im Kontext der Corona Fallzahlen.
- Das Prozente-Rauf-und-Runter Spiel
Hier das Rauf-und-Runter als Spiel für zwei Personen (Nullsummenspiel). Zwei Personen X und Y haben je 100 Euro. Sie verabreden folgendes „Spiel“: Ein Zug besteht aus zwei Aktionen
- X gibt 20% seines Vermögens an Y
- Y gibt 20% seines Vermögens an X
Was passiert? Nach 5 Zügen, nach 10 Zügen? Nach unendlich vielen Zügen? Wer gewinnt und wieviel, in % des Startguthabens?
Hier zunächst die Antworten. Die Begründung findet sich als Anhang am Schluss.
- Nach 5 Zügen hat X 109,92 Euro, Y hat 90,08 Euro
- Nach 10 Zügen steht es: 110,98 Euro zu 89,02 Euro
- Nach unendlich vielen Zügen hat X 111,11 Euro, Y hat 88,89 Euro
- X gewinnt
- Sein Gewinn ist 11,11 %, der Verlust von Y ist 11,11 %, was klar ist wegen des Nullsummen-Spiels
- Kleine Zahlen – Große Prozente
Der CDU-Vorstand wählte vor kurzem den CDU Kanzlerkandidaten, in einer Stichwahl zwischen A. Laschet und M. Söder. Die Presse berichtete, dass 77,5 % der Stimmen für Laschet abgegeben wurden. Klingt gut, nach ordentlichen Prozenten. Aber was steckt dahinter?
Tatsächlich bestand der Vorstand aus 46 Mitgliedern, von denen sich 6 enthalten haben und 9 für Söder gestimmt haben. D.h. auf Laschet entfielen 31 Stimmen!
Die 77,5% berücksichtigen nur die Nicht-Enthaltungen. Alternativ wurden 67,4 % errechnet bei Berücksichtigung des gesamten Vorstands. Wir haben hier also zwei Prozentzahlen für das gleiche Ergebnis.
Schlimmer noch: was sollen 77,5% bedeuten, wenn es nur 46 Abstimmende gegeben hat. In Worten wäre eine Bedeutung: „Von je 100 Vorstandsmitgliedern stimmten 77,5 – nein, 67,4 - für Herrn Laschet. Nun gab es aber keine 100 oder mehr Vorstandsmitglieder, sondern nur 46.
Ein Fehler, der sehr häufig gemacht wird, unreflektiert: Kleine Zahlen in Prozente (pro Hundert) umzurechnen. Auch in wissenschaftlichen Arbeiten.
Wenn Sie lesen, dass bei 75% der Probanden ein neues Medikament wirksam war, dann klingt das nach viel. 50% klingt schon nicht mehr so gut. Was, wenn die Wirksamkeitsaussage sich dabei aber auf nur 9 Fälle bezieht? Bei kleinen Zahlen sind außerdem Zufallsschwankungen üblich. Eine Abweichung um 2 Probanden macht das Ergebnis dann schon zu nur noch 58%. Die %-Zahlen vernebeln hier die Realität.
- Große Zahlen – kleine Prozente
Es gibt auch den umgekehrten Effekt.
In den täglichen Corona-Statistiken wird u.a. die Inzidenz angegeben, also die Anzahl Neuinfektionen über die vergangenen 7 Tage je 100.000 Bevölkerung 1). Damit hat man einen guten Vergleichswert, um z.B. die Entwicklung in den verschiedenen Ländern zu vergleichen.
Interessant wären natürlich Feinanalysen, um Bereiche mit besonders hohen oder niedrigen Inzidenzwerten zu erkennen. Die Stadt Köln hat diese Feinanalyse für sämtliche Ortsteile / Veedel veröffentlicht.
Der Bezirk Chorweiler hatte am 26.4. einen Inzidenzwert von 520. Die Ortsteile Hahnwald und Fühlingen 0 und Esch/Auweiler iregndwas zwischen 200 und 300 (Kölner Stadtanzeiger 29.4.2021). Das klingt nach viel für Chorweiler und Esch/Auweiler und wenig für Hahnwald und Fühlingen – weswegen es Chorweiler und Hahnwald auch in die TV-Nachrichten gebracht haben.
Nach Definition des Inzidenzwerts hatten also: Chorweiler 520 Neuinfektion je 100.000 Einwohner, Esch/Auweiler ca. 250, Hahnwald und Fühlingen 0 je 100.000 Einwohner. Allerding, keiner dieser Ortsteile hat nur annähernd 100.000 Einwohner.
Hier eine aktuelle Tabelle mit Zahlen der Stadt Köln mit Daten vom 28.4.2021, die sich insbesondere für die kleinen Ortsteile (Fühlingen, Hahnwald) nach zwei Tagen teilweise drastisch geändert haben:
Ortsteil | Einwohner | Inzidenz-Zahl |
Chorweiler | 12.900 | 543,4 |
Esch/Auweiler | 7.000 | 168,1 |
Fühlingen | 2.100 | 47,8 |
Hahnwald | 2.066 | 145,2 |
Roggendorf/ Thenhofen | 4.500 | 683,0 |
Die Inzidenzzahlen sollen vergleichbar machen - ok. Bei der Ortsteil-Analyse, oder gar bei Analyse nach anderen Kriterien (Sozialstatus, Einkommen, Bildungsstand), ergeben sich einige verfälschende Eindrücke oder Scheingenauigkeiten. Ähnlich wie bei den Prozenten der Kanzlerkandidaten-Wahl (bezogen auf 100) ist die Grundgesamtheit hier eine viel kleinere Zahl als die Bezugsgröße 100.000 (Die Inzidenzzahlen sind also Angaben in Tausenstel Prozent oder Milliprozent).
- Die Inzidenzzahlen werden oft mit ein, zwei Stellen hinter dem Komma angegeben, was eine Scheingenauigkeit suggeriert.
- Hohe Inzidenz auf kleiner Basisgesamtheit suggeriert hohe, teilweise sehr hohe Fallzahlen von Neuinfektionen. Da die Zahl der Basisgesamtheit in der Regel nicht angegeben wird, werden die Inzidenzahlen intuitiv als Maßstab empfunden (Hotspot). Bezogen auf die Einwohnerzahl hat z.B. Roggendorf/Tenhofen mit Inzidenz 683 insgesamt 31 Neuinfektionen über die 7-Tage-Zeitspanne, Chorweiler mit geringerer Inzidenz mehr als das Doppelte (70) an Neuinfektionen, also im Schnitt etwa 10 neue Fälle pro Tag.
- Niedrige Inzidenz bei kleinen Basiszahlen kann ebenfalls leicht in die Irre führen. Wenn Hahnwald mit Inzidenz 145 vermerkt ist, bedeutet das 3 neue Fälle in 7 Tagen. Die kleinen Zahlen sind sensibel gegen „Störungen“: Kommt ein Fall hinzu, steigt die Inzidenz auf 210 und Hahnwald wird Hotspot. Fällt ein Fall heraus, sinkt sie auf 97 mit den entsprechenden Konsequenzen. Der Zustand Inzidenz Null ist besonders „instabil“. Eine einzige Neuinfektion treibt den Wert bereits an die 50er-Marke (48,4).
- Rangfolge-Darstellungen nach Inzidenzwert suggerieren eine Vergleichbarkeit, die statistisch unsinnig ist, aber immer gerne angewendet wird. Sinnvoller ist eine Rangfolge des Infektionsgeschehens nach Prozent der Bevölkerung. Die Rangfolge ist zwar in beiden Fällen gleich. Für die Prozentzahlen spricht aber, dass Basiszahlen alle deutlich über 100 liegen (aber nie über 100.000), daher ist ein Vergleich unkritisch und aussagekräftiger und die deutlich kleineren %-Zahlen liegen innerhalb des üblichen „normierten“ Wahrnehmungsbereichs von 0 bis 100%.
Ortsteil | Einwohner | Inzidenz-Zahl | Prozent | Rang |
Chorweiler | 12.900 | 543,4 | 0,54 % | 2 |
Esch/Auweiler | 7.000 | 168,1 | 0,19 % | 3 |
Fühlingen | 2.100 | 47,8 | 0,05 % | 5 |
Hahnwald | 2.066 | 145,2 | 0,15 % | 4 |
Roggendorf/ Thenhofen | 4.500 | 683,0 | 0,69 % | 1 |
- Andere Zahlen, andere Prozente
Die Inzidenzkarte der Stadt Köln zeigt im Drill-Down erfreulicherweise auch die Basiszahlen und mehr für die Ortsteile an, so dass man sich selbst ein Bild „errechnen“ kann.
Üblicherweise werden die Neuinfektionsstatistiken und Inzidenzzahlen aber ohne Bezug zu den entsprechenden täglichen Testzahlen kommuniziert. Stattdessen wird gelegentlich der Verdacht diskutiert (not least by Mr. Trump), dass die „schlechte Entwicklung der Infektionszahlen“ schon durch eine verbesserte Testdichte und Test-Willigkeit zu erklären sei, also ein statistisches Artefakt. Daher wären mitlaufende Zahlen für Test-Anzahl oder Testdichte (Anzahl Tests pro Bevölkerung in %) eine wichtige Information.
In einem Youtube-Video kritisiert ein Mathematik-Student die Inzidenz-Berechnung als mathematisch falsch. Statt auf 100.000 Bevölkerung müsse man die Inzidenz auf die Anzahl der Tests in einer Bevölkerungsgruppe beziehen. (Der Link wurde inzwischen gelöscht, vermutlich aufgrund kritischer Gegenkommentare. S. z.B. hier.)
Genauer betrachtet, handelt es sich hier jedoch nicht um einen Fehler, sondern lediglich um zwei unterschiedliche Kennzahlen, deren Bedeutung entsprechend differenziert werden muss.
Die Inzidenzzahl bezieht sich auf die Gesamtheit der betrachteten Bevölkerungsgruppe. Als relative Häufigkeit, oder idealisiert als Wahrscheinlichkeit, haben wir hier ein Maß für die apriori-Wahrscheinlichkeit P(+) = Anzahl (+) / Anzahl (Bevölkerung). Die Alternative ist im weitesten Sinne eine Bayes’sche Interpretation der Positiv-Wahrscheinlichkeit, allerdings trivial reduziert zu P(+|Test) = Anzahl (+) / Anzahl (Test), da die positiv Getesteten schlicht eine Teilmenge der Getesteten sind, die wiederum ein Teilmenge der betrachteten Bevölkerung sind.
Wir haben es hier also nicht mit einem Fehler zu tun, sondern mit einer anderen Kenngröße, und man kann darüber diskutieren, welche davon sinnvoller ist. Hier ein Denkansatz dazu:
- Die „Inzidenz“ bezogen auf die Tests kann a) einen Teil der täglichen Schwankungen erklären und hat b) als Bezugsgröße einen realen Wert statt 100.000, erfüllt damit den Kritikpunkt in 4 besser
- Die Inzidenz bezogen auf 100.000 einer Bevölkerungsgruppe (auch wenn die real viel kleiner ist) gibt einen Eindruck vom noch möglichen Potenzial an Neuinfektionen und dem Einfluss von Steuerungsmaßnahmen.
Make your choice! I take both.
- Fälle, Relative Häufigkeiten, Wahrscheinlichkeiten - Prozente, Prozente!
Prozente sind nicht gleich Prozente. Bei der Kanzlerkandidaten-Wahl (s. 3.) entfielen 77,5% der abgegebenen Stimmen auf A.L. Andererseits erhielt A.L. 67,4% der Wahlberechtigten (CDU Präsidium). Zwei unterschiedliche Prozent-Ergebnisse für den gleichen Vorgang. In diesem Fall ist der Unterschied durch die Bezugsgröße (Grundgesamtheit) erklärt und meist geht diese auch in einem sprachlich verfassten Text zur Prozentzahl mit erwähnt.
Allerdings - die sprachliche Ergänzung ist oft nicht eindeutig. Was sind „die abgegebenen Stimmen“, welche Grundgesamtheit bezeichnet dieser Begriff? Zählen die Enthaltungen ebenfalls zu den abgegebenen Stimmen? Gut, wenn man vorher eine Definition gegeben hat.
Aber nicht immer geht das so einfach.
In Zusammenhang mit der Corona-Pandemie werden üblicherweise Todeszahlen „durch oder im Zusammenhang mit Corona“ als Absolutzahlen (Fälle) angegeben. Gelegentlich werden auch Prozentzahlen angegeben, typischerweise nach wissenschaftlichen Festlegungen aus der Epidemiologie. Was ebenfalls zu unterschiedlichen Prozentwerten für das gleiche Geschehen führt. So bekommt man auf die Frage „Wie groß ist (oder war, bis März 2021) die Wahrscheinlichkeit „durch oder im Zusammenhang mit Corona“ zu sterben, unterschiedliche Antworten, selbst bei gleicher Datenlage.
Um das zu illustrieren, gehen wir von folgenden Zahlen aus, die man beim Statistischen Bundesamt bzw. den Meldeämtern beziehen kann:
Rohdaten normiert auf 12 Monate ab 03/20 | ||
Population DE | N | 83.200.000 |
Gemeldete Todesfälle 2020 gesamt | T | 982.000 |
Corona Infektionen gesamt 03/20 – 04/21 (RKI) | C | 2.754.000 |
Corona Todesfälle 03/20 – 04/20 (RKI) | D | 72.800 |
Anm.: Die Daten sind auf 12 Monate zurückgerechnet, teilweise ausgehend von Zahlen für 03/20 bis 04/20. Die Symbole N, T, C, D stehen im Folgenden für die Fallzahlen, gelegentlich aber auch als Abkürzung für die Mengen-Bezeichnungen in der linken Spalte.
Die Tabelle zeigt die absoluten Häufigkeiten in „Fällen“. Relative Häufigkeiten werden in Bezug auf eine andere, umfassendere Menge definiert und meist in % angegeben. Die Wahrscheinlichkeit eines Zufalls-Ereignisses wird dagegen in Zahlen von 0,0 bis 1,0 dargestellt – die aber gelegentlich durch Multiplikation mit 100 auch in Prozentangaben umgerechnet wird. Oft wird die Wahrscheinlichkeit eines Ereignisses aus relativen Häufigkeiten empirischen Daten „gesetzt“.
Wenn also gefragt wird: „Wie groß ist die Wahrscheinlichkeit an Corona zu sterben?“ gibt es nach der obigen Tabelle schon mal drei verschiedene Antworten:
- Wahrscheinlichkeit ein Corona-Todesfall zu sein: 0,09 %
- Wahrscheinlichkeit als Corona-Patient zu sterben: 2,64 %
- Wahrscheinlichkeit, dass ein Todesfall auf Corona-Erkrankung zurückzuführen ist: 7,41 %
Es wird deutlich, dass diese Aussagen sprachlich und in der Bedeutung nur schwer auseinander zu halten und (in den Medien) zu vermitteln sind. Dennoch bedeuten sie Unterschiedliches und haben daher unterschiedliche Werte.
Für Interessierte hier kurz die Erklärung der Ergebnisse. (Die methodische Anmerkung am Schluss erklärt, warum wir hier vereinfachend von Wahrscheinlichkeiten W sprechen.)
Antwort a) ist einfach zu verstehen: W(D) = D/N = 0,0009. D.h. 0,09 % der Bevölkerung sind als Corona-Todesfälle ausgewiesen. Wie sieht es mit b) und c) aus?
Mit der sog. Bayes’schen Betrachtungsweise sind die Unterschiede leicht als sog. „Bedingte Wahrscheinlichkeiten“ zu beschreiben. Das „bedingt“ stellt den Bezug zu einer Menge her, die selbst wiederum Teilmenge der Grundgesamtheit ist. Bei a) ist die „Bezugsmenge“ die Grundgesamtheit selbst, also die Bevölkerung N. Schauen wir mal auf die Teilmengenverhältnisse gemäß deren Bedeutung: T, C, D stehen für Teilmengen der Gesamtbevölkerung. D ist Teilmenge von T und von C, also sind T^D und C^D dasselbe, nämlich D. T und C sind i.a. nicht Teilmengen voneinander. (Das ^ steht für den Mengendurchschnitt).
Antwort b) bedeutet W(Todesfall, gegeben Corona-Erkrankung) = W(Todesfall und Corona-Erkrankung) / W(Corona-Erkrankung), als Formel: W(T|C) = W(T^C)/W(C).
Setzen wir für die Wahrscheinlichkeiten rechts wieder die relativen Häufigkeiten (in Bezug auf N) ein, dann bekommen wir auf der rechten Seite: (D/N)/(C/N) = D/C = 72.800/2.754.000 = 0,0264 Oder: W(T|C) ist 2,64 % , die Wahrscheinlichkeit zu sterben, wenn man Corona-erkrankt ist.
Antwort c) sagt etwas ganz anderes aus: Die Wahrscheinlichkeit, dass eine Person Corona-erkrankt war, die gestorben ist. Als bedingte Wahrscheinlichkeit ausgedrückt: W(C|T) = W(C^T)/W(T). Man sieht hier die Änderung der „Bezugsgröße“ im Nenner. Da C^T und T^C die gleiche Schnittmenge bezeichnen, liegt der Unterschied im Nenner, also W(T), statt W(C) bei b).
Setzen wir für die Wahrscheinlichkeiten rechts wieder die relativen Häufigkeiten (in Bezug auf N) ein, dann bekommen wir auf der rechten Seite: (D/N)/(T/N) = D/T = 72.800/982.000 = 0,0741 Oder: W(C|T) ist 7,41% , die Wahrscheinlichkeit, dass eine Person an Corona erkrankt war, wenn sie gestorben ist.
Die Formulierung mit „wenn“ ist übrigens auch eine gute Möglichkeit zu überprüfen welche Wahrscheinlichkeit man meint: Wahrscheinlichkeit dafür, dass A, wenn B.
Methodische Anmerkung:
Relative Häufigkeiten sind immer in Bezug zu einer Grundmenge zu sehen. So ist nach der obigen Tabelle die relative Häufigkeit der Corona-Todesfälle (D) D/N = 0,0009 (0,09 %), bezogen auf die Gesamtbevölkerung (N), aber D/C = 0,0264 (2,64 %) bezogen auf die Corona-Erkrankungen.
Mit den entsprechenden Wahrscheinlichkeitsaussagen ist das allerdings so eine Sache. Formal zwar nicht; denn die Grundlagen der W-Rechnung gehen von einer definierten Ergebnismenge (Ergebnisse eines Zufalls-Prozesses) aus, und Wahrscheinlichkeiten sind für Teilmengen davon, „Ereignisse“ genannt, definiert. Der Bezug zur Grundgesamtheit ist also prinzipiell durch die Ergebnismenge implizit vorgegeben, wird aber oft bei Interpretationen „vergessen“.
Wenn man die Formeln für b) und c) in Beziehung setzt:
W(T|C) = W(T^C)/W(C) = W(T^C)*W(T)/(W(C)*W(T)) = W(C|T)*W(T)/W(C)
bekommt man die berühmte Bayes’sche Formel für den Zusammenhang von W(T|C) und deren Umkehrung W(C|T).
Anhang: Das Rauf-und-Runter-Spiel
Wir bezeichnen die Guthaben von X bzw. Y nach dem n-ten Zug als xn und yn. Die Werte nach jeweils der 1. Aktion des n-ten Zuges bezeichnen wir mit x’n und y’n. Das Spiel beginnt mit x0 = y0 = 100 Euro.
Für den n-ten Zug berechnen sich die x- und y-Werte so:
Zug n : Aktion 1
y’n = yn-1 + 0,2xn-1 und x’n = xn-1 - 0,2xn-1
Zug n : Aktion 2
yn = y‘n - 0,2y’n und xn = x’n + 0,2y’n
Dieser kleine Algorithmus lässt sich in der Tabellenkalkulation leicht darstellen:
Prozente | 20% | |||
x | y | |||
n=0 | 100,00 | 100,00 | ||
n=1 | 80,00 | 120,00 | ||
104,00 | 96,00 | |||
n=2 | 83,20 | 116,80 | ||
106,56 | 93,44 | |||
n=3 | 85,25 | 114,75 | ||
108,20 | 91,80 | |||
n=4 | 86,56 | 113,44 | ||
109,25 | 90,75 | |||
n=5 | 87,40 | 112,60 | ||
109,92 | 90,08 | |||
n=6 | 87,93 | 112,07 | ||
110,35 | 89,65 | |||
n=7 | 88,28 | 111,72 | ||
110,62 | 89,38 | |||
n=8 | 88,50 | 111,50 | ||
110,80 | 89,20 | |||
n=9 | 88,64 | 111,36 | ||
110,91 | 89,09 | |||
n=10 | 88,73 | 111,27 | ||
110,98 | 89,02 | |||
n unendlich | 111,111111 | 88,8888889 |
Die Werte nach unendlich vielen Zügen ergeben sich, indem man die Iteration „zugweise“ formuliert, also die x‘ und y‘ eliminiert:
Zug n:
yn = 0,8yn-1 + 0,16xn-1 und xn = 0,2yn-1 + 0,84xn-1
Die Konvergenzbedingung - also Werte von x und y, bei denen sich nichts mehr ändert - ist damit einfach das Gleichungssystem
y = 0,8y + 0,16x und x = 0,2y + 0,84x
deren Auflösung für x = 5/9 * 200 = 111,11 Euro (Gewinner ist X!) und für y = 4/9 *200 = 88,89 Euro ergibt.
Q16 Quanten und Qubits - Was man so liest
Von Bernhard Thomas und Ulrich Trottenberg
Quanten-Computing wird in den Medien, aber auch in Vorträgen und in der Fachliteratur mit einer Reihe von Aussagen charakterisiert, die als Sprachkonstrukte ziemlich exotisch klingen - nach einer anderen Welt, in der logisch Unmögliches möglich scheint. Wir wollen uns einige dieser Sprachfiguren ansehen und überlegen, was dahinter steckt.
Unsere bisherigen Blog-Abschnitte über Qubit-Algorithmen sollten ausreichen, hier ein klares Verständnis zu schaffen. Hier die Übersicht über die Aussagen.
"Quanten können 0 und 1 gleichzeitig sein"
"Mit n Qubits kann man 2**n Zahlen gleichzeitig darstellen"
"Für N Zahlen benötigt ein Quanten-Computer nur log(N) Qubits"
"Ein Quanten-Computer kann mehrere Berechnungen gleichzeitig durchführen (Quanten-Parallelismus)"
"Was auf herkömmlichen Rechner Jahre dauert, kann ein Quanten-Rechner in Sekunden erledigen (Exponentielle Beschleunigung)"
"Quanten-Rechner werden herkömmlichen Rechnern überlegen sein (Quanten-Supremacy)"
"Jedes zusätzlich Qubit verdoppelt die Leistungsfähigkeit des Systems"
"Quanten können 0 und 1 gleichzeitig sein"
Dieser Satz und Abwandlungen davon ziehen sich durch die Quanten-Computing-Literatur wie ein Mantra des QC. Auch wenn er gelegentlich nur als Metapher gesehen wird, suggeriert dieser Satz in der öffentlichen Diskussion eine mystische Eigenschaft der Quanten, nicht zuletzt illustriert durch das Bild von Schrödingers Katze, die "gleichzeitig tot und lebendig" ist.
Damit werden auch die informatischen Gegenstücke der Bits, die Qubits, charakterisiert. Im Gegensatz zu Bits, die nur "0 oder 1" sein können, können Qubits "0 und 1 gleichzeitig" sein.
Wie könnten wir das feststellen? Wir wissen, dass die Messung eines Qubits entweder 0 oder 1 ergeben kann, aber nicht beides. Wenn wir mehrfach messen, bekommen wir manchmal eine 0, manchmal eine 1 als Ergebnis, aber nie "gleichzeitig". Was kann also gemeint sein - wenn es überhaupt einen Sinn ergibt.
Es gibt Varianten dieser "Gleichzeitig"-Sprachfigur, die etwas tiefergehend klingen: "Quanten können verschiedene Zustände gleichzeitig einnehmen". Wir wissen, dass man Zustände von Systemen in Form von mathematisch eindeutigen Ausdrücken beschreiben kann - so auch Qubits und Qubit-Systeme. Ausgehend von einem Anfangszustand sahen wir, wie mittels Qubit-Operationen (oder Gates) ein Qubit-Zustand in einen nächsten überführt werden kann. Zu jedem Zeitpunkt ist der Zustand des Qubits daher eindeutig festgelegt. Wenn wir nicht unsere normale zweiwertige Logik (2 Wahrheitswerte: wahr, falsch - oder 0, 1) in Frage stellen, kann ein Qubit nicht zwei verschiedene Zustände gleichzeitig haben. Eine Zahl, ein mathematischer Ausdruck, der einben Zustand beschreibt, kann nicht gleichzeitig 0 und 1 sein: z = 0 = 1?
Manchmal findet man Texte, in denen das "Gleichzeitige" durch die "Superpostion" ergänzt wird: "Quanten können in einer Superosition von 0 und 1 gleichzeitig sein". Wir wissen, was eine Superpostion ist. Z.B. ist 1/√2 (|0>+|1>), die Hadamard-Operation auf den Basiszustand |0>, eine Superpostion (oder mathematisch: Linearkombination) der Qubit-Zustände |0> und |1>. Wir haben Qubit-Zustände meist in Form von x-y-Koordinaten eines Punktes auf dem Einheitskreis beschrieben - im Beispiel also (1/√2,1/√2). Somit können wir korrekt formulieren: Ein Qubitzustand hat zwei Koordinaten. Aber was heißt dann "gleichzeitig"? Wenn jemand in Ingolstadt ist, befindet er sich z.B. auf der Strecke von München nach Nürnberg - aber ist er (möglicherweise) in München und Nürnberg "gleichzeitig"?
Wenn auch die Redewendung "... kann 0 und 1 gleichzeitig sein" etwas Unsinniges suggeriert, können wir sie als solche akzeptieren, wenn man sie auf die Möglichkeit einer Superposition von zwei (Basis-)Zuständen eines Qubits zurückführt. Darin unterscheiden sich Qubits und Bits tatsächlich.
Und während ein Bit nur einen der beiden Zustände 0 oder 1 repräsentieren kann (siehe BIT-Box in Q3), kann ein Qubit einen Zustand aus einer unendlichen Menge von Superpositionszuständen annehmen. Wobei wir das "unendlich" im Sinne aller Punkte auf dem Einheitskreis verstehen, ohne zu fragen, ob wirklich unendlich viele Superpositionen realisierbar sind (technisch und quantenmechanisch).
Eine elegante und gleichzeitig korrekte, einfache Erklärung finden wir im Glossar der IBM (Übersetzung DeepL):
Ein Qubit (ausgesprochen "kju-bit" und kurz für Quantenbit) ist der physikalische Träger der Quanteninformation. Es ist die Quantenversion eines Bits, und sein Quantenzustand kann Werte von |0> , |1> oder die Linearkombination von beiden annehmen, was ein Phänomen ist, das als Superposition bekannt ist.
Mehr ist eigentlich nicht zu sagen.
"Mit n Qubits kann man 2**n Zahlen gleichzeitig darstellen"
Mit n Bits kann man zwar auch 2**n verschiedene Zahlen darstellen - gemeint sind Binärzahlen in Form von Bitketten - aber immer nur eine zu einem Zeitpunkt, z.B. im Speicher eines klassischen Computers.
Diese Aussage zusammen mit dem "Quantenparallelismus" (s.u.) soll die überragende Leistungsfähigkeit von Quanten-Computern deutlich machen. Man liest auch: "Mit jedem weiteren Qubit verdoppelt sich die Kapazität" und "Schon 300 Qubits können mehr Werte speichern, als das bekannte Universum Teilchen enthält".
Nun ja, wie soll man das verstehen? Zunächst zu den beiden letzten Versionen des "Kapazitätssatzes": Auch mit jedem weiteren Bit verdoppeln sich die möglichen Werte, die man speichern - und wieder lesen - kann. Immer einer zu einer Zeit (Schreib-Lese-Zyklus). Und mit 300 Bits kann man mehr als alle Teilchen des bekannten Universums abzählen, oder je eine Zahl zu einem Zeitpunkt im Bereich 0 bis 2**300-1 speichern. Bei Qubits liegt das Geheimnis offenbar wieder im "gleichzeitig". Wieder nur eine Metapher?
Ein System von n Qubits, z.B. n=3, befindet sich zu einem Zeitpunkt in einem Zustand (von prinzipiell unendlich vielen), der eine Linearkombination (Superposition) von nunmehr 2**n Basiszuständen ist, also 8 bei n=3. In der ket-Schreibweise tritt jede n-lange Bitkette als ein Basiszustand auf, bei n=3 also |000>, |001>, |010>, |011>, |100>, |101>, |110>, |111>. Bei n = 300 sind es halt ......
Denken wir an Koordinatensysteme, wie z.B. in Q11, dann haben wir ein 8-dimensionales Koordinatensystem und jeder 3-Qubit-Zustand wird durch 8 Koordinaten beschrieben. "Gleichzeitig" - für einen Punkt braucht man 8 Koordinaten "gleichzeitig".
Kann man in einer Superposition von 2**n Basiszuständen das gleichzeitige Speichern von 2**n Zahlen sehen? Nehmen wir eine gleichmäßige (uniforme) Superposition, d.h. alle Basiszustände kommen mit dem gleichen Koeffizienten vor. Bei n=3 also mit 1/√8.
Speichern nützt nur dann etwas, wenn man mit dem Gespeicherten etwas anfangen kann, z.B. weiter verarbeiten mittels Qubit-Operationen oder Lesen, d.h. Messen. Beim Weiterverabeiten zu einem neuen Zustand können tatsächlich alle Komponenten der Linearkombination in einer Operation berücksichtigt werden (Quantenparallelismus, s.u.). Beim Messen (gegen die Basiszustände) erhält man eine Häufigkeitsverteilung über alle Bitketten, die als Basiszustände in der aktuellen Superposition vertreten sind. Sind einige nicht vertreten, tauschen sie, bis auf Quantenfehler, auch nicht im Messergebnis auf.
Aber was machen wir damit? Welche Information ziehen wir daraus? Dass 2**n Bitketten beim Messen auftreten können, wussten wir schon vorher. Wir "lesen" also nichts Neues. Wenn wir 2**300 Teilchen mit unterschiedlichen Bitketten versehen wollten, konnten wir das auch schon ohne Quanten-Computer (QC).
Wo liegt also die Information, die wir durch die Quanten-Berechnung gewonnen haben? Wohl in der gemessenen Häufigkeitsverteilung:
- Wir schauen nur auf "vorhanden" und "nicht vorhanden" von gemessenen Bitketten. Eine häufige Form der Interpretation von QC-Ergebnissen, z.B. beim Herausfinden eines Orakels, wie im Bernstein-Vazirani Problem oder dem von Deutsch-Josza. Man kann sich das so vorstellen: Der Qubit-Algorithmus "rechnet" mit den 2**n Basiszuständen des n-Qubit Systems, der Ergebnis-Zustand enthält aber in nur einen Basiszustand, der dann bei der Messung eine ziemlich eindeutige Bitkette liefert. Eine solche Methode ist auch die sogenannte Amplituden-Verstärkung (amplitude amplification). Zum Auffinden einer bestimmten Bitkette beginnt man mit einer uniformen Superposition und verändert diesen Zustand Schritt für Schritt so, dass die Amplitude des Basiszustands mit der gesuchten Bitkette zunehmend "größer" wird. Die Iteration wird beendet, wenn man nahe genug an der gesuchten Bitkette ist, d.h. wenn beim Messen diese Bitkette eine überragende Wahrscheinlichkeit erreicht. Das Verfahren wird auch Grover-Iteration genannt.
- Uns interessiert ein "numerisches" Ergebnis, z.B. eine Zahl oder eine Reihe von Zahlen (Vektor), die sich bei der Messung am Ende der Rechnung als Häufigkeiten bestimmter Bitketten ergeben. Als "numerisches" Ergebnis nimmt man dann die Liste dieser Häufigkeiten. Hier stoßen wir aber auf verschiedene Probleme. Eines davon ist, dass ein echter QC die Häufigkeiten nicht exakt misst. Um halbwegs brauchbare Werte abzuleiten, müssen wir das QC Programm wiederholt durchlaufen lassen. Wie oft? Für n=3 kann man das ja einmal ausprobieren mit dem IBM QC. Wie oft bei n=50 oder n=300?
"Für N Zahlen benötigt ein Quanten-Computer nur log(N) Qubits"
Dies ist eine Variante der vorigen Aussage und besagt: "Während man auf herkömmlichen Computern für N Zahlen auch N Speicherplätze benötigt, braucht ein Quanten-Computer nur log(N) Qubits". Man hat also, umgekehrt gesehen, einen exponentiellen Effekt. Und damit ist ein Quanten-Computer exponentiell leistungsfähiger als ein herkömmlicher. Wie auch immer das gemeint ist, es läuft darauf hinaus, dass man eine Überlagerung der N Basiszustände eines "log(N) großen" Qubit-Systems herstellt, bei der die Koeffizienten (auch Amplituden genannt) gerade die gewünschten N Zahlen sind. Wenn man also weiß, wie, kann man einen solchen Superpositionszustand als "Input" herstellen, und einen Qubit-Algorithmus damit weiterrechnen lassen. Das ist das sog. Amplituden-Verfahren oder auch Amplituden Encoding.
Aber halt! Die N Amplituden müssen ja in der Summe der Quadrate 1 ergeben. Schränkt das nicht die freie Wählbarkeit der N Zahlen ein? Nicht wirklich - man muss nur vorher jede Zahl durch die Summe aller Quadrate teilen, genauer, durch die Quadratwurzel dieser Summe. Damit kann man dann "Quanten-Rechnen". Allerdings tritt bei der Ergebnis-Festellung wieder das Problem aus 2. auf.
Um die N Zahlen als Input verwenden zu können, muss man zu Beginn des Qubit-Algorithmus geeignete Qubit-Operationen (Gates) ausführen, so dass sie in einer Superposition zu Koeffizienten von Basiszuständen werden. Das kann trotz "Quantenparallelität" aufwendig sein. Hier ein Beispiel:
Angenommen, wir wollen die 4 Zahlen 1.0, 1.0, √2 = 1.414, 2.0 als Input in Form von Amplituden für ein 2-Qubit-System bereitstellen (N=4, n=2). Die Summe der Quandrate ist 1.0+1.0+2.0+4.0 = 8.0. Die Wurzel daraus ist √8. Dadurch müssen wir die 4 Zahlen teilen, damit diese eine gültige 2-Qubit Superposition ermöglichen: 1/√8, 1/√8, 1/√4, 1/√2. Es ist damit z.B. der Zustand 1/√8 |00> + 1/√8 |01> + 1/√4 |10> + 1/√2 |11> durch einen Qubit-Circuit herstellbar. Wie geht das? Hier ist eine Lösung:



Das "Fine-Tuning" der Amplituden erfolgt hier mittels Drehungen (Ry). Der resultierende Zustand ist verschränkt, d.h. er kann nicht als Kombination der einzelnen Qubits hergestellt werden. Das kann man nach der Methode in Q9 nachprüfen. (Ergebnis eines Simulatorlaufs mit 1024 shots.)
"Ein Quanten-Computer kann mehrere Berechnungen gleichzeitig durchführen"
Diese Aussage wird häufig als Verdeutlichung des sog. Quanten-Parallelismus verwendet. Auch hier wird wieder das Mantra-Wort "gleichzeitig" verwendet, dieses Mal aber in einer sinnvollen Bedeutung, nämlich im Gegensatz zu "nacheinander" (sequentiell). Natürlich können auch herkömmliche Computer heutzutage mehrere Berechnungen zeitlich parallel ausführen. Der Unterschied ist aber technisch fundamental: Herkömmliche Parallelrechner (z.B. MIMD-Architekturen) führen mehrere, durchaus auch verschiedene, Computerbefehle (Instructions) zur gleichen Zeit aus und verwenden dabei u.U. unterschiedliche Daten als Input.
Quanten-Computer führen zu einem Zeitpunkt einen Befehl (in Form von Gates) auf einer Datenstruktur aus. Die Datenstruktur ist der aktuelle Zustand eines n-Qubit-Systems, also meist eine Superposition oder gar eine Verschränkung. Der Zustand eines n-Qubit-Systems kann aber, wie wir zuvor gesehen haben, bis zu N=2**n Zahlen (in Form von Amplituden) repräsentieren. Indem der Qubit-Befehl auf den Zustand wirkt, wirkt er simultan auf alle Basiszustände, die in der Superposition vorkommen. Als Ergebnis können sich damit simultan alle Amplituden der Basiszustände verändern. Bingo!
Mathematisch gesehen ist das überhaupt nichts Ungewöhnliches. Eine Matrix A "wirkt" bei Multiplikation mit einem Vektor x auf alle seine Komponenten "gleichzeitig": y= Ax (Lineare Algebra). Wird ein Punkt (x,y) mittels einer Funktion F verschoben, dann werden alle Koordinaten "gleichzeitig" verschoben: (u,v) = F(x.y). Und auch die Qubit-Operatoren (Gates) können mathematisch als Matrizen dargestellt und verwendet werden. Wenn es allerdings ans praktische Rechnen geht, etwa mit einem Algorithmus, der die Matrixmultiplikation explizit durchführt, dann geht es klassisch (auf einem herkömmlichen Rechner) wieder nur Schritt für Schritt: die Operation wird in viele Einzelschritte zerlegt, die nacheinander ausgeführt werden. Hier unterscheiden sich klassische und Quanten-Computer tatsächlich fundamental. Quanten-Computer, wie die von IBM, sind technisch so aufgebaut, dass sie eine komplette Superposition in einem, statt in vielen Schritten verarbeiten können.
Wie man sich das vorstellen kann, zeigen wir an einem einfachen Beispiel: Das exklusive Oder (XOR) von zwei Bits entspricht der einfachen Bit-Addition bis auf die Operation "1+1", die 0 ergibt statt 2. (Dafür verwendet man auch das Symbol ⊕ statt +). Wir können die Bit-weise XOR-Berechnung auch als Qubit-Circuit durchführen. Das ergibt die 4 Auswertungen in der Abbildung, wobei jeweils q0 und q1 auf Zustand 0 bzw. 1 gesetzt werden und das Ergebnis den neuen Zustand von q1 ergibt.

Quanten-Parallelismus ermöglicht aber Superpositionen statt einzelner Basiszustände als Input zu präparieren, typischerweise mit dem H-Gate (Hadamard-Gate). Damit muss die Berechnung nur einmal ausgeführt werden und wir erhalten alle 4 Ergebnisse auf einmal.

Um die Ergebnisse einfacher "lesen" zu können, haben wir hier das XOR Ergebnis auf ein drittes Qubit q2 übertragen. So erhalten wir als Messergebnis genau die obige XOR Tabelle mit XOR -> q2 : 000, 101, 110, 011 (q2 steht hier wieder jeweils ganz links in der Bitkette).
"Was auf herkömmlichen Rechnern Jahre dauert, kann ein Quanten-Rechner in Sekunden erledigen"
Als Begründung liest man dabei oft, dass Quantenrechner "exponentiell schneller" rechnen können als herkommliche. Was bedeutet das?
Das heißt zum Beispiel folgendes: Wenn wenn wir zwei Methoden haben, die eine Aufgabe lösen, etwa eine Berechnung durchführen oder ein "Geheimnis" (Q15) zu finden, und die eine Methode benötigt N Zeiteinheiten oder Rechenschritte, die andere aber nur log(N) viele, dann stellt die zweite Methode eine exponentielle Verbesserung - oder Beschleunigung - gegenüber der ersten dar. (Denn, für k=log(N) ist N=exp(k).)
Es gibt eine ganze Reihe von solchen "Beschleunigungsbeziehungen" zwischen Methoden zur Lösung gleicher Aufgaben. Der Grover Qubit-Algorithmus benötigt nur etwa √N Schritte gegenüber N Schritten bei der klassischen Methode. Hier haben wir also eine quadratische Beschleunigung. In Q15 hatten wir das am Beispiel des Bernstein-Vazirani-Algorithmus diskutiert.
Solche Beschleunigungen gibt es von je her auch im klassischen Computing als Effekt einer algorithmischen Verbesserung. So gibt es z.B. unterschiedliche Sortier-Algorithmen, die sich bezüglich ihres Rechenaufwands erheblich unterscheiden, oder auch Verfahren zur numerischen Simulation, bei denen sogenannte Mehrgitterverfahren große Beschleunigungsraten bringen.
Der tatsächliche Beschleunigungseffekt des Quanten-Computing gegenüber herkömmlichen Bit-Computing beruht auf einer Kombination von zwei Dingen: dem Quanten-Parallelismus der Hardware (s. voriger Abschnitt) und dem Algorithmus, der für Qubits konstruiert werden kann.
Ein Rechenbeispiel: Hätte man eine (hypothetische) Aufgabe, die auf einem gewöhnlichen Rechner mit dem schnellsten Algorithmus 10 Jahre dauern würde, dann würde eine exponentielle Beschleunigung auf einen Zeitaufwand von rund 20 Sekunden führen: log(10*360*24*60*60) = log(311040000) = 19,56. Diese Zahlen sind allerdings eher fiktiv, da wie keine konkrete Aufgabe vor Augen haben und Wiederholungen und anderen "Overhead" nicht berücksichtigen. Aber es zeigt, wie sich die Größenordnung ändern.
Hätten wir also eine Aufgabe, die herkömmlich Jahre dauern würde, und hätten wir dazu ein Quanten-Computer, der sie alternativ mit exponentieller Beschleunigung löst, könnten wir die Aussage so akzeptieren. Allerdings gibt es noch nicht viele Algorithmen für Quanten-Computer, die in dieser Form praktische verwendbar sind. Was nicht zuletzt auch an der Größe und "Sensibilität" heutiger QC liegt.
Ein relevantes Beispiel, das immer wieder als "Gefahr durch Quanten-Computer" zitiert wird, ist das Verfahren von Shor, mit dem man einen wichtigen Schritt beim "Knacken" von besten heutigen Verschlüsselungsverfahren in akzeptabler Zeit durchführen kann. Um das zu verstehen, braucht es aber schon mehr Einsicht in die zugrunde liegende Mathematik. Daher wird hier meist nur der (befürchtete) Effekt zitiert und auf Verständnis verzichtet.
"Quanten-Rechner werden herkömmlichen Rechnern überlegen sein"
Man spricht auch generell von Quanten-Überlegenheit (Quantum Supremacy). Trotz der beängstigent klingenden Bezeichnung handelt es sich hier um eine unspektakuläre Sache. Es bedeutet lediglich das Ereignis, dass es eine Berechnung gibt, die ein Quanten-Computer schneller als jeder herkömmliche Supercomputer durchführen kann. Dabei ist es erst einmal egal, ob diese Berechnung einen Sinn macht oder praktische Bedeutung hat. Wie man kürzlich lesen konnte, hat man (mit einem QC von Google) bereits eine solche Berechnung durchführen können, d.h. der Meilenstein Quantum Supremacy ist schon erreicht.
"Jedes zusätzlich Qubit verdoppelt die Leistungsfähigkeit des Systems"
Hier bleibt einerseits unklar, was mit Leistungsfähigkeit gemeint ist - Rechenleistung, Speicherleistung, Leistung eines Algorithmus, der ein Qubit mehr zur Verfügung hat? Auch wenn wir einen Bit-Speicher (Register) um ein Bit erweitern, also von n auf n+1 Bits, können wir damit 2**(n+1) = 2*2**n Werte speichern bzw. mehr oder längere Befehle ausführen. So hatte sich auch die Prozessorarchitektur von früheren 32 Bit auf 64 Bit bei herkömmlichen Computern verändert und dabei prinzipiell eine 32-fache Verdoppelung der Leistung ermöglicht.
Was macht nun ein Qubit mehr aus bei einem Quanten-Computer? Zum einen gibt es dann doppelt so viele Basiszustände. Z.B. von 8 bei einem 3-Qubit System auf 16 bei 4 Qubits. In Superposition können damit 16 statt nur 8 Koeffizienten (Amplituden) einen Zustand bestimmen. Diese Verdoppelung ist analog der Situation bei Bits und wir hatten das schon oben bei N vs log(N) erklärt.
Zum anderen wissen wir, dass - ganz ander als beim Bit-Computing - verschränkte Zustände eine wichtige Rolle im Qubit-Computing spielen. Man kann sich also fragen, was bringt ein zusätzliches Qubit für die möglichen Verschränkungen, oder allgemein für die möglichen "Konfigurationen" von Superpositionen. Anders ausgedrückt: wieviel mehr Möglichkeiten gibt es für Zustände, in denen nur ein Basiszustand vertreten ist, oder zwei, oder drei usw. - unabhängig von den Werten der Amplituden. Diese Zahl wächst offenbar kombinatorisch. Für n=2 sind die "Muster" noch überschaubar: 4 mal |x>, 6 mal |x>+|y>, 3 mal |x>+|y>+|z> und 1 mal |x>+|y>+|z>+|v>, wenn |x>,|y>,|z>,|v> die Basiszustände |00>, |01>,|10>,|11> durchlaufen.
In Q13 (Superdichte Codierung) haben wir einen anderen Verdopplungseffekt gesehen: die Kapazität, Bitketten in GHZ-verschränkten Qubits zu "speichern" bzw. zu übertragen. Hier brachte jedes weitere Qubit in einer solchen Verschränkung eine Verdoppelung der Anzahl übertragbarer Bitketten.
Zuletzt eine Anmerkung: Bei "Was man so liest" fragt man sich leicht, wo man das gelesen hat. Die konkreten Aussagen in den Überschriften sind keine echten Zitate, obwohl sie so oder in Variationen der Wortwahl tatsächlich vorkommen. Wir wollen hier aber kein "Bashing" anzetteln, sondern nur kostruktiv klären, was dahinter steckt oder wo man leicht fehlgeleitet wird. Daher verzichten wir auf Quellenangaben.
Quantencomputing ohne Quantenmechanik?
Von Ulrich Trottenberg und Bernhard Thomas

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

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!

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 |
Q6 Zwischenspiel - ZBIT-Spielereien
Hier wollen wir mit dem verbesserten ZBIT-Modell aus Q5 ein wenig rumspielen, um mit dem Modell und den Definitionen ein wenig vertrauter zu werden. Um so leichter fällt dann der letzte (kleine) Schritt zum Qubit. Wegen des letzten Abschnitts ist dieser Blog etwas länger geraten. Dafür führt er uns aber zu einer Modell-Darstellung, die schon die für das Qubit-Modell sein wird. Wer keine Lust hat zum Spielen, kann auch einfach nur einen Kaffee trinken und gleich mit dem nächsten Blog weitermachen.
Wir hatten schon festgestellt, dass die inneren Zustände eigentlich beliebig wählbar sind, vorausgesetzt, die Maschinen-Tabellen (Output und Zustandsübergänge) sind konstistent.
1. Alice, Bob, Charly und Debbie
Statt [00] usw. können wir z.B. Namen nehmen:
Alice, Bob, Charly und Debbie statt [00], [10], [01], [11]. Wenn wir die vier dann als Ecken eines Quadrats aufstellen, etwa in der Sporthalle, können wir das Modell als Ballspiel beschreiben:
- Jede Runde beginnt bei Alice, sie hat den Ball (Operation R)
- Jeder spielt den Ball entsprechend den Regeln von X und H.
- Jeder ist dabei frei, welche der Regel sie oder er "werfen" will
- Irgendwann pfeift der Referee ab (M)
Die Grafik illustriert das Set-up. Die Pfeile zeigen, wie X und H gespielt werden dürfen. Da die Personen formal Zustände sind, zeigt die Grafik ein sog. Zustandsüberführungs-Diagramm, ein Wort, das man üben muss.
Wir haben noch nicht gesagt, was D, L und P sein sollen. Da wir die inneren Zustände und Übergänge beim Ballspiel beobachten, könnten wir trivialerweise festlegen: D, wenn der Ball bei Abpfiff bei Alice ist, L, wenn er bei Debbie ist und P, wenn er bei einem der beiden anderen ist. Das ist nicht beonders interessant.
Wie wäre es, wenn bei Abpfiff der Ball in einen Basketball-Korb geworfen werden muss? Das ganze Spiel findet hinter einem Vorhang statt, sodass wir es nicht sehen können. Allein den Wurf auf den Korb können wir sehen. Dabei bedeutet D, dass der Ball niemals versenkt wird (Alice), L, dass er mit Sicherheit reingeht (Debbie), und P, dass er manchmal trifft und manchmal nicht, im Verhältnis 1:1.
Fragen: Können wir herausfinden, wer den Ball zum Korb wirft? Wie wäre es, wenn wir dem Team bzw. dem Referee Spielpläne vorgeben würden (Algorithmen)? Wie könnte ein "autonomes" Spiel aussehen? D.h. jeder Spieler entscheidet (zufällig) welchen der möglichen Würfe (R, X, H, M) er oder sie macht.
Wer Lust hat, kann Überlegungen oder Antworten als Kommentar einfügen.
Nun gut, lassen wir die vier weiter spielen und wenden uns einer Darstellung zu, mit der wir das ZBIT-Modell simulieren können.
2. Ein ZBIT-Box Simulationsmodell
Wir haben im Beitrag "Etwas ist anders - Hello Qubit World" die Partitur eines QuBit-Algorithmus gesehen - ohne zu wissen, worum es geht. Solche Partituren können, wenn sie fehlerfrei sind, von Quanten-Computern oder auch von QC-Simulatoren abgearbeitet werden. Es wäre doch interessant, wenn wir die ZBIT-Experimente in diese Form bringen könnten und sie dem Simulator vorlegen könnten.
Da die Experimente mit den ZBIT- und BIT-Modellen schon in Anlehnung an die "Partitur-Form" beschrieben wurden, sollte es uns tatsächlich leicht fallen.
Die Modell-Beschreibung für den QC-Simulator ändert sich kaum: X und H werden vom Simulator "verstanden", das R gibt es nicht explizit, sondern jede Partitur beginnt mit dem Ausgangszustand. Der wird im Simulator mit |0> gekennzeichnet statt mit [00], aber die Namen der inneren Zustände sind ja unwesentlich. (Was |0> bedeutet, werden wir später sehen.) Das Anzeige-Symbol ("Tacho-Nadel") steht für die Operation M (Messen).
Anders als bei den bisherigen Modell-Beschreibungen können wir nichts über die inneren Zustände des Simulators wissen. Die Zeile der Zustandsübergänge in den bisherigen Experimenten ist nicht verfügbar - jedenfalls beim QC. Die Messergebnisse des Simulators können '0' oder '1' sein, das entspricht dem D und L im ZBIT-Modell. Was wir für P bekommen sehen wir im Experiment.
Wir nehmen das ZBIT-Vorhersage-Experiment aus dem vorausgehenden Blog:
R ------ H ----- X ----- H ---- H ----- M -> P
und bilden es ab auf den QC-Simulator (hier: IBM Q Experience Circuit Composer).
Mit dem QC-Simulator können wir dieses Experiment einmal durchführen und erhalten:
{'0': 1}. Wir wiederholen und bekommen wieder ein {'0': 1}, dann ein {'1': 1}. Das bedeutet, die ersten drei Experiment-Durchläufe resultierten jeweils in einer '0', bzw. einer '1'. Wir bekommen also D oder L als Output. Wie bei der ZBIT-Box machen wir jetzt Mehrfach-Experimente, z.B. eine Serie von 50 Durchläufen. Das Ergebnis:
also 28 mal L und 22 mal D in unserer ZBIT-Interpretation.
Das sieht schon recht spannend aus. Im Prinzip könnten wir alle bisherigen Experimente mit dem BIT-Modell und dem ZBIT-Modell in dieser Weise simulieren. Damit kommen wir dem Konzept von Qubit-Algorithmen schon sehr nahe.
Und wir gewinnen eine wichtige Erkenntnis: ZBIT (das verbesserte) und BIT sind Teilmodelle des - hier noch unbekannten - Qubit-Modells.
Wer Lust hat, kann nicht nur Fragen und Antworten als Kommentar unten anfügen, sondern auch unter IBM Q Experience sich registrieren und schon mal im Circuit Composer stöbern. Wir schauen uns das in einem späteren Blog noch mal näher an. Eine ähnliche Umgebung bietet auch Google an mit Cirq.
Nun wenden wir uns einer Darstellung zu, mit der wir das ZBIT-Modell mit einfachen Formeln berechnen können.
3. Ein Modell mit Formeln
Wir wollen nun versuchen, die Zustände so zu definieren, dass man mit ihnen "rechnen" kann. Statt in den Automaten-Tabellen die Zustandsübergänge nachzusehen, wollen wir sie mit einfachen Formeln berechnen können. Das gleiche für die Outputs.
Eine naheliegende Idee wäre es, die Ziffern in den Zuständen [00] usw. tatsächlich als Zahlen aufzufassen und dazu auch die Output-Ergebnisse in Zahlen umzuwandeln: D entspricht 0, L entpricht 1, und P dem Wert 1/2. Diese Werte können verstanden werden als Wahrscheinlichkeiten, dass wir Licht sehen, wenn wir die Klappe öffnen. Wir schreiben dafür p(L).
Allerdings hatten wir [00] usw. eigentlich nur als "Label" für die Zustände eingeführt und nicht als arithmetische Größen. Daher wäre es ein erstaunlicher Zufall, wenn wir damit ein konsistentes arithmetisches Modell bilden könnten.
Tatsächlich geht das aber, bis zu einem gewissen Punkt. Wer sich davon überzeugen will: es gibt einen Annex zu Q6, in dem das dargestellt wird. Wenn wir allerdings das Modell erweitern wollen, z.B. um Zustände, die p(L) = 1/4 als Output liefern, gibt es Schwierigkeiten.
Wir geben uns daher etwas mehr Freiheit bei der Definition eines rechnerischen Modells, indem wir die Zustände ("Labels"), in ein x-y-Koordinatensystem einbetten. (Wir erinnern uns, dass wir mit den zwei-ziffrigen Zuständen in Q5 so etwas wie 2-dimensionale Zustände eingeführt hatten.) Die Zustände werden dann zu Punkten in der x-y-Ebene.
Wir halten die Bezeichnungen [00] bzw. Alice zunächst einmal bei. Sie benennen die Punkt, so wie man Punkte A, B und C eines Dreiecks in der Ebene benennt und mit Koordinaten versieht. Trotzdem können die 0-en und 1-en etwas verwirrend wirken. Die Punkte werden mit ihren Koordinaten in normalen Klammern geschrieben, also z.B. (1,0), die [00] in eckigen Klammern sind die Label der Punkte, ebenso wie die Namen Alice etc.
Das Einfachste ist, die beiden Zustände [00] und [11] - die ja auch die BIT-Zustände repräsentieren - auf die Koordinaten-Achsen zu platzieren. [00] als Punkt auf der x-Achse bei 1: (x,y) = (0,1). Und [11] entsprechend auf der y-Achse: (x,y) = (1,0). Das Diagramm zeigt wie.

Wo würden wir dann die Zustände [10] und [01] positionieren? Nun, das können wir bereits "ausrechnen". Schauen wir uns dazu zunächst die passenden Formeln für die Wirkung der Operatoren R, X und H an.
R ist einfach: R(x,y) = (1,0). Das Reset überführt jeden Zustand in den Ausgangszustand, der jetzt die Koordinaten (0,1) hat.
Auch X ist nicht schwer: X(x,y) = (y,x). X als "Switch" vertauscht die Koordinaten. Das passt schon mal für die beiden vorgegeben Zustände (1,0) <-> (0,1).
Wir haben uns noch nicht um den Output gekümmert. Der Output von (1,0) (i.e. [00]) muss p(L) = 0 sein, der vom (0,1) (i.e. [11]) entspechend p(L) = 1. Es liegt daher nahe, die y-Koordinate als p(L) zu übernehmen. Die x-Koordinate wäre entsprechend als Wahrscheinlichkeit für D zu interpretieren: p(D).
Hieraus folgt direkt und zwingend: p(L) + p(D) = 1.
Damit bekommen wir folgende Bedingungen für die Zustände [10] und [01]:
(1) Sie müssen so positioniert werden, dass die Summe ihrer beiden Koordinaten 1 ergeben.
(2) Der zugehörige Output muß 1/2 ergeben; die y-Koordinate muss also 1/2 sein.
(3) Wegen der Wirkung von HH, müssen H[00] = [01] und H[11] = [10] unterschiedliche Koordinaten haben.
Man sieht sofort, dass diese Bedingungen unvereinbar sind: [01] kann mit den Koordinaten (1/2,1/2) die Bedingung (1) und (2) erfüllen. Es gibt aber keinen weiteren Punkt, der (1) und (2) erfüllt.
Wir ändern daher die Output-Definition: M (x,y) = p(L) = |y|, d.h. die Wahrscheinlichkeit für L ist der Absolutbetrag von y. Die Bedingungen (1) und (2) werden dann zu
(1') Die Summe der Beträge der Koordinaten muss 1 sein: |x|+|y| = 1. Und
(2') Der Betrag der y-Koodinate muss 1/2 sein
Wenn wir dann [10] mit den Koordinaten (1/2,-1/2) versehen, werden alle drei Bedingungen erfüllt. (Siehe Grafik.)

Weiter stellen wir fest, dass aus der Anwendung X und H auf schon bekannte Zustände neue Punkte hervorgehen, die wir ebenfalls als Zustände zulassen müssen. So muß z.B. mit (1/2,-1/2), den Koordinaten für [10], auch X(1/2,-1/2) = (-1/2,1/2) = -(1/2,-1/2) ein zulässiger Zustand sein. Wenn H(1/2,-1/2) wieder (0,1) sein soll (doppelte H Anwendung auf [11]), dann muss H(-1/2,1/2) = (0,-1) zulässig sein. Und X(0,-1) = (-1,0) = -(1,0) ebenso. Das Diagramm zeigt die Zustände als Punkte, die Pfeile für die Operatoren sind wegen der Übersichtlichkeit nicht eingezeichnet. Man kann aber, wenn man Lust hat, selbst versuchen, diese Zustandsübergänge einzuzeichnen (gedanklich), soweit es geht.
Das ist zunächst einmal überraschend: Wenn wir die 4 Zustände des ZBIT-Modell durch Punkte im (x,y)-Koordinatensystem darstellen wollen, erweitert sich das Modell zwangsläufig auf 8 Zustände! In unserem ZBIT Ball Game oben, würden dann Alice, Bob, Charly und Debbie jeweils einen Zwilling bekommen, Twin-Alice usw. Eigentümlich - aber niemand zwingt uns, bei einem Modell für die ZBIT-Box mit nur 4 Zuständen auszukommen. Vier ist das Minimum, aber 8 geht auch. Im Diagramm sind die "Twins" als helle Punkte eingezeichnet. Frage: Welcher Punkt ist Twin von wem?
Damit haben wir für das Koordinaten-basierte Modell:
- Die Zustandsmenge
- Die Wirkung von R und X als Formel
- Die Zustand -> Output Abbildung M mit der Interpretation als p(L), Wahrscheinlichkeit für L als Messergebnis
Was fehlt, ist die Formel für H. Wir hatten festgelegt, dass (1,0) (Label [00]) durch H in (1/2,1/2) überführt werden soll und (0,1) (Label [11]) in (1/2,-1/2). Eine naheliegende Formel für H wäre: H(x,y) = 1/2 (x+y, x-y). Sie liefert für (1,0) und (0,1) genau das, was sie soll. Aber wie sieht es mit (1/2,1/2) und (1/2,-1/2) aus. H auf diese Zustände angewandt müsste ja wieder (1,0) bzw. (0,1) ergeben.
Jedoch: H(1/2,1/2) = 1/2 (1/2+1/2, 1/2-1/2) = 1/2 (1,0). Den gleichen Widerspruch erhalten wir für (1/2,-1/2). Der Faktor 1/2 macht die Inkonsistenz aus. Wenn wir allerdings den Faktor 1/2 in der Definition von H weg lassen, bekommen wir für (1,0) und (0,1) schon gleich falsche Ergebnisse.
Was tun? Vielleicht etwas dazwischen - zwischen 1/2 und 1? Wie es die Mathematiker gerne machen, wenn man sich nicht entscheiden kann, setzt man anstelle von 1/2 eine Variable, sagen wir a, und versucht, dafür einen passenden Wert zu bestimmen. Das ist sehr elegant. Probieren wir also: H(x,y) = a*(x+y,x-y).
H(1,0) ergibt dann nicht mehr (1/2,1/2) sondern (a,a), was immer a auch ist. Entsprechend H(0,1) = (a,-a). Wenn wir darauf wieder H anwenden, bekommen wir H(a,a) = a*(a+a,a-a) = a*(2a,0) und H(a,-a) = a*(a+(-a),a-(-a)) = a*(0,2a). Andererseits muss H(a,a) = (1,0) sein, also a*2a = 2a² = 1 oder a = 1/sqrt(2). Das klappt auch mit der zweiten Bedingung. Très chic !
Allerdings stehen wir damit wieder am Anfang. Wir müssen die drei Spiegelpunkte oben wieder neu festlegen. Aber dieses Mal lohnt sich die Spielerei; denn wir haben hiermit automatisch die grundlegenden Komponenten für ein Qubit-Modell in Q7 abgeleitet.
- Die 8 Zustände sind (1,0), (0.1), (-1,0), (0-1) und (a,a), (-a,a), (-a,-a), (a,-a) mit a = Wurzel aus 1/2. Alle diese Zustände liegen auf einem Kreis mit Radius 1.0 im x,y-Koordinatensystem. Sie erfüllen die Bedingung x² + y² = 1, die Gleichung des Einheitskreises.
- R und X sind genau wie zuvor definiert, und H als H(x,y) = a*(x+y,x-y).
- Wie ist die Zustand-Output Beziehung? Jetzt ergibt M(x,y) = y² das p(L), die Wahrscheinlichkeit für L bei einer Messung. Und p(D) ist entsprechend x² = 1-y², was ja für alle Zustände auf dem Einheitskreis stimmt.
Das Diagramm zeigt das ZBIT-Modell mit diesen Festlegungen.

Der letzte Abschnitt war sicher keine einfache Spielerei mehr. Aber wir haben es geschafft. Und, wie wir sehen werden, gleichzeitig DAS Werkzeug für Qubit-Algorithmen gefunden.
Frage: Wie würde das ZBIT Ball Game aussehen, wenn wir die vier neuen Spieler ins Feld bringen würden - nennen wir sie Twin-Alice, Twin-Bob, Twin-Charly und Twin-Debbie? Wer Lust hat usw.
Im nächsten Blog, versprochen, kommen wir aber zum QuBit-Modell - zumindest in einer ersten Form.
Fortsetzung folgt - Stay tuned!
Q5 Ein verbessertes ZBIT-Modell
Können wir ein verbessertes ZBIT-Modell entwerfen, dass den Widerspruch bei der doppelten H Operation auflöst? Wir erinnern uns:
Wir haben beim Experimentieren mit der ZBIT-Box gesehen, dass sich zweimal H hintereinander aufheben. Mit dem bisherigen ZBIT-Modell ließ sich dieses Ergebnis nicht herbeiführen. Denn H auf [0] angewendet ergibt [1/2], aber auch H auf [1] angewendet ergibt [1/2]. Damit kann nicht gleichzeitig HH[0] = H[1/2] = [0] und HH[1] = H[1/2] = [1] sein.
Ein verbessertes ZBIT-Modell
Wie können wir ein verbessertes Modell für die ZBIT-Box entwerfen? Der Widerspruch entstand, als wir H auf den einen neu eingeführten Zustand [1/2] anwendeten und erwarteten, dass daraus zwei verschiedene Ergebnisse hervorgehen. Das war zwar naheliegend (Occam's Razor Prinzip, mal bei Wikipedia nachschlagen), aber vielleicht hätten wir besser zwei neue Zustände eingeführt.
Das kann man einfach erreichen, indem man zu der ursprünglichen Zustandsvariablen mit zwei möglichen Werten eine weitere mit ebenfalls zwei Werten hinzufügt. D.h. der innere Zustand hat zwei Größen, sagen wir s1 und s2, die die Werte [0] und [1] haben können. Die Zahlen haben wieder keine Bedeutung; wir könnten die Zustände auch a und b nennen oder a1, b1 und a2, b2 nennen. Damit gibt es für (s1, s2) genau vier mögliche Kombinationen!
Die Wahl von [0] und [1] erweist sich aber als ganz praktisch. So können wir uns z.B. einfach vorstellen, dass die inneren Zustände des neuen ZBIT-Modells die vier Ecken des Einheitsquadrats in der Ebene darstellen - weswegen wir auch sagen, dass der Zustand 2-dimensional ist.
Das neue ZBIT-Modell legen wir ähnlich wie oben fest:
- Wir nehmen für das neue Modell zwei Zustandsvariablen (oder: einen zwei-dimensionalen Zustand) und kennzeichen diese [0][0], [0][1], [1][0] und [1][1]. Um uns die Klammerei zu erleichtern, "labeln" wir die Zustände stattdessen einfach mit [00], [01], [10] und [11].
- Wir setzen [00] als den Startzustand
- Die Outputs werden als D, L und P abgekürzt, für Dunkel und Licht und den variablen Zufalls-Output.
- Die Operationen sind wieder mit R, X und H bezeichnet und repräsentieren Klappe zu und das Berühren von Touch-Feld X bzw. H.
- Das Messen (M) des 2-dimensionalen ZBIT-Zustands (Klappe auf und schauen), d.h. die Zuordnung Output zu Zustand, kann nun vier Ergebnisse haben. Wir legen fest:
M: [00] -> D, [01] -> P, [10] -> P und [11] -> L
Auch die Wirkung der Operatoren R, X und H müssen wir neu festlegen. Das geschieht am übersichtlichsten in eine vollständigen Tabelle, analog der vom ersten Versuch.
Zustand | Neuer Zustand bei | R X H [00] | [00] [11] [01] [01] | [00] [10] [00] [10] | [00] [01] [11] [11] | [00] [00] [10]
Als technische Konstruktion des Modell können wir uns vorstellen, dass im Inneren zwei (!) Schalter sitzen, die durch die Touch-Felder bzw. "Klappe zu" betätigt werden. Wie, sagt die Tabelle. Und die Schalterstellung bestimmt, ob Dunkel, oder Licht oder zufällig zur Hälfte Licht und Dunkel zu sehen ist beim Öffnen der Klappe. Z.B. besagt die M-Tabelle, dass, wenn die Schalter "verschieden" gesetzt sind, der Zufallsoutput erfolgen muss. Wie man das baut - mal ausprobieren. Z.B. mit Roberta (IAIS).
An dieser Stelle ist noch einmal wichtigt zu bedenken, dass auch die technische Konstruktion ein Modell für die Blaue Box ist. Im Gegensatz zur Box haben wir aber vollständige Einsicht in unsere Modell-Box.
Wir müssen nun erneut prüfen, ob das Modell widerspruchsfrei ist, d.h. im Experiment das Verhalten der blauen ZBIT-Box zeigt. Für die Operationen R, X, H müssen wir in die Tabelle schauen, für M in die Output-Liste. Wir beschränken uns hier auf die Beispiele vom ersten Modell und die "Problemfälle" dort.
R ------ X ------ H ---- M -> 1:1 liefert die ZBIT-Box im Serienexperiment
[00] -> [11] -> [10] -> P liefert das neue Modell. Das passt wieder.
"1:1" bedeutet Dunkel / Licht im Verhältnis 1:1.
R ------ H ------ X ---- M -> 1:1 ZBIT-Box Messreihe
[00] -> [01] -> [10] -> P ZBIT-Modell Output
Noch ein paar einfache Fälle, die wir schon aus dem BIT-Modell kennen:
R ----- M -> Dunkel R ----- X -----M -> Licht
[00] -> D [00] -> [11] -> L
R ------ X ------ X ---- M -> Dunkel
[00] -> [11] -> [00] -> D
Passt also. Nun die Doppel-H Experimente:
R ------ H ----- H -----M -> Dunkel als ZBIT-Box Output
[00] -> [01] -> [00] -> D Modell Output. Passt!
Für HH[11] müssen wir zunächst den Ausgangszustand [00] mit Hilfe von X zu [11] machen und dan HH anwenden.
R ------ X ------ H ----- H -----M -> Licht in der Box
[00] -> [11] -> [10] -> [11] -> L "Licht" im Modell
Durch Hinzunahme einer zweiten Zustandsgröße konnten wir also den Widerspruch des ersten Versuchs auflösen. Das ist auch leicht zu verstehen: der Zustand nach dem ersten Anwenden von H würde bei Messung zwar immer P ergeben, er trägt aber noch die Information, "woher" er kommt, von [00] oder [11]. nämlich in der Reihenfolge von 0 und 1 im Zustand. (Genial! findet der G.E.)
ZBIT Vorhersagen
Natürlich können wir auch jetzt noch nicht ausschließen, dass das Modell nicht widerspruchsfrei ist. Dazu müssten wir alle möglichen Abfolgen von Operationen (Algorithmen) gegen die ZBIT-Box evaluieren - oder zumindest eine endliche Menge davon, auf die "alle möglichen" reduziert werden können.
Was wir weiterhin machen können, sind Vorhersagen. D.h. wir können eine noch nicht gesehene Abfolge von Operationen im Modell berechnen und das Ergebnis experimentell an der ZBIT-Box überprüfen. Ein Beispiel, das wir bei der Erforschung der Box oben noch nicht als Experiment durchgeführt hatten
R ------ H ----- X ----- H ---- H ----- M ergibt [00] -> [01] -> [10] -> [11] -> [10] -> P
Das zugehörige Experiment: Klappe zu -> Touch H -> Touch X -> Touch H -> Touch H -> Klappe auf: Dunkel. Wir wissen, dass wir das gleiche Experiment vorsichtshalber in Serie durchführen müssen, um zwischen P und Licht oder Dunkel unterscheiden zu können. Wir tun das 20 Mal und sehen 11 Mal Dunkel und 9 Mal Licht, experimentell also eindeutig P bestätigt.
Fragen: Wie oft müssten wir das Experiment mindestens wiederholen, bis wir das Ergebnis P bestätigen können? Wie oft, um ein vorausgesagtes Ergebnis L zu bestätigen? Hier haben wir offenbar ein Problem. Wir können, da wir das "Innere" der Box nicht kennen können, nie sicher sein, ob nicht bei der nächsten Wiederholung ein D folgt. Wie immer müssen wir uns damit zufrieden geben, L als bestätigt zu sehen, wenn wir bei einer großen Anzahl von Wiederholungen immer L gesehen haben. Anders ausgedrückt, wir "bestätigen" das Ergebnis mit (einfachen) statistischen Methoden - aber das ist eine ganz andere Baustelle.
Aufgaben:
- Die 2-dim Zustandsdefinition erinnert an die üblichen vier 2-Bit Kombinationen. Könnte man die ZBIT-Box möglicherweise mittels zweier BIT-Modelle modellieren?
- Was wäre, wenn man beim Berühren von H nicht Licht und Dunkel im Verhältnis 1:1 beobachtet sondern z.B. 1:3 (Häufigkeit von D etwa 1/4)?
- Das dauernde Wiederholen eines Experiments, von dem man als Output P erwartet ist eigentlich lästig. Könnten wir uns eine technische Konstruktion ausdenken, die den Output P durch ein halb so helles Licht anzeigt?
Wer Lust hat, kann gerne die Fragen und die Aufgaben im Kommentarfeld unten diskutieren.
Vom ZBIT-Modell ist es nun nur noch ein kleiner Schritt zum Qubit-Modell. Aber erst mal wieder: Pause - also einen Kaffee trinken oder etwas spielen.
Hier geht's weiter.
Q4 ZBIT - unterwegs zum Qubit-Modell
Im vorausgegangenen Teil haben wir ein sog. Automaten-Modell für die BIT-Box entwickelt. Ein Automat, genauer, ein endlicher Automat (im Englischen Finite State Machine), ist ein einfaches Konstrukt, das aus folgenden Teilen besteht: Eingabe - innerer Zustand - Ausgabe, eine Methode zur Änderung des Zustands und eine, die den Output festlegt. Endlich heißt der Automat, weil die Möglichkeiten zur Eingabe, die Zustände und die Ausgaben nur einen endlichen Umfang haben.
Das BIT-Box-Modell hat, so gesehen, Null Eingabe-Möglichkeiten (ja, auch das geht!), 2 Zustände und 2 Output-Möglichkeiten. Die Zustandsveränderungen sind durch die beiden kleinen Tabellen für R und X festgelegt und die Output-Methode ist das Messen, M, das auch durch eine Tabelle festgelegt ist. Das BIT-Box-Modell ist damit ein sehr einfacher endlicher Automat. Was dazu führt, dass man sich angewöhnt hat, die mögliche Struktur, die technische Konstruktion eines BITs zu ignorieren und einfach davon zu sprechen, dass ein Bit etwas ist, was "im Zustand 0 oder 1 sein kann". Mit dieser Definition kann man z.B. hervorragend Informatik betreiben, ohne sich um die Physik zu kümmern. Aber das führt hier zu weit - wir wollen ja zum Qubit-Modell.
Z B I T
Am Ende des letzten Abschnitts hatte uns der Große Experimentator mit einer blauen ZBIT-Box konfrontiert. Die wollen wir jetzt verstehen. Wir machen wieder allerlei Klappe-auf / Klappe-zu Experimente, berühren die Touch-Felder usw. Also los!
Als erstes wiederholen wir die für die BIT-Box. Klappe auf: Dunkel. Erst X, dann Klappe auf: Licht usw. Die Messergebnisse sind wie bei der BIT-Box. Jetzt beziehen wir das neue Touch-Feld H in die Experimente ein:
Ausgangspuntk ist immer "Klappe zu".
H und Klappe auf: Licht. Wiederholung: Klappe zu, H und Klappe auf: Dunkel. Nanu! Wiederholung: Dunkel, Wiederholung: Licht. Jetzt werden wir systematisch und wiederholen in einer Serie das Experiment 20 mal und notieren uns die Ergebnisse. Wir bekommen 12 mal Licht, 8 mal Dunkel. Wir wiederholen die Serie: 11 mal Dunkel, 9 mal Licht... Am Ende sind wir überzeugt:
H und M (Klappe auf) ergibt "zufällig" Licht oder Dunkel, im Schnitt jeweils in der Hälfte der Experimente einer Serie.
Jetzt wissen auch auch, warum der G.E. das Feld mit "H" bezeichnet hat: H wie Halbe, oder Hälfte, oder 1/2. Und warum die Box ZBIT heißt: Abkürzung für "Zufalls BIT Intelligence Tester".
Jetzt kommt uns eine weitere Idee: bisher war H berührt worden direkt nach dem Ausgangspunkt (Klappe zu). Was wäre, wenn wir vorher noch das X berühren? Machen wir also die Serien noch mal, aber in der Abfolge: Ausgangspunkt, X, H und dann M. Wir stellen fest: bis auf zufällige Abweichungen das gleiche Verhalten wie vorher, ohne X. Halb Licht, halb Dunkel.
Und was ist, wenn wir H zweimal hintereinander berühren, nachdem die Klappe geschlossen wurde? Wir bekommen, auch in Serie, immer Dunkel. Wenn wir vorher noch X berühren, immer Licht. Doppeltes Berühren von H hebt sich also auf.
Das ZBIT-Modell
Bevor wir weiter experimentieren, versuchen wir uns ein Modell zu machen in der Art wie bei der BIT-Box, quasi als Erweiterung. Wir sehen zunächst, ob das klappt, und überprüfen es dann mit verschiedenen Experimenten.
- Wir nehmen für das ZBIT-Modell 3 interen Zustände und und kennzeichen diese Zustände mit [0], [1] und - neu - [1/2]. Die Zahlen haben wieder keine Bedeutung; wir könnten die Zustände auch Alice, Charly und Bob nennen.
- Wir setzen [0] als den Startzustand
- Die bekannten Outputs sind wieder D und L, für Dunkel und Licht. Neu ist der in der Serie variable Output, den wir mit P kennzeichnen.
- Die beiden Operationen X und R hatten wir schon eingeführt, für Touch-Feld X Berühren bzw. Klappe zu.
- Neu hinzugekommen ist das Touch-Feld H. Dafür führen wir den Operator H im Modell ein.
- Die Wirkung von R, X, H auf die ZBIT-Zustände ist wie folgt:
R: [0] -> [0] und [1] -> [0] (Reset)
X: [0] -> [1] und [1] -> [0] (Switch)
H: [0] -> [1/2] und [1] -> [1/2] (Halbe-Halbe)
Das Messen des ZBIT-Zustands (Klappe auf und schauen) kürzen wir mit M ab. Messen des Zustands ergibt
M: [0] -> D und [1] -> L und [1/2] -> P
Da fehlt doch was! Wie wirken die Operationen R, X und H auf den neuen Zustand [1/2]? Wir machen dazu eine zunächst mal plausible Erweiterung der drei kleinen Tabellen und prüfen dann, ob das in sich stimmig wird.
R: [1/2] -> [0] ist plausibel, da "Klappe zu" den Ausgangszustand herstellen soll
X: [1/2] -> [1/2] ist ebenfalls plausibel, denn das Touch-Feld X vertauscht die Zustände nur. Und [1/2] ist der einzige Zustand, der beim "Vertauschen" von [1/2] mittels X entstehen könnte.
H: [1/2] -> ? Hier müssen wir kurz nachdenken. Wenn der Zustand [1/2] die Bedeutung hätte, in der Hälfte der Fälle eigentlich [0] zu sein und in der anderen Hälfte [1], dann würde H in der einen Hälfte auf [0] wirken und [1/2] ergeben, in der anderen Hälfte auf [1] und ebenfalls [1/2] ergeben. Also scheint es plausibel zu setzen:
H: [1/2] -> [1/2]
Hier noch mal gesamte Tabelle der Zustandsübergänge als Übersicht:
Zustand | Neuer Zustand bei | R X H [0] | [0] [1] [1/2] [1] | [0] [0] [1/2] [1/2] | [0] [1/2] [1/2]
Wir wollen nun einige Experimente (Algorithmen) mit diesen Operationen durchführen und damit überprüfen, ob das ZBIT-Modell mit der ZBIT-Box übereinstimmt.
R ---- X ---- H ---- M -> 1:1 liefert die ZBIT-Box in Serie
[0] -> [1] -> [1/2] -> P liefert das Modell. Das passt.
R ---- H ------- X ---- M -> 1:1 ZBIT-Box Experimente (in Serie)
[0] -> [1/2] -> [1/2] -> P ZBIT-Modell Output
Soweit stimmen Modell und die ZBIT-Box des G.E. überein.
Wir haben beim Experimentieren oben gesehen, dass sich zweimal Touch-Feld H hintereinander aufheben. Wir prüfen, ob das mit dem Modell übereinstimmt. Offenbar nicht! H auf [0] angewendet ergibt [1/2], aber auch H auf [1] angewendet ergibt [1/2]. Damit kann nicht gleichzeitig HH[0] = H[1/2] = [0] und HH[1] = H[1/2] = [1] sein. Und wie wir der Tabelle entnehmen, hatten wir sinnvollerweise auch HH[0] = HH[1] = H[1/2] = [1/2] gesetzt.
Diese Herleitung ist gleichzeitg ein schönes Beispiel dafür, wie man mit den Automaten-Symbolen rechnen kann! Vielleicht etwas ungewöhnlich, aber verständlich.
Wir müssen also offenbar unser schönes ZBIT-Modell verwerfen, da es mit der Beobachtung an der ZBIT-Box im Widerspruch steht. Ein ganz normales wissenschaftliches Vorgehen.
Können wir ein verbessertes ZBIT-Modell entwerfen, das diesen Widerspruch auflöst? Das besprechen wir im nächsten Blog. Denn auch wenn wir den "Zufalls BIT Intelligenz Test" noch nicht bestanden haben, brauchen wir erst mal eine Pause. Danach geht es dann einen großen Schritt weiter in Richtung Qubit.