Após computar a^x mod N coerentemente, valores repetidos correlacionavam expoentes separados por r. A transformada quântica de Fourier no registrador de x convertia esse espaçamento em picos de frequência.
A QFT mapeava |x⟩ para uma superposição com fases e^{2πixy/Q}. Para um padrão periódico, contribuições de x separados por r reforçavam y próximos de múltiplos de Q/r e se cancelavam em outras posições.
Lia mediu um y e formou y/Q, aproximação de uma fração s/r. Frações contínuas recuperavam candidatos a r; exponenciação modular clássica verificava se a^r≡1 mod N. Uma amostra podia ser insuficiente, então o protocolo repetia.
A QFT tinha circuito polinomial em n=log Q usando Hadamards e rotações controladas. Ela não imprimia todas as componentes de Fourier: a medição amostrava picos. A promessa periódica e o pós-processamento tornavam poucas amostras úteis.
Tomás comparou com FFT clássica. A QFT atua sobre amplitudes de um estado e não recebe uma lista clássica explícita de Q valores para devolver outra lista. Sua eficiência não permite substituir qualquer FFT de dados clássicos; entrada e saída são diferentes.
Pequenas rotações podem ser aproximadas para reduzir portas, com erro controlado. Em hardware tolerante a falhas, compilar aritmética e rotações em conjuntos discretos de portas domina recursos. Polinomial não significa pequeno.
Fourier ouviu o espaçamento e devolveu uma fração. Lia viu a arquitetura de Shor inteira: estrutura algébrica, superposição, fase, interferência, amostragem e verificação clássica. Nenhuma etapa era onisciente; juntas mudavam a complexidade.