Kuantum Fourier Dönüşümü

Kuantum algoritmaların çoğunda kritik bir adım vardır: süperpozisyonun içindeki periyodiklik bilgisini ölçülebilecek keskin olasılık tepelerine dönüştürmek. Bu işi yapan üniter operatör Kuantum Fourier Dönüşümü'dür (kısaca QFT); bu derste tanımını, kapı devresini ve küçük bir örnekle adım adım çalışmasını göreceğiz. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin; önceki derste gördüğün Simon Algoritması periyodikliği klasik adıma bırakmıştı, bu ders o işi yapan kuantum aracıyı tanıtıyor.

Fourier Dönüşümü Neyi Bulur?

Klasik Fourier dönüşümü, bir sinyalin hangi frekanslardan oluştuğunu söyler: birkaç saf tonun karışımı olan sese dönüşüm uygularsan tonların güçlerini okursun. Genel ilke şudur: sinyal düzenli bir ritimle tekrar ediyorsa dönüşüm bu tekrarı tek bir keskin tepede gösterir; yani Fourier dönüşümü özünde bir periyodilik bulucudur.

Kuantumda aynı soru farklı kıyafetle gelir: genlikleri periyodik tekrar eden bir durum varsa periyot nasıl okunur? Genlikler doğrudan gözlenemez; ölçüm tek temel durum döndürür. QFT'nin işi, genliklerdeki tekrar bilgisini ölçüm istatistiğinde görünecek olasılık tepelerine taşımaktır. Ölçüm sonrası veriyi nasıl okuduğunu Sonuçların İstatistiksel Analizi dersinde görmüştün; QFT, ölçümden hemen önce devreye giren hazırlık adımıdır.

Kuantum Fourier Dönüşümü Nedir?

QFT, n kübitlik uzayda (N = 2ⁿ) her temel durumu, tüm temel durumların belirli fazlarla karışımıyla değiştiren üniter dönüşümdür:

|j⟩ → (1/√N) Σₖ e^(2πi·jk/N) |k⟩ , k = 0, 1, …, N−1

Burada e^(2πi·jk/N), birim çemberde jk/N turu demektir; jk, N'in katı olduğunda faz 1 olur. Üniterlik: her satır birim büyüklükte, farklı satırlar ortogonaldır; çünkü j ≠ j′ iken bileşen fazları e^(2πi(j−j′)k/N) çemberi tam doldurur ve toplam sıfır olur, norm korunur. Çizgisellik: süperpozisyonun dönüşümü bileşenlerin dönüşümlerinin toplamıdır; QFT genlikleri αⱼ olan herhangi bir Σⱼ αⱼ|j⟩ durumuna uygulanabilir.

Küçük Bir Hesap: N = 4

n = 2 kübit, N = 4 alıp |1⟩'in QFT'sini hesaplayalım. Fazlar k = 0, 1, 2, 3 için sırasıyla 1, i, −1, −i'dir; çünkü e^(2πi/4) = i, e^(4πi/4) = −1, e^(6πi/4) = −i. Sonuç:

QFT|1⟩ = (1/2)(|0⟩ + i|1⟩ − |2⟩ − i|3⟩)

Olasılıkların hepsi 1/4: norm korundu, tek durum dört durumun eşit karışımına yayıldı. Asıl ilginç girdi periyodik olandır: |ψ⟩ = (1/√2)(|0⟩ + |2⟩); genlikler ikişer atlıyor, periyot r = 2. |0⟩'ın QFT'si (1/2)(|0⟩ + |1⟩ + |2⟩ + |3⟩); |2⟩'ninkisi ise e^(πik) = (−1)^k olduğundan (1/2)(|0⟩ − |1⟩ + |2⟩ − |3⟩). Toplayınca ortadaki terimler sönümlenir, geriye (1/√2)(|0⟩ + |2⟩) kalır: olasılığın tamamı N/r = 2'nin katlarına, yani 0 ve 2'ye yığıldı. QFT'nin özeti budur: genliklerdeki periyodikliği, olasılıklardaki keskin tepelere çevirir.

QFT Devresi: Kapılar ve Karmaşıklık

QFT kapılarla kurulur; n kübit için üç malzeme yeter: Hadamard, kontrollü faz kapıları ve sonda bit sırasını düzelten SWAPlar. n = 3 için: en anlamlı kübite Hadamard; ikinci kübit ona kontrollü e^(2πi/4), üçüncü kübit kontrollü e^(2πi/8) fazı ekler. Sonra ikinci kübite Hadamard ve üçüncüden gelen kontrollü e^(2πi/4); son kübit yalnızca Hadamard alır. Devre bitleri ters sırada ürettiği için uç kübitler SWAP'lanır. Kontrollü kapılar Rₘ = diag(1, e^(2πi/2ᵐ)) biçimindedir; toplam n(n−1)/2 kontrollü faz + n Hadamard + ~n/2 SWAP, yani O(n²) kapı.

