Quanten-Fourier-Transformation
Das Gegenstück zur FFT, nur auf einem Quantenregister — exponentiell schneller, aber das Ergebnis lässt sich nicht auslesen.
Während die klassische schnelle Fourier-Transformation in der Größenordnung von N log N Operationen benötigt, schafft die Quantenvariante das im Quadrat der Qubit-Zahl — also exponentiell weniger Schritte, gemessen an der Datenmenge. Der Haken: Die Transformation hinterlässt Amplituden, die sich nicht inspizieren lassen; man kann nur messen, und dabei erhält man ein einziges Ergebnis.
Der Nutzen entsteht, wenn man etwas über eine Periodizität wissen will statt über einzelne Werte. Genau das nutzt Shors Algorithmus: Faktorisierung wird darauf reduziert, die Periode einer Funktion zu finden, und dort liefert die Transformation nach wenigen Durchläufen mit hoher Wahrscheinlichkeit die Antwort.