
The quantum Fourier transform is a method used in quantum computing to enhance signal detection, sensor precision, and computational efficiency.La transformation de Fourier quantique est une application unitaire qui transforme la base de calcul |j⟩ en une superposition uniforme avec des phases exp(2π i j k / N), où N = 2^n. C'est l'analogue quantique de la transformation de Fourier discrète et peut être réalisée avec O(n^2) portes, offrant une accélération exponentielle par rapport à la FFT classique qui nécessite O(N log N) opérations sur un vecteur de taille N. La QFT est à la base des algorithmes de recherche de périodicité cachée et d'estimation de phase.
Décrite pour la première fois dans le cadre de l'algorithme de factorisation de Peter Shor (1994). Une construction efficace avec un nombre polynomial de portes a été développée par Don Coppersmith (1994) et simultanément par le groupe de Deutsch. Auparavant, en 1985, David Deutsch avait montré la possibilité de principe d'accélération grâce au parallélisme quantique. D'un point de vue mathématique, la QFT est une réalisation de la transformation de Wigner sur un corps fini et est étroitement liée à la théorie des représentations des groupes.
Le circuit quantique commence dans l'état |x_1 x_2 ... x_n⟩. On applique H au premier qubit, créant une superposition (|0⟩ + e^{2π i 0.x_1}|1⟩). Ensuite, on applique une porte R_2 contrôlée par le deuxième qubit, ajoutant une contribution de phase exp(2π i 0.x_1 x_2), et ainsi de suite jusqu'à R_n. Les mêmes opérations sont répétées sur le deuxième qubit avec les rotations R_2...R_{n-1}, etc. L'amplitude finale pour l'état |k⟩ est (1/√N) Σ_j exp(2π i j k / N) x_j, où x_j est l'amplitude d'entrée. Lors de la mesure, la distribution de probabilité est concentrée près de la fréquence multiple de 1/T si une périodicité T était cachée dans les données d'entrée.
Cœur de l'algorithme de Shor qui menace les systèmes de chiffrement RSA actuels, ainsi qu'une étape clé de l'estimation de phase dans le calcul quantique — de la recherche de valeurs propres à l'estimation de la périodicité de motifs cachés.
La transformation de Fourier quantique ne peut pas être directement utilisée pour la compression de photos ou de vidéos, car le résultat reste à l'intérieur de la puce quantique et est détruit lors de la lecture ; en revanche, pour extraire des périodicités globales, elle fait gagner des milliers de fois en temps.















