Kwantum-Fouriertransformatie
Het kwantumequivalent van de FFT op een kwantumregister: exponentieel sneller, maar het resultaat is niet uit te lezen.
Waar de klassieke snelle Fouriertransformatie in de orde van N log N bewerkingen nodig heeft, redt de kwantumversie het met het kwadraat van het aantal qubits, dus exponentieel minder stappen ten opzichte van de datagrootte. Het addertje: de transformatie laat amplitudes achter die niet te inspecteren zijn; je kunt alleen meten en krijgt dan één uitkomst.
De waarde zit in situaties waarin iets over een periodiciteit moet worden geleerd in plaats van over afzonderlijke waarden. Precies dat benut het algoritme van Shor: factoriseren komt neer op het vinden van de periode van een functie, en daar geeft de transformatie na een handvol runs met grote waarschijnlijkheid het antwoord.