Der Bernstein-Vazirani-Algorithmus - aus der Informatikperspektive

Lernziele

Ziel dieses Teils der Unterrichtseinheit ist es, dass Schüler*innen ihr Verständnis des Bernstein‑Vazirani-Algorithmus durch die Analyse seiner quantenmechanischen Implementierung vertiefen.

Anhand eines niedrigdimensionalen Beispiels konzentrieren sich die Schüler*innen darauf, wie die Abfolge von Quantengattern zur Messung des versteckten Bitstrings führt und wie sich dieses Ergebnis auf größere Eingabewerte übertragen lässt.

Sie können das Arbeitsblatt als PDF- und docx-Datei herunterladen.

Zusätzliches Tool für die Bernstein‑Vazirani-Unterrichtseinheit

Das Tabellenkalkulations-Tool kann verwendet werden, um jedes 3‑Qubit-Bernstein‑Vazirani-Problem zu modellieren und die grundlegende Struktur der Funktion sowie der zugrunde liegenden Schaltung zu veranschaulichen. Durch den Einsatz von Hadamard-Gattern zeigt es, wie der versteckte Bitstring bestimmt werden kann, und die $a_i$-Koeffizienten können ausgeblendet werden, sodass Schüler*innen versuchen können, den String selbst zu erschließen.

Das Tool ist für eine lehrkraftgeleitete Einführung vor den Übungen der Unterrichtseinheit konzipiert. Obwohl es für jedes Bernstein‑Vazirani-Problem konfiguriert werden kann, wurden vier Versionen vorab so eingestellt, dass sie den Aufgaben des Arbeitsblatts entsprechen.

Sie finden das zusätzliche Excel-Tool hier zum Download. 

Einleitung

Stell dir vor, du bist in einer Spielhalle und entdeckst einen geheimnisvollen Spielautomaten. So funktioniert er: Du hast drei Münzen – einige 10-Cent-Münzen und einige 20-Cent-Münzen. Der Automat erlaubt dir, diese Münzen in verschiedenen Kombinationen einzuwerfen. Als Ergebnis bekommst du entweder nichts oder genau 1 Euro. Dein Ziel ist es, die exakte versteckte Kombination aus 10-Cent- und 20-Cent-Münzen herauszufinden, die den Dollar-Jackpot auslöst.

Dieses Spiel ist eine anschauliche Analogie für den Bernstein-Vazirani-Algorithmus, der ein ähnliches Problem löst – allerdings mit einem Quanten-Algorithmus! So wie der Spielautomat eine versteckte Regel besitzt, die von deiner Münzkombination abhängt, geht es bei diesem Algorithmus darum, ein geheimes Muster (eine versteckte Folge aus 0 und 1) zu entdecken, das das Verhalten einer Funktion bestimmt. Die Herausforderung besteht darin, dies möglichst effizient zu tun.

Spielregeln:

1. Die Schüler*innen erhalten drei Münzen, dargestellt als Bits (0 für die 10-Cent-Münze und 1 für die 25-Cent-Münze)
2. Der Spielautomat (Lehrkraft) kennt die geheime Kombination (versteckte Bitfolge) und überprüft die eingegebene Kombination. Er gibt zurück: 0 → kein Gewinn oder 1 → Gewinn (1 Euro).
3. Ziel: Die Schüler*innen sollen die versteckte Regel (Bitfolge) herausfinden.

Mathematische Beschreibung des Problems

Stell dir vor, du hast eine Blackbox, die durch eine Funktion $f_a$ definiert wird. Die Eingabe in die Box (bzw. in die Funktion) ist eine Binärzahl mit $n$ Bits. Die Ausgabe ist entweder 0 oder 1. Die Funktion $f_a$ wird über eine festgelegte geheime Binärzahl $a=(a_1,a_2,\mathrm{...},a_{\mathrm{n}})$ definiert, wobei jedes $a_i$ 0 oder 1 ist.

Um die Ausgabe $f_a\left(x\right)$ zu berechnen, machen wir die folgenden Schritte:

1. Die Eingabe besteht aus $n$ Bits $x=(x_1,x_2,\mathrm{...},x_{\mathrm{n}})$, wobei $x_i$ jeweils 0 oder 1 ist.
2. Multipliziere jedes Eingabebit mit dem entsprechenden Bit aus $a$: $a_1\cdot x_1+a_2\cdot x_2+...+a_{\mathrm{n}}\cdot x_{\mathrm{n}}$
3. Überprüfe das Ergebnis der Summe:

• Falls die Summe gerade ist, gibt die Funktion 0 zurück.
• Falls die Summe ungerade ist, gibt die Funktion 1 zurück.

Aufgabe 1

Berechne die Ausgaben $f_a\left(x\right)$ für $a=(1,0,1)$(also $n=3$) anhand der Tabelle:

