Quantencomputing: Grover-Algorithmus und finite Elemente im Überblick

Inhaltsverzeichnis

So erstaunlich und nützlich Quantenalgorithmen auch sind, den Titel "The most important quantum algorithm of our lifetime" wird vielleicht einmal ein anderer bekommen. Die Rede ist vom Grover-Algorithmus.

Im Jahr 1994 entdeckte der indisch-amerikanische Informatiker Lov Grover die ultimative Quantenversion für sämtliche Brute-Force-Strategien. Ähnlich wie die Fast Fourier Transform besitzt der Grover-Algorithmus einen moderaten quadratischen Vorteil gegenüber herkömmlichen Verfahren.

Mehr zu Quantencomputern

• Quantencomputing: Einstieg in die Welt der Quantenalgorithmen
• Quantenalgorithmen: Vom Grover-Algorithmus zu den finiten Elementen
• Sechs technische Konzepte für Quantencomputer
• Verschlüsselungssysteme: Kryptoagil gegen hackende Quantencomputer
• Quantencomputer: Wie man mit Quantengattern programmiert
• Die Mathematik von Qubits erklärt
• QuNET-Projekt baut Quantenkommunikation auf
• Eine Einführung in maschinelles Lernen mit Quantencomputern
• Quanten-Annealer – Vorbote des Quantencomputers
• Was Fujitsus Digital Annealer von Quantencomputern unterscheidet
• Eine praktische Einführung ins Quanten-Annealing

Eine Kette von Hadamard-Gattern über alle Qubits erzeugt zunächst eine Überlagerung aller möglichen Lösungskandidaten des Problems in Form von Bitsequenzen. Danach führt der Algorithmus in mehreren Durchläufen die Unterroutine Orakel + Diffusionsoperator aus. Das Orakel ist einfach nur ein Test, ob ein Lösungskandidat tatsächlich eine Lösung der Aufgabe darstellt. Die Prüfroutine verkehrt dabei die Anteile beziehungsweise die Amplituden der korrekten Lösungen in der Überlagerung ins Negative. Die anderen falschen Anteile bleiben unverändert.

Das war die Leseprobe unseres heise-Plus-Artikels "Quantencomputing: Grover-Algorithmus und finite Elemente im Überblick". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.