Quantenalgorithmus
Ein Rechenverfahren, das Quanteneffekte wie Superposition und Verschränkung nutzt, um bestimmte Probleme schneller zu lösen als klassische Algorithmen.
Quantenalgorithmen nutzen die besonderen Eigenschaften von Qubits, um Berechnungen durchzuführen, die auf klassischen Computern unpraktikabel langsam wären. Die Beschleunigung kommt aus zwei Quellen: Superposition erlaubt die gleichzeitige Verarbeitung vieler Zustände, und Interferenz ermöglicht es, richtige Antworten zu verstärken und falsche auszulöschen.
Die bekanntesten Quantenalgorithmen: Shors Algorithmus (1994) für Primfaktorzerlegung mit exponentieller Beschleunigung, Grovers Algorithmus (1996) für die Suche in unsortierten Datenbanken mit quadratischer Beschleunigung, und der VQE (Variational Quantum Eigensolver) für die Berechnung molekularer Grundzustände.
Neuere Entwicklungen konzentrieren sich auf NISQ-kompatible Algorithmen, die mit der fehlerbehafteten Hardware der aktuellen Generation funktionieren. Variationelle Algorithmen wie QAOA (Quantum Approximate Optimization Algorithm) kombinieren Quanten- und klassische Berechnung: Der Quantencomputer erzeugt Lösungskandidaten, ein klassischer Computer bewertet und optimiert die Parameter.
Die Suche nach neuen Quantenalgorithmen ist ein aktives Forschungsfeld. Für viele wichtige Probleme (NP-vollständige Probleme wie das Handlungsreisendenproblem) ist bisher kein Quantenalgorithmus bekannt, der eine exponentielle Beschleunigung bietet. Quantencomputer sind leistungsfähig, aber sie sind keine Wundermaschinen.
Gerade die Quantenalgorithmen entscheiden darüber, wofür ein Quantencomputer überhaupt taugt, denn die Hardware allein bringt keinen Vorteil. Erst ein cleveres Verfahren, das Superposition und Interferenz gezielt ausnutzt, verwandelt die fragilen Qubits in echte Rechenkraft. Dabei zeigt sich, dass der Quantencomputer kein universeller Beschleuniger ist: Für viele schwierige Probleme kennt man bislang keinen Algorithmus, der einen entscheidenden Vorsprung böte. Genau diese Lücke macht die Suche nach neuen Quantenalgorithmen zu einem der spannendsten Felder der Informatik und hält die Erwartung in Schach, das Quantenrechnen werde einfach alles über Nacht lösen.
Verwandte Begriffe
Bücher zum Thema
