Quantenalgorithmen – Eine kurze Einführung

Inhalt
Deutsch-Algorithmus
Deutsch‑Jozsa‑Algorithmus 
Der Shor-Algorithmus 
Der Grover-Algorithmus  

Computer lösen Probleme mithilfe von Algorithmen. Man kann sich einen Algorithmus als eine Reihe von Anweisungen vorstellen. Der wesentliche Unterschied zwischen klassischen Algorithmen, die auf herkömmlichen Computern laufen, und Quantenalgorithmen liegt in der Art und Weise, wie sie Informationen verarbeiten.

Klassische Computer verwenden Bits, die entweder 0 oder 1 sein können. Sie verarbeiten Daten sequenziell, d. h. sie lösen einen Schritt nach dem anderen. Selbst Supercomputer, die Algorithmen parallel auf mehreren Prozessoren ausführen, führen diese Algorithmen dennoch Schritt für Schritt aus. Klassische Algorithmen sind für viele Aufgaben sehr effizient, aber bei komplexen Problemen wie dem Knacken von Verschlüsselungen oder der Simulation großer Moleküle geraten sie an ihre Grenzen, da die Laufzeit der Programme einfach zu groß wird.

Quantencomputer verwenden Qubits, die sich in einer Superposition zweier Zustände befinden können. Dadurch können Quantenalgorithmen Berechnungsschritte gleichzeitig verarbeiten, wodurch sie bestimmte Arten von Problemen viel schneller lösen. Eine weitere wichtige Eigenschaft der Quantenphysik ist die Verschränkung. Sie erlaubt es, Qubits miteinander zu verknüpfen, was wiederum die Recheneffizienz erhöht.

Deutsch‑Algorithmus

Was er macht  
Man stelle sich eine Funktion ${\displaystyle f}$ vor, die ein einzelnes Bit (0 oder 1) als Eingabe erhält und ein einzelnes Bit als Ausgabe liefert. Es gibt vier mögliche Funktionen dieser Art: zwei konstante Funktionen ( ${\displaystyle f(0)=f(1)=0}$ oder ${\displaystyle f(0)=f(1)=1}$) und zwei sogenannte ausgeglichene Funktionen ${\displaystyle \left(f\right(0)\ne f(1\left)\right)}$. Der Deutsch‑Algorithmus bestimmt, ob die Funktion ${\displaystyle f}$ konstant oder ausgeglichen ist.

Quanten vs. klassisch 
Um klassisch festzustellen, ob eine Funktion konstant oder ausgeglichen ist, müsste man die Funktion für beide möglichen Eingaben auswerten, also ${\displaystyle f\left(0\right)}$ und ${\displaystyle f\left(1\right)}$. Dies erfordert zwei Funktionsauswertungen. Der Deutsch‑Algorithmus erzielt dasselbe Ergebnis jedoch mit nur einer einzigen quantenmechanischen Abfrage der Funktion.

Deutsch‑Jozsa‑Algorithmus

Was er macht 
Man stelle sich eine Funktion ${\displaystyle f}$ vor, die ${\displaystyle n}$ Bits als Eingabe nimmt und ein einzelnes Bit als Ausgabe erzeugt. Der Deutsch‑Jozsa‑Algorithmus bestimmt, ob die Funktion konstant ist (das bedeutet, sie gibt für alle möglichen Eingaben dasselbe Bit aus) oder ausgeglichen (das bedeutet, sie gibt für genau die Hälfte der Eingaben den Wert 0 und für die andere Hälfte den Wert 1 aus).

Quanten vs. klassisch 
Um festzustellen, ob die Funktion konstant oder ausgeglichen ist, müsste man die Funktion für alle möglichen Eingaben auswerten. Da es ${\displaystyle 2^n}$ mögliche Eingaben gibt, erfordert dies ${\displaystyle 2^n}$ Funktionsauswertungen. Wenn die Funktion ausgeglichen ist, kann man Glück haben und dies nach weniger Versuchen feststellen, aber im ungünstigsten Fall muss man die Hälfte der Eingaben überprüfen. Der Deutsch‑Jozsa‑Algorithmus kann die Art der Funktion jedoch mit nur einer quantenmechanischen Abfrage der Funktion bestimmen, unabhängig von der Anzahl der Eingabebits ${\displaystyle n}$.

Der Shor-Algorithmus

Was er macht 
Der Shor-Algorithmus ist ein Quantenalgorithmus, der auf sehr effiziente Weise die Primfaktoren großer natürlicher Zahlen findet. Dieses Problem ist für seine rechnerische Schwierigkeit auf klassischen Computern bekannt. Daher wird das Prinzip der Primfaktorzerlegung häufig für Verschlüsselungsmethoden wie die RSA-Verschlüsselung verwendet (RSA steht für die Erfinder der Methode: die Mathematiker Rivest, Shamir und Adleman). Ein Quantencomputer, der den Shor-Algorithmus nutzt, um große Zahlen effizient zu faktorisieren, stellt eine erhebliche Bedrohung für aktuelle kryptografische Systeme dar.

Quanten vs. klassisch 
Der wesentliche Unterschied liegt in der Periodenfindung, d. h. in dem Schritt, in dem ein oder mehrere periodische Muster in den Faktoren der Faktorisierung gefunden werden müssen (siehe auch Das Unknackbare knacken: Der Shor-Algorithmus). Klassische Algorithmen zur Periodenfindung erfordern eine exponentielle Laufzeit, was bedeutet, dass die Zeit, die zum Faktorisieren einer gegebenen Zahl benötigt wird, exponentiell mit der Größe der Zahl zunimmt. Bei sehr großen Zahlen wird die Rechenzeit einfach so absurd groß, dass eine Berechnung auf einem klassischen Computer nicht mehr sinnvoll ist. Der Shor-Algorithmus kann die Periode jedoch in einer polynomialen Rechenzeit finden: Das ist eine drastische Beschleunigung.

Der Grover-Algorithmus

Der Grover-Algorithmus ist ein Quantenalgorithmus zum Durchsuchen einer unsortierten Datenbank. Er führt zu einer erheblichen Beschleunigung der Rechenzeit für diese Art von Aufgaben.

Quanten vs. klassisch 
In der klassischen Informatik erfordert die Suche nach einem Element in einer unsortierten Datenbank mit N Einträgen die Überprüfung von im Durchschnitt N/2 Einträgen. Im schlimmsten Fall müssen möglicherweise alle N Einträge (genauer gesagt N – 1) überprüft werden. Der Grover-Algorithmus benötigt jedoch nur etwa √N Schritte, um den gesuchten Eintrag zu finden. Dies ist eine Beschleunigung, die mit zunehmender Größe der Datenbank immer relevanter wird.

Arbeitsblatt: Den Grover-Algorithmus verstehen

Ziel ist es, den Grundgedanken und die Funktionsweise des Grover-Algorithmus zu erfassen, insbesondere wie er die Suche in einer unsortierten Liste von Elementen beschleunigen kann. Für diese Aufgabe müsst ihr zu fünft sein.

Arbeitsblatt mit Lösungen: docx oder als PDF.
Arbeitsblatt für Schüler*innen: docx oder als PDF.