Trasformata di Fourier quantistica
L'equivalente della FFT su un registro quantistico: esponenzialmente più veloce, anche se il risultato non può essere letto.
Dove la trasformata di Fourier veloce classica richiede all'incirca N log N operazioni, la versione quantistica si accontenta del quadrato del numero di qubit, cioè esponenzialmente meno passi rispetto alla dimensione dei dati. Il problema è che la trasformata lascia ampiezze che non si possono ispezionare: si può solo misurare, ottenendo un unico esito.
Il valore emerge quando si vuole sapere qualcosa su una periodicità anziché sui singoli valori. È esattamente ciò che sfrutta l'algoritmo di Shor: la fattorizzazione si riduce a trovare il periodo di una funzione, e lì la trasformata dà la risposta con alta probabilità dopo poche esecuzioni.