Was ist der Grover-Algorithmus?

Einer der vielen Vorteile eines Quantencomputers gegenüber einem klassischen Computer ist seine überlegene Geschwindigkeit beim Durchsuchen von Datenbanken. Der Grover-Algorithmus ist ein Beispiel dafür.

Lov Grover, ein indisch-amerikanischer Informatiker, veröffentlichte 1996 ein Paper, das ihn in der Quanteninformatik berühmt machte. Seine Forschungsarbeit befasste sich mit der Optimierung unstrukturierter Suchprobleme.

Grover schlug vor, einen als Amplitudenverstärkung bekannten Trick in der Quanteninformatik anzuwenden, um die benötigte Zeit zum Auffinden des Gewinners w in einer unstrukturierten Datenbank erheblich zu reduzieren. Grover ließ sich beim Schreiben seines Papers von mehreren Dingen inspirieren. Laut Grover „bewegen“ sich Quantensysteme zu Punkten mit niedrigem Potenzial. Das System sucht nach dem Punkt mit dem niedrigsten Potenzial, damit der Zustand eine größere Wahrscheinlichkeitsamplitude erhält.

Zweitens verwendete er die Schrödinger-Gleichung (die das zukünftige Verhalten eines dynamischen Systems vorhersagt). Die Gleichung basiert auf der Wellenfunktion und sagt Ereignisse oder Ergebnisse analytisch und präzise voraus). Außerdem fand er unitäre Versionen seiner diskretisierten Evolutionsmatrizen. Die Auswahl der Phase und die anschließende Diffusion eines Anfangs- oder Versuchsquantenzustands sind die beiden wesentlichen Elemente des Grover-Algorithmus. Grover verwendet metrikbasierte markierte Zustände nach Markov, die jedoch nicht unitär sind. (Eine Markov-Matrix, auch bekannt als stochastische Matrix, wird verwendet, um die Schritte in einer Markov-Kette auszudrücken. Jeder Eintrag in der Übergangsmatrix repräsentiert die Wahrscheinlichkeit eines Ergebnisses.)

Nach Grover kann ein Suchvorgang durch eine Funktion f(x) dargestellt werden, die auf das Element x wirkt. Wenn die Suche erfolgreich war, ist f(x)=1. Wenn das Element x nicht gefunden wird, ist f(x)=0. Mithilfe des Quantencomputers kann das unstrukturierte Suchproblem in O√N gelöst werden, was im Vergleich zu klassischen Suchalgorithmen sehr effizient ist.

Ein vereinfachtes Beispiel des Grover-Algorithmus:
Angenommen, Sie möchten einen bestimmten Schlüssel unter N Schlüsseln finden, die sich zufällig in einer Schachtel befinden.
Um den gesuchten Schlüssel zu finden, muss man die Schachtel im Durchschnitt N/2-mal durchsuchen, im schlimmsten Fall N-mal. Mithilfe der Quantentechnologie kann dieser Prozess auf √N-mal beschleunigt werden.
Bei einer Schachtel mit 100 Schlüsseln würde das bedeuten, nur mehr 10 statt 50–100 Schlüssel auszuprobieren.

Ein weiterer Vorteil von Grovers Algorithmus ist, dass er mit nur O(√N log N) Gattern arbeitet. Grover verwendet das Konzept des Orakels, das einem Blackbox-Vorgang gleicht, bei dem n Bits binär eingegeben und m Bits erzeugt werden. Ebenso geben seine Diffusionsoperatoren eine Inversion um den Mittelwert, sodass die unendlich skalierten kleinen Schritte messbar werden.

Anwendungen des Grover-Algorithmus

Der Grover-Algorithmus kann Probleme lösen, die mit der Eliminierung von Mittelwert und Median für eine Menge von Zahlen verbunden sind. Außerdem kann er Kollisionsprobleme lösen:

• Er kann NP-vollständige Probleme lösen, indem er eine erschöpfende Suche nach möglichen Lösungen durchführt
• Der Algorithmus hilft, unstrukturierte Suchprobleme in quadratischer Reihenfolge zu beschleunigen und die Laufzeit vieler anderer Algorithmen zu verkürzen.
• Zusätzlich zur Amplitudenverstärkung nutzt er Phaseninterferenz und Superposition, um die Position des zu suchenden Elements zu bestimmen.

Utimaco bietet quantenresistente Lösungen, die es Unternehmen ermöglichen, ihre Systeme gegen Angriffe auf Quantencomputer und die Ausführung des Grover-Algorithmus zum Auffinden kryptografischer Schlüssel zu verteidigen. Unsere umfangreichen Investitionen in die Post-Quanten-Kryptografie haben zu NIST- und BSI-zertifizierten PQC-Algorithmen geführt, die bereits in unseren Cybersicherheitslösungen implementiert werden können.