Technologien

Was ist der Grover-Algorithmus?

Definition: Der Grover-Algorithmus ist ein sehr schneller Quanten-Suchalgorithmus. Der Algorithmus bietet im Gegensatz zu anderen klassischen Algorithmen eine quadratische Beschleunigung für unstrukturierte Suchen. Er wird für die Suche in einer unsortierten Datenbank verwendet. Er findet mit hoher Wahrscheinlichkeit die einzige Eingabe für eine Black-Box-Funktion, die einen bestimmten Ausgabewert erzeugt, mit nur O√N Auswertungen der Funktion, wobei N die Größe der Domäne der Funktion ist.

Erläuterung

Erläuterungen zum 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.

Lösungen

Lösungen

Blogbeiträge

Blogbeiträge

Verwandte Produkte

Verwandte Produkte

Kontakt

Ihre Fragen beantworten wir sehr gerne.

Wie können wir Ihnen helfen?

Sprechen Sie mit einem unserer Spezialisten und erfahren Sie, wie Utimaco Sie unterstützen kann.
Sie haben zwei verschiedene Arten von Downloads ausgewählt, so dass Sie verschiedene Formulare absenden müssen, die Sie über die beiden Tabs auswählen können.

Ihre Download-Sammlung:

    Direkt nach dem Absenden des Formulars erhalten Sie die Links zu den von Ihnen ausgewählten Downloads.

    Ihre Download-Sammlung:

      Für diese Art von Dokumenten muss Ihre E-Mail Adresse verifiziert werden. Sie erhalten die Links für die von Ihnen ausgewählten Downloads per E-Mail, nachdem Sie das unten stehende Formular abgeschickt haben.

      Downloads von Utimaco

      Besuchen Sie unseren Download-Bereich und wählen Sie aus: Broschüren, Datenblätter, White-Papers und vieles mehr. 

      Fast alle können Sie direkt ansehen und speichern (indem Sie auf den Download-Button klicken).

      Für einige Dokumente muss zunächst Ihre E-Mail-Adresse verifiziert werden. Der Button enthält dann ein E-Mail-Symbol.

      Download via e-mail

       

      Der Klick auf einen solchen Button öffnet ein Online-Formular, das Sie bitte ausfüllen und abschicken. Sie können mehrere Downloads dieser Art sammeln und die Links per E-Mail erhalten, indem Sie nur ein Formular für alle gewählten Downloads ausfüllen. Ihre aktuelle Sammlung ist leer.