Quantencomputing: Grover-Algorithmus und finite Elemente im Überblick
Der Grover-Algorithmus und seine Weiterentwicklungen können Aufgaben schneller berechnen als klassische Verfahren. Dafür existieren jedoch kaum Quantencomputer.
(Bild: AdobeStock; agsandrew)
- Jens Marre
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.
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.
Immer mehr Wissen. Das digitale Abo für IT und Technik.
Karrierewechsel: Warum sich ein Informatikstudium auch für Quereinsteiger lohnt
Elektroauto Mercedes EQA 300 4Matic im Test: Fährt gut, lädt gemächlich
Virtualisierungsoftware: Alternativen zu VMware
CPU-Guide 2024: Notebook-Prozessoren von AMD, Apple und Intel im Vergleich
Günstigerer Strom für die Wärmepumpe: Was Sie jetzt wissen müssen
Elektroauto MG4 Trophy im Test: Bestseller mit Batterie-Upgrade
Immer mehr Wissen. Das digitale Abo für IT und Technik.
Karrierewechsel: Warum sich ein Informatikstudium auch für Quereinsteiger lohnt
Elektroauto Mercedes EQA 300 4Matic im Test: Fährt gut, lädt gemächlich
Virtualisierungsoftware: Alternativen zu VMware
CPU-Guide 2024: Notebook-Prozessoren von AMD, Apple und Intel im Vergleich
Günstigerer Strom für die Wärmepumpe: Was Sie jetzt wissen müssen