Source vérifiéeNiveau 3
Transformée de Fourier quantique
La QFT est l'analogue quantique de la transformée de Fourier discrète avec O(n²) portes.
Ce que cela signifie
Transforme la base computationnelle en base frequentielle.O(n²) au lieu de O(n·2^n).Sous-routine cle pour Shor et estimation de phase.Analogie du quotidien
Comme decomposer un accord en notes.
Comme un prisme.
Idées reçues fréquentes
- L'acceleration QFT n'est pas directement utilisable pour le traitement du signal.
- QFT n'est pas l'algorithme FFT classique.
À retenir
- O(n²) portes.
- Exponentiellement moins que FFT.
- Cle pour Shor et estimation de phase.
Vérifiez votre compréhension
Combien de portes pour QFT n-qubit?
- A.O(n)
- B.O(n²)
- C.O(2^n)
- D.O(n·2^n)
Voir la réponse
Réponse: B. O(n²)
Pourquoi: O(n²) portes.
S’appuie sur
Source primaire: Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Circuit form per Coppersmith (1994), arXiv:quant-ph/0201067.
Apprendre en pratiquant
Ce concept fait partie d’un cursus de 46 niveaux, avec un simulateur interactif et Lumen — un tuteur dont les réponses sont vérifiées avant affichage. Les niveaux 1–5 sont gratuits.