Die Quanten-Fouriertransformation

Ein wesentlicher Baustein vieler Algorithmen auf einem Quantencomputer
ist die diskrete Fouriertransformation. Diese läßt sich auf einem
Quantencomputer mit exponentiellem Geschwindigkeitszuwachs gegenüber
der klassischen schnellen Fouriertransformation (FFT) realisieren, und
das ist der Schlüssel zum Verständnis der Effizienz vieler
Quantenalgorithmen.

In dem Vortrag wird die Fouriertransformation auf endlichen abelschen
Gruppen vorgestellt und anhand von Beispielen erläutert. Bei dieser
Gelegenheit wird auch kurz auf den Zusammenhang mit der (den meisten
wohl wesentlich vertrauteren) Fourierentwicklung periodischer
Funktionen nach harmonischen Funktionen (sin, cos)
eingegangen. Schließlich wird der Algorithmus der schnellen
Fouriertransformation und dessen Implementierung auf einem
Quantencomputer dargestellt.