Analysiere die Ergebnisse: Wie viele und welche Kombinationen aus 10-Cent- und 20-Cent-Münzen führen zu einem Gewinn von 1 Euro? Merke dir, wie die Ausgaben vom versteckten Muster  abhängen. Dieses Muster ist der Schlüssel zum Verständnis des Funktionsverhaltens.

Aufgabe 2

Nun betrachten wir das eigentliche Problem: Bestimme die versteckte Bitfolge $a=(a_1,a_2,a_3)$ einer Funktion $f_a(x_1,x_2,x_3)$ aus der folgenden Tabelle.

Überlege dir die effizienteste Strategie, um $a=(a_1,a_2,a_3)$ zu bestimmen:

• Wie viele Abfragen benötigst du?
• Welche Eingabewerte $(x_1,x_2,x_3)$ solltest du nutzen, um $a=(a_1,a_2,a_3)$ am effizientesten zu bestimmen?
• Wie lautet die geheime Binärzahl $a$?

Simulation mit dem IBM Quantum Composer

1. Erster Ansatz: Klassische Lösung zum Finden der geheimen Zeichenkette

Öffne die Seite https://quantum.ibm.com/composer/files/new. Die folgende Schaltung implementiert eine bestimmte Bitfolge, die wir herausfinden möchten.

Beispiel: Eingabe $x_1=(1,0,0)$.

• Die Eingabewerte $x_1,x_2,x_3$ entsprechen den Werten der drei ersten Qubits $q\left[0\right]$, $q\left[1\right]$, $q\left[2\right]$.
• Das Ergebnis der Funktion ist der output von Qubit $q\left[3\right]$.
• Alle Qubits haben den Startwert 0. Um von 0 zu 1 zu wechseln, wende $\oplus$ auf das entsprechende Qubit an.
• Die Messung des letzten Qubits $q\left[3\right]$ ergibt das Ergebnis $f(x_1,x_2,x_3)$.

Der gemessene Wert (in diesem Fall 1) kann im Wahrscheinlichkeitsdiagramm der Simulation abgelesen werden:

Aufgabe 3

Baue die obige Schaltung nach und verwende den Quantum Composer, um die Tabelle zu vervollständigen:

2. Der Bernstein-Vazirani-Algorithmus ist ein Quanten-Algorithmus, der den untenstehenden Schaltkreis verwendet.

Die Funktion wird, wie im klassischen Fall, mit zwei CNOT-Gates implementiert. Die versteckte Bitfolge erhält man nach der Messung der ersten drei Qubits. Wie beim Deutsch-Algorithmus erzeugen die anfänglichen Hadamard-Gates eine Superposition aller möglichen Eingabewerte.

Baue den Schaltkreis im Quantum Composer nach und bestätige: Die Simulation liefert dieselbe Bitfolge wie in Aufgabe 3. 

Beachte: Klassisch waren drei Abfragen notwendig, während der Quanten-Algorithmus nur eine Abfrage benötigt.

Um besser zu verstehen, wie der Quanten-Algorithmus das Problem löst, betrachten wir ein Beispiel mit nur zwei Bits $f(x_1,x_2)$. Wir können die Zustandsentwicklung dann einfach mit einer Tabellenkalkulation nachvollziehen.

Hier finden Sie die Excel-Tabelle zum Download.

Aufgabe 4

Baue die folgende Schaltung Gate für Gate nach und ergänze parallel die Tabelle in einem Tabellenkalkulationsprogramm Schritt für Schritt.

Überprüfe nach jedem Schritt: Stimmt deine Berechnung in der Tabelle mit der Simulation im Composer überein?

Hinweise zur Hilfe:

• Verwende die Ket-Notation, wobei in der Tabelle der Normierungsfaktor weggelassen wird.
• Zunächst sind alle Qubits in Zustand $|0⟩$:   $|q_0⟩|q_1⟩|q_2⟩\equiv |q_0,q_1,q_2⟩=|0,0,0⟩.$
• Das $\oplus$-Gate wird auf $|q_2⟩$ ausgeführt und ändert den Gesamtzustand zu $|0,0,1⟩$, was in der Tabelle folgendermaßen notiert wird:

Das Hadamard auf $|q_0⟩$ erzeugt eine Superposition $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$. Der Gesamtzustand ist daher $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)|0⟩|1⟩=\frac{1}{\sqrt{2}}(|0,0,1⟩+|1,0,1⟩)$. Ohne den Normalisierungsfaktor $\frac{1}{\sqrt{2}}$ ergibt sich in der Tabelle dann:

Beantworte anschließend folgende Fragen:

1. Welche Bedeutung haben die beiden Hadamard-Gates am Anfang?
2. Warum befindet sich am Anfang ein $\oplus$ -Gate auf dem Ausgabe-Qubit $q\left[2\right]$? Was würde passieren, wenn dieses Gate fehlen würde?
3. Welche Funktion haben die letzten beiden Hadamard-Gates?
4. Welche Bitfolge $(a_1,a_2)$ ergibt sich aus der Messung?