Transformada de Fourier quântica
A contraparte da FFT num registrador quântico — exponencialmente mais rápida, embora o resultado não possa ser lido.
Enquanto a transformada rápida de Fourier clássica precisa de cerca de N log N operações, a versão quântica faz o trabalho com o quadrado do número de qubits, ou seja, exponencialmente menos passos em relação ao tamanho dos dados. O problema é que a transformada deixa amplitudes que não podem ser inspecionadas; só se pode medir, e aí se obtém um único resultado.
O valor aparece quando se quer descobrir algo sobre uma periodicidade, e não sobre valores individuais. É exatamente o que o algoritmo de Shor explora: fatorar se reduz a encontrar o período de uma função, e nisso a transformada dá a resposta com alta probabilidade após poucas execuções.