Neden önemli? Klasik hızlı Fourier dönüşümü (FFT), N noktalık girdiyi O(N log N) işlemde dönüştürür; N = 2ⁿ olduğundan bu O(2ⁿ·n)'dir. QFT ise O(n²)'dir: n = 30 için FFT kabaca 32 milyar işlem, QFT birkaç yüz kapı. Ama kritik ayrıntı: QFT'nin çıktısını baştan sona okuyamazsın. N adet sayısal değer n kübittedir, ölçüm tek temel durum verir; QFT bu yüzden periyot okuma bileşenidir, FFT'nin hızlı kopyası değil. Kapı bütçesi dar cihazlarda küçük fazları atlayan yaklaşık QFT çoğu zaman yeterlidir; donanım için Backend ve Cihaz Kavramı dersine bakabilirsin.

QFT Nerede Kullanılır?

İlk müşteri özdeğer fazıdır: U|ψ⟩ = e^(2πiφ)|ψ⟩ özdurumundaki gizli φ, Faz Tahmini'nin konusudur. Kontrol kübitleri U'nun üstel kuvvetleriyle e^(2πiφk) fazlarını biriktirir; çıkan (1/√N)Σₖ e^(2πiφk)|k⟩ benzeri duruma ters QFT (QFT⁻¹) uygulanır. İkinci müşteri çarpanlara ayırmadır: Shor Algoritması, aˣ mod N'in periyodu r'yi bulmak için modüler üs almanın hazırladığı periyodik duruma QFT uygular; olasılık N/r'nin katlarında toplanır, ölçülen c'den c/N ≈ s/r oranı sürekli kesirlerle r'yi verir.

Üçüncüsü saymadır: Kuantum Sayma, çözüm sayısını Faz Tahmini altyordamıyla, dolayısıyla QFT ile tahmin eder. Ortak kalıp 'gizli periyodu QFT ile oku'dur; genel çerçeve Gizli Alt Grup Problemi dersinde açılır. İki bağ notu: Simon Algoritması'ndaki Hadamard dönüşümü aslında (ℤ₂)ⁿ grubunun Fourier dönüşümüdür — o ders QFT'nin özel bir hâliydi. Grover Arama Algoritması tarafında mekanizma başkadır: periyodiklik değil, tekrar eden Genlik Genişletme turu çözüme yığar.

Sık Yapılan Hatalar ve Akılda Kalanlar

QFT'yi ilk öğrenenlerde en sık görülen kaymalar şunlardır:

• 'QFT tüm Fourier katsayılarını verir' sanmak. Vermez; katsayılar kübitlerde bulunur ama ölçüm tek temel durum döndürür. Dağılım için hazırla → QFT → ölç döngüsünü çok kez tekrarlayıp istatistik toplarsın.
• 1/√N çarpanını unutmak. Normalizasyon süs değildir; olmazsa toplam olasılık 1 değil N olur ve dönüşüm üniterlikten çıkar.
• Bit sırasını düzeltmemek. Devre çıktıyı ters sırada verir; SWAP'ları atlarsan ölçtüğün sayı beklediğinin bitleri ters çevrilmiş hâli olur.
• 'QFT her işte FFT'yi geçti' sanmak. Kapı sayısında O(n²) ≪ O(2ⁿ·n) doğrudur ama FFT girdisini baştan sona okuyabilir, QFT okuyamaz; kazanım yalnızca periyodikliğin yeterli olduğu problemlerde anlamlıdır.

Bu Dersten Akılda Kalanlar

Tek cümleyle: QFT, temel durumları tüm temel durumların fazlı karışımlarıyla değiştiren, O(n²) kapıyla kurulan ve genliklerdeki periyodikliği ölçülebilir tepelere taşıyan üniter dönüşümdür.

• QFT|j⟩ = (1/√N) Σₖ e^(2πi·jk/N)|k⟩; çizgiseldir, üniterdir, N = 2ⁿ uzayında tanımlıdır.
• N = 4: |1⟩ → (1/2)(|0⟩ + i|1⟩ − |2⟩ − i|3⟩); periyodu 2 olan (1/√2)(|0⟩ + |2⟩) girdisinde olasılık tümüyle N/r = 2'nin katlarında.
• Devre: Hadamard + kontrollü Rₘ kapıları + SWAP; O(n²) kapı, FFT'nin O(2ⁿ·n) maliyetine karşı.
• Kullanım: Faz Tahmini (QFT⁻¹ ile), Shor (periyot okuma), Kuantum Sayma; ortak çerçeve Gizli Alt Grup Problemi.

Kaynaklar ve İleri Okuma

Quantum Fourier transform — Wikipedia — QFT'nin tanımı, matrisi ve devresi için standart başvuru.

Fourier transform — Wikipedia — klasik Fourier dönüşümünün tanımı ve periyodiklik yorumu.

QFT — Qiskit Dokümantasyonu — QFT devresini kuran Qiskit sınıfının resmî API belgesi.

An approximate Fourier transform useful in quantum factoring — D. Coppersmith (arXiv) — Shor bağlamında yaklaşık QFT fikrinin kaynağı olan klasik makale.