QuellengeprüftLevel 3
Quanten-Fourier-Transformation
Die QFT ist das Quantenanalogon der diskreten Fourier-Transformation mit O(n²) Gattern.
Was es bedeutet
Transformiert Rechenbasis in Frequenzbasis.O(n²) statt O(n·2^n).Schlüssel-Subroutine für Shor und Phasenschätzung.Alltagsvergleich
Wie Akkordzerlegung in Noten.
Wie ein Prisma.
Häufige Missverständnisse
- QFT-Speedup nicht direkt für Signalverarbeitung nutzbar.
- QFT ist nicht der klassische FFT-Algorithmus.
Das Wichtigste
- O(n²) Gatter.
- Exponentiell weniger als FFT.
- Schlüssel für Shor und Phasenschätzung.
Verständnis prüfen
Wie viele Gatter für n-Qubit-QFT?
- A.O(n)
- B.O(n²)
- C.O(2^n)
- D.O(n·2^n)
Antwort anzeigen
Antwort: B. O(n²)
Warum: O(n²) Gatter.
Baut auf
Primärquelle: 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.
Praktisch lernen
Dieses Konzept ist Teil eines Curriculums mit 46 Leveln, einem interaktiven Simulator und Lumen — einem Tutor, dessen Antworten vor der Anzeige geprüft werden. Level 1–5 sind kostenlos.