Der Bernstein-Vazirani-Algorithmus: Mathematische Betrachtung

Übersicht

Sekundarstufe

Physik, Mathematik, Informatik

Quantencomputing

Auf einen Blick

Schlüsselbegriffe: Algorithmus, Superposition, Interferenz
Alter: 16–18 Jahre
Vorkenntnisse/Fertigkeiten: Grundkenntnisse zu Qubits, Dirac-Notation, Zustandsvektoren und der Matrixdarstellung einfacher Quantengatter, der Deutsch-Algorithmus
Zeitumfang: 90 Minuten (Doppelstunde)

Autor: Sergio Rivera Hernandez (DE)

Inhalt

Lernziele
Unterrichtsplan
Arbeitsblatt 1: Klassische Lösung und Quantenlösung
  • Das Problem
  • Aufgabe 1, Aufgabe 2, Aufgabe 3
  • Die Quantenlösung: Der Bernstein‑Vazirani-Algorithmus
  • Aufgabe 4
Arbeitsblatt 2: Test des Algorithmus für den Fall n = 2
  • Aufgabe 1, Aufgabe 2, Aufgabe 3, Aufgabe 4
  • Optionale Aufgabe

Zusammenfassung

Diese Unterrichtseinheit stellt den Bernstein-Vazirani-Algorithmus als Beispiel vor, bei dem ein quantenbasierter Ansatz dem klassischen Ansatz bei der Suche nach einer verborgenen binären Zeichenfolge deutlich überlegen ist. Die Schüler*innen arbeiten den Algorithmus Schritt für Schritt durch. Sie nutzen Tabellen, Hadamard-Gatter und Zustandstransformationen, um zu verstehen, wie die verborgene Zeichenfolge mit einer einzigen Abfrage ermittelt wird. Anschließend werden die theoretischen Berechnungen mit einer konkreten Schaltungsimplementierung unter Verwendung des IBM Quantum Composer verbunden.

Lernziele

Ziel dieser Unterrichtsstunde ist es, dass die Schüler*innen die in Lektion 1 eingeführten allgemeinen physikalischen Prinzipien – Superposition, Interferenz und Quanten-Funktionsauswertung – nun im Kontext des Bernstein-Vazirani-Algorithmus anwenden und vertiefen.

Zunächst erschließen die Schüler*innen die Grundidee des Algorithmus, ähnlich wie bereits in Lektion 2. Anschließend wenden sie den Algorithmus auf den Fall n=2 an.

Wichtig ist, dass die Schüler*innen im Verlauf der Stunde verstehen, dass die Rechnungen für n≥3 schnell deutlich aufwendiger werden. Wer jedoch den Fall n=2 verstanden hat, kann den Algorithmus auf größere Werte von n verallgemeinern. Die Wahl von n=2 beruht daher einerseits auf den zeitlichen Rahmenbedingungen und andererseits darauf, dass größere Fälle nicht notwendig sind, um die grundlegenden Prinzipien des Algorithmus zu verstehen.

Diese Stunde vertieft außerdem erneut die grundlegende Struktur, die vielen Quantenalgorithmen zugrunde liegt und als Golden-Circuit bezeichnet wird.

Unterrichtsplan

Zeit in Minuten	Unterrichtsphase	Aktivität	Material
0–5	Einstieg	In dieser Phase erläutert die Lehrkraft, dass in dieser Stunde ein anspruchsvollerer Algorithmus behandelt wird, der eines der in Lektion 1 eingeführten Suchprobleme in nur einem einzigen Schritt löst.
5–20	Arbeitsphase I	In dieser Phase erhalten die Schüler*innen das Arbeitsblatt, bearbeiten die Aufgaben 1, 2 und 3 und lesen die drei Schritte des Algorithmus.	Arbeitsblatt 1
20–45	Zwischenreflexion und Arbeitsphase II	In dieser Phase werden die Ergebnisse der ersten drei Aufgaben besprochen, um sicherzustellen, dass die Schülerinnen die Grundidee verstanden haben, bevor sie mit der konkreten Anwendung des Algorithmus fortfahren. Anschließend erklärt die Lehrkraft den Algorithmus im Detail, damit die Schülerinnen ihn vollständig verstehen, bevor sie Aufgabe 4 bearbeiten.
45–75	Arbeitsphase III	In dieser Phase erhalten die Schüler*innen das nächste Arbeitsblatt und bearbeiten die Aufgaben 1–4. Wer früher fertig ist, kann am Computer weiterarbeiten und mit der Zusatzaufgabe fortfahren.	Arbeitsblatt 2
75–90	Sicherung	Besprechung der Ergebnisse. In diesem Abschnitt betont die Lehrkraft erneut die physikalischen Prinzipien hinter dem Algorithmus und hebt hervor, dass diese Prinzipien in der nächsten Stunde wieder benötigt werden.

Hinweis für Lehrkräfte

Diese Unterrichtsstunde ist als Doppelstunde (ca. 90 Minuten) konzipiert. Wenn Ihr Stundenplan mit 45-Minuten-Einheiten arbeitet, können Aufgabe 4 und die Arbeit mit dem IBM Composer als Hausaufgabe vergeben oder in einer zweiten Stunde behandelt werden.

Sie können beide Arbeitsblätter für Ihre Klasse herunterladen:

Arbeitsblatt 1: pdf und docx
Arbeitsblatt 2: pdf und docx

Arbeitsblatt 1

Der Bernstein-Vazirani-Algorithmus, entwickelt im Jahr 1993, baut auf dem Deutsch-Algorithmus auf und zeigt, wie Quantencomputer bestimmte Probleme effizienter lösen können als klassische Computer.

In Lektion 1 hast du bereits eine Aufgabe kennengelernt, bei der ein geheimer Bitstring mit Ja/Nein-Fragen Bit für Bit bestimmt werden musste. Ein klassischer Algorithmus benötigt dafür im ungünstigsten Fall eine Abfrage pro Bit. Für einen geheimen Bitstring mit n Bits sind also n Abfragen notwendig. Der Bernstein-Vazirani-Algorithmus schafft dies mit nur einer einzigen Quantenabfrage, unabhängig von der Länge des Bitstrings.

In dieser Lektion lernst du anhand eines Beispiels mit drei Bits, wie dieser Quantenvorteil entsteht. Anschließend überträgst du das Prinzip auf beliebige Bitlängen.

Das Problem

Stell dir eine Blackbox vor, die durch eine Funktion $f_{a}$ beschrieben wird. Diese Box ist besonders: Wenn man ihr eine Binärzahl mit $n$ Bits gibt, liefert sie als Ausgabe entweder $0$ oder $1$ . Die Funktion $f_{a}$ ist dabei über einen feste, geheimen Binärstring $a = (a_{1} a_{2} ... a_{n})$ definiert, wobei jedes $a_{i}$ entweder $0$ oder $1$ ist.

Um den Funktionswert $f_{a} (x)$ , zu berechnen, wird folgender Ablauf genutzt:

Man gibt eine $n$ -stellige Binärzahl $x = (x_{1} x_{2} ... x_{n})$ ein, wobei jedes $x_{i}$ ebenfalls $0$ oder $1$ ist.
Multipliziere jedes Eingabebit mit dem entsprechenden Bit von a: $a_{1} \cdot x_{1} + a_{2} \cdot x_{2} + ... + a_{n} \cdot x_{n}$
Anschließend prüft man die Summe:
- Ist die Summe gerade, gibt die Funktion $0$ zurück.
- Ist die Summe ungerade, gibt die Funktion $1$ zurück.

Diese Art der Addition nennt man Addition modulo 2. Dabei gilt: Gibt es insgesamt eine gerade Anzahl von Einsen, ist das Ergebnis 0. Gibt es eine ungerade Anzahl von Einsen, ist das Ergebnis 1.

Aufgabe 1

Verwende den geheimen Binärstring $a = (1, 0, 1)$ für den Fall $n = 3$ und vervollständige die folgende Tabelle, indem du $f_{a} (x)$ berechnest.

Eingabe x	$a \cdot x = a_{1} \cdot x_{1} + a_{2} \cdot x_{2} + a_{3} \cdot x_{3}$	Ungerade	Gerade	Ausgabe $f_{a} (x)$
$(0, 0, 0)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 0$		x	0
$(0, 0, 1)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 = 1$	x		1
$(0, 1, 0)$
$(0, 1, 1)$
$(1, 0, 0)$
$(1, 0, 1)$
$(1, 1, 0)$
$(1, 1, 1)$

Verständnis des Problems

Unser Ziel ist es, die geheime Binärzahl $a$ , die in der Funktion $f_{a} (x)$ verwendet wird, herauszufinden. Dazu können wir der Funktion Fragen stellen, indem wir ihr verschiedene Binärzahlen $x = (x_{1} x_{2} \dots x_{n})$ übergeben und beobachten, welche Ausgabe wir erhalten.

Lösung zu Aufgabe 1 Lösung zu Aufgabe 1

Berechnung von $f_{a} (x)$ für $a = (1, 0, 1)$ und $n = 3$

Eingabe x	$a \cdot x = a_{1} \cdot x_{1} + a_{2} \cdot x_{2} + a_{3} \cdot x_{3}$	Ungerade	Gerade	Ausgabe $f_{a} (x)$
$(0, 0, 0)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 0$		x	0
$(0, 0, 1)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 = 1$	x		1
$(0, 1, 0)$	$1 \cdot 0 + 0 \cdot 1 + 1 \cdot 0 = 0$		X	0
$(0, 1, 1)$	$1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 = 1$	X		1
$(1, 0, 0)$	$1 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 = 1$	X		1
$(1, 0, 1)$	$1 \cdot 1 + 0 \cdot 0 + 1 \cdot 1 = 2$		X	0
$(1, 1, 0)$	$1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 = 1$	X		1
$(1, 1, 1)$	$1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 = 2$		x	0

Klassische Lösung

Aufgabe 2

Bestimme die minimale Anzahl an Abfragen, die nötig ist, um den Binärstring $a = (a_{1}, a_{2}, a_{3})$ vollständig zu ermitteln. Begründe deine Antwort.

Hinweis: Denk an die Aufgabe zurück, bei der du eine versteckte Binärzahl durch Ja/Nein-Fragen herausfinden musstest. Wie hängt das mit dem aktuellen Problem zusammen?

Lösung zu Aufgabe 2 Lösung zu Aufgabe 2

Klassisches Vorgehen zur Bestimmung von $a$

Minimale Anzahl benötigter Abfragen: 3 (eine pro Bit)

Begründung: Jedes Bit $a_{i}$ wird in der Funktion $f_{a (x)}$ nur durch das entsprechende Bit $x_{i}$ beeinflusst. Daher kann man $a$ durch geschickt gewählte Abfragen Schritt für Schritt bestimmen:

Die Abfrage $x = (1, 0, 0)$ liefert $a_{1}$ .
Die Abfrage $x = (0, 1, 0)$ liefert $a_{2}$ .
Die Abfrage $x = (0, 0, 1)$ liefert $a_{3}$ .

Aufgabe 3

Betrachte nun den Fall, dass der Binärstring $n$ Bits hat: $a = (a_{1} a_{2} \dots a_{n})$ .

Bestimme, wie viele Abfragen in diesem allgemeinen Fall notwendig sind. Begründe deine Antwort.

Lösung zu Aufgabe 3 Lösung zu Aufgabe 3

Verallgemeinerung auf $n$ Bits

Benötigte Anzahl an Abfragen im klassischen Fall: $n$

Begründung: Die beste Strategie besteht darin, jeweils ein Bit nach dem anderen abzufragen:

$x = (1000 \dots 0)$ liefert $a_{1}$
$x = (0100 \dots 0)$ liefert $a_{2}$
$x = (0010 \dots 0)$ liefert $a_{3}$ , usw.

Die Quantenlösung: Der Bernstein-Vazirani-Algorithmus

Anstatt die Funktion wie im klassischen Verfahren mehrfach abzufragen, bestimmt der Bernstein-Vazirani-Algorithmus den gesamten geheimen Bitstring mit nur einer einzigen Abfrage mithilfe des folgenden Quantenschaltkreises:

Es funktioniert in den folgenden Schritten:

Schritte des Bernstein-Vazirani-Algorithmus Schritte des Bernstein-Vazirani-Algorithmus

Schritt I: Erzeugung einer Superposition

Bereite im ersten Register $n$ Qubits im Zustand $| 0 ⟩$ vor. Wende auf jedes dieser Qubits ein Hadamard-Gatter an. Dadurch entsteht eine Superposition aller möglichen Zustände der  $n$ Qubits:

$H | 0 ⟩ H | 0 ⟩ \dots H | 0 ⟩ = \frac{1}{\sqrt{2^{n}}} (| 00 \dots 0 ⟩ + | 00 \dots 1 ⟩ + \dots + | 11 \dots 1 ⟩)$

Schritt II: Anwenden der Funktion $f_{a}$ und Einführen von Phasen

Wende die Funktion $f_{a}$ auf den Zustand aus Schritt I an, indem du das zweite Register verwendest. Dabei wird jeder Basiszustand der Superposition mit einem Phasenfaktor ${(-1)}^{0}$ oder ${(-1)}^{1}$ multipliziert:

$\frac{1}{\sqrt{2^{n}}} [{(-1)}^{f_{a} (00 \dots 0)} | 00 \dots 0 ⟩ + {(-1)}^{f_{a} (00 \dots 1)} | 00 \dots 1 ⟩ + \dots + {(-1)}^{f_{a} (11 \dots 1)} | 11 \dots 1 ⟩]$

Schritt III: Anwendung von Hadamard-Gattern

Wende erneut auf jedes Qubit im ersten Register ein Hadamard-Gatter an:

$\frac{1}{\sqrt{2^{n}}} [{(-1)}^{f_{a} (00 \dots 0)} H | 0 ⟩ H | 0 ⟩ \dots H | 0 ⟩ + {(-1)}^{f_{a} (00 \dots 1)} H | 0 ⟩ H | 0 ⟩ \dots H | 1 ⟩ + \dots {(-1)}^{f_{a} (11 \dots 1)} H | 1 ⟩ H | 1 ⟩ \dots H | 1 ⟩]$

Hinweis: Dass die Funktion diese Phasenverschiebungen im ersten Register einführt, ohne das zweite Register direkt zu verändern, ist ein zentrales Prinzip des Quantencomputings. Wer genauer verstehen möchte, warum und wie diese Phasen entstehen, kann das Arbeitsblatt zur Quantenauswertung von Funktionen bearbeiten.

Abschließende Messung

Eine Messung des ersten Registers liefert jetzt mit 100 % Wahrscheinlichkeit den geheimen Bitstring $a$ . Im Gegensatz zur klassischen Methode, bei der mehrere Abfragen nötig sind, bestimmt der Quantenalgorithmus $a$ mit nur einer Abfrage. Das Messergebnis ist dann der Zustand: $| a ⟩ = | a_{1} a_{2} \dots a_{n} ⟩$

Aufgabe 4

Vergleiche den Schaltkreis des Deutsch-Algorithmus (siehe Abbildung) mit dem Schaltkreis des Bernstein-Vazirani-Algorithmus und beantworte die folgenden Fragen:

Erläutere die Gemeinsamkeiten und Unterschiede zwischen den beiden Algorithmen. Wie hängt der Deutsch-Algorithmus mit dem Bernstein-Vazirani-Algorithmus zusammen?

Lösung zu Aufgabe 4 Lösung zu Aufgabe 4

Vergleich des Deutsch-Algorithmus und des Bernstein-Vazirani-Algorithmus

Aspekt	Deutsch-Algorithmus	Bernstein-Vazirani Algorithm
Ziel des Algorithmus	Bestimmt ob $f (x)$ konstant oder balanciert ist	Bestimmt den geheimen Bitstring $a$
Anzahl der Qubits	2 Qubits (1 Eingabe + 1 Hilfsqubit)	$(n + 1)$ Qubits (n Eingabequbits + 1 Hilfsqubit)
Quanten-Vorteil	Reduziert die Anzahl der Abfragen von 2 auf 1	Reduziert die Anzahl der Abfragen von $n$ auf 1
Zentraler Unterschied	Löst ein binäres Entscheidungsproblem	Extrahiert die vollständige Information über $a$

Arbeitsblatt 2

Test des Algorithmus für den Fall $n = 2$

Nun wirst du jeden Schritt des Algorithmus analysieren, um zu verstehen, wie die zugrunde liegenden Quantenprinzipien es ermöglichen, das Problem mit nur einer einzigen Abfrage zu lösen – im Fall $n = 2$ . Hier siehst du den Schaltkreis für diesen Fall: