Quantenalgorithmus

Ein Quantenalgorithmus ist ein Algorithmus, welcher auf Quantencomputern ausgeführt werden kann. Anders als analytische Algorithmen erzeugen Quantenalgorithmen, bei denen es sich um probabilistischen Algorithmen handelt, keine eindeutigen Ergebnisse, sondern geben Wahrscheinlichkeiten für bestimmte Ergebnisse an. Durch wiederholtes Anwenden des Algorithmus kann die Fehlerwahrscheinlichkeit beliebig klein werden. Ist die anfängliche Erfolgswahrscheinlichkeit groß genug, reichen wenige Wiederholungen aus.

Für die Berechnung werden verschränkte Zustände von Quanten verwendet, bei denen sich verschiedene, gleichzeitig existierende quantenmechanische Zustände der Teilsysteme überlagern. Die Variablen der Algorithmen werden in Qubits gespeichert.

Kategorien

Die bisher gefundenen Algorithmen für Quantencomputer lassen sich grob in drei Kategorien einteilen:

• Algorithmen, die auf der Quanten-Fouriertransformation beruhen. Darunter fällt auch der wohl berühmteste Algorithmus für Quantencomputer, der Shor-Algorithmus zur Faktorisierung großer ganzer Zahlen, der für die Primzahlzerlegung in der Kryptographie eine wichtige Rolle spielt. Der Zeitaufwand ist dabei polynomiell in der Anzahl der Ziffern. Im Gegensatz dazu benötigt der beste zurzeit bekannte klassische Algorithmus, das Zahlkörpersieb, superpolynomiell (aber subexponentiell) viel Zeit. Die Bedeutung von Shors Algorithmus beruht auf der Tatsache, dass die Sicherheit der asymmetrischen Verschlüsselungsverfahren wie RSA darauf basiert, dass keine hinreichend effizienten klassischen Algorithmen zur Faktorisierung großer Zahlen bekannt sind.
• Quanten-Suchalgorithmen. Hierzu gehören der Grover-Algorithmus und Varianten davon. Er dient der effizienten Suche in einem unsortierten Array. Ein gewöhnlicher Computer muss sich bei $n$ Einträgen im schlimmsten Fall alle Einträge ansehen (d. h. vergleichen), klassisch ist dieses Problem also in ${\mathcal {O}}(n)$ Rechenschritten lösbar. Auf einem Quantencomputer kann man dies mit dem Grover-Algorithmus in lediglich ${\mathcal {O}}\left({\sqrt {n}}\right)$ Operationen erledigen. Diese Schranke ist scharf, das heißt, kein Quantenalgorithmus kann dieses Problem in (asymptotisch) weniger Operationen lösen. Daraus folgt, dass im Allgemeinen kein exponentieller Geschwindigkeitsvorteil bei Verwendung von Quantenalgorithmen zu erwarten ist.
• Quanten-Simulation. Um quantenmechanische Systeme zu simulieren, bietet es sich an, wieder quantenmechanische Systeme zu benutzen. Mit einem geeigneten Satz von Quantengattern in einer Quantenschaltung lässt sich jeder Hamiltonian darstellen. Algorithmen dieser Art würden in der Quantenchemie die Simulation von Molekülen erlauben, bei denen mit heutigen Mitteln grobe Näherungen erforderlich sind.

Beispiele

Bekannte Beispiele für einen Quantenalgorithmus sind der Algorithmus von Deutsch beziehungsweise dessen Erweiterung der Deutsch-Jozsa-Algorithmus, die zwar nicht von großem praktischem Nutzen sind, aber als erste Quantenalgorithmen schneller arbeiteten als klassische Algorithmen und somit das Potential von Quantencomputern deutlich machen konnten.

Literatur

• Jozef Gruska: Quantum Computing, McGraw-Hill, 1999
• Matthias Homeister: Quantum Computing verstehen: Grundlagen – Anwendungen – Perspektiven, Springer-Verlag, 2015, ISBN 978-3658104559

Weblinks

• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2001
• Helmut Alt: Seminar über Algorithmen für Quantencomputer, Freie Universität Berlin