Der Deutsch-Algorithmus: Mathematische Betrachtung

Übersicht

Sekundarstufe

Physik, Mathematik

Quantencomputing

Deutsch

Auf einen Blick

Schlüsselbegriffe: Algorithmus, Deutsch Algorithmus
Alter: 16-18 Jahre
Erforderliche Kenntnisse/Fähigkeiten: keine spezifischen Vorkenntnisse erforderlich
Zeitrahmen: 60 Minuten

Autor: Sergio Rivera Hernandez (DE)

Inhalt

Lernziele
Unterrichtsplan
Arbeitsblatt 1: Exkurs zur Quanten-Funktionsauswertung mit Lösungen
Arbeitsblatt 2: Deutsch Algorithmus mit Lösungen
Abschließendes Fazit

Zusammenfassung

Diese Unterrichtseinheit behandelt den Deutsch- Algorithmus, der als erster Quantenalgorithmus einen Geschwindigkeitsvorteil gegenüber einem klassischen Ansatz erzielt. Im mathematischen Zugang liegt der Fokus darauf, warum die Superposition diesen Vorteil ermöglicht. Lehrkräfte führen Schüler*innen schrittweise durch die Frage, wie Superposition zu einer Beschleunigung bei der Lösung des Deutsch-Orakelproblems führt, und führen in die Struktur des Golden-Circuit-Musters ein.

Lernziele

Ziel dieser Unterrichtsstunde ist es, dass die Schüler*innen ein erstes Beispiel für einen Quantenalgorithmus verstehen, der die grundlegende Struktur verdeutlicht, auf der viele Quantenalgorithmen beruhen. Dabei wird ein Fall betrachtet, in dem die Quantenmethode mit weniger Funktionsauswertungen auskommt als eine klassische deterministische Methode. Diese Struktur, bekannt als das Golden-Circuit-Muster, besteht aus:

Hadamard-Gatter, um eine Superposition zu erzeugen.
Quanten-Funktionsauswertung, um Interferenz einzuführen.
Hadamard-Gatter, um die Interferenz auszulesen.
Messung, um nützliche Informationen zu gewinnen.

Auf den ersten Blick wirkt der Deutsch-Algorithmus vielleicht simpel, doch er enthält die zentralen Prinzipien, auf denen nahezu alle Quantenalgorithmen beruhen. Die zentrale Herausforderung für die Lehrkraft besteht darin, die Stunde so zu gestalten, dass die Schülerinnen und Schüler seine Bedeutung erkennen.

Unterrichtsplan

Bevor die Schüler*innen mit dem Arbeitsblatt beginnen, ist es entscheidend, dass die Lehrkraft hervorhebt, warum dieser Algorithmus wichtig ist. Auch wenn das Problem, das er löst, trivial oder unnötig erscheinen mag, ist das zugrunde liegende physikalische Prinzip dasselbe wie bei fortgeschritteneren Quantenalgorithmen, auch wenn diese deutlich mehr mathematische Werkzeuge erfordern.

Am Ende der Stunde sollte die Lehrkraft ausdrücklich erläutern, dass und wie das Golden-Circuit-Muster in den folgenden Quantenalgorithmen dieses Kurses erneut auftauchen wird.

Zeit in Minuten	Unterrichtsphase	Aktivität	Material
0 - 5	Einstieg	Dies ist eine zentrale Phase der Stunde. Die Lehrkraft sollte betonen, dass es sich um den einfachsten Quantenalgorithmus handelt und um ein erstes Beispiel dafür, wie ein Quantencomputer ein Problem auf eine Weise löst, die eine klassische deterministische Methode so nicht leisten kann. Trotz seiner Einfachheit, die es den Schülerinnen ermöglicht, jeden Schritt im Detail nachzuvollziehen, veranschaulicht dieser Algorithmus die grundlegenden physikalischen Prinzipien, die auch hinter komplexeren Quantenalgorithmen stehen. Genau das macht ihn so wichtig: Wenn die Schülerinnen die Grundprinzipien dieses Algorithmus verstehen, verstehen sie auch die Prinzipien anderer Quantenalgorithmen, weil diese auf denselben Grundlagen aufbauen. Diese Botschaft sollte klar und ausdrücklich kommuniziert werden.
5 – 15	Erarbeitungsphase I	In dieser Phase erhalten die Schüler*innen das Arbeitsblatt, bearbeiten die Aufgaben 1 und 2 und lesen die drei Schritte des Algorithmus.	AB 2, Aufgaben 1-2
15 - 25	Zwischensicherung	In dieser Phase werden die Ergebnisse der ersten beiden Aufgaben besprochen, um sicherzustellen, dass die Schüler*innen die Grundidee verstanden haben, bevor sie mit der konkreten Anwendung des Algorithmus fortfahren.
25 -50	Erarbeitungsphase II	In dieser Phase bearbeiten die Schüler*innen die Aufgaben 3–6. Wer früher fertig ist, kann am Computer weiterarbeiten und mit den nächsten Aufgaben fortfahren, von denen einige mit dem Quantum Composer gelöst werden.	AB 2, Aufgaben 3-6
50 - 60 [FU1.1]	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. Die Schüler*innen sollten prüfen, dass sie verstanden haben, warum der Quantenalgorithmus nur eine Abfrage der Funktion benötigt, während eine klassische deterministische Methode zwei Abfragen benötigt.

