GPT#9 Intelligente Obstkasse - Machine Learning mit ChatGPT
ChatGPT generiert Machine Learning Programme
Aus: KI-Stories für den Informatikunterricht NRW - „Obstsalat-1 und -2“
Aufgabe: Maschinelles Lernen einer fiktiven Obst-Scannerkasse zur Klassifikation von Obstsorten anhand zweier Merkmale: Länge und Breite des Obststücks. Die Aufgabe besteht darin, den Kern eines Python-Programms unter Verwendung von ML Libraries zu generieren. Es werden zwei Verfahrensvarianten verlangt: Eine datenanalytische (SVM - Support Vector Machine) und eine mittels eines Künstlichen Neuronalen Netze (KNN).
Kommentar:
Dialog: Der Eingangsdialog der Aufgabenstellung für zwei Obstsorten (Banane, Birne) führt das Sprachmodell dazu, das “k-nearest neighbors” Verfahren (k-NN) anzuwenden. Und das ohne explizite Anforderung und anders als im Dialog in GPT#8. Das Verfahren wird kurz erklärt, was zunächst nicht erstaunlich ist. Erstaunlich ist aber, dass das Sprachmodell das Verfahren (ohne explizite Programmierung) in einfachster Form offenbar aus dem Dialog heraus anwenden kann. Insofern ist die Herleitung ähnlich der simplen Argumentation in GPT#8.
SVM: Offenbar “kennt” ChatGPT neben k-NN auch das SVM-Verfahren und bietet einen Support Vector Classifier (SVC) als Alternative an (mit Erläuterung). Auch hier bleibt unklar, wie das Sprachmodell es schafft, “auf Basis der Beispiel-Daten” (Zitat) ein Ergebnis des SVC für das Beispiel (13, 8) korrekt herzuleiten.
Grundlage für die Entscheidung per SVC ist die sog. Entscheidungslinie (Decision Boundary, DB). Es wird deshalb im Weiteren versucht herauszufinden, ob das Sprachmodell die DB für diesen Fall “kennt”. Das ist offensichtlich nicht der Fall - das Sprachmodell “beschreibt”, wie eine DB im linearen Fall bestimmt werden kann und wie sie aussehen wird. Die Koeffizienten (Achsenabschnitt und Steigung) kennt der Chat offenbar nicht. Richtig ist, dass man die erst kennt, wenn das SVC-Modell mit den Vorgabe-Daten trainiert ist (fit).
Die Aufforderung, dies zu tun, wird erwartungsgemäß mit einem Python-Programm ("Python" und "Programm" waren nicht vorgegeben, sind aber naheliegend für das Sprachmodell). Es wird sklearn als ML-Paket verwendet.
Zur Überprüfung wurde das Programm in Google Colab ausgeführt. Das Programm ist korrekt und umfasst auch die Ausgabe der angepassten DB-Koeffizienten in Form der Geradengleichung.
Ergänzend wird ChatGPT aufgefordert, die Daten und die DB grafisch darzustellen, was wie erwartet in Form eines Programm-Vorschlags geschieht. Die Ausführung in Google Colab stößt auf einen Fehler, der aber immerhin durch eine kleine Korrektur in der Zeile Z = model.predict zu beheben ist. Die Grafik ist am Ende des Dialogs eingefügt.
KNN: Hier haben wir die Aufforderung nach einem Programm gestellt, dass die Klassifikation von 4 Obstsorten anhand der beiden Merkmale lernen soll. “Neuronales Netz” als Methode ist nicht explizit erwähnt, dafür aber mit ‘keras’ eine sehr verbreitete ML Bibliothek zur Modellierung von NN-Systemen benannt.
Die Antwort ist erwartungsgemäß ein Programm für ein NN-Model, das zudem näher erklärt wird.
Die Datenaufbereitung wird nicht näher beschrieben, insbesondere die für das Modell unterstellte, erforderliche one-hot-Kodierung der Klassen-Labels - ist aber auch zunächst nicht nachgefragt worden. Nachträglich gestellt, gibt ChatGPT die richtige Hinweise.
Dies ist keine Überraschung, da der Code und die Erläuterungen tausendfach in Beispielen und Tutorials im Internet zu finden sind.
Anm.: Wegen des Umfangs sei auf eine Übersetzung hier verzichtet.
Task & Prompt: Bernhard Thomas
Generator: ChatGPT
Translator: n/a
Editing: n/a (ChatGPT Originaltext)
Authoring: Bernhard Thomas
Credits: n/a
Dialog und SVM
Assume bananas and pears are characterized by their length and width in cm.
Okay, got it. Bananas and pears can be characterized by their length and width in centimeters.
If length is 20 and width is 5, what is it?
It is not possible to determine what the object is based solely on its length and width measurements of 20 cm and 5 cm. Further information is needed to identify the object.
This list characterises bananas (20,4),(17,5),(18,3.5),(15,5) and this list characterizes pears (10,6),(8.5,5),(11,8),(9.5,7). If a fruit is (15, 4.5) is a banana or a pear?
To determine whether a fruit with length 15 cm and width 4.5 cm is a banana or a pear, you could use a machine learning algorithm such as k-nearest neighbors (k-NN) to compare the given measurements with the previously observed banana and pear measurements. The k-NN algorithm would identify the k nearest fruits in the training data to the given measurements, and predict the class (banana or pear) based on the majority class of the nearest neighbors.
Using the sample data, a k-NN algorithm with k=1 would predict the fruit with length 15 cm and width 4.5 cm to be a banana, since the nearest neighbor (20, 4) is a banana.
What is (13, 8) banana or pear?
Using the same method as before, a k-NN algorithm with k=1 would predict the fruit with length 13 cm and width 8 cm to be a pear, since the nearest neighbor (11, 8) is a pear. However, this answer could change depending on the value of k used in the k-NN algorithm.
Actually, (13, 8) is a banana
Okay, if you say so. In that case, the fruit with length 13 cm and width 8 cm would be considered a banana.
Instead of k-NN use a SVC
Sure, a Support Vector Machine (SVM) classifier, such as a Support Vector Classification (SVC) algorithm, could also be used to predict whether a fruit with length 13 cm and width 8 cm is a banana or a pear.
The SVC algorithm creates a decision boundary to separate the classes in the feature space, in this case the length and width of the fruit. The SVC algorithm tries to find the optimal hyperplane that maximally separates the two classes, bananas and pears, in the feature space. Points on different sides of the hyperplane are classified as belonging to different classes.
Given the sample data, an SVC algorithm would fit the data and create a decision boundary in the feature space. The fruit with length 13 cm and width 8 cm would then be classified based on which side of the decision boundary it lies on, either being predicted as a banana or a pear.
So what is (13, 8)?
Based on the sample data, a Support Vector Classification (SVC) algorithm would predict the fruit with length 13 cm and width 8 cm to be a banana.
What is the decision boundary for this sample set?
The decision boundary is a hyperplane in the feature space that separates the two classes, bananas and pears, into distinct regions. The hyperplane is defined by a linear equation, and the coefficients of the equation are determined by the Support Vector Classification (SVC) algorithm during the training phase.
In this case, the feature space is two-dimensional, with one axis representing the length of the fruit and the other axis representing the width. The SVC algorithm would fit a hyperplane to the data, such that the bananas and pears are separated as much as possible.
It is not possible to determine the exact equation of the decision boundary without additional information, such as the specific SVC algorithm used and the values of the parameters for that algorithm, as well as the training data.
Training data are the lists above, use linear kernel and C=1
Okay, given the sample data and the specified SVC algorithm parameters (linear kernel and C=1), we can fit the SVC model to the data and visualize the decision boundary.
With a linear kernel, the decision boundary will be a straight line in the feature space that separates the two classes, bananas and pears. The value of C determines the trade-off between a smooth decision boundary and classifying all the training points correctly. A smaller value of C will result in a smoother decision boundary, while a larger value of C will aim to classify all the training points correctly, potentially resulting in a more complex decision boundary.
To obtain the equation of the decision boundary, we would need to fit the SVC model to the sample data and extract the coefficients of the linear equation that defines the hyperplane. Without more information, it is not possible to determine the exact equation of the decision boundary.
So please fit the SVC model to the data given above and show the equation of the decision boundary
To fit the SVC model with a linear kernel and C=1 to the given training data, we can use Python's scikit-learn library. Here's an example code snippet to fit the model and extract the coefficients of the decision boundary:
Running this code will output the equation of the decision boundary, which is a linear equation in two variables (x and y) that represents the separating hyperplane in the feature space:
Note that the coefficients of the decision boundary are specific to the training data and the parameters used in the SVC model (linear kernel and C=1). If the training data or the parameters were to change, the coefficients and the decision boundary would also change.
Make a plot of the data and the decision boundary
Sure, here's an example code snippet that uses matplotlib to create a scatter plot of the training data and the decision boundary obtained from the SVC model:
This code creates a scatter plot of the training data, with bananas plotted as blue dots and pears plotted as orange dots. It then creates a contour plot of the decision boundary obtained from the SVC model, which is a straight line in this case. The plot also includes labels, a title, and a legend.
The resulting plot should show the distribution of bananas and pears in the feature space, with the decision boundary separating the two classes.
Die Grafik
Mehrschichtiges Neuronales Netz
Write a python code for a classifier for four classes and two features using keras
Here is an example of a Python code using Keras to create a classifier for four classes and two features
In this example, the input layer has two neurons (one for each feature), and the output layer has four neurons (one for each class). The hidden layer has 8 neurons and uses the ReLU activation function. The output layer uses the softmax activation function, which is commonly used for multiclass classification problems. The model is then compiled using the categorical_crossentropy loss function and the Adam optimizer. Finally, the model is trained on the training data using the fit() method, and evaluated on the test data using the evaluate() method.
Note that the X_train, y_train, X_test, y_test are the training and test dataset and should be provided before running the code. Also, this is just an example, you may want to adjust the number of neurons, layers, epochs and batch size based on your dataset and problem.
What are the data format requirements for this model?
The data format requirements for this model depend on the input data shape and the data type of the features and labels.
Assuming the input data is in the form of a numpy array, the input data (X) should have a shape of (n_samples, n_features), where n_samples is the number of samples (rows) and n_features is the number of features (columns). In this case, since we have two features, each row of X should contain two values.
The labels (y) should also be a numpy array, with a shape of (n_samples, n_classes), where n_classes is the number of classes in the classification problem (in this case, 4). Each row of y should be a one-hot encoded vector indicating the class label for that sample. For example, if a sample belongs to class 2, the corresponding row of y should be [0, 0, 1, 0].
Additionally, the input data and labels should be of the appropriate data type for the model. In this case, the input data should be a float32 data type, and the labels should be integers or categorical data type.
It's also important to note that the input data and labels should be properly preprocessed before feeding into the model. This may include tasks such as normalization, scaling, and encoding of categorical variables.
07.02.2023
bernhard.thomas@interscience.de
Naive Bayes Modell löst das Even-Odd Learning Problem
KI im Informatikunterricht
Dieser Beitrag kann als Grundlage für die Einführung des Themas „Künstliche Intelligenz“ im Schulunterricht eingesetzt werden. Er illustriert „Maschinelles Lernen“ anhand einer für die Schüler* einfach verständlichen Aufgabe mittels einer Data Analytics Methode: Naive-Bayes. Die Aufgabe kann mit „Papier und Bleistift“ durchgeführt werden. Die Voraussetzungen beschränken sich auf Erstellen von Tabellen, Auszählen von Häufigkeiten und Berechnung von relativen Häufigkeiten.
Die Blogserie „Six not so easy pieces for AI” (Sechs nicht so einfache Aufgaben für AI) begann in 2019 mit der einfachen Fragestellung, ob AI in der Lage ist, eine der einfachsten „intellektuellen“ Leistungen zu erbringen, nämlich zu lernen, ob eine Zahl gerade oder ungerade ist. (Siehe hier.)
Abstrakte Fragestellung - Allgemeines Schema
Hier bedeuten die einzelnen Attribute des Input-Vektors die Dezimalstellen einer ganzen Zahl, beginnend bei den „Einern“ ganz rechts. Der Wertebereich (Kategorien-Labels) ist jeweils 0,1,…,9. Die Response im Supervised Learning gibt jeweils an, ob die Zahl gerade oder ungerade ist. Die entsprechenden Klassen sind 0 (für Gerade) und 1 (für Ungerade). Im trainierten Zustand gibt R die „Vorhersage“ für eine Testzahl.
Es ist wichtig zu bedenken, dass ein "lernendes KI-System" hier kein Konzept von Zahlen, Dezimalstellen und deren Bedeutung innerhalb einer Zahl (z.B. Einer, Zehner etc.) hat. Die Inputs sind für das System nichts weiter als eine Liste von Ziffern.
Das Training-Szenario
Als Training-Daten wird eine Anzahl von ganzen positiven Zahlen in Form einer Liste der einzelnen Dezimalstellen samt der richtigen Klassifikation in gerade / ungerade vorgegeben.
Als Testdaten werden einzelne Zahlen oder ein Set von Zahlen in dieser Form ohne Klassifikation verwendet. Diese sind nicht in den „Lernvorgang“ eingegangen. Das Ergebnis (Prediction) kann mit dem wahren Wert verglichen werden.
Die ML Methode
Als ML-Methode verwenden wir hier, anders als in der erwähnten Blog-Serie, ein Naive-Bayes Verfahren. Kurz erläutert, wertet das NB-Verfahren die Trainingsdaten aus und bestimmt – mittels der Bayes-Formel - die bedingte Wahrscheinlichkeit dafür, dass, gegeben eine m-stellige Zahl (Input-Vektor), das Ergebnis R=0 ("gerade") ist. Entsprechend für R=1 ("ungerade"):
P(R=0|a0 a1 … am)
Der Input-Vektor ist einfach die Ziffernfolge der Zahl, wobei für die Dezimalstellen untereinander keine Abhängigkeit besteht. (Grundannahme für die Gültigkeit von „Naive“ Bayes.)
Im „gelernten“ Zustand kann das Modell (auch Classifier genannt) für unbekannte Zahlen b = b0 b1 … bm entscheiden, ob diese gerade oder ungerade ist, anhand der berechneten Wahrscheinlichkeiten P(R=0|b) und P(R=1|b) – je nachdem, welche der Wahrscheinlichkeiten größer ist.
(In der Regel reichen wenige Zahlen für das Training aus, sofern man die sog. Glättung im Classifier „ausschaltet“. Die Glättung kompensiert Fälle, in denen eventuell einzelne Werte in den Input-Daten nicht vorkommen (missing data), und sich damit Schwierigkeiten in der Auswertung ergeben können.)
Für unser gerade-ungerade-Lernen Problem zeigt sich, dass die o.a. Wahrscheinlichkeiten P entweder 0.0 oder 1.0 sind. Im Sinne der Blogserie haben wir es hier also mit „starkem Lernen“ zu tun.
Ist das Lernverfahren auch „robust“? In der Blogserie hatten wir damit ein Lernverfahren gekennzeichnet, das ein gewisses Maß an Fehlern in den Trainingsdaten vertragen kann und trotzdem „richtig“ lernt. Und dabei auch die Fehler „richtigstellt“ (im Code-Beispiel: 5% Zufallsstörung)
Da die Input-Werte ganzzahlig (Kategorien) sind (0,..9) und die Response-Klassen ebenfalls (0,1), setzen wir hier die Variante CategoricalNB() aus der scikit-learn Toolbox an.
Outline des Algorithmus „Gerade/Ungerade Lernen“
Als Programm liegt dieses Beispiel als ein Jupyter Notebook vor, ablauffähig und mit kleinen Zwischentexte zur Erläuterung. Wegen Problemen bei der Kompatibilität der Dokumentenformate liegt das Notebook als html-Datei hier: NB_even-odd_problem_notebook
Der übliche, grobe Ablauf ist wie folgt:
- Problem Defintion: Beschreibung der Aufgabe als Text
- Problem-Dimensionen und Datensatzumfang (Code-Zelle)
- Parameter für Problem-Varianten (optional, Code)
- Generierung des Datensets: (Code-Zellen) Inputzahlen per Zufallsgenerator, dargestellt als Liste von Dezimalziffern je Zeile, davon N Zeilen (Matrix-Struktur Nx6). Zugehörige Klassifikation (R-Werte) als Liste von 0 und 1 für jede Matrix-Zeile (Zahl). Beispiel:
- Datenset-Aufteilung Tranings-/Testdaten: z.B. 70% zu 30% (Code)
- Categorical Naive Bayes Modell: Modell-Defintion und Training (g_u_model.fit()) mit den Trainingsdaten (Code)
- Ergebnisse: 7.1Test-Beispiele, 7.2 Genauigkeit der Klassifikation durch das Modell für Trainings- und Testdaten, 7.3 „Innere“ Daten des trainierten Modells (s. Code-Zellen)
- (Optional) Aufgaben-Varianten: 8.1 Verfälschen der Klassifikationen in den Trainingsdaten zur einem kleinen Prozentsatz per Zufall. 8.2 Probieren, Teilbarkeit durch 5 zu lernen. (Code Zellen)
- (Optional) Experimentieren: Teilbarkeit durch 3, 4 o.ä. Warum funktioniert Naiv-Bayes hier nicht?
Links zu NaiveBayes Methoden
https://scikit-learn.org/stable/modules/naive_bayes.html
https://scikit-learn.org/stable/modules/generated/sklearn.naive_bayes.CategoricalNB.html
https://www.analyticsvidhya.com/blog/2017/09/naive-bayes-explained/
Q16 Quanten und Qubits - Was man so liest
Von Bernhard Thomas und Ulrich Trottenberg
Quanten-Computing wird in den Medien, aber auch in Vorträgen und in der Fachliteratur mit einer Reihe von Aussagen charakterisiert, die als Sprachkonstrukte ziemlich exotisch klingen - nach einer anderen Welt, in der logisch Unmögliches möglich scheint. Wir wollen uns einige dieser Sprachfiguren ansehen und überlegen, was dahinter steckt.
Unsere bisherigen Blog-Abschnitte über Qubit-Algorithmen sollten ausreichen, hier ein klares Verständnis zu schaffen. Hier die Übersicht über die Aussagen.
"Quanten können 0 und 1 gleichzeitig sein"
"Mit n Qubits kann man 2**n Zahlen gleichzeitig darstellen"
"Für N Zahlen benötigt ein Quanten-Computer nur log(N) Qubits"
"Ein Quanten-Computer kann mehrere Berechnungen gleichzeitig durchführen (Quanten-Parallelismus)"
"Was auf herkömmlichen Rechner Jahre dauert, kann ein Quanten-Rechner in Sekunden erledigen (Exponentielle Beschleunigung)"
"Quanten-Rechner werden herkömmlichen Rechnern überlegen sein (Quanten-Supremacy)"
"Jedes zusätzlich Qubit verdoppelt die Leistungsfähigkeit des Systems"
"Quanten können 0 und 1 gleichzeitig sein"
Dieser Satz und Abwandlungen davon ziehen sich durch die Quanten-Computing-Literatur wie ein Mantra des QC. Auch wenn er gelegentlich nur als Metapher gesehen wird, suggeriert dieser Satz in der öffentlichen Diskussion eine mystische Eigenschaft der Quanten, nicht zuletzt illustriert durch das Bild von Schrödingers Katze, die "gleichzeitig tot und lebendig" ist.
Damit werden auch die informatischen Gegenstücke der Bits, die Qubits, charakterisiert. Im Gegensatz zu Bits, die nur "0 oder 1" sein können, können Qubits "0 und 1 gleichzeitig" sein.
Wie könnten wir das feststellen? Wir wissen, dass die Messung eines Qubits entweder 0 oder 1 ergeben kann, aber nicht beides. Wenn wir mehrfach messen, bekommen wir manchmal eine 0, manchmal eine 1 als Ergebnis, aber nie "gleichzeitig". Was kann also gemeint sein - wenn es überhaupt einen Sinn ergibt.
Es gibt Varianten dieser "Gleichzeitig"-Sprachfigur, die etwas tiefergehend klingen: "Quanten können verschiedene Zustände gleichzeitig einnehmen". Wir wissen, dass man Zustände von Systemen in Form von mathematisch eindeutigen Ausdrücken beschreiben kann - so auch Qubits und Qubit-Systeme. Ausgehend von einem Anfangszustand sahen wir, wie mittels Qubit-Operationen (oder Gates) ein Qubit-Zustand in einen nächsten überführt werden kann. Zu jedem Zeitpunkt ist der Zustand des Qubits daher eindeutig festgelegt. Wenn wir nicht unsere normale zweiwertige Logik (2 Wahrheitswerte: wahr, falsch - oder 0, 1) in Frage stellen, kann ein Qubit nicht zwei verschiedene Zustände gleichzeitig haben. Eine Zahl, ein mathematischer Ausdruck, der einben Zustand beschreibt, kann nicht gleichzeitig 0 und 1 sein: z = 0 = 1?
Manchmal findet man Texte, in denen das "Gleichzeitige" durch die "Superpostion" ergänzt wird: "Quanten können in einer Superosition von 0 und 1 gleichzeitig sein". Wir wissen, was eine Superpostion ist. Z.B. ist 1/√2 (|0>+|1>), die Hadamard-Operation auf den Basiszustand |0>, eine Superpostion (oder mathematisch: Linearkombination) der Qubit-Zustände |0> und |1>. Wir haben Qubit-Zustände meist in Form von x-y-Koordinaten eines Punktes auf dem Einheitskreis beschrieben - im Beispiel also (1/√2,1/√2). Somit können wir korrekt formulieren: Ein Qubitzustand hat zwei Koordinaten. Aber was heißt dann "gleichzeitig"? Wenn jemand in Ingolstadt ist, befindet er sich z.B. auf der Strecke von München nach Nürnberg - aber ist er (möglicherweise) in München und Nürnberg "gleichzeitig"?
Wenn auch die Redewendung "... kann 0 und 1 gleichzeitig sein" etwas Unsinniges suggeriert, können wir sie als solche akzeptieren, wenn man sie auf die Möglichkeit einer Superposition von zwei (Basis-)Zuständen eines Qubits zurückführt. Darin unterscheiden sich Qubits und Bits tatsächlich.
Und während ein Bit nur einen der beiden Zustände 0 oder 1 repräsentieren kann (siehe BIT-Box in Q3), kann ein Qubit einen Zustand aus einer unendlichen Menge von Superpositionszuständen annehmen. Wobei wir das "unendlich" im Sinne aller Punkte auf dem Einheitskreis verstehen, ohne zu fragen, ob wirklich unendlich viele Superpositionen realisierbar sind (technisch und quantenmechanisch).
Eine elegante und gleichzeitig korrekte, einfache Erklärung finden wir im Glossar der IBM (Übersetzung DeepL):
Ein Qubit (ausgesprochen "kju-bit" und kurz für Quantenbit) ist der physikalische Träger der Quanteninformation. Es ist die Quantenversion eines Bits, und sein Quantenzustand kann Werte von |0> , |1> oder die Linearkombination von beiden annehmen, was ein Phänomen ist, das als Superposition bekannt ist.
Mehr ist eigentlich nicht zu sagen.
"Mit n Qubits kann man 2**n Zahlen gleichzeitig darstellen"
Mit n Bits kann man zwar auch 2**n verschiedene Zahlen darstellen - gemeint sind Binärzahlen in Form von Bitketten - aber immer nur eine zu einem Zeitpunkt, z.B. im Speicher eines klassischen Computers.
Diese Aussage zusammen mit dem "Quantenparallelismus" (s.u.) soll die überragende Leistungsfähigkeit von Quanten-Computern deutlich machen. Man liest auch: "Mit jedem weiteren Qubit verdoppelt sich die Kapazität" und "Schon 300 Qubits können mehr Werte speichern, als das bekannte Universum Teilchen enthält".
Nun ja, wie soll man das verstehen? Zunächst zu den beiden letzten Versionen des "Kapazitätssatzes": Auch mit jedem weiteren Bit verdoppeln sich die möglichen Werte, die man speichern - und wieder lesen - kann. Immer einer zu einer Zeit (Schreib-Lese-Zyklus). Und mit 300 Bits kann man mehr als alle Teilchen des bekannten Universums abzählen, oder je eine Zahl zu einem Zeitpunkt im Bereich 0 bis 2**300-1 speichern. Bei Qubits liegt das Geheimnis offenbar wieder im "gleichzeitig". Wieder nur eine Metapher?
Ein System von n Qubits, z.B. n=3, befindet sich zu einem Zeitpunkt in einem Zustand (von prinzipiell unendlich vielen), der eine Linearkombination (Superposition) von nunmehr 2**n Basiszuständen ist, also 8 bei n=3. In der ket-Schreibweise tritt jede n-lange Bitkette als ein Basiszustand auf, bei n=3 also |000>, |001>, |010>, |011>, |100>, |101>, |110>, |111>. Bei n = 300 sind es halt ......
Denken wir an Koordinatensysteme, wie z.B. in Q11, dann haben wir ein 8-dimensionales Koordinatensystem und jeder 3-Qubit-Zustand wird durch 8 Koordinaten beschrieben. "Gleichzeitig" - für einen Punkt braucht man 8 Koordinaten "gleichzeitig".
Kann man in einer Superposition von 2**n Basiszuständen das gleichzeitige Speichern von 2**n Zahlen sehen? Nehmen wir eine gleichmäßige (uniforme) Superposition, d.h. alle Basiszustände kommen mit dem gleichen Koeffizienten vor. Bei n=3 also mit 1/√8.
Speichern nützt nur dann etwas, wenn man mit dem Gespeicherten etwas anfangen kann, z.B. weiter verarbeiten mittels Qubit-Operationen oder Lesen, d.h. Messen. Beim Weiterverabeiten zu einem neuen Zustand können tatsächlich alle Komponenten der Linearkombination in einer Operation berücksichtigt werden (Quantenparallelismus, s.u.). Beim Messen (gegen die Basiszustände) erhält man eine Häufigkeitsverteilung über alle Bitketten, die als Basiszustände in der aktuellen Superposition vertreten sind. Sind einige nicht vertreten, tauschen sie, bis auf Quantenfehler, auch nicht im Messergebnis auf.
Aber was machen wir damit? Welche Information ziehen wir daraus? Dass 2**n Bitketten beim Messen auftreten können, wussten wir schon vorher. Wir "lesen" also nichts Neues. Wenn wir 2**300 Teilchen mit unterschiedlichen Bitketten versehen wollten, konnten wir das auch schon ohne Quanten-Computer (QC).
Wo liegt also die Information, die wir durch die Quanten-Berechnung gewonnen haben? Wohl in der gemessenen Häufigkeitsverteilung:
- Wir schauen nur auf "vorhanden" und "nicht vorhanden" von gemessenen Bitketten. Eine häufige Form der Interpretation von QC-Ergebnissen, z.B. beim Herausfinden eines Orakels, wie im Bernstein-Vazirani Problem oder dem von Deutsch-Josza. Man kann sich das so vorstellen: Der Qubit-Algorithmus "rechnet" mit den 2**n Basiszuständen des n-Qubit Systems, der Ergebnis-Zustand enthält aber in nur einen Basiszustand, der dann bei der Messung eine ziemlich eindeutige Bitkette liefert. Eine solche Methode ist auch die sogenannte Amplituden-Verstärkung (amplitude amplification). Zum Auffinden einer bestimmten Bitkette beginnt man mit einer uniformen Superposition und verändert diesen Zustand Schritt für Schritt so, dass die Amplitude des Basiszustands mit der gesuchten Bitkette zunehmend "größer" wird. Die Iteration wird beendet, wenn man nahe genug an der gesuchten Bitkette ist, d.h. wenn beim Messen diese Bitkette eine überragende Wahrscheinlichkeit erreicht. Das Verfahren wird auch Grover-Iteration genannt.
- Uns interessiert ein "numerisches" Ergebnis, z.B. eine Zahl oder eine Reihe von Zahlen (Vektor), die sich bei der Messung am Ende der Rechnung als Häufigkeiten bestimmter Bitketten ergeben. Als "numerisches" Ergebnis nimmt man dann die Liste dieser Häufigkeiten. Hier stoßen wir aber auf verschiedene Probleme. Eines davon ist, dass ein echter QC die Häufigkeiten nicht exakt misst. Um halbwegs brauchbare Werte abzuleiten, müssen wir das QC Programm wiederholt durchlaufen lassen. Wie oft? Für n=3 kann man das ja einmal ausprobieren mit dem IBM QC. Wie oft bei n=50 oder n=300?
"Für N Zahlen benötigt ein Quanten-Computer nur log(N) Qubits"
Dies ist eine Variante der vorigen Aussage und besagt: "Während man auf herkömmlichen Computern für N Zahlen auch N Speicherplätze benötigt, braucht ein Quanten-Computer nur log(N) Qubits". Man hat also, umgekehrt gesehen, einen exponentiellen Effekt. Und damit ist ein Quanten-Computer exponentiell leistungsfähiger als ein herkömmlicher. Wie auch immer das gemeint ist, es läuft darauf hinaus, dass man eine Überlagerung der N Basiszustände eines "log(N) großen" Qubit-Systems herstellt, bei der die Koeffizienten (auch Amplituden genannt) gerade die gewünschten N Zahlen sind. Wenn man also weiß, wie, kann man einen solchen Superpositionszustand als "Input" herstellen, und einen Qubit-Algorithmus damit weiterrechnen lassen. Das ist das sog. Amplituden-Verfahren oder auch Amplituden Encoding.
Aber halt! Die N Amplituden müssen ja in der Summe der Quadrate 1 ergeben. Schränkt das nicht die freie Wählbarkeit der N Zahlen ein? Nicht wirklich - man muss nur vorher jede Zahl durch die Summe aller Quadrate teilen, genauer, durch die Quadratwurzel dieser Summe. Damit kann man dann "Quanten-Rechnen". Allerdings tritt bei der Ergebnis-Festellung wieder das Problem aus 2. auf.
Um die N Zahlen als Input verwenden zu können, muss man zu Beginn des Qubit-Algorithmus geeignete Qubit-Operationen (Gates) ausführen, so dass sie in einer Superposition zu Koeffizienten von Basiszuständen werden. Das kann trotz "Quantenparallelität" aufwendig sein. Hier ein Beispiel:
Angenommen, wir wollen die 4 Zahlen 1.0, 1.0, √2 = 1.414, 2.0 als Input in Form von Amplituden für ein 2-Qubit-System bereitstellen (N=4, n=2). Die Summe der Quandrate ist 1.0+1.0+2.0+4.0 = 8.0. Die Wurzel daraus ist √8. Dadurch müssen wir die 4 Zahlen teilen, damit diese eine gültige 2-Qubit Superposition ermöglichen: 1/√8, 1/√8, 1/√4, 1/√2. Es ist damit z.B. der Zustand 1/√8 |00> + 1/√8 |01> + 1/√4 |10> + 1/√2 |11> durch einen Qubit-Circuit herstellbar. Wie geht das? Hier ist eine Lösung:
Das "Fine-Tuning" der Amplituden erfolgt hier mittels Drehungen (Ry). Der resultierende Zustand ist verschränkt, d.h. er kann nicht als Kombination der einzelnen Qubits hergestellt werden. Das kann man nach der Methode in Q9 nachprüfen. (Ergebnis eines Simulatorlaufs mit 1024 shots.)
"Ein Quanten-Computer kann mehrere Berechnungen gleichzeitig durchführen"
Diese Aussage wird häufig als Verdeutlichung des sog. Quanten-Parallelismus verwendet. Auch hier wird wieder das Mantra-Wort "gleichzeitig" verwendet, dieses Mal aber in einer sinnvollen Bedeutung, nämlich im Gegensatz zu "nacheinander" (sequentiell). Natürlich können auch herkömmliche Computer heutzutage mehrere Berechnungen zeitlich parallel ausführen. Der Unterschied ist aber technisch fundamental: Herkömmliche Parallelrechner (z.B. MIMD-Architekturen) führen mehrere, durchaus auch verschiedene, Computerbefehle (Instructions) zur gleichen Zeit aus und verwenden dabei u.U. unterschiedliche Daten als Input.
Quanten-Computer führen zu einem Zeitpunkt einen Befehl (in Form von Gates) auf einer Datenstruktur aus. Die Datenstruktur ist der aktuelle Zustand eines n-Qubit-Systems, also meist eine Superposition oder gar eine Verschränkung. Der Zustand eines n-Qubit-Systems kann aber, wie wir zuvor gesehen haben, bis zu N=2**n Zahlen (in Form von Amplituden) repräsentieren. Indem der Qubit-Befehl auf den Zustand wirkt, wirkt er simultan auf alle Basiszustände, die in der Superposition vorkommen. Als Ergebnis können sich damit simultan alle Amplituden der Basiszustände verändern. Bingo!
Mathematisch gesehen ist das überhaupt nichts Ungewöhnliches. Eine Matrix A "wirkt" bei Multiplikation mit einem Vektor x auf alle seine Komponenten "gleichzeitig": y= Ax (Lineare Algebra). Wird ein Punkt (x,y) mittels einer Funktion F verschoben, dann werden alle Koordinaten "gleichzeitig" verschoben: (u,v) = F(x.y). Und auch die Qubit-Operatoren (Gates) können mathematisch als Matrizen dargestellt und verwendet werden. Wenn es allerdings ans praktische Rechnen geht, etwa mit einem Algorithmus, der die Matrixmultiplikation explizit durchführt, dann geht es klassisch (auf einem herkömmlichen Rechner) wieder nur Schritt für Schritt: die Operation wird in viele Einzelschritte zerlegt, die nacheinander ausgeführt werden. Hier unterscheiden sich klassische und Quanten-Computer tatsächlich fundamental. Quanten-Computer, wie die von IBM, sind technisch so aufgebaut, dass sie eine komplette Superposition in einem, statt in vielen Schritten verarbeiten können.
Wie man sich das vorstellen kann, zeigen wir an einem einfachen Beispiel: Das exklusive Oder (XOR) von zwei Bits entspricht der einfachen Bit-Addition bis auf die Operation "1+1", die 0 ergibt statt 2. (Dafür verwendet man auch das Symbol ⊕ statt +). Wir können die Bit-weise XOR-Berechnung auch als Qubit-Circuit durchführen. Das ergibt die 4 Auswertungen in der Abbildung, wobei jeweils q0 und q1 auf Zustand 0 bzw. 1 gesetzt werden und das Ergebnis den neuen Zustand von q1 ergibt.
Quanten-Parallelismus ermöglicht aber Superpositionen statt einzelner Basiszustände als Input zu präparieren, typischerweise mit dem H-Gate (Hadamard-Gate). Damit muss die Berechnung nur einmal ausgeführt werden und wir erhalten alle 4 Ergebnisse auf einmal.
Um die Ergebnisse einfacher "lesen" zu können, haben wir hier das XOR Ergebnis auf ein drittes Qubit q2 übertragen. So erhalten wir als Messergebnis genau die obige XOR Tabelle mit XOR -> q2 : 000, 101, 110, 011 (q2 steht hier wieder jeweils ganz links in der Bitkette).
"Was auf herkömmlichen Rechnern Jahre dauert, kann ein Quanten-Rechner in Sekunden erledigen"
Als Begründung liest man dabei oft, dass Quantenrechner "exponentiell schneller" rechnen können als herkommliche. Was bedeutet das?
Das heißt zum Beispiel folgendes: Wenn wenn wir zwei Methoden haben, die eine Aufgabe lösen, etwa eine Berechnung durchführen oder ein "Geheimnis" (Q15) zu finden, und die eine Methode benötigt N Zeiteinheiten oder Rechenschritte, die andere aber nur log(N) viele, dann stellt die zweite Methode eine exponentielle Verbesserung - oder Beschleunigung - gegenüber der ersten dar. (Denn, für k=log(N) ist N=exp(k).)
Es gibt eine ganze Reihe von solchen "Beschleunigungsbeziehungen" zwischen Methoden zur Lösung gleicher Aufgaben. Der Grover Qubit-Algorithmus benötigt nur etwa √N Schritte gegenüber N Schritten bei der klassischen Methode. Hier haben wir also eine quadratische Beschleunigung. In Q15 hatten wir das am Beispiel des Bernstein-Vazirani-Algorithmus diskutiert.
Solche Beschleunigungen gibt es von je her auch im klassischen Computing als Effekt einer algorithmischen Verbesserung. So gibt es z.B. unterschiedliche Sortier-Algorithmen, die sich bezüglich ihres Rechenaufwands erheblich unterscheiden, oder auch Verfahren zur numerischen Simulation, bei denen sogenannte Mehrgitterverfahren große Beschleunigungsraten bringen.
Der tatsächliche Beschleunigungseffekt des Quanten-Computing gegenüber herkömmlichen Bit-Computing beruht auf einer Kombination von zwei Dingen: dem Quanten-Parallelismus der Hardware (s. voriger Abschnitt) und dem Algorithmus, der für Qubits konstruiert werden kann.
Ein Rechenbeispiel: Hätte man eine (hypothetische) Aufgabe, die auf einem gewöhnlichen Rechner mit dem schnellsten Algorithmus 10 Jahre dauern würde, dann würde eine exponentielle Beschleunigung auf einen Zeitaufwand von rund 20 Sekunden führen: log(10*360*24*60*60) = log(311040000) = 19,56. Diese Zahlen sind allerdings eher fiktiv, da wie keine konkrete Aufgabe vor Augen haben und Wiederholungen und anderen "Overhead" nicht berücksichtigen. Aber es zeigt, wie sich die Größenordnung ändern.
Hätten wir also eine Aufgabe, die herkömmlich Jahre dauern würde, und hätten wir dazu ein Quanten-Computer, der sie alternativ mit exponentieller Beschleunigung löst, könnten wir die Aussage so akzeptieren. Allerdings gibt es noch nicht viele Algorithmen für Quanten-Computer, die in dieser Form praktische verwendbar sind. Was nicht zuletzt auch an der Größe und "Sensibilität" heutiger QC liegt.
Ein relevantes Beispiel, das immer wieder als "Gefahr durch Quanten-Computer" zitiert wird, ist das Verfahren von Shor, mit dem man einen wichtigen Schritt beim "Knacken" von besten heutigen Verschlüsselungsverfahren in akzeptabler Zeit durchführen kann. Um das zu verstehen, braucht es aber schon mehr Einsicht in die zugrunde liegende Mathematik. Daher wird hier meist nur der (befürchtete) Effekt zitiert und auf Verständnis verzichtet.
"Quanten-Rechner werden herkömmlichen Rechnern überlegen sein"
Man spricht auch generell von Quanten-Überlegenheit (Quantum Supremacy). Trotz der beängstigent klingenden Bezeichnung handelt es sich hier um eine unspektakuläre Sache. Es bedeutet lediglich das Ereignis, dass es eine Berechnung gibt, die ein Quanten-Computer schneller als jeder herkömmliche Supercomputer durchführen kann. Dabei ist es erst einmal egal, ob diese Berechnung einen Sinn macht oder praktische Bedeutung hat. Wie man kürzlich lesen konnte, hat man (mit einem QC von Google) bereits eine solche Berechnung durchführen können, d.h. der Meilenstein Quantum Supremacy ist schon erreicht.
"Jedes zusätzlich Qubit verdoppelt die Leistungsfähigkeit des Systems"
Hier bleibt einerseits unklar, was mit Leistungsfähigkeit gemeint ist - Rechenleistung, Speicherleistung, Leistung eines Algorithmus, der ein Qubit mehr zur Verfügung hat? Auch wenn wir einen Bit-Speicher (Register) um ein Bit erweitern, also von n auf n+1 Bits, können wir damit 2**(n+1) = 2*2**n Werte speichern bzw. mehr oder längere Befehle ausführen. So hatte sich auch die Prozessorarchitektur von früheren 32 Bit auf 64 Bit bei herkömmlichen Computern verändert und dabei prinzipiell eine 32-fache Verdoppelung der Leistung ermöglicht.
Was macht nun ein Qubit mehr aus bei einem Quanten-Computer? Zum einen gibt es dann doppelt so viele Basiszustände. Z.B. von 8 bei einem 3-Qubit System auf 16 bei 4 Qubits. In Superposition können damit 16 statt nur 8 Koeffizienten (Amplituden) einen Zustand bestimmen. Diese Verdoppelung ist analog der Situation bei Bits und wir hatten das schon oben bei N vs log(N) erklärt.
Zum anderen wissen wir, dass - ganz ander als beim Bit-Computing - verschränkte Zustände eine wichtige Rolle im Qubit-Computing spielen. Man kann sich also fragen, was bringt ein zusätzliches Qubit für die möglichen Verschränkungen, oder allgemein für die möglichen "Konfigurationen" von Superpositionen. Anders ausgedrückt: wieviel mehr Möglichkeiten gibt es für Zustände, in denen nur ein Basiszustand vertreten ist, oder zwei, oder drei usw. - unabhängig von den Werten der Amplituden. Diese Zahl wächst offenbar kombinatorisch. Für n=2 sind die "Muster" noch überschaubar: 4 mal |x>, 6 mal |x>+|y>, 3 mal |x>+|y>+|z> und 1 mal |x>+|y>+|z>+|v>, wenn |x>,|y>,|z>,|v> die Basiszustände |00>, |01>,|10>,|11> durchlaufen.
In Q13 (Superdichte Codierung) haben wir einen anderen Verdopplungseffekt gesehen: die Kapazität, Bitketten in GHZ-verschränkten Qubits zu "speichern" bzw. zu übertragen. Hier brachte jedes weitere Qubit in einer solchen Verschränkung eine Verdoppelung der Anzahl übertragbarer Bitketten.
Zuletzt eine Anmerkung: Bei "Was man so liest" fragt man sich leicht, wo man das gelesen hat. Die konkreten Aussagen in den Überschriften sind keine echten Zitate, obwohl sie so oder in Variationen der Wortwahl tatsächlich vorkommen. Wir wollen hier aber kein "Bashing" anzetteln, sondern nur kostruktiv klären, was dahinter steckt oder wo man leicht fehlgeleitet wird. Daher verzichten wir auf Quellenangaben.