Kvant-fouriertransform
Motsvarigheten till FFT fast på ett kvantregister — exponentiellt snabbare, men resultatet går inte att läsa ut.
Där den klassiska snabba fouriertransformen behöver storleksordningen N log N operationer klarar kvantvarianten det på kvadraten av antalet qubitar, alltså exponentiellt färre steg räknat i datamängden. Haken är att transformen lämnar amplituder som inte går att inspektera; man kan bara mäta, och då får man ett enda utfall.
Nyttan uppstår när man vill veta något om en periodicitet snarare än om enskilda värden. Det är precis vad Shors algoritm utnyttjar: faktorisering reduceras till att hitta perioden hos en funktion, och där ger transformen svaret med hög sannolikhet efter ett fåtal körningar.