Der Deutsch-Algorithmus: Aus der Informatikperspektive
Übersicht
Auf einen Blick
Schlüsselbegriffe: Algorithmus, Deutsch-Algorithmus, Superposition
Alter: 16-18 Jahre
Erforderliche Kenntnisse/Fähigkeiten: keine spezifischen Vorkenntnisse erforderlich
Zeitrahmen: 40 Minuten
Autor: Sam Robbins (UK)
Lernziele
Ziel der Stunde ist es, den Deutsch-Algorithmus zur Untersuchung einer unbekannten Funktion kennenzulernen. Dabei wird deutlich, dass klassische Verfahren weder die konkrete Funktion noch ihre Funktionsklasse mit weniger als zwei Abfragen bestimmen können, während ein Quantenverfahren bereits mit einer einzigen Abfrage entscheiden kann, ob die Funktion konstant oder balanciert ist. Die Stunde führt in die Idee ein, Superposition zu nutzen, um mehrere Zustände gleichzeitig zu untersuchen. Dieses Prinzip bildet die Grundlage aller späteren Algorithmen in diesem Kurs.
Unterrichtsplan
| Zeit in Minuten | Unterrichtsphase | Aktivität | Material |
|---|---|---|---|
| 0–10 | Aufgabe 1 | Die Schüler*innen experimentieren mit der Tabellenkalkulation und notieren eine Strategie, mit der sich die unbekannte Funktion bestimmen lässt. | Arbeitsblatt + Tabellenkalkulationswerkzeug |
| 10-20 | Aufgabe 2 | Die Schüler*innen experimentieren mit der Tabellenkalkulation und notieren eine Strategie, mit der sich die Funktionsklasse der unbekannten Funktion bestimmen lässt. | Arbeitsblatt + Tabellenkalkulationswerkzeug |
| 20-30 | Aufgabe 3 | Die Schüler*innen nutzen die Tabellenkalkulation, um zu bestimmen, welcher Schaltkreis zu welcher Funktion gehört. | Arbeitsblatt + Tabellenkalkulationswerkzeug |
| 30-40 | Aufgabe 4 | Die Schüler*innen nutzen die Tabellenkalkulation bzw. den Quantum Composer[1], um die Strategie hinter dem Deutsch-Algorithmus zu erschließen. | Arbeitsblatt + Tabellenkalkulationswerkzeug / Quantum Composer |
Sie können das Arbeitsblatt (als PDF und DOCX) sowie die Tabellenkalkulation (als Excel-Datei) am Ende der Seite herunterladen.
In dieser Stunde wird ein Tabellenkalkulationswerkzeug mit dem Namen DeutschAlgorithm.xlsm verwendet, das eingebettete Makros enthält. Je nach Sicherheitseinstellungen Ihres Systems werden diese Makros beim Herunterladen der Datei möglicherweise blockiert. Um sie wieder zu aktivieren, klicken Sie mit der rechten Maustaste auf die Datei, wählen „Eigenschaften“ und anschließend „Zulassen“ bzw. „Blockierung aufheben“, wie unten dargestellt:
Konzeptionelle Einführung
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.
Aufgaben und Hinweise für Lehrkräfte
Das Problem
Stellen Sie sich vor, wir haben eine Blackbox-Funktion f, die als Eingabe ein einzelnes klassisches Bit (0 oder 1) erhält und als Ausgabe wiederum ein einzelnes klassisches Bit (0 oder 1) liefert. Insgesamt gibt es vier mögliche Funktionen, die sich in der Blackbox befinden könnten:
| f1(0)=0 f1(1)=0 | f2(0)=1 f2(1)=1 | f3(0)=0 f3(1)=1 | f4(0)=1 f4(1)=0 |
Das Problem besteht darin, dass wir nicht wissen, welche dieser Funktionen sich in der Blackbox befindet. Unsere Aufgabe ist es, dies allein dadurch herauszufinden, dass wir die Eingaben der Blackbox verändern und die Ausgaben beobachten.
Aufgabe 1
Die Tabellenkalkulationsdatei „Deutsch Functions“ zeigt, wie diese vier Funktionen arbeiten, und enthält außerdem einen Generator für eine unbekannte Funktion (mystery function). Klicken Sie auf die Schaltfläche „Generate mystery function“, um zufällig eine der vier Funktionen auszuwählen. Wenn Sie die Eingabe in Zelle B12 verändern, wird die Ausgabe der unbekannten Funktion in Zelle E12 angezeigt. Wie können Sie durch Variation der Eingaben herausfinden, welche unbekannte Funktion vorliegt, und wie viele Abfragen sind dafür nötig? Begründen Sie Ihre Antwort.
Die Schüler*innen sollten erkennen, dass es unmöglich ist, die Funktion mit weniger als zwei Abfragen zu bestimmen. Beachten Sie, dass die Schülerinnen und Schüler ihre Vermutungen jeweils überprüfen können, indem sie auf die Schaltfläche „Reveal Function“ klicken.
Konstante Funktionen und balancierte Funktionen
Nehmen wir nun an, wir ordnen die vier möglichen Funktionen in zwei Klassen ein:
| Konstante Funktionen | Balancierte Functionen | ||
| f1(0)=0 f1(1)=0 | f2(0)=1 f2(1)=1 | f3(0)=0 f3(1)=1 | f4(0)=1 f4(1)=0 |
Aufgabe 2
Verwenden Sie erneut die Tabellenkalkulation: Wie viele Abfragen sind nötig, um festzustellen, ob die unbekannte Funktion konstant oder balanciert ist? Wie verhält sich dies im Vergleich dazu, die konkrete Funktion selbst zu bestimmen? Begründen Sie Ihre Antwort.
Die Antwort lautet auch hier, dass es unmöglich ist, die Funktion mit weniger als zwei Abfragen zu bestimmen.
Zusammenfassung der klassischen Ergebnisse
Wir haben gesehen, dass in beiden Fällen zwei Abfragen erforderlich sind, um mit klassischen Suchverfahren das gewünschte Ergebnis zu erhalten. Im ersten Fall – also bei der Bestimmung der konkreten Funktion – würde auch ein Quantencomputer zwei Abfragen benötigen. Im zweiten Fall hingegen – also bei der Entscheidung, ob die Funktion konstant oder balanciert ist – kann Quantencomputing eine deutliche Verbesserung ermöglichen.
Konstruktion der Funktion auf einem Quantencomputer
Der erste Schritt bei der Untersuchung dieses Problems auf einem Quantencomputer besteht darin, die Funktionen mithilfe von Quantengattern zu konstruieren. Es ist möglich, alle vier Funktionen durch Kombinationen von NOT-Gattern, CNOT-Gattern oder auch ganz ohne Gatter darzustellen.
Dazu benötigen wir zwei Qubits: q0, das die Eingabe der Funktion aufnimmt, und q1, das die Ausgabe liefert (nachdem es zunächst in den Zustand gesetzt wurde).
Verwenden Sie den IBM Quantum Composer, um die folgenden vier Schaltkreise zu erstellen:
Beispiel
Für den Schaltkreis (a) gilt: Wenn wir das Eingangsqubit q0 auf den Zustand setzen und das Ausgangsqubit q1 zunächst ebenfalls auf den Zustand , dann sehen wir, dass der Endzustand von q1 ebenfalls der Zustand ist (da das CNOT-Gatter nicht ausgelöst wird):
Das bedeutet: Eine Eingabe von 0 wird von der Funktion auf eine Ausgabe von 0 abgebildet.
Wenn wir nun das Eingangsqubit q0 auf den Zustand setzen, sehen wir, dass der Endzustand von q1 nun der Zustand ist (da das CNOT-Gatter jetzt ausgelöst wird und den Zustand von q1 invertiert):
Das bedeutet: Eine Eingabe von 1 wird von der Funktion auf eine Ausgabe von 1 abgebildet.
Diese Zuordnung entspricht der Funktion f3 (der ersten der balancierten Funktionen).
Aufgabe 3
Die Tabellenkalkulationsdatei „Quantum Circuits“ enthält die vier dargestellten Schaltkreise. Der Eingabezustand von q0 ist in den fett gedruckten blauen Zellen dargestellt, der Endzustand des Ausgangsqubits q1 in den fett gedruckten roten Zellen. Bestimmen Sie durch Variation der Anfangszustände von q0 und durch Beobachtung der Endzustände von q1, welcher Funktion (f1, f2, f3 und f4) die Schaltkreise (b), (c) und (d) jeweils entsprechen. Tragen Sie Ihre Antworten unten ein:
a) f3 ; b) f1 ; c) f2 ; d) f4
Bestimmung der unbekannten Funktion mit einem Quantencomputer
Die Technik, die wir hier verwenden, nutzt Superposition durch die Anwendung von Hadamard-Gattern. Dies ist einer der wichtigsten Tricks des Quantencomputings, und wir werden ihn in jedem Quanten-Suchalgorithmus dieses Kurses wiedersehen.
Erstellen Sie den folgenden Schaltkreis im IBM Quantum Composer:
Beachten Sie, dass das NOT-Gatter verwendet wird, um den Zustand von q1 auf zu initialisieren, während das Fehlen eines NOT-Gatters auf q0 bedeutet, dass dieses Qubit auf den Zustand initialisiert wird.
Aufgabe 4
Diese Aufgabe kann entweder mit dem Quantum Composer oder mit der Tabellenkalkulationsdatei „Quantum Circuits with Hadamards“ bearbeitet werden. Stellen Sie q0 auf den Zustand ein und q1 auf den Zustand . Fügen Sie anschließend nacheinander die Schaltkreise für f1, f2, f3 und f4 in den Abschnitt des Schaltkreises ein, der mit der Blackbox f gekennzeichnet ist.
Betrachten Sie die Werte, die q0 nach der Messung annimmt. Wie kann diese Information dazu genutzt werden, zu bestimmen, ob eine Funktion balanciert oder konstant ist? Wie viele Abfragen sind nun erforderlich, um dies zu zeigen? Tragen Sie Ihre Antworten unten ein:
Der Endzustand des Eingangsqubits ist bei beiden konstanten Funktionen und bei beiden balancierten Funktionen . Dadurch konnten wir bereits mit einer einzigen Abfrage bestimmen, zu welcher der beiden Funktionsklassen die unbekannte Funktion gehört.
Die zentralen Lernpunkte, denen die Schülerinnen und Schüler im weiteren Verlauf des Kurses erneut begegnen werden, sind:
- (1) Hadamard-Gatter ermöglichen es (durch die Erzeugung einer Superposition), Informationen über mehrere Eingaben gleichzeitig zu gewinnen.
- (2) Die entscheidende Information wird durch die Betrachtung des Endzustands des Eingangsqubits gewonnen.
Zusammenfassung der Quantenergebnisse
Durch die Nutzung von Superposition konnten wir bestimmen, ob die Funktion konstant oder balanciert ist, und dafür nur eine einzige Abfrage statt zwei benötigen. Damit kann ein Quantencomputer dieses Problem mit weniger Abfragen lösen als ein klassischer Computer. Der Deutsch-Algorithmus macht außerdem zwei wichtige Punkte deutlich:
- Quantencomputer sind nicht in jeder Situation klassischen Computern überlegen. Wie wir hier gesehen haben, hilft der Quantenalgorithmus nur bei der Unterscheidung zwischen konstanten und balancierten Funktionen, nicht jedoch bei der Bestimmung, welche konkrete Funktion sich in der Blackbox befindet. Ob ein Problem durch einen Quantencomputer effizienter gelöst werden kann, muss daher immer sorgfältig geprüft werden.
- Die Lösung dieses Problems wurde durch die Betrachtung des Eingangsqubits gefunden, nicht durch die Betrachtung des Ausgangsqubits. Die Information wurde im Eingangsqubit gewonnen, während im Ausgangsqubit Information verloren ging. Quantencomputing ist häufig mit solchen Trade-offs verbunden, und Lösungen müssen oft an unerwarteten Stellen gesucht werden.
Obwohl das Deutsch-Problem ein etwas künstliches Beispiel ist, zeigte es das Potenzial von Quantencomputern und ebnete den Weg für weitere, inhaltlich bedeutendere Quantenalgorithmen, die wir in den nächsten Lektionen kennenlernen werden.
Diese Seite teilen