Das Arbeitsblatt lässt die Normierungsfaktoren bewusst weg, damit der Fokus auf den physikalischen Prinzipien des Algorithmus bleibt. Würde man sie mitführen, könnte das die Schüler*innen davon ablenken, die zentralen quantenmechanischen Mechanismen zu verstehen. Die Lehrkraft sollte dies bei der Durchführung der Stunde im Blick behalten.

Arbeitsblatt 1: Exkurs zur Quanten-Funktionsauswertung mit Lösungen

Im Zentrum von Quantenalgorithmen steht die Interferenz – ein fundamentales Phänomen der Quantenmechanik. Interferenz entsteht, wenn eine Funktion $f$ auf die Zustände des ersten Registers angewendet wird. In dieser Lektion lernen Sie, wie genau dieser Prozess abläuft.

Die folgenden Aufgaben können Sie als Arbeitsblatt in pdf oder docx herunterladen.

Im Arbeitsblatt wird vorausgesetzt, dass die Anwendung der Funktion f im ersten Register eine Phasenverschiebung der Form

${(- 1)}^{f (0)} |0⟩ + {(- 1)}^{f (1)} |1⟩$

bewirkt. Diese Aussage wird im Hauptarbeitsblatt jedoch nicht im Detail hergeleitet. Zu diesem Zweck wurde das „Arbeitsblatt 1: Exkurs zur Quanten-Funktionsauswertung“ entwickelt, das die Quanten-Funktionsauswertung vollständig und Schritt für Schritt behandelt.

Es wird empfohlen, dieses Zusatzarbeitsblatt mit der gesamten Lerngruppe zu bearbeiten, wenn die Schüler*innen leistungsstark und mathematisch sicher sind. Andernfalls kann es als optionaler Exkurs für Schüler*innen oder Lehrkräfte genutzt werden, die dieses Thema vertiefen möchten.

Aufgabe 1

Im ersten Register befinden sich Zustände der Form $|x⟩$ , wobei jedes x entweder 0 oder 1 ist. Die Funktion $f$ wirkt auf diese Weise:

Wenn $f (x) = 0$ ist, bleibt der Zustand des zweiten Registers unverändert.
Wenn $f (x) = 1$ ist, dann wird $|0⟩$ im zweiten Register zu $|1⟩$ und $|1⟩$ zu $|0⟩$ .

Dieses Verhalten – dass also das erste Register kontrolliert, ob das zweite Register verändert wird – ist in der Abbildung dargestellt. Man sagt: Das erste Register kontrolliert das zweite^[1].

Trage in die folgende Tabelle ein, was mit dem zweiten Register geschieht, wenn die Funktion $f$ den angegebenen Wert hat:

Funktionswert der auf das erste Register angewendeten Funktion $f (x_{1}, \dots, x_{n})$	Anfangszustand des zweiten Registers	Endzustand des zweiten Registers (gesteuert durch $f$ )
0	$\| 0 ⟩$
0	$\| 1 ⟩$
1	$\| 0 ⟩$
1	$\| 1 ⟩$
0	$\| 0 ⟩ - \| 1 ⟩$
1	$\| 0 ⟩ - \| 1 ⟩$

Aufgabe 1: Lösungen Aufgabe 1: Lösungen

Funktionswert $f (x_{1}, \dots, x_{n})$ (wirkt auf 1. Register)	Anfangszustand des 2. Registers	Endzustand des 2. Registers (gesteuert durch $f$ )
0	$\| 0 ⟩$	$\| 0 ⟩$
0	$\| 1 ⟩$	$\| 1 ⟩$
1	$\| 0 ⟩$	$\| 1 ⟩$
1	$\| 1 ⟩$	$\| 0 ⟩$
0	$\| 0 ⟩ - \| 1 ⟩$	$\| 0 ⟩ - \| 1 ⟩$
1	$\| 0 ⟩ - \| 1 ⟩$	$\| 1 ⟩ - \| 0 ⟩ = - (\| 0 ⟩ - \| 1 ⟩)$

Aufgabe 2

In dieser Aufgabe nutzen Sie die Ergebnisse aus Aufgabe 1, um den entscheidenden Trick zu verstehen, der in Quantenalgorithmen zur Erzeugung von Interferenz verwendet wird – dem Herzstück des Quantencomputings.

Quantenalgorithmen nutzen folgenden Schaltkreis, bei dem eine Funktion auf das erste Register wirkt und dabei den Zustand des zweiten Registers kontrolliert verändert:

a) Zeigen Sie, dass der Gesamtzustand

|x⟩ (|0⟩ - |1⟩)

unverändert bleibt, wenn gilt: $f (x) = 0$

b) Zeigen Sie, dass sich der gleiche Zustand

|x⟩ (|0⟩ - |1⟩)

bei $f (x) = 1$ in den Zustand

|x⟩ (|1⟩ - |0⟩)

verwandelt, was man alternativ schreiben kann als:

(- 1) |x⟩ (|0⟩ - |1⟩)

c) Begründen Sie, dass sich die Ergebnisse aus a) und b) zusammenfassen lassen durch den allgemeinen Ausdruck:

{(- 1)}^{f (x)} | x ⟩ (| 1 ⟩ - | 0 ⟩)

Aufgabe 2: Lösungen Aufgabe 2: Lösungen

Schritt 1: Zeigen, dass bei $f (x₁, ..., xₙ) = 0$ , der Gesamtzustand gleich bleibt

Wir starten mit dem Anfangszustand:

|x₁⟩ \dots |xₙ⟩ \otimes (|0⟩ - |1⟩)

• Da $f (x₁, ..., xₙ) = 0$ , vertauscht die Funktion das zweite Register nicht.
• Das zweite Register bleibt daher im ursprünglichen Zustand: $|0⟩ - |1⟩$ .
• Somit bleibt auch der Gesamtzustand unverändert:

|x₁⟩ \dots |xₙ⟩ \otimes (|0⟩ - |1⟩)

Fazit: Der Zustand wird nicht verändert, wenn $f (x₁, ..., xₙ) = 0$ .

Schritt 2: Zeigen, dass bei $f (x) = 1$ , der Zustand umgeformt wird

Wir starten mit demselben Anfangszustand:

|x₁⟩ \dots |xₙ⟩ \otimes (|0⟩ - |1⟩)

• Da $f (x) = 1$ , vertauscht die Funktion das zweite Register:
$|0⟩ \to |1⟩ und |1⟩ \to |0⟩$

Dadurch entsteht:

|x₁⟩ \dots |xₙ⟩ \otimes (|1⟩ - |0⟩)

Das ist gleichbedeutend mit dem Einführen eines Phasenfaktors:

(- 1) |x₁⟩ \dots |xₙ⟩ \otimes (|0⟩ - |1⟩)

Fazit: Wenn $f (x₁, ..., xₙ) = 1$ , erhält der Zustand einen Phasenfaktor (-1).

Schritt 3: Begründung des allgemeinen Ausdrucks

Aus den beiden vorherigen Schritten folgt:

Wenn $f (x₁, ..., xₙ) = 0$ :

|x₁⟩ \dots |xₙ⟩ \otimes (|0⟩ - |1⟩)

(keine Änderung)

Wenn $f (x₁, ..., xₙ) = 1$ :

(- 1) |x₁⟩ \dots |xₙ⟩ \otimes (|0⟩ - |1⟩)

Dieses Muster lässt sich in der verallgemeinerten Form zusammenfassen:

{(- 1)}^{f (x)} | x_{1} ⟩ \dots | x_{n} ⟩ \otimes (| 0 ⟩ - | 1 ⟩)

Fazit: Das bedeutet: Das zweite Register $|1⟩ - |0⟩$ bleibt vollständig unverändert, doch das erste Register erhält einen Phasenfaktor der Form ${(- 1)}^{f (x)}$ .

Abschließende Erkenntnis: Die Rolle der Quanten-Funktionsauswertung in Quantenalgorithmen

In dieser Lektion haben Sie gelernt, wie die Quanten-Funktionsauswertung Interferenz erzeugt – den zentralen Mechanismus, auf dem viele Quantenalgorithmen basieren.

Anders als bei klassischen Funktionen wird bei der Quanten-Funktionsauswertung nicht einfach der Zustand eines Qubits verändert. Stattdessen wird Information in die Phase des ersten Registers eingeschrieben.

Der Zustand $|0⟩ - |1⟩$ im zweiten Register ist entscheidend für die Erzeugung der Interferenz. Er stellt sicher, dass bei der Funktionsauswertung keine klassische Information gespeichert, sondern eine Phasenmodifikation des ersten Registers vorgenommen wird.

Da diese Phasenkodierung in den meisten Quantenalgorithmen vorkommt, ist das Verständnis dieses Prinzips sowohl für die mathematische Beschreibung des Quantencomputings als auch für dessen praktische Umsetzung (z. B. mit Tools wie dem Quantum Composer oder Qiskit) unerlässlich.

Wer dieses Prinzip durchdringt, versteht besser, wie und warum Quantencomputer bestimmte Probleme effizienter lösen können als klassische Computer.

In den nächsten Lektionen werden Sie sehen, wie diese Technik in echten Quantenalgorithmen angewendet wird.

Arbeitsblatt 2: Deutsch Algorithmus mit Lösungen

Die folgenden Aufgaben können Sie als Arbeitsblatt in pdf oder docx herunterladen.

Der von David Deutsch im Jahr 1985 entwickelte Deutsch-Algorithmus stellt einen wichtigen Meilenstein in der Geschichte des Rechnens dar. Er war das erste Beispiel dafür, dass ein Quantenalgorithmus einen potenziellen Vorteil gegenüber klassischen Verfahren bieten kann. Diese Entdeckung eröffnete die Perspektive, dass Computer auf Basis quantenmechanischer Prinzipien bestimmte Problemstellungen effizienter lösen könnten als klassische Rechner.

In dieser Lektion lernen Sie Schritt für Schritt, wie der Deutsch-Algorithmus funktioniert. Um seine Tragweite vollständig zu erfassen, betrachten wir zunächst, wie sich das zugrunde liegende Problem mit klassischen Rechenmethoden angehen lässt.

Die Aufgabe

Stellen Sie sich vor, wir haben eine geheimnisvolle Black Box, die durch eine Funktion beschrieben wird. Diese Box ist besonders: Wenn man ihr eine Zahl als Eingabe gibt (entweder 0 oder 1), gibt sie eine Zahl als Ausgabe zurück (ebenfalls 0 oder 1).

Aber es gibt ein Geheimnis: Wir wissen nicht genau, wie die Box arbeitet – und genau das wollen wir herausfinden.
Die Box funktioniert auf eine von zwei Arten:

Konstante Funktionen		Balancierte Funktionen
$f_{1} (0) = 0$ $f_{1} (1) = 0$	$f_{2} (0) = 1$ $f_{2} (1) = 1$	$f_{3} (0) = 0$ $f_{3} (1) = 1$	$f_{4} (0) = 1$ $f_{4} (1) = 0$

Unsere Aufgabe besteht darin, herauszufinden, ob es sich bei der geheimnisvollen Black Box (also der Funktion $f (x)$ ) um eine konstante oder eine balancierte Funktion handelt. Dazu dürfen wir ihr Fragen stellen – das heißt: Wir geben ihr Eingabewerte (0 or 1) und beobachten, welche Ausgabewerte sie zurückliefert.

Klassische Lösung

Aufgabe 1: Beschreiben Sie den Hauptunterschied zwischen einer konstanten und einer balancierten Funktion.

Aufgabe 2: Bestimmen Sie die minimale Anzahl an Fragen, die Sie der Black Box stellen müssen, um herauszufinden, ob die Funktion konstant oder balanciert ist. Begründen Sie Ihre Antwort.

Beschreibung der Quantenlösung: Beschreibung der Quantenlösung:

Der Deutsch-Algorithmus löst unser Problem mit nur einer einzigen Abfrage. Er verwendet den folgenden Quantenschaltkreis:

Dieser Schaltkreis arbeitet in drei Hauptschritten unter Verwendung von Quantenbits (Qubits) und Quantengattern. So ist er aufgebaut:

Für das erste Qubit (im ersten Register) beginnen wir im Zustand $|0⟩$ .
Das zweite Register wird in einer speziellen Überlagerung $|0⟩ - |1⟩$ vorbereitet.

Der Algorithmus läuft in drei Schritten ab:

Schritt I: Ein Hadamard-Gatter wird auf das erste Register $|0⟩$ angewendet, um eine gleichgewichtete Superposition der Zustände $|0⟩$ und $|1⟩$ zu erzeugen.

Schritt II: Die Funktion $f$ wird angewendet. Sie verändert die Phase des ersten Registers gemäß dem Ausdruck ${(- 1)}^{f (x)}$ . Dieser Schritt ist entscheidend für die quantenmechanische Interferenz.

Hinweis: Wer genauer verstehen möchte, wie dieser Phasenfaktor entsteht, kann sich das optionale Arbeitsblatt „Quantenfunktionenauswertung“ ansehen.

Schritt III: Erneut wird ein Hadamard-Gatter auf das erste Register angewendet. In diesem Schritt interferieren die phasenmodifizierten Zustände miteinander, sodass durch eine anschließende Messung entschieden werden kann, ob die Funktion $f (x)$ konstant oder balanciert ist.

Ihre Aufgabe: Schrittweises Verstehen des Deutsch-Algorithmus

Aufgabe 3, Schritt I: Zeigen Sie, dass sich der Eingabezustand $|0⟩$ nach dem Anwenden des ersten Hadamard-Gatters in den Zustand $|0⟩ + |1⟩$ verwandelt.

Hinweis: Der Hadamard-Operator lässt sich wie folgt darstellen:

H = \frac{1}{\sqrt{2}} (|0⟩⟨0| + |0⟩⟨1| + |1⟩⟨0| - |1⟩⟨1|)

. Beachten Sie, dass das Ergebnis bis auf einen insgesamt irrelevanten Vorfaktor betrachtet wird.

Aufgabe 4, Schritt II: In diesem Schritt wird durch die Anwendung der Quantenfunktionsauswertung eine Phasenverschiebung im ersten Register eingeführt. Es lässt sich zeigen (siehe Arbeitsblatt Quantenfunktionsauswertung), dass sich der Zustand $|0⟩ + |1⟩$ in den folgenden Zustand transformiert:

{(- 1)}^{f (0)} |0⟩ + {(- 1)}^{f (1)} |1⟩

Zeigen Sie,

a) Dass bei einer konstanten Funktion $f$ , der Zustand ${(- 1)}^{f (0)} |0⟩ + {(- 1)}^{f (1)} |1⟩$ sich – bis auf einen insgesamt irrelevanten Vorfaktor – zu $|0⟩ + |1⟩$ vereinfacht.

b) Dass bei einer balancierten Funktion $f$ , der Zustand ${(- 1)}^{f (0)} |0⟩ + {(- 1)}^{f (1)} |1⟩$ sich – bis auf einen insgesamt irrelevanten Vorfaktor – zu $|0⟩ - |1⟩$ vereinfacht.

Aufgabe 5, Schritt III: In diesem Schritt wenden Sie das Hadamard-Gatter auf die Zustände an, die in Aufgabe 4 erhalten wurden.

a) Wenn die Funktion konstant ist, wenden Sie das Hadamard-Gatter auf den Zustand $|0⟩ + |1⟩$ an und zeigen Sie, dass sich daraus der Zustand $|0⟩$ ergibt.

b) Wenn die Funktion balanciert ist, wenden Sie das Hadamard-Gatter auf den Zustand $|0⟩ - |1⟩$ an und zeigen Sie, dass sich daraus der Zustand $|1⟩$ ergibt.

Aufgabe 6: Messung

a) Welchen Zustand misst man nach Schritt III, wenn die Funktion konstant ist? ___ $|0⟩$ ___ $|1⟩$

b) Welchen Zustand misst man nach Schritt III, wenn die Funktion balanciert ist? ___ $|0⟩$ ___ $|1⟩$

c) Erklären Sie, warum Ihre Antworten in a) und b) das ursprüngliche Problem lösen.

Implementierung mit dem Quantum Composer

Der Deutsch-Algorithmus lässt sich mit dem Quantum Composer leicht umsetzen – mithilfe des folgenden Quantenschaltkreises:

Aufgabe 7: Modellieren Sie zunächst die konstanten und balancierten Funktionen mit dem Quantum Composer. Diese Funktionen lassen sich durch bestimmte Konfigurationen von Quantengattern darstellen.

Betrachten Sie $q_{0}$ als den Eingangs-Qubit (also den x-Wert der Funktion $f (x)$ ) und beobachten Sie, wie sich der Zustand des zweiten Registers nach Anwendung der angegebenen Gatter verändert. Der Endzustand des zweiten Registers repräsentiert den Funktionswert $f (x)$ .

Im Folgenden sehen Sie vier Gatterkonfigurationen, die jeweils einer der Funktionen $f_{1}$ , $f_{2}$ , $f_{3}$ und $f_{4}$ entsprechen.

Ordnen Sie jeder der Funktionen $f_{1}$ , $f_{2}$ , $f_{3}$ und $f_{4}$ das passende Schaltbild zu.

Aufgabe 8: Erklären Sie, warum der folgende Teil des Schaltkreises

zum Zustand $|0⟩ - |1⟩$ führt.

Aufgabe 9: Nun sind Sie bereit, mit dem Quantum Composer zu experimentieren. Wählen Sie eine der Darstellungen der Funktionen $f_{1}$ , $f_{2}$ , $f_{3}$ oder $f_{4}$ , implementieren Sie den vollständigen Schaltkreis im Quantum Composer und überprüfen Sie, ob der Algorithmus wie erwartet funktioniert.

Arbeitsblatt 2: Lösungen Arbeitsblatt 2: Lösungen

Aufgabe 1: Unterschied zwischen konstanten und balancierten Funktionen

Konstante Funktion: Gibt für alle Eingaben denselben Wert aus (entweder immer 0 oder immer 1).
Balancierte Funktion: Gibt für eine Eingabe 0 und für die andere Eingabe 1 aus.

Aufgabe 2: Minimale Anzahl an Abfragen (klassischer Fall)

Klassisch benötigt man zwei Abfragen der Funktion, um sicher zu entscheiden, ob die Funktion konstant oder balanciert ist.

Aufgabe 3: Anwendung des Hadamard-Gatters in Schritt I

Das Hadamard-Gatter erzeugt eine Superposition: $H | 0 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩)$
Das heißt, $|0⟩$ wird zu $|0⟩ + |1⟩$ (bis auf den Normierungsfaktor).

Aufgabe 4: Phasenkodierung durch Anwendung der Funktion in Schritt II

Für eine konstante Funktion $f (x)$ : ${(- 1)}^{f (0)} |0⟩ + {(- 1)}^{f (1)} |1⟩$
~ $|0⟩ + |1⟩$ (kein relativer Phasenunterschied)
Für eine balancierte Funktion $f (x)$ : $- {(- 1)}^{f (0)} |0⟩ + {(- 1)}^{f (1)} |1⟩$
~ $|0⟩ - |1⟩$ (relative Phasenverschiebung)

Aufgabe 5: Erneute Anwendung des Hadamard-Gatters (Schritt III)

Wenn $f (x)$ konstant ist: $H (|0⟩ + |1⟩) ~ |0⟩$ .
Wenn $f (x)$ balanciert ist: $H (|0⟩ - |1⟩) ~ |1⟩$ .

Aufgabe 6: Messergebnis

Ist die Funktion konstant, wird $|0⟩$ gemessen.
Ist die Funktion balanciert, wird $|1⟩$ gemessen.

Zusammenfassung der Quantenlösung Zusammenfassung der Quantenlösung

Durch die Nutzung von Superposition kann das Quantenprogramm mit nur einer Abfrage entscheiden, ob die Funktion konstant oder balanciert ist. Eine klassische deterministische Methode benötigt dafür zwei Abfragen, weil sie beide Eingabefälle getrennt prüfen muss.

Bemerkenswert ist dabei, dass „konstant“ versus „balanciert“ eine globale Eigenschaft der Funktion ist. Das bedeutet: Man kann sie nicht anhand eines einzelnen Eingabe-Ausgabe-Paares erkennen. Erst durch den Vergleich von $f (0)$ und $f (1)$ ist eine sichere Entscheidung möglich. Daher muss ein klassisches Verfahren beide Werte separat abfragen.

Ein Quantenalgorithmus wie der Deutsch-Algorithmus nutzt dagegen Superposition und Interferenz, um beide Eingaben gleichzeitig zu verarbeiten. Dadurch kann die globale Struktur der Funktion in nur einem Rechenschritt analysiert werden. Im Messprozess gewinnt man schließlich ein einziges Bit Information, das aber genau die gesuchte globale Eigenschaft verrät.

Zwei weitere Punkte verdeutlicht der Deutsch-Algorithmus:

Quantencomputer sind nicht in jeder Hinsicht überlegen.
Der Quantenalgorithmus entscheidet nur, ob eine Funktion konstant oder balanciert ist. Welche konkrete Funktion sich in der Black Box befindet, bleibt offen. Ob ein Problem für Quantencomputer geeignet ist, muss stets im Einzelfall analysiert werden.
Die Lösung steckt im Eingangs-Qubit.
Am Ende wird nicht der Ausgangs-Qubit, sondern der Eingangs-Qubit gemessen. Die Information wurde während des Algorithmus in diesen Qubit „verschoben“, während der andere Teil des Systems Information verliert. Solche Verschiebungen sind typisch für viele Quantenalgorithmen. Häufig liegt die Lösung nicht dort, wo man sie intuitiv vermuten würde.

Obwohl das Deutsch-Problem eher theoretisch und einfach konstruiert ist, hat es grundlegende Prinzipien des Quantencomputings erstmals demonstriert. Es ebnete den Weg für bedeutendere Quantenalgorithmen, die in den nächsten Lektionen behandelt werden.

Abschließendes Fazit

Das zweite Register wird dabei nie inhaltlich verändert; es bleibt (bis auf ein Vorzeichen) gleich. Entscheidend ist nur, dass sich die Phase des Zustands abhängig von $f (x)$ ändert.
Diese Phasenkodierung ist zentral für Quanteninterferenz und bildet die Grundlage dafür, dass Quantenalgorithmen in manchen Aufgaben weniger Funktionsabfragen benötigen als klassische Verfahren.

Quellenverzeichnis Quellenverzeichnis

Mathematisch entspricht diese Operation einer sogenannten kontrollierten Modulo-2-Addition (XOR-Verknüpfung), die sich wie folgt ausdrücken lässt:
$|x⟩ |y⟩ ⟼ |x⟩ | y \oplus f (x) ⟩$ .
Dabei steht ⊕ für die Addition Modulo 2. Das bedeutet: Wenn $f (x) = 1$ , wird der Zustand des zweiten Qubits $|y⟩$ umgeklappt ( $|0⟩ \leftrightarrow |1⟩$ ); ist $f (x) = 0$ , bleibt der Zustand unverändert. Dieses Prinzip bildet die Grundlage für viele quantenlogische Operationen.
Alle Bilder sind Screenshots aus dem IBM Quantum Composer.

Weiter zu: Der Bernstein-Vazirani-Algorithmus - aus der Informatikperspektive

Weiter zu: Der Bernstein-Vazirani-Algorithmus: Mathematische Betrachtung

Diese Seite teilen

Funktionswert der auf das erste Register angewendeten Funktion $f (x_{1}, \dots, x_{n})$	Anfangszustand des zweiten Registers	Endzustand des zweiten Registers (gesteuert durch $f$ )
0	$\| 0 ⟩$
0	$\| 1 ⟩$
1	$\| 0 ⟩$
1	$\| 1 ⟩$
0	$\| 0 ⟩ - \| 1 ⟩$
1	$\| 0 ⟩ - \| 1 ⟩$

Funktionswert $f (x_{1}, \dots, x_{n})$ (wirkt auf 1. Register)	Anfangszustand des 2. Registers	Endzustand des 2. Registers (gesteuert durch $f$ )
0	$\| 0 ⟩$	$\| 0 ⟩$
0	$\| 1 ⟩$	$\| 1 ⟩$
1	$\| 0 ⟩$	$\| 1 ⟩$
1	$\| 1 ⟩$	$\| 0 ⟩$
0	$\| 0 ⟩ - \| 1 ⟩$	$\| 0 ⟩ - \| 1 ⟩$
1	$\| 0 ⟩ - \| 1 ⟩$	$\| 1 ⟩ - \| 0 ⟩ = - (\| 0 ⟩ - \| 1 ⟩)$