Transformée de Fourier quantique
L'équivalent de la FFT sur un registre quantique — exponentiellement plus rapide, mais dont le résultat ne peut pas être lu.
Là où la transformée de Fourier rapide classique demande de l'ordre de N log N opérations, la version quantique s'en tire avec le carré du nombre de qubits, donc exponentiellement moins d'étapes rapportées à la taille des données. Le hic : la transformée laisse des amplitudes qu'on ne peut pas inspecter ; on ne peut que mesurer, et l'on obtient alors un seul résultat.
L'intérêt apparaît quand on veut apprendre quelque chose sur une périodicité plutôt que sur des valeurs individuelles. C'est exactement ce qu'exploite l'algorithme de Shor : factoriser se ramène à trouver la période d'une fonction, et la transformée en donne la réponse avec une forte probabilité après une poignée d'exécutions.