KI-Modelle für den Informatik-Unterricht

 Kommentiertes Inhaltsverzeichnis

Bernhard Thomas – Ulrich Trottenberg

Interscience Akademie für Algorithmik

Sept. 2021, Jan., Apr. 2022

Das Ziel dieser Serie von KI-Beispielen für die Schule ist die Heranführung  an eine Auswahl von KI-Methoden (Maschinelles Lernen, Data Analytics). Im Vordergrund steht dabei stets ein einfacher  (Lern-) Aufgabenkontext, wie er aus dem Schulunterricht oder dem Alltagsleben bekannt ist. Auf die üblichen Cook-Book Beispiele wird bewusst verzichtet. Der Ansatz ist daher stets die Frage: Kann eine KI lernen, die vorliegende Aufgabe zu lösen? Präziser heißt das: Mit welcher Methode des maschinellen Lernens und auf welchem Wege kann ein System dies lernen. Geht das überhaupt, und wenn ja, wie gut? Wie macht das der Mensch, als Kind, als Schüler*.

Diese Übersicht gibt neben dem Titel eine kurze Erläuterung des Beispiels. Zusätzlich wird vermerkt, welche KI-Methode verwendet wird. Weiter wird angedeutet, wie das Verfahren mit einfachen Mitteln, etwa Papier-und-Farbstift, Zirkel-und-Lineal oder spielerisch nachvollzogen und die Aufgabe eigenständig variiert werden kann. Dies ist im jeweiligen Text (Story) genauer beschrieben.

Die Verfahren werden blackbox-artig den Aufgaben angemessen in ihrer Wirkung und Anwendung erklärt. Es ist nicht nötig, die  teilweise komplexe Theorie (höhere Mathematik) der Verfahren zu erklären, und auch die teilweise exotisch (mathematisch) klingenden Bezeichnungen werden weitestgehend vermieden. In dieser Übersicht sind sie lediglich als Referenz aus dem KI-Methoden-Baukasten erwähnt.

Die zugehörigen ausführlichen Texte und Programme sind als Grundlage zu verstehen. Je nach Einsatzzweck (z.B. Schule) können daraus zielgruppenspezifisch vollständige Kurse entwickelt werden. Dabei ist jeweils der Stand der Mathematik-Kompetenz der Jahrgangsstufe / Schulform zu berücksichtigen.

Als zusammenfassende Tabellen sind A.) die Titel der Themen aufgelistet und am Ende B.) eine Übersicht der der in den Artikeln verwendeten Verfahren und Varianten als Referenz zusammengestellt. Die Reihenfolge der Beispiele in der Übersicht ist ohne weitere Bedeutung.

 

 

 

 

 

 

 

 

 

 

 

 

  1. Tabelle der Themen
# Thema
01 KI lernt gerade und ungerade Zahlen zu unterscheiden
02 KI lernt Gleichungen mit 3 Unbekannten lösen (3x3 Teil 1)
03 Pizza-Bringdienst - KI lernt Vorhersagen zu machen ohne die Lösung zu kennen (3x3 Teil 2)
04 KI lernt aus Erfahrung Vorhersagen zu machen (3x3 Teil 3)
05 KI lernt PKWs zu klassifizieren (PKW Teil 1)
06 KI bestimmt eine PKW Klasseneinteilung selbstständig ohne Vorgaben (PKW Teil 2)
07 KI lernt Größer und Kleiner zu unterscheiden
08 KI lernt Obstsorten zu unterscheiden (Obst Teil 1)
09 Erweiterte Aufgaben für die intelligente Scanner-Kasse (Obst Teil 2)
10 Scanner-Kasse lernt Obstsorten zu unterscheiden ohne Vorgaben (Obst Teil 3)
11 KI-Unterstützung: Was ist wichtig?
12 KI lernt quadratische Gleichungen zu lösen
13 KI lernt die Umkehrmatrix für Gleichungen mit 3 Unbekannten (3x3 Teil 4)
14 KI lernt die Formel zur Lösung von quadratischen Gleichungen
15 KI lernt Zählen (Zählen Teil 1)
16 KI lernt Abzählen (Zählen Teil 2)
17 KI lernt Wetter-Apps zu bewerten
18 Größer/Kleiner unterscheiden lernen – KI-Varianten
19 Mein Smartes Zimmer - Chatbot lernt Anweisungen zu verstehen und auszuführen
20 NN lernt Klassifizieren (am Beispiel Obstsorten)
21 KI lernt die kleinste Zahl aus einer Reihe von Zahlen zu finden
22 Ein Robot lernt Richtungsmuster zu erkennen (directions Teil 1)
23 Escape Room: Ein Robot lernt Richtungshinweise auszuwerten (directions Teil 2)
24 Hunting Fox – Weg zum Erfolg finden

 

Stand Jan. 2022: Alle Themen mit Jupyter Notebooks, kursive Nummern noch ohne „Story“-Text

#01 KI lernt gerade und ungerade Zahlen zu unterscheiden

Aus vorgelegten 6-stelligen Zahlen soll ein ML-Verfahren lernen, Zahlen nach gerade / ungerade zu klassifizieren. Wie lernt ein Kind diese Unterscheidung? Die „intellektuelle Fähigkeit“ besteht darin, Auffälligkeiten in den Trainingszahlen zu erkennen und diese mit „gerade“ oder „ungerade“ zu verbinden.

KI-Methode: Data Analytics – Categorical Naïve Bayes
Nachvollziehbarkeit: Tabellen, Häufigkeiten auszählen, ggf. mit Excel
Eigene Variationen: Bunte Kärtchen statt Zahlen, Vielfache von 5

 

#02 KI lernt Gleichungen mit 3 Unbekannten lösen (3x3 Teil 1)

Ein Logikrätsel und ein Pizza-Bringdienst bieten 2 Beispiele typischer Textaufgaben, die jeweils zu 3 Gleichungen mit 3 Unbekannten führen. Die ML Lernaufgabe besteht darin, die Lösungen zu finden. Eine ungewöhnliche Verwendung eines einfachen künstlichen neuronalen Netzes (KNN) zur Iteration der Lösung.

KI-Methode: Machine Learning mit KNNs (Lineares Perzeptron), Backpropagation
Nachvollziehbarkeit: Rechnen mit der KNN Struktur, Ausprobieren, Übergang von Text zu Gleichungen, bekannte Lösungsmethode aus dem Unterricht.
Eigene Variationen: Weitere Textaufgaben, 2 Gleichungen mit 2 Unbekannten, einfache lineare Gleichung.

 

 

#03 Pizza-Bringdienst - KI lernt Vorhersagen zu machen ohne die Lösung zu kennen (3x3 Teil 2)

Die Textaufgabe zum Pizza-Bringdienst wird ergänzt durch die Anforderung, Vorhersagen für die nächste Woche abzuleiten. Vorgegeben sind die „Erfahrungen“ der zurückliegenden drei Tage, in Form der 3 Gleichungen. Die klassische Lernaufgabe für ein KNN (lineares Perzeptron).

KI-Methode: Machine Learning mit mehrschichtigen KNNs, Lineare Aktivierung, Backpropagation
Nachvollziehbarkeit: Rechnen mit der KNN Struktur, Ausprobieren
Eigene Variationen: Lösungsberechnung und Anwendung der Ergebnisse auf Vorhersagezeitraum

 

#04 KI lernt aus Erfahrung Vorhersagen zu machen (3x3 Teil 3)

Der Pizza-Bringdienst sammelt Daten über einen längeren Zeitraum und will daraus eine Planungsvorhersage für die nächste Woche erstellen. Variation der Aufgabe #03. Vorgegeben sind die gesammelten „Erfahrungen“  als Trainingsdaten. Planungsdaten folgen aus Anwendung des trainierten ML-Modells auf die nächsten Wochentage (Testdaten).  Die klassische Lernaufgabe für ein KNN-Modell (lineares Perzeptron).

KI-Methode: Machine Learning mit linearem Perzeptron, Backpropagation
Nachvollziehbarkeit: Rechnen mit der KNN Struktur, Ausprobieren, Papier-und-Bleistift-Algorithmus
Eigene Variationen: Spielen mit unterschiedlichen Daten-Szenarien, Aufgabe mit E-Fahrzeugen.

 

#05 KI lernt PKWs zu klassifizieren (PKW Teil 1)

Anhand von drei Kenndaten sollen PKWs als Fahrzeuge der Oberklasse, Mittelklasse, Kompaktklasse oder Kleinwagenklasse klassifiziert werden.  Mit Trainingsbeispielen wird ein Entscheidungsbaum (decision tree) trainiert, der dann für die Klassifikation neuer Fahrzeuge eingesetzt wird. Ebenfalls ein typisches Beispiel für „überwachtes Lernen“ (supervised learning).

KI-Methode: Machine Learning mit Entscheidungsbäumen, Klassifikation
Nachvollziehbarkeit: Aufmalen von Entscheidungsbäumen, Zuordnungen ausprobieren, Korrektur der Verzweigungsbedingungen.
Eigene Variationen: Andere oder mehr Kenndaten, Variation der PKW-Klassen ( 6 bzw. 3), Anwendung auf E-Fahrzeuge.

 

#06 KI bestimmt eine PKW Klasseneinteilung selbstständig ohne Vorgaben (PKW Teil 2)

Ein Fahrzeug anhand von Beispiel-PKWs in vorgegebene Fahrzeugklassen einzuordnen ist eine Sache – geeignete Fahrzeugkategorien für die Einordnung erst einmal festzulegen, ist eine andere, vielleicht schwierigere Sache. Eine “datenanalytische“ Methode der KI findet in den Daten Gruppen, die man als mögliche PKW-Klassen identifizieren kann. Ein typisches Beispiel für „unüberwachtes Lernen“ (unsupervised learning).

KI-Methode: Clustering (k-means), Zentralpunkte
Nachvollziehbarkeit: Imitieren des KI-Verfahrens, Punktdiagramm für 2 Kenndaten, Cluster per Augenmaß durch „Kreise“ abgrenzen und Mittelpunkte einzeichnen.
Eigene Variation: Verschiedene Anzahl Cluster, Gruppenbezeichungen finden, neue Fahrzeuge einzeichnen.

 

#07 KI lernt Größer und Kleiner zu unterscheiden

Lernt jedes Kind – früher oder später. Aber wie lernt es das? Und wie eine KI? Anhand von Zahlenpaaren lernt ein einfaches Neuronales Netz, welche Zahl die größere ist, und kann das danach für neue Zahlenpaare entscheiden. Einigermaßen sicher.

KI-Methode: Lineare Regression, Machine Learning mit KNN, nichtlineare Aktivierung, 2 verschiedene KNN Strukturen.
Nachvollziehbarkeit: Punktdiagramm, KNN rechnerisch auswerten. Raten der Gewichte.
Eigene Variation: KNN-Varianten vergleichen

 

#08 KI lernt Obstsorten zu unterscheiden (Obst Teil 1)

Eine vereinfachte Scanner-Kasse erfasst eine Reihe von Merkmalen bei Obststücken: Breite, Länge, Gewicht und Farbe. Sie soll zunächst lernen, Bananen und Birnen anhand von 2 Merkmalen zu unterscheiden. Das KI-Verfahren lernt anhand von Beispielen Bananen von Birnen zu „trennen“ und entscheidet dann, zu welcher Obstsorte weitere Obststücke gehören.

KI-Methode: SVM-Klassifikation, lineare Trennlinie / Korridor (SVM = „Support Vector Machine“)
Nachvollziehbarkeit: Manueller „Algorithmus“ mit Punktgrafik. Ausprobieren verschiedener gerader Trennlinien.
Eigene Variation:  Gerade Linien, gekrümmte Linien, andere 2 Obstsorten aus dem Datensatz, Preisberechnung durch Scanner-Kasse

 

#09 Erweiterte Aufgaben für die intelligente Scanner-Kasse (Obst Teil 2)

Die „intelligente“ Scanner-Kasse soll nun verschiedene 2 Obstsorten mittels bis zu vier Merkmalen klassifizieren. Welche Merkmale sind am wichtigsten für die Unterscheidung? Wie lernt die Scanner-Kasse alle 4 Obstsorten unterscheiden? Es wird komplizierter, aber im Wesentlichen verwendet sie das gleiche Verfahren wie in Teil 1.

KI-Methode: Lineare SVM-Klassifikation, paarweise und „Eine gegen den Rest“ Separierung, Entscheidungsfunktion
Nachvollziehbarkeit: Vereinfachung (Feature Reduktion), Mehrfach-Trennlinien.
Eigene Variation:  Gerade Linien, gekrümmte Linien, Diskussion der „Lern-Schwierigkeiten“

 

#10 Scanner-Kasse lernt Obstsorten zu unterscheiden ohne Vorgaben (Obst Teil 3)

Die Scanner-Kasse bekommt nur Obststücke vorgelegt ohne Angabe, um welches Obst es sich handelt. Sie lernt anhand der Merkmalsausprägungen, Obststücke zu gruppieren, z.B. in 4 Gruppen und sortiert neue Stücke (anhand der Merkmale) in die Gruppen ein. Das KI-Verfahren bildet die Gruppen nach dem Prinzip der „Ähnlichkeit“ bezogen auf die Merkmalsdaten. Aber - was ist dann was?

KI-Methode: k-Means Clustering, Confusion Matrix, Skalierung
Nachvollziehbarkeit: Grafik mit einfarbigen Punkten, nach Augenmaß umkreisen von zusammengehörigen Punkten in 4 Gruppen
Eigene Variation:  Versuche mit 2 oder 6 Gruppen, Zuordnung: welche ist (z.B.) die Bananen-Gruppe

 

#11 KI-Unterstützung: Was ist wichtig?

Möglichst viele Merkmale sind nicht unbedingt besser für Entscheidungen und machen auch die maschinellen Verfahren komplizierter. Welche Objekt-Merkmale (Features) sind ausschlagegebend für eine Klassifizierung? In Obst Teil 2 wurden zwei von vier Merkmalen durch Probieren als dominierend identifiziert. Auch hierfür kann man eine maschinelle Methode einsetzen.

KI-Methode: PCA (Hauptkomponenten-Analyse), Abbildung auf Feature-Achsen
Nachvollziehbarkeit: In Punktwolken die Richtungen der größten Ausdehnung einzeichnen, Interpretation im Merkmalsraum
Eigene Variation:  Obst-Datensatz variieren. PCA mit 2, 3 oder 4 Komponenten analysieren. Interpretation als Merkmale.

 

#12 KI lernt quadratische Gleichungen zu lösen (QGln Teil 1)

Hier wird nicht die Lösungsformel ausgerechnet, sondern ein (mehrschichtiges) soll KNN lernen, eine Lösung zu finden. Zum Training werden Zahlenpaare vorgegeben, die entstehen, wenn die Gleichung für verschiedene Werte ausprobiert wird. Mit dem Trick, Input (x) und Output (y) des KNN zu vertauschen, kann das KNN trainiert werden, eine Lösung zu berechnen.

KI-Methode: Mehrschichtiges KNN mit sigmoider Aktivierung, universelle Approximationseigenschaft von KNNs
Nachvollziehbarkeit: Zeichnen der Kurve zur Gleichung und der Umkehrung (x,y vertauschen)
Eigene Variation:  Verschiedene quadratische Gleichungen, Fälle mit 1 und 2 Lösungen.

 

#13 KI lernt die Umkehrmatrix für Gleichungen mit 3 Unbekannten (3x3 Teil 4)

Drei Gleichungen mit 3 Unbekannten kann man in der sogenannten Matrix-Form schreiben, d.h. mit einer 3x3 Matrix der Koeffizienten, und der rechten Seite als 3x1 Matrix (Vektor). Ein KNN lernt, die „Umkehrmatrix“ (Inverse) zu bestimmen, mit der man die Lösung direkt ausrechnen kann.

KI-Methode:  Lineares KNN mit „dichter“ Verknüpfung (Dense Layer), universelle Approximationseigenschaft von KNNs
Nachvollziehbarkeit: Probieren, Rechnen, Korrigieren mit Papier und Bleistift
Eigene Variation:  Besondere Matrizenformen, Vergleich mit direkten Lösungsalgorithmen aus dem Unterricht

 

#14 KI lernt die Formel zur Lösung von quadratischen Gleichungen (QGln Teil 2)

Für quadratische Gleichungen gibt es Lösungsformeln, die (a,b,c)- oder die (p,q)-Formel. Das KI-Verfahren (hier wieder ein KNN) soll aus eine Reihe von verschiedenen Gleichungen mit den Koeffizienten a,b,c und vorgegebener Lösung lernen, die Lösung von anderen Gleichungen zu bestimmen. Variante: Ein KNN soll lernen, die entsprechenden Koeffizienten der Lösungsfomel zu bestimmen.

KI-Methode: Mehrschichtiges KNN mit sigmoider Aktivierung, universelle Approximationseigenschaft von KNNs
Nachvollziehbarkeit: Beispielhafte Zuordnung von (a,b,c)-Tripeln zu Lösungen, bzw. zu den Koeffizienten der p-q-Formel
Eigene Variation:  Möglichkeiten grafischer Darstellung

 

#15 KI lernt Zählen (Zählen Teil 1)

Jedes Kind lernt Zählen, von 1 bis 10, von 10 bis Hundert, aber wie? Was kommt nach Eintausendachthundertundzwölf? Gleich zwei KI-Methoden lernen die Nachfolgerregel, eine datananalytische und ein neuronales Netz.

KI-Methode: Zweischichtiges, minimales KNN, Lineare Regression
Nachvollziehbarkeit: Wie hat man Zählen gelernt, Trainingsdaten und grafische Darstellung
Eigene Variation:  Negative Zahlen

 

#16 KI lernt Abzählen (Zählen Teil 2)

Eine andere Art des Zählens: Abzählen von Objekten, z.B. rote Legosteine in einer Box. Wie lernt man das? Für KI ist das keine so einfache Aufgabe. Der Lernprozess besteht aus zwei einfacheren Lern-Phasen, für die u.a. unterschiedliche KI-Methoden zusammen kommen.

KI-Methode: Nicht-lineare SVM + KNN, KNN mit Transfer Learning
Nachvollziehbarkeit: Imitieren der zwei Phasen mit physischen Objekten oder Zahlen
Eigene Variation:  Worte statt Legosteine

 

#17 KI lernt Wetter-Apps zu bewerten

Welche der 4 Wetter-Apps auf dem Smartphone macht die beste Vorhersage für das Wochenende? Erfahrungen über mehrere Wochen werden protokoliert und dienen als Trainingsdaten. Hier gibt es gleich mehrere KI-Methoden, die aus der Erfahrung lernen und Vorhersagen machen, welcher App man trauen sollte.

KI-Methode: Methoden im Vergleich: Naive Bayes, KNN, SVM Classifier, Decision Tree, Reinforcement
Nachvollziehbarkeit: Datenmodell verstehen, Protokolldarstellung, Auszählen für Naive Bayes
Eigene Variation:  Nachhalten der Voraussagen, Nach-Training der Modelle.

(geplant)

 

#18 Größer / Kleiner unterscheiden lernen – KI-Varianten

Anhand dieser einfachen Lernaufgabe werden neben dem nichtlinearen Perzeptron (s. #07) zwei weitere grundlegende Formen von Neuronalen Netzen erläutert: NN mit separaten Inputströmen und klassifizierende NN.

KI-Methode: Regression NN, Categorical NN, separate Inputs, Gewichte-Analyse.
Nachvollziehbarkeit: Nachrechnen der Modelle, Einfluss der Gewichte, Aufgaben-Analogie mittels Farbkärtchen.
Eigene Variation: Farbkärtchen-Lernaufgaben, Übertragung auf Obst-Klassifikation

 

#19 Mein Smartes Zimmer - Chatbot lernt Anweisungen zu verstehen und auszuführen

Ein "smartes Zimmer" (Chatbot) lernt im Dialog verstehen, ob es ein Fenster öffnen oder schließen soll und das Licht an- oder ausschalten soll.

KI-Methode: Einfacher endlicher Automat, variierender Text-Input (keine NLP Verfahren), Reinforcement.
Nachvollziehbarkeit: Datenmodell und Dialog-Ablauf verstehen
Eigene Variation: Erweiterung, anderer Konversationskontext, andere Aktionen

 

#20 Neuronales Netz lernt Klassifizieren von Obstsorten  (Obst Teil 4)

Für die Unterscheidung von Obstsorten soll ein Neuronales Netz lernen, Objekte zu klassifizieren. D.h. die Scanner-Kasse wird mit einer anderen Art von KI als in Teil 1 ausgestattet. Auch hier werden die einzelnen Obststücke durch Breite, Länge, Gewicht und Farbe erfasst, und diese Informationen werden für das Training zusammen mit der Sorte (Klasse) für das NN geeignet aufbereitet.

KI-Methode: Klassifizierendes Neuronales Netz, zwei und mehr Klassen, Wahrscheinlichkeiten
Nachvollziehbarkeit: Berechnen eines Vorwärts-Durchlaufs des NN, grafische Modellierung mit Open Roberta NN. Versuchen, aus einer Reihe von Input-Daten selbst auf die Klasse zu schließen
Eigene Variation: Im Open Roberta NN Gewichte manipulieren. Verschiedene Feature-Kombinationen.

 

#21 KI lernt die kleinste Zahl aus einer Reihe von Zahlen zu finden

Es gilt, die kleinste Zahl aus einer Reihe von z.B. 10 Zahlen zu finden. Und zwar durch Angabe der Position innerhalb der Zahlenreihe.  Kann ein Neuronales Netzt das allein aus vorgelegten Beispielen lernen? Wie würde man das aus Beispielen selbst lernen, d.h. ohne „zu wissen“, dass man die kleinste Zahl suchen soll?

KI-Methode: Klassifizierendes NN, Mehrfach-Klassen, StandardSkalierung, Softmax, one-hot Kodierung
Nachvollziehbarkeit: Ablauf eines Vorwärts-Durchlaufs des NN (ohne Rechnen). Versuchen, aus Zahlenreihen und Vorgabe einer Positionsnummer die Aufgabe zu erkennen
Eigene Variation:  Übergang von Größer/Kleiner zu „Kleinste Zahl finden“. Variation der Aufgabenstellung, z.B. größte Zahl finden, verschiedene Reihenlänge, one-hot Kodierung für Beispielklassen erstellen.

 

#22 Ein Robot lernt Richtungsmuster zu erkennen

Als Vorstufe für die Escape Room Aufgabe (#23) soll eine KI lernen einfache Muster in einem 3x3 Feld zu erkennen Z.B. die beiden Diagonalen. Zunächst werden die Gewichte (Filter) von Hand vorgegeben und modifiziert um das Lernziel zu erreichen. Im zweiten Schritt wird das NN darauf trainiert. Es soll experimentiert und erklärt werden können, warum das NN ein nicht-diagonales Muster als eine der beiden Diagonalen interpretiert.

KI-Methode: Lineares / nichtlineares Perzeptron, einfaches Convolutional NN, Filter
Nachvollziehbarkeit: Verwenden von Schablonen zum Erkennen der Diagonalen. Umsetzung in der OpenRoberta/TF-Playground Umgebung (IAIS), Setzen und modifizieren der Gewichte von Hand. Erklären der Entscheidungen. Variante: Ausschließlich Verwendung von ganzen nicht-negativen Zahlen.
Eigene Variation: Weitere Muster erkennen, 4x4 Feld

 

#23 Escape Room: Ein Robot lernt Richtungsanzeigen erkennen

Ein Robotfahrzeug soll seinen Weg aus einem „Escape Room“  finden, oder durch ein Labyrinth oder durch einen Stadtteil von New York (bildlich). Der Weg ist durch Richtungshinweise markiert. Die KI des Robots muss lernen, die Richtungszeichen zu verstehen, d.h. in die richtige Bewegung umzusetzen.

KI-Methode: Tiefes NN, einfaches Convolutional NN
Nachvollziehbarkeit: Verwenden von Schablonen zum Entdecken und Deuten von Richtungshinweisen, in Bewegungseinheiten übersetzen, kleines Vehikel bewegen je nach Lernstand
Eigene Variation: Gestörte Richtungshinweise, andere / weitere Richtungszeichen, Stoppzeichen, „von A nach B“

 

#24 Hunting Fox – Weg zum Erfolg finden

Ein simuliertes Tier (Fuchs- Robot) erkundet sein Habitat (seine Umwelt) auf der Suche nach Nahrung (Rewards). In Bau-Nähe findet sich nur wenig, aber es gibt einen weiter entfernten Flecken mit reichlich Nahrung. Wie lernt er den Weg dorthin?

KI-Methode: Reinforcement Learning, Q-Learning, Tiefes NN
Nachvollziehbarkeit: Spielerisch auf linearem oder quadratischen Spielplan
Eigene Variation: Veränderliche Rewards, zwei ergiebige Ressourcen in unterschiedlichen Richtungen, Fehlleitende Reward-Verteilung

 

 

 

  1. Tabelle der KI-Methoden (Data Analytics, Machine Learning)
Verfahren Variante Typ Verwendet in:
Entscheidungsbaum Binär Categorical #05, #17
Naive Bayes Categorical #01, #17
Support Vector Machine Linear, multi-class, ovo, ovr Categorical #08, #09
Support Vector Machine Nicht-linear, rbf kernel Categorical #16, #17
K-means Clustering Confusion matrix Categorical #06, #10
Hauptkomponenten-Analyse PCA Feature #11
Feature Regularisierung StandardScaling Feature #10, #20, #21
Encoding One-hot Feat. / Target #18, #20
Lineare Regression Regressional #07, #15
Neuronale Netze Lineares Perzeptron (LP) Regressional #02, #04
Neuronale Netze Multi-layer LP (MLP) Regressional #03, #15
Neuronale Netze Nicht-linear, multi-layer NN Regressional #07, #18
Neuronale Netze MLP, sigmoid Aktivierung Regressional #12, #13, #14
Neuronale Netze One-hot Target Categorical #18, #20
Kombiniert (Transfer Learn.) SVM+KNN, KNN+KNN Cat. / Regr. #16
(Reinforcement) Dialog #19
Neuronale Netze CNN (Convolutional NN) Categorical #23
Reinforcement Q-Learning Regr. / Cat. #24
XAI (Ansätze) Effektanalyse Input / Gewichte Categorical #22, #23

 

Anmerkungen:

  • Jupyter Notebooks, Python Libraries, Durchführung z.B. auf Google Colaboratory Umgebung (Internet / Browser)
  • NN-Modelle auf OpenRoberta mit IAIS TF Playground Integration

 

 


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:

  1. Problem Defintion: Beschreibung der Aufgabe als Text
  2. Problem-Dimensionen und Datensatzumfang (Code-Zelle)
  3. Parameter für Problem-Varianten (optional, Code)
  4. 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:
  5. Datenset-Aufteilung Tranings-/Testdaten: z.B. 70% zu 30% (Code)
  6. Categorical Naive Bayes Modell: Modell-Defintion und Training (g_u_model.fit()) mit den Trainingsdaten (Code)
  7. 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)
  8. (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)
  9. (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?

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

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

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

  1. X gibt 20% seines Vermögens an Y
  2. 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.

  1. Nach 5 Zügen hat X 109,92 Euro, Y hat 90,08 Euro
  2. Nach 10 Zügen steht es: 110,98 Euro zu 89,02 Euro
  3. Nach unendlich vielen Zügen hat X 111,11 Euro, Y hat 88,89 Euro
  4. X gewinnt
  5. Sein Gewinn ist 11,11 %, der Verlust von Y ist 11,11 %, was klar ist wegen des Nullsummen-Spiels

 

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

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

  1. Die Inzidenzzahlen werden oft mit ein, zwei Stellen hinter dem Komma angegeben, was eine Scheingenauigkeit suggeriert.
  2. 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.
  3. 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).
  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

 

  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.

 

  1. 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:

  1. Wahrscheinlichkeit ein Corona-Todesfall zu sein: 0,09 %
  2.  Wahrscheinlichkeit als Corona-Patient zu sterben: 2,64 %
  3.  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.

 

 


Was macht BitCoin eigentlich zum großen Energiefresser?

Krypto-Währungen und speziell Bitcoin sind inzwischen auch in der seriösen Finanzwelt angekommen und werden mächtig ge-hyped. Selbst große Banken und Unternehmen der Digital-Branche interessieren sich inzwischen für eigene Krypto-Währungen. Gültige Bitcoins entstehen aber nicht durch nationale Zentralbanken sondern „verteilt“. D.h. jeder kann Bitcoins „herstellen“, sofern ein bestimmtes algorithmisches Protokoll dabei beachtet wird.

Eine Anforderung des Bitcoin-Protokolls ist, dass ein sog. „Proof of Work“ nachgewiesen wird; also eigentlich, dass man sich den „Buckel krumm arbeitet“ um ein Bitcoin zu generieren - fast wie beim Gold-Schürfen. Nur müssen hierzu inzwischen riesige Computersysteme ran, um ein „mathematisches Rätsel“ zu lösen, wie es in den Medien oft vereinfachend dargestellt wird. Obwohl das Rätsel an sich mathematisch äußerst simpel ist, ist es mit der Zeit immer schwieriger geworden,  dafür eine Lösung zu finden. Und das erfordert inzwischen enorme Computer-Leistung mit dem entsprechenden Energie-Bedarf.

Worin besteht nun bei Bitcoins das viel zitierte „mathematische Rätsel“, und warum beschäftigt das  inzwischen riesige Computersysteme und verbraucht dabei offenbar Unmengen an Energie?

Das „Rätsel“ – im Bitcoin Kontext Proof of Work genannt - besteht in einer simplen Aufgabe.

Es geht im Prinzip nur darum, eine Zahl zu finden, die unterhalb einer aktuellen Schranke, Target genannt,  liegt. Die Bitcoin-Schranke verändert sich von Zeit zu Zeit nach einem ausgeklügelten Algorithmus, der unter anderem verhindert, dass weltweit zu schnell zu viele Bitcoins generiert werden. (Wer Interesse hat, kann das weiter unten nachlesen.) Wenn die Schranke  z.B. eine Zahl mit 19 Nullen hinter dem Komma ist,  muss der Proof of Work eine Zahl liefern die noch kleiner ist. Klingt einfach, ist es aber nicht! Denn das Finden der Zahl unterliegt einer vorgeschriebenen mathematischen Berechnung und kann nicht einfach „eingegeben“ werden.

Am einfachsten vergleichbar ist das mit einem Zufallszahlengenerator. Der muss so lange neue Zahlen generieren, bis eine davon kleiner als die Schranke ist. Und das kann dauern. Und viele Computer beschäftigen und viel Energie verbrauchen. Zurzeit liegt der Bitcoin-Stromverbrauch etwa zwischen dem von Schweden und der Ukraine (SZ vom 29.4.2021)

In Realität (Bitcoin-Protokoll) werden bei diesen Berechnungen 64-stellige Hexadezimal-Zahlen generiert, die gleichzeitig die Fälschungssicherheit von Transaktionen nach dem Blockchain-Konzept (sog. Block-Hashes) gewährleisten. Bei jeder Berechnung geht auch eine Zufallszahl ein, so dass jedes Mal eine andere Zahl heraus kommt, auch wenn der sonstige Input für die Berechnung gleich bleibt. Die Schranke, mit der das Ergebnis verglichen wird, ist ebenfalls eine Hexadezimal-Zahl, mit vielen Nullen am Anfang der 64 Stellen.

Das war die geniale Idee des bis heute anonym gebliebenen Satoshi Nakamoto, der das Blockchain- und Bitcoin-Konzept 2008 in einem nur 8 Seiten langen Paper veröffentlichte. Daraus stammt das geradezu bescheidene Zitat:

”We define an electronic coin as a chain of digital signatures” (S.N. 2008)

Zu Beginn der Bitcoin-Blockchain, am 03.01.2009, wurde die Schranke auf hex ‘000 000 00 ffff‘  gesetzt. Bis Ende 2009 änderte sie sich nicht. Am 30.12.2009 sank sie auf hex ‘000 000 00 d86a‘, war damit also ein stückweit kleiner geworden. Da war es noch einfach, das „mathematische Rätsel“ zu lösen. Am 12.06.2016 hatte sie bereits 17 vorlaufende Nullen, aktuell sind es 19. Bemerkenswert ist auch, dass dieses "mathematische Rätsel" an sich völlig nutzlos ist, also kein anderes Ziel hat, als hohen Computing-Aufwand zu erfordern.

Inzwischen gibt es eine Vielzahl von anderen Blockchain-Protokollen, die anders als die Bitcoin-Blockchain zur Validierung eines neuen Blocks weniger aufwändige "Proofs" oder Konsens-Verfahren vorschreiben.

In unserem ausführlichen Whitepaper „Yet Another Blockchain Paper“ finden Sie übrigens ausführliche Erklärungen, was eine Blockchain und was insbesondere Krypto-Währungen ausmacht. (Bernhard Thomas, 2016, unter IT-Rebellen.de und eine Aktualisierung 2017 hier auf ISAFA.de. )

 

Ergänzende Vertiefung:

Zum Schluss, wen es interessiert, sei der Algorithmus für die Lösung des „Rätsels“ und für die Anpassung der Schranke kurz erläutert, sowie Beispiele für Schranken aufgeführt.

Der Blockchain „ Mathe-Rätsel“ Wettlauf für Bitcoins:

  • Berechne Hash-Wert von (Hash des letzten Blocks, Neue Transaktionen, Zufallszahl)
  • Prüfe, ob Hash-Wert < Aktueller Schranke
  • Falls nicht: Neuer Versuch mit neuer Zufallszahl
  • Falls ja: Das „Rätsel ist gelöst“, der aktuelle Block ist validiert

Der Wettlauf besteht darin, dass derjenige (Computer), der das aktuelle Rätsel als erstes löst, eine „Belohnung“ in Form von Bitcoins gut geschrieben bekommt. Nur auf diesem Wege „entstehen“ neue Bitcoins. Die Höhe der Belohnung reduziert sich in vordefinierten Zeitabständen.

 

Algorithmus zur Anpassung der Schranke:

Die Schranke (das Target) wird jeweils nach 2016 neuen Blocks angepasst, und zwar so, dass es im Schnitt etwa 10 Minuten dauert, bis weltweit ein neuer Block validiert ist (s. Mathe-Rätsel Wettlauf). Das reguliert automatisch die „Ausgaberate“ neuer Bitcoins, anders als bei Zentralbanken, die ihr Geld beliebig „drucken“ können.

Aus dem Satoshi Nakamoto Paper:

“To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If they’re generated too fast, the difficulty increases.”

(Die Difficulty oder Schwierigkeit ist eine Art von Kehrwert der Schranke.)

 

Schranken

Um einen Eindruck für die Entwicklung der Schranke (Target) zu geben, hier die Werte für einige Zeitpunkte. Man beachte die Entwicklung der Anzahl vorlaufender Nullen.

03 Jan 2009, 18:15:05 00000000ffff0000000000000000000000000000000000000000000000000000
18 Dec 2009, 09:56:01 00000000ffff0000000000000000000000000000000000000000000000000000
30 Dec 2009, 06:11:04 00000000d86a0000000000000000000000000000000000000000000000000000
08 Jun 2016, 03:41:58 0000000000000000059ba0000000000000000000000000000000000000000000
01 May 2021, 21:27:02 0000000000000000000da8630000000000000000000000000000000000000000

(Aus https://learnmeabitcoin.com/technical/target)

 

Ergänzendes Informationsmaterial auf dieser Web-Seite

Neben dem ausführlichen Whitepaper gibt es auf dieser Webseite zwei einführende Präsentationen zum Thema Blockchain. Eine mit Blick auf Business Development Möglichkeiten durch Blockchain: Blockchain Technology (CommaSoft). Eine zweite mit etwas mehr technischer Tiefe: Blockchain Technology (Pallas).

 

 


Six not so easy pieces for AI

In einer Artikelserie für die weit verbreitete Zeitungsbeilage PRISMA hatte Ulrich vor einiger Zeit schon versucht, KI und die Konsequenzen allgemein verständlich darzustellen. Die Serie beginnt mit dem Beitrag "Künstliche Intelligenz I: Von Menschen für Menschen geschaffen".

Die Frage, worin die Intelligenz von KI-Systemen besteht, ob KI-Systeme selbstständige Intelligenz entwickeln können, oder man ihnen intellektuelle Fähigkeiten zusprechen kann, wird zurzeit heftiger denn je diskutiert – nicht nur in Kreisen der „Techniker“ sondern auch in den Gesellschafts- und Cognitiv-Wissenschaften.

Beginnen wir mit einigen aktuellen  Zitaten zu Intelligenz und Künstlicher Intelligenz –  drei plausible aus Millionen von möglichen Zitaten.


„Allgemeine Künstliche Intelligenz: AKI – ein System, das alle intellektuellen Fähigkeiten eines Menschen in sich vereint.“ ([KI, S. 39]

„Wenn Maschinen oder Computer kognitive oder geistige Fähigkeiten zeigen, die denen des Menschen ähneln, so nennt man das Künstliche Intelligenz. Bei diesen Fähigkeiten kann es sich z.B. um Lernen aus Erfahrung handeln oder um die Lösung von Problemen.“ [KI]

In einem Fernseh-Interview [MG] definiert Markus Gabriel erstmalig "Intelligenz" als die Fähigkeit, für ein Problem eine Lösung zu finden. Er ergänzt: das setzt voraus dass man überhaupt ein Problem hat (oder erkennt). Und zu KI, recht restriktiv: in der KI sind es die Menschen, die die Probleme definieren, nicht die KI-Systeme / Algorithmen. Folglich sind KI-Systeme - trotz des "I" im Namen - nicht intelligent.


Es geht offenbar nicht nur darum, eine Aufgabe zu bewältigen, sondern um die Fähigkeit der Lösungsfindung.

Die intellektuelle „Intelligenz“ eines KI Systems besteht  nicht (so sehr) in der Fähigkeit ein Problem zu lösen, sondern in der Fähigkeit, Lösungen für ein Problem zu finden. Das bedeutet im konkreten Fall, die Fähigkeit, die Lösung einer Aufgabe zu erlernen  – weniger, sie nur auf eine Aufgabe anzuwenden. Ein Algorithmus, der z.B. den größten gemeinsamen Teiler (ggT)  von zwei Zahlen bestimmt, löst diese Aufgabe. Er kann das. Ein Algorithmus, der lernt, wie der ggT. von zwei Zahlen bestimmt wird, hat eine ganz andere „intellektuelle“ Aufgabe. Menschenskinder lernen das spätestens als Schüler früher oder später.

Offenbar ist Erfahrung eine wesentliche Voraussetzung für die Lösungsfindung. Erfahrung kann vermittelt werden, durch Lehrer:innen, durch Beispiele (Daten) oder durch eigene, wiederholte Beobachtungen entstehen.

Sofern das System, das lernt, ein menschliches Artefakt ist (Programm, Computer, Robot) spricht man von Machine Learning -  für Lebewesen verwendet man eher den Begriff „Animal Learning and Cognition“, aber das ist ein anderes Thema.

Ohne Zweifel ist heute die Leistungsfähigkeit spezieller KI Methoden, insbesondere des Maschinellen Lernens (ML), spezialisiert für bestimmte Aufgaben der Erkennung, Analyse und Klassifizierung den vergleichbaren menschlichen Fähigkeiten weit überlegen, dank der Fortschritte in der Computer- und Algorithmen-Entwicklung. Aber das haben Technologie-Fortschritte so an sich. Einen schon atemberaubenden Einblick in die Hochleistungssysteme und algorithmischen Techniken von ML Verfahren, insbesondere mit Tiefen Neuronalen Netzen, findet man in dem kürzlich erschienen Buch [KI].

Die Lernfähigkeit als (quasi-)intellektuelle Fähigkeit künstlicher Systeme zeichnet also Systeme aus, die sich vom Zustand des Nicht-Lösen-Könnens in den des Lösen-Könnens entwickeln können. Klingt kompliziert, ist es auch – wie soll das gehen? In der KI Praxis hat man dafür, dank der enormen Rechenleistung von Spezial-Computern und der Intelligenz von ML-Wissenschaftlern, Verfahren entwickelt und verfeinert, die diese Lernfähigkeit in Form von hochdimensionalen Parameter-Anpassungen gewinnen.

Das heißt aber auch, dass hier nicht ein „KI-System“ diese Lernfähigkeit entwickelt, sondern dass diese zunächst einmal durch enorme menschliche intellektuelle Leistungen – von Mathematikern, Informatikern, SW-Ingenieuren usw. – in Algorithmen oder technischen Systemen vorbereitet wird.

Man kann zwar  „höhere“ KI-Systeme mit ML-Methoden ausstatten, die sich die algorithmischen Komponenten nach bestimmten Zielvorgaben selbst zusammenstellen, etwa der, das Lernen für eine bestimmte Problemklasse zu optimieren oder Erklärungen für bestimmte Ergebnisse zu liefern. Insofern kann man davon sprechen, dass sich die sogenannte Schwache KI (z.B. Machine Learning, Robot-Steuerung) durch Vielseitigkeit und Lernleistung in Richtung Starker KI (intellektuelle Leistungen) entwickelt. Aber auch das beruht primär auf menschlicher Intelligenz, sowohl was die Meta-Problemstellung betrifft als auch die algorithmischen Verfahren.  Das KI-System kann dabei das Ausprobieren verschiedener Strukturen und Anpassen von sog. Hyperparametern automatisieren.

(Anmerkung: Das sieht nach einem „infiniten Regress“ Problem für die Allgemeine Künstliche Intelligenz aus. Was fehlt, ist ein Prinzip der Entwicklung. Etwa ein Evolutionsprinzip (Genetische Variation, Selektion), das ja offensichtlich erfolgreich zu Animal Learning and Cognition und insbesondere zur  menschlichen Intelligenz als Maß aller Dinge geführt hat.)

In der Blog-Serie „Sechs nicht so einfache Aufgaben für KI“  haben wir der KI ein paar einfachste, anspruchslose Aufgaben vorgelegt, die jedes Kind zu bewältigen lernt. Sie sind der Verstehbarkeit halber aus der Mathematik gewählt. Also etwa das Zählen, oder gerade und ungerade Zahlen zu unterscheiden. Wir wollten daran sehen, wie es um die Lernfähigkeit bestellt ist, was man als Entwickler dazu beitragen muss, welche Qualitäten des Lernens man dabei entdecken kann und, was KI daraus lernen kann, wie Kinder diese Aufgaben – vermutlich – zu lösen lernen.

Die Blog-Serie ist auf Medium für Beck et al. GmbH, München, auf Deutsch veröffentlicht. Den Einstieg findet man in dem kurzen Einführungsblog: Sechs nicht so einfache Aufgaben für KI, oder über die Webseite von https://becketal.com unter #our_blog. Im Laufe der Zeit (2019) war die Serie ordentlich angewachsen, weshalb der Einführungsblog-Beitrag am Ende auch ein Verzeichnis aller Beiträge der Serie enthält, in der empfohlenen Lesereihenfolge und direkt bzw. untereinander verlinkt.

Noch ein Hinweis: Die Beiträge sind in Form so genannter Jupyter Notebooks (für Python) entstanden. D.h. der erzählende Text wird unterstützt durch kurze Python-basierte Code-Blöcke (unter Verwendung einschlägiger Packages wie keras / Tensorflow für Neuronale-Netze-Modelle). Mit denen können die beschriebenen Ideen bei Interesse nachgebildet werden.

Zum Abschluss noch ein älteres Zitat, nicht weniger bedeutend als die aktuellen:


"I propose to consider the question, "'Can machines think?' This should begin with definitions of the meaning of the terms 'machine' and 'think'. The definition might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous..." [AT]


[KI] G. Paaß, D. Hecker: Künstliche Intelligenz Springer 2021

[MG] Markus Gabriel: Sendung aspekte vom 12.3.2021

[AT] Alan Turing: Computing Machinery and Intelligence, Oxford University Press, 1950

 


Q-IBM - Wie man Zugang zum IBM Quanten-Computing bekommt

Die Qubit-Algorithmen dieser Blog-Serie zu verstehen und nachzuvollziehen macht mehr Spaß, wenn wir sie selber erstellen und laufen lassen können. Das geht mit IBM Quantum Experience, einer frei zugänglichen Umgebung, in der man Qubit-Circuits entwerfen und testen kann. Testen auf einem Simulator oder sogar echten IBM Quanten-Computern.

Wie kommt man da dran?

Zugang zur IBM Quantum-Computing-Umgebung

Es findet wie heute üblich, alles im Browser statt (Web-Application). Gesonderte Apps für Smartphone und Tablet gibt es für IBM Q Experience Apps (noch) nicht. Und über den Browser geht es dort nicht so richtig gut. Es wird also ein "richtiges" Gerät -  PC, Laptop, Mac oder ähnliches - empfohlen.

Im Browser gibt man ein
https://quantum-computing.ibm.com/login

Man sieht ... alles auf Englisch, natürlich! Daher ein paar Hinweise.

Beim ersten Mal muss man sich zunächst registrieren. (Später wird man direkt auf seine aktuelle Arbeitsumgebung geführt (s. Dashboard, unten)). Zum Registrieren dient der Link hinter "Create an IBM Account". Damit startet man die Registrierung. Ist erkennbar, dass der Link von einem deutschsprachigen PC aufgerufen wurde, findet der weitere Dialog auf Deutsch statt: "Bei IBM anmelden". "Sie haben noch kein Konto?" - Genau! Deshalb geht es dort weiter: Link "IBMId erstellen" (Die IBMId wird dann bei weiteren Login's gebraucht.)

Nun wird es wieder Englisch: "Sign up for an IBMId" ist die Seite, auf der E-mail, Name und Passwort und Land (Germany) eingegeben werden. Mit "Next" geht's weiter zu "Verify email", d.h. zur Überprüfung, ob die E-mail Adresse gültig ist und im rechtmäßigen Besitz des Users. Es wird dazu ein 7-stelliger Code an die eingetragene E-mail Adresse geschickt.  Also, in der Mailbox nachsehen und die 7 Zeichen in die kleine Box "Verification token" eintragen. Anschließend endlich "Create account" (Konto erstellen) anklicken. Dann erscheint - unvermeidbar - erst noch die Einwilligung zum IBM Konto Datenschutz. Mit "Proceed" bestätigen, und dann ist es schon geschafft.

Danach kann man die Kontoinformationen (E-Mail Adresse, Password) zum Login verwenden: Link-Adresse wie oben und dann auf "Bei IBM anmelden" die E-mail-Adresse eingeben und "Weiter". Wenn gewünscht, kann man vorher das Kästchen "Merken" ankreuzen. Dann noch das Passwort unter "Kennwort" eingeben. Und schon ist man drin!

Halt - nein! Beim ersten Mal muss man noch das IBM Quantum End User Agreement ankreuzen und "Accept & continue" klicken. Das ist halt so üblich, dass man die "Geschäftsbedingungen" akzeptiert. Und wie bei (kosten-)freien Diensten üblich, wird man anschließend gebeten, etwas über sich preis zu geben. "Your institution" ist ein Muss (Sternchen-Feld): hier gibt man  z.B. die Schule an oder irgendwas. Der Rest ist optional: Drop-down Auswahl über seine Vorkenntnisse mit "quantum", Freitext-Feld um anzugeben, was man mit IBM Q Experience machen will, und Auswahl-Liste, welche Informationen man zu IBM Q Experience erhalten will (per E-mail).

Dann endlich "Continue" und jetzt ist man (fast) drin. Wo drin?

Erscheinungsbild (User Interface) der IBM Quantum-Computing-Umgebung

Anfangs oder immer wieder beim Login wird man mit einem Fenster konfrontiert, das uns ein "Get started" Tutorial anbietet. Nicht schlecht, das mal durchzugehen, wenn man Zeit hat oder schon ein wenig mit dem Circuit Composer "gespielt" hat. Mit "Close" lehnen wir das Angebot ab.

Wenn man seine Zugangsdaten gespeichert hat und den gleichen Browser benutzt, wird man schon direkt auf seine aktuelle Arbeitsumgebung geführt (s. Dashboard, unten).

Anm.: Es ist natürlich alles auf Englisch, von daher erfordern die Tutorials und weitere Dokumente möglicherweise Englischkenntnisse, die über das schulische Niveau einer Mittelstufe hinausgehen.

Das User Interface öffnet sich mit einer Welcome-Seite. Neben der Begrüßung findet man dort einige Informationen über das, was man schon gemacht hat: Welche Circuits, welche Ergebnisse (results) anstehen (pending), welche zuletzt angefallen sind (Latest).

Spannend ist die Liste rechts der gerade verfügbaren "Backends". Das sind die Quanten-Computer, die weltweit zur Verfügung stehen (online). Zu jedem Eintrag gibt es Informationen darüber, wo er steht, wieviel Qubits er hat - und wieviel "Jobs" (Programmausführungen) in der Warteschlange stehen. Am Ende der Liste ist der "virtuelle" Quanten-Computer aufgeführt, der ibmq_qasm_simulator, den man aktuell mit bis zu 32 Qubits nutzen kann.

Diese Informationen sind umrahmt von einer Menüleiste mit teilweise kryptischen Symbolen. Die Menüleiste befindet sich links (s. Bild unten).

Einige Menü-Punkte des User Interfaces

Oben in der Ecke deuten drei waagerechte Striche an, dass man hiermit das Menü ausklappen kann, so dass man sehen kann, was die Symbole bedeuten. Hier einige kurz erläutert:

  • Dashboard: So heißt die Welcome Seite
  • Tools | Circuit Composer: Enthält im Kern den grafischen Circuit Composer mit den möglichen Gates und den (einstellbaren) Qubit / Mess-Bit Linien. Seit August 2020 sind hier noch eine ganze Reihe weiterer Widgets (Fensterchen) mit dargestellt.
    • Das für Messergebnisse (Measurement Probabilities) ist für die Blog-Serie interessant.
    • Statevector (Zustandsvektor) zeigt die (theoretischen) Faktoren an (als farbige Säulen), mit denen die verschiedenen Basiszustände in einer Superposition vertreten sind, so wie sie vom Qubit-Algorithmus gerade erzeugt wird. In der Blog-Serie auch als Koordinaten bezeichnet. Im Fachjargon des Quanten-Computing spricht man auch von der Amplitude.
    • Rechts gibt es noch einen Bereich für Dokumente und Tutorial-Empfehlungen. Alternativ (Tabs direkt darüber) kann man sich hier den QASM Skript-Code zur Grafik anzeigen lassen und verändern, oder die aktuelle Job-Übersicht.
    • Das ist leider ziemlich viel auf einmal und wird gegenüber der Vorversion leicht unübersichtlich für unsere Zwecke. Aber man gewöhnt sich daran und kann über den Menüpunkt View einiges "abwählen".
    • Die einzelnen Menüpunkte oben in der Leiste mit ihren Unter-Optionen muss man Zug um Zug kennenlernen. Zuviel, um das alles hier zu erklären. Es wird sicher auch deutschsprachige Tutorials dazu geben.
  • Tools | Quantum Lab: Der Bereich, in dem man Qubit-Algorithmen in Form von Python-Notebooks und mit Verwendung der Qubit-Programmbibliothek Qisqit erstellen und managen kann. Wir hatten ein Beispiel dafür im Kommentar zu Blog Q8.
  • Tools | Results: Zeigt die Übersicht der Resultate von QC-Jobs an.
  • Resources | Docs und Support: IBM Q Experience Dokumentationen, Tutorials und Zugang zu Q&A und anderen Support-Formen.

Der Circuit Composer in Kurzfassung

Ein kurzer Blick auf den Circuit Composer. Er erscheint innerhalb des User-Interfaces mit seiner Menüleiste am linken Rand, wie oben erklärt.

  • Der Circuit Composer hat eine eigene Menüleiste, waagerecht oben im Widget.
  • Im oberen Bereich (Widget) hat man die "Partitur". Die Gates und die Qubit- und Messbit-Linien. Natürlich kann man diese einstellen über Edit.
  • Darunter hat man weitere Widgets, z.B. die Measurement Probabilities, also die theoretische Vorhersage der Messergbnisse. Oder den "Zustandsvektor", der den (Superpositions-) Zustand des Qubit-Systems zeigt. Gezeigt wird der Zustand, der am Ende des Circuits resultieren würde. Alle nicht benötigten Widgets kann man "verstecken", z.B. über View.
  • Über Run Settings und Run on ... kann man den Qubit Circuit starten.
  • Die Ergebnisse findet man unter Jobs, einer von 3 Inhalten, die man in einem Widget ganz rechts darstellen kann. (Im Bild ausgeblendet.) Die anderen beiden enthalten Dokumentationen und Hinweise (Docs) und das QASM Code-Skript zum aktuellen Circuit.
  • Zwischen oberer Menüleiste und den Gates-Symbolen findet man eine typische Pfadangabe: Verzeichnis/Datei. Hier Circuits/Untitled Circuit. D.h. für den gezeigten Circuit haben wir noch keinen Namen vergeben. Das kann man mit dem Stift-Symbol ändern. Der Stift erscheint, wenn sich der Mauszeiger über den Circuit Namen befindet. Das Verzeichnis Circuits ist das Standard-Verzeichnis, in dem man alle seine gespeicherten Circuits (saved) wiederfindet.
  • Die Details und Unterpunkte findet man am besten heraus, indem man sie ausprobiert. Allerdings muss man sich mit einigen englischen Begriffen vertraut machen - was aber nicht so schwierig sein sollte, da die meisten ohnehin auch schon im deutschen Sprachgebrauch verwendet werden.

Wenn diese Zusatzinformation aus dem Kontext von Q8 heraus aufgerufen wurde: hier gehts zurück zu Q8.

 


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:

  1. 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.
  2.  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:

Codieren der 4 Zahlen mittels 2 Qubits
Amplituden der Superposition: 0.354, 0.354, 0.5, 0.707
Messergebnisse: Häufigkeiten1/8, 1/8, 1/4, 1/2 (idealisiert)

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.

Abb.: Vier Berechnungen von XOR als Qubit-Algorithmus

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.

 

Abb.: XOR Berechnungen mit Quanten-Parallelismus

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.

 


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

Von Bernhard Thomas und Ulrich Trottenberg

 

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

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

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

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

Schulwissen

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

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

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

Entdecken statt Auswendiglernen

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

Qubits oder Quanten?

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

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

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

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

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

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

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

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

Hier endet der "Quanten-Absatz".

Qubit Prinzipien

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

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

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

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

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

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

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

Spannend! Mit Qubit-Algorithmen auf echten Quantenrechnern experimentieren

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

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

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

 

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

Q1 Etwas ist anders! - Qubit-Algorithmen

Die An-Moderation.

Q2 Etwas ist anders! - Hello Qubit World

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

Q3 Vom Bit- zum Qubit-Modell

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

Q4 ZBIT – unterwegs zum Qubit-Modell

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

Q5 Ein verbessertes ZBIT-Modell

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

Q6 Zwischenspiel - ZBIT-Spielereien

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

Q7 Qubit - Ein Modell für Qubit Algorithmen

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

Q8 Fingerübungen - Einfache Qubit Algorithmen ausprobiert

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

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

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

Q10 Qubit-Algorithmen - Hinter die Kulissen geschaut

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

Q11 3-Qubit Circus

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

Q12 Ein echter Quanten-Würfel in 3 Qubits

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

Q13 Superdichte Codierung und Quanten-Kommunikation

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

Q14 Quanten-Teleportation

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

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

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

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

Q16 Was man so liest

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

QX Etwas ist anders - und es gibt noch viel mehr

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

Und hier beginnt die Q-Serie.

 

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

 

Dank

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

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

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

Kontakte

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

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


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

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

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

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

Orakel und Geheimnisse

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

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

Wie kann man diese Bit-Kette herausfinden?

Das erste Orakel

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

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

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

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

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

Das zweite Orakel

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

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

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

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

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

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

Bernstein-Vazirani-Algorithmus

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

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

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

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

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

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

Das Orakel und das Phase Kickback

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

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

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

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

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

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

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

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

Einsatz eines echten Quanten-Computers: IBMQX2

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

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

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

Hier zunächst das Ablaufprotokoll:

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

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

Die ersten beiden Algorithmen "aufgedeckt"

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

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

 

 

 

 

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

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

Wie geheim ist geheim?

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

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

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

Generieren eines zufälligen Orakels - mit Qiskit

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

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

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

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

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

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

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

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

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

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

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

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

 


Q14 Quanten-Teleportation

Die geheimnisvolle Kunst des Teleportierens kennt man - je nach Alter - aus Raumschiff Enterprise ("Beam' mich hoch, Scotty!") oder als Zauber aus Harry Potter (Disapparieren und Apparieren). Hier wie da verschwindet etwas oder jemand und taucht an anderer Stelle wieder auf. Der "3D-Druck" tut im Effekt etwas Ähnliches, nur verschwindet das Original nicht, wenn eine Kopie des Objekts an anderer Stelle "erscheint". Lediglich die (geometrischen) Daten des Original-Objekts werden an die Empfangsstelle übertragen. Quanten-Teleportation ist beides - oder beides nicht: das Original-Qubit verschwindet und taucht an anderer Stelle als neues Qubit-Objekt auf. Dazwischen wird Information übertragen.

Etwas ernsthafter: Als Quanten-Teleportation bezeichnet man die Übertragung eines Qubit-Zustands mittels klassicher Bit-Information, um ein anderes Qubit in den Zustand des Originals zu versetzen. Dabei geht der Original-Zustand verloren. Und da Qubits keine "Individualität" haben, hat man vorher und nachher das gleiche Qubit, nur an einem anderen Ort. Teleportation eben.  Das funktioniert tatsächlich auch technisch und wurde schon über viele Kilometer hinweg realisiert wie ein Blick ins Wikipedia zeigt.

Die Quanten-Teleportation ist das Gegenstück zur Quanten-Kommunikation (s. Q13):  Die Quanten-Kommunikation übermittelt zwei Bit Information mittels eines Qubit-Zustands, die Quanten-Teleportation übermittelt einen Qubit-Zustand mittels zweier Bits. Und in beidem spielt die Verschränkung eine entscheidende Rolle.

Das Teleportationsverfahren schrittweise von der Ausgangssituation her zu entwicklen, wird leicht mühselig, auch für den Leser. Daher schlagen wir dieses Mal den umgekehrten Weg ein: Wir stellen den Algorithmus vor, experimentieren damit ein wenig und liefern die Erklärung weiter unten nach, als systematische Darstellung der Zustandsabfolge.

Teleportation - der Algorithmus

Der Ablauf ist schnell erzählt: Alice möchte Bob den Zustand ihres Qubit (q0) übermitteln. Bob erzeugt dazu ein Qubit-Paar (q1, q2) mit der üblichen Verschränkung (siehe Circuit 7) und schickt das eine davon (q1) an Alice. Das andere verbleibt bei Bob.  Alice wendet auf ihre beiden Qubits (q0, q1) zwei Gates an, ein CNOT von q0 zu q1 und danach ein H-Gate auf q0.Anschließend misst sie die Zustände der beiden Qubits. Die beiden Bits aus der Messung schickt sie auf dem klassichen Übertragungsweg an Bob. Der steuert damit ein X- und ein Z-Gate, die auf den Zustand seines Qubits (q2) wirken. Als Ergebnis erhält er q2 in dem Zustand, in dem q0 zuvor war. Wie man das nachprüft, sehen wir anschließend.

Im Composer sieht die Teleportation wie folgt aus:

Dieses Composer-Bild hat drei 1-Bit Linien, für jede Qubit-Messung eine. Bisher hatten wir die Messbits von Multi-Qubit-Systemen immer auf einer "Schiene". Der Vorteil hier ist, dass wir die Messbits unabhängig voneinander zur Steuerung einsetzen können, statt über die 3-Bit Binärzahl-Werte zu steuern. Man sieht das an den bedingten X- und Z-Gates.

Die Barrieren (gestrichelte Linien) dienen hier nur zur grafischen Gliederung: Links definiert Alice den Zustand von q0, der teleportiert werden soll. Hier (0,1). Im zweiten Abschnitt erzeugt Bob ein verschränktes Qubit-Paar, wovon er q1 an Alice schickt. Im mittleren Abschnitt wendet Alice auf ihre Qubits ein CNOT und ein Hadamard-Gate an und misst das Ergebnis. Das Ergebnis von q0 wird auf das Bit c1 übertragen, das von q1 auf d1. Alice sendet diese klassichen Bits an Bob. der wendet Bit-controlled Operationen (X, Z) auf sein Qubit an. Wenn der Zustand von q1 als 1 gemessen wird, wird das X-Gate auf q2 angewendet. Wird für q0 eine 1 gemessen, wird das Z-Gate angewendet. Sind beide Messbits 1, dann wirken beide Gates.  Abschließend wird q2 gemessen. Wenn alles gut gegangen ist, müsste q2 nun im Zustand (0,1) sein.

Wir starten  den Algorithmus und bekommen als Ergebnis z.B. 110 bei einem Durchlauf. Ok, für q2 wird eine 1 gemessen. Die Logik: Wenn q2 nach Teleportation im Zustand (0,1) ist, darf eine Messung keine 0 ergeben. Mit 1024 shots bekommen wir dieses Histogramm:

Alle Messergebnisse liefern eine 1 für q2. Interessant ist auch zu bemerken, dass q0 sowohl 1 als auch 0 liefert. D.h. q0 hat seinen ursprünglichen Zustand verloren, der nur das Messergebnis 1 hatte.

Wenn Alice q0 im Zustand (1,0) teleportieren will, entfällt das X-Gate am Anfang. Das Ergebnis-Histogramm zeigt, wie zu erwarten, dann nur 3-Bit-Ketten, die links eine 0 haben. Klar!

Damit haben wir die Basiszustände teleportiert.

Teleportation allgemeiner Qubit-Zustände

Wenn wir einen beliebigen Qubit-Zustand als Superposition der Basiszustände (1,0) und (0.1) teleportieren wollen, können wir eigentlich davon ausgehen, dass, wenn diese korrekt teleportiert werden, auch ihre Kombination korrekt in q2 übertragen wird. Wir probieren das gleich mal aus.

Dabei machen wir uns die Darstellung des Messergebnisses von q2 etwas einfacher, indem wir nach der Teleportation q0 und q1 in den Standard-Anfangszustand versetzen und erneut messen. Etwas so:

Wir setzen statt X das Rotationsgate Ry mit dem Drehwinkel 30° an den Anfang von q0. Eine direkte Messung des Qubits in diesem Zustand ergibt, idealisiert, zu 75% Bit 0 und zu 25% Bit 1. Wir wollen sehen, ob nach Durchlauf des Circuits auch q2 diese Eregbnis liefert.

Mit der "Neutralisierung" von q0 und q1 am Ende des Circuits bekommen wir ein Histogram mit zwei Säulen, die sich nur im Messwert für q2 unterscheiden.

Und wir finden tatsächlich insgesamt etwa 75% der Ergebnisse mit 0 und 25% mit 1 für das linke Bit. Also genau wie erwartet!

Qubit Zustände und Messergebnisse

Wir machen das gleiche mit dem Zustand 1/√2(|0>-|1>), der entsteht, wenn wir X --- H hintereinander auf |0> anwenden. Wie erwartet, ergibt die direkte Zustandsmessung von q0 das gleiche wie die Messung von q2 nach Durchlauf der Teleportation. Scheint also unsere Vermutung zu bestätigen. Scheint! Wir wollen aber nicht Messergebnisse teleportieren, sondern Qubit-Zustände. Können wir hier aus dem Ergebnis der q2-Messung schließen, dass tatsächlich der Zustand von q0 korrekt auf q2 übertragen wurde? Nein! Ein einfacher Versuch: mit dem Zustand H|0> =1/√2(|0>+|1>) (plus!) bekommen wir die gleichen Messergebnisse. Man kann also nicht sagen, ob die q2-Messung von dem ersten oder dem zweiten Teleportationsbeispiel stammt.

An dieser Stelle müssen wir uns noch einmal klarmachen, dass man zwar immer vom Zustand eines Qubit-Systems auf das Messergebnis schließen kann, aber aus einem Messergebnis nicht  eindeutig auf den Zustand zurück schließen kann. Man sagt, die übereinstimmenden Messergebnisse sind eine notwendige Bedingung für die korrekte Teleportation, aber keine hinreichende. Wie können wir hier eine Unterscheidung herbei führen und festellen, ob die Teleportation gelungen ist?

Zwei Möglichkeiten stehen uns zur Verfügung. Erstens, die Abfolge der Zustandsänderungen dieses 3-Qubit-Systems Schritt für Schritt mittels der Formeln nachzuvollziehen und am Ende den tatsächlichen Zustand von q2 mit q0 zu vergleichen. Das "üben" wir am Ende des Blogs.

Als zweite Möglichkeit nutzen wir die grundsätzliche Umkehrbarkeit von Qubit-Operationen. Wenn wir nach der Teleportation erst noch ein Gate auf q2 anwenden, das das H-Gate umkehrt, und die Teleportation korrekt funktioniert hat, müssten wir im ersten Fall (X --- H) immer 1 als das linke Messbit bekommen, im anderen Fall 0. Im Beispiel-Fall ist H selbst ein komplementäres Gate, das wir direkt hinter der letzten Barriere eingefügt haben. (Alternativ könnte man auch Ry(3π/2) verwenden. Mal ausprobieren!) Aus diesen Messergebnissen können wir dann schließen, dass wir in q2 den Zustad |1> bzw. |0> vorliegen haben, und damit der mit H veränderte Zustand korrekt übertragen wurde. Das Umkehr-Verfahren komplementiert also das Messverfahren bei der Bestimmung von Zuständen.

Tatsächlich bekommen wir hier zu 100% die 1 für q2.

Anm.: Natürlich können auch die Basiszustände mit einem Minuszeichen versehen sein, z.B. per 180° Drehung und dabei 0 bzw. 1 als Messergebnis liefern. Dieser Faktor -1 macht aber nichts aus, denn die  beiden Zustände im Beispiel unterscheiden sich ja schon über die Messergebnisse.

Teleportieren, Klonen, Kopieren, Übertragen

Warum das doch recht aufwändige Teleportieren, um ein "anderes" Qubit in den Zustand von q0 zu bringen? Kann man den Zustand nicht einfach kopieren wie bei "gewöhnlichen" Algorithmen? Beispiel: a = 5, b=a , dann haben wir zwei Variablen mit dem Wert 5 (wie auch immer dies in einer Programmiersprache umgesetzt wird).

Kopieren bedeutet eine Kopie herstellen, d.h. das Original bleibt erhalten, die Kopie ist etwas anderes als das Original. Klonen bedeutet, das Original noch einmal herstellen. Wenn wir den Zustand eines Qubits auf ein zweites Qubit kopieren wollten, würde wir es automatische klonen, denn es gibt nichts, was zwei Qubits voneinander unterscheiden könnte als der Zustand.

Nun gibt es in der Theorie der Qubits ein Theorem, das besagt, dass man Qubits nicht klonen kann, das sog. No-Cloning-Theorem (s. Wikipedia). Das ist nicht zu schwer zu beweisen, überschreitet aber den mathematischen Rahmen, in dem wir uns hier bewegen wollen. Wir müssen also akzeptieren, dass man nicht aus dem (beliebigen, unbekannten) Zustand eines Qubits ein zweites herstellen kann, ohne z.B. das Original zu zerstören. Natürlich kann man, wenn man den Zustand eines Qubits kennt und weiß, wie er "hergestellt" wurde, ein zweites Qubit mit Hilfe von Gates so präparieren, dass es den gleichen Zustand hat. Dazu muss man aber den Zustand des Originals explizit kennen!

Man kann aber den Zustand eines Qubits übertragen. Teleportation ist eine Methode. Eine ganz einfache Methode ist das Swap-Gate: es vertauscht die Zustände von zwei Qubits in einem Circuit. Man kann das so sehen, dass der Zustand von einem Qubit auf das andere übertragen wird und umgekehrt. In herkömmlichen Algorithmen sieht ein Variablen-Swap zwischen a und b so aus: s = a, a = b, b = s (nicht etwa: a=b, b=a !). Im Effekt haben wir aber nur die Qubit-Variablen getauscht.

Eine echte Übertragungsmethode ist eine Art lokale Version der Teleportation. Lokal deshalb, weil hierbei keine Übertragung im Sinne eines Transports zwischen entfernten Orten (Alice und Bob) stattfindet. Der Composer-Circuit dazu sieht so aus:

Das Ergebnis Histogramm entspricht dem ersten oben, d.h. q2 liefert nur 1, die beiden anderen - insbesondere q0 - jeweils 0 und 1.

Statt Bit-controlled Gates wie bei der Teleportation haben wir hier ein CNOT (auch cX genannt) und ein cZ. Damit "kürzen" wir den Umweg über die Messwerte ab. Statt zu messen, ob q0 bzw. q1 eine 1 oder 0 liefern, und danach die Gates X und Z für q2 zu steuern, nehmen wir gleich die Zustände von q0 und q1, um die Gates zu steuern. Man beachte, dass dabei stillschweigend unterstellt wird, das z.B. Zustand |1> und Messung 1 äquivalent sind.

Der Unterschied zwischen Teleportation und lokaler Übertragung liegt in der "Anwendung" der Algorithmen. Bei der Teleporation werden Qubits an unterschiedlichen Orten behandelt und die Zustandsübertragung mittels klassicher Bits - und damit klassischer Übertragungsmedien - durchgeführt. Alice kann damit den Zustand eines Qubits, das sich bei ihr befindet, auf ein Qubit von Bob übertragen. Dagegen ist die lokale Übertragung - eben lokal.

Das Zustandsprotokoll

Wenn wir den Teleportationsalgorithmus schon nicht entworfen haben, wollen wir ihn wenigstens verstehen. Dazu versuchen wir die Entwicklung der Zustände des 3-Qubit Systems Schritt für Schritt anhand eines Zustandsprotokolls nachzuvollziehen. Dazu konstruieren wir uns eine Tabelle, die im Wesentlichen die 8 Koordinaten  eines 3-Qubit als Spalten hat. Jede Zeile steht für einen Schritt im Algorithmus. Der jeweilige Schritt wird in der Zeile links symbolisch dargestellt. Rechts ist noch Platz für eventuelle Erläuterungen oder Hinweise. Die Zustandskoordinaten der Qubits q2, q1 und q0 werden mit (r,s), (u,v) bzw. (x,y) benannt. Wir wollen das erste Beispiel oben nachvollziehen, beginnen also mit dem X-Gate auf q0.

(r,s)⊗(u,v)⊗(x,y) rux ruy rvx rvy sux suy svx svy Koordinaten (q2,q1,q0)
Ket- / Messbits 000 001 010 011 100 101 110 111 Kets / Messwerte (f1, d1, c1)
Dezimal 0 1 2 3 4 5 6 7 Binär-Werte
q0: X(1,0)=(0,1) 1 q1, q2 sind (1,0)
q1: H(1,0) 1/√2 1/√2 Hadamard q1 ->1/√2(1,1)
CNOT q1->q2 1/√2 1/√2
CNOT q0->q1 1/√2 1/√2
q0: H 1/2 -1/2 1/2 -1/2 Hadamard q0 ->1/√2(1,-1)
Messung (und Transfer) 010 011 100 101 Häufigkeit ca 25%
q2: If d1==1 X 1/2 -1/2 1/2 -1/2 Bedingtes X-Gate
q2: If c1==1 Z 1/2 1/2 1/2 1/2 Bedingtes Z-Gate
Messung 100 101 110 111 q2 liefert immer 1

(Die leeren Felder stehen für 0, bzw. 0 Häufigkeit bei Messungszeilen.)

Wir haben damit am Ende nicht nur die konsistenten Messergebnisse, sondern auch den separierbaren 3-Qubit Zustand (0,1)⊗(1/√2,1/√2)⊗(1/√2,1/√2) mit q2 im Zustand (0,1). Auf ähnliche Weise kann man auch die Teleportation anderer q0-Zustände entwicklen.

Im nächsten Abschnitt werden wir uns mit einem Orakel beschäftigen und einem Algorithmus, der exemplarisch für den Beschleunigungseffekt des "Quanten-Parallelismus" steht. Doch zunächst die Ergänzung der Begriffstabelle und eine Pause.

Hier geht's dann weiter - stay tuned!

Begriff englisch Begriff deutsch Bedeutung
Barrier Barriere Senkrechte, gestrichelte Linie in Composer-Circuit zur Abtrennung von Optimierungsbereichen. Hier nur als Strukturierung verwendet
Necessary condition Notwendige Bedinung In "wenn A, dann B":  B ist notwendig für A. Zwangsläufige Folge
Sufficient condition Hinreichende Bedingung In "wenn A, dann B": A ist hinreichend für B
Reversibility method Umkehr-Verfahren Methode, das Vorliegen eines Qubit-Zustands zu prüfen unter Verwendung der prinzipiellen Umkehrbarkeit von Qubit-Operationen
No-Cloning Theorem No-Cloning Theorem Generelles Prinzip, dass Qubits nicht geklont werden können
State protocol Zustandsprotokoll Schematische Darstellung der Zustandsabfolge eines Qubit-Algorithmus
Quantum parallelism Quanten-Parallelität Bei Superpositionen wirkt ein Gate auf alle Komponenten der Basis-Zustände "parallel"