Quantum Fourier Transform (QFT)

Normales Fourier Transform (FFT) zerlegt ein Musikstück in seine Noten (Frequenzen). Ein klassischer Computer braucht dafür $O(N \log N)$ Schritte. Bei $2^{100}$ Datenpunkten dauert das ewig. Die Quantum Fourier Transform (QFT) macht das Gleiche für Quanten-Zustände. Aber sie braucht nur $O(\log^2 N)$ Schritte! Das ist exponentiell schneller. Es ist der "Motor" fast aller berühmten Quanten-Algorithmen (wie Shors Algorithmus zum Knacken von RSA). Der Haken: Du bekommst die Frequenzen nicht als Liste. Sie sind im Quanten-Zustand versteckt. Du kannst sie nicht einfach "abmessen".

Merksatz: Das Quanten-Analogon der diskreten Fourier-Transformation, das exponentiell schneller berechnet werden kann als die klassische FFT, aber nur Zugang zu den Amplituden im Rahmen anderer Quantenalgorithmen bietet.

Niemals isoliert. QFT ist immer ein Sub-Modul. Beispiel: Quantum Phase Estimation. Du willst wissen: "Welchen Eigenwert hat dieser Operator?"

Bereite Qubits vor.
Wende Operator an.
Mache Inverse QFT.
Miss die Qubits -> Der Messwert ist die Phase (Eigenwert).

1. Implementierung

QFT besteht nur aus Hadamard-Gattern und Controlled-Phase-Shift Gattern ($R_k$). Interessant: Die Phase-Shifts werden immer kleiner ($R_2, R_3, \dots$). Für große Qubitzahlen sind die Drehungen so winzig, dass sie physikalisch kaum von Rauschen zu unterscheiden sind (Implementation Challenge).

2. Kein Speedup für Daten?

Warum kann ich damit MP3s nicht schneller encoden? Weil QFT auf Amplituden arbeitet. Um die MP3 reinzukriegen, brauchst du $2^N$ Schritte (Laden). Um das Ergebnis rauszukriegen, brauchst du $2^N$ Messungen (Sampling). Der Speedup gilt nur, wenn die Daten schon im Quantencomputer entstehen (durch Berechnung).

1. Approximate QFT (AQFT)

In der echten Hardware sind die winzigen Phasen-Drehungen ($R_{10}, R_{20} \dots$) das Hauptproblem. Sie sind so klein, dass sie im Rauschen untergehen. AQFT ist ein Forschungsansatz: Man lässt alle Drehungen weg, die kleiner als ein bestimmter Schwellenwert sind. Erstaunlich: Die Algorithmen (wie Shor) funktionieren trotzdem noch sehr gut. Das spart massiv Schaltungstiefe (Depth) und macht die QFT auf heutigen NISQ-Rechnern überhaupt erst möglich.

2. Logarithmic Depth & Connectivity

Ein naiver QFT-Circuit braucht $O(n^2)$ Gatter. Durch geschicktes Re-Arranging (ähnlich wie beim klassischen FFT Butterfly-Graph) kann man die Tiefe reduzieren. Das größte Hindernis in der Produktion ist jedoch die Connectivity. QFT verlangt, dass jedes Qubit mit jedem anderen interagiert. In echten Chips (wie bei IBM) sind die Qubits aber meist nur in einem Gitter (Grid) verbunden. Der Transpiler muss also unzählige SWAP-Gatter einfügen, um Qubits physikalisch nebeneinander zu schieben. Diese SWAPs fressen die Kohärenzzeit auf. Ein Experte optimiert daher nicht die Mathe der QFT, sondern das Layout auf dem Chip.

3. Semiclassical QFT

Ein brillanter Trick für sparsame Rechner: Die Semiclassical QFT. Wenn man die QFT nur am Ende einer Berechnung nutzt, um ein Ergebnis zu messen (wie bei der Phasen-Schätzung), braucht man gar keine Quanten-Gatter für die Phasen-Drehungen! Man kann ein Qubit messen, den Wert an einen klassischen Computer schicken, und dieser justiert dann die Mess-Basis für das nächste Qubit "on the fly". Das ersetzt Quanten-Kopplung durch klassische Feedback-Loops. Das spart Qubit-Verschränkung und reduziert die Fehlerrate dramatisch.