Genlik Genişletme

Bu derste kuantum hızlandırmalarının ortak motoru olan genlik genişletmeyi (amplitude amplification) sıfırdan öğreneceksin. Kuantum Hesaplama dersleri serisinde artık kapıları, oracle fikrini ve ölçüm istatistiğini biliyorsun; bu ders o parçaları tek bir mimariye oturtuyor. Grover algoritmasının bu yapının özel bir durumu olduğunu görecek, bir turun genlikleri nasıl döndürdüğünü hesaplayacak ve doğru tur sayısını sin² salınımından çıkaracaksın.

Genlik ile Olasılık: Kuvadratik Fark

Kuantum durumunu ψ = Σᵢ αᵢ|xᵢ⟩ diye yazdığımızda ölçümün bileşenleri |αᵢ|² olasılığıyla seçtiğini biliyorsun; Sonuçların İstatistiksel Analizi dersinde gördüğümüz gibi bu olasılıklar ancak ölçüm tekrarıyla, yavaş okunur. Kuantum müdahalesi (interference) ise doğrudan genlikler üstünde çalışır: bir genliği ekleyebilir, çıkarabilir, işaretini çevirebilirsin — genlik büyüdükçe olasılık onun karesiyle koşar. Kıyas tablosu:

• Klasik: her denemenin başarı olasılığı p = M/N; sabit başarı için yaklaşık N/M deneme gerekir. Bu olasılıksal çerçeve Olasılıksal Karmaşıklık BPP dersinde işlenir.
• Kuantum: her tur olasılığı değil genliği büyütür; genlik (2k+1)θ ile doğrusal, olasılık (2k+1)²θ² ile kuvadratik büyür.
• Sonuç: problem iki kat büyürse klasik maliyet iki kat, kuantum tur sayısı yalnızca √2 kat artar.

Oracle ve Durum Hazırlığı: A Operatörü

Problemin girdisi, n kübitlik x değerleri üzerinde tanımlı bir f fonksiyonudur: f(x) = 1 ise x çözümdür. N = 2ⁿ olası değerden M tanesi çözüm olsun. Faz oracle’ı S_f, |x⟩ → (−1)^{f(x)}|x⟩ dönüşümü yapar; tek işi, yalnızca çözüm bileşenlerin işaretini −1 ile çarpmaktır, kapının içinde liste satır satır okunmaz. Fazın bilgi taşıdığı fikrini Bernstein-Vazirani Algoritması dersindeki faz kickback’te görmüştün; buradaki oracle aynı mekanizmanın arama yüzüdür.

İkinci parça durum hazırlama operatörü A’dır: A|0...0⟩ = |s⟩ ile başlangıcı üretir. En yaygın seçim tüm kübitlere Hadamard uygulamaktır; o zaman |s⟩ = (1/√N) Σₓ|x⟩ eşit genlikli üst üste binmedir. Ama A bununla sınırlı değildir: eldeki en iyi tahmine göre başlangıç hazırlarsan gereken tur sayısı da kısalmıştır. Şimdi |s⟩’yi çözüm durumların normalize toplamı |β⟩ ile çözüm olmayanların normalize toplamı |α⟩’ya ayıralım: |s⟩ = sin θ·|β⟩ + cos θ·|α⟩, burada sin θ = √(M/N), yani θ = arcsin√(M/N). İki bileşen diktir (⟨α|β⟩ = 0) ve normalizasyon kendiliğinden sağlanır: sin²θ + cos²θ = M/N + (N−M)/N = 1; tüm oyun bu iki eksen arasındaki tek düzlemde geçer.

Bir Turun Anatomisi: Q = (2|s⟩⟨s| − I)·S_f

Bir tur iki yansımadan oluşur. Birinci yansıma oracle S_f’dir: |β⟩’nin işaretini çevirir, |α⟩’ya dokunmaz; durum |α⟩ ekseni etrafında yansıtılır. İkinci yansıma hazırlamanın geriye çevrilmesiyle kurulur: S₀ = I − 2|0...0⟩⟨0...0| tanımlanırsa A S₀ A⁻¹ = I − 2|s⟩⟨s| olur; bunun eksi işaretlisi durumu başlangıç ekseni |s⟩ etrafında yansıtır. Genel tur operatörü:

Q = −A·S₀·A⁻¹·S_f = (2|s⟩⟨s| − I)·S_f

Klasik geometriden bilirsin: aralarındaki açı θ olan iki eksen etrafında art arda yansıtma, durumu 2θ döndürür. |α⟩ ekseni ile |s⟩ arasındaki açı tam da θ olduğundan her Q turu durumu |β⟩ yönüne 2θ döndürür. k tur sonunda durum

|ψₖ⟩ = sin((2k+1)θ)·|β⟩ + cos((2k+1)θ)·|α⟩

olur; ölçümde çözüm görme olasılığı P(k) = sin²((2k+1)θ)’dir. İki boyutlu bu düzlemde Q’nun özdeğerleri e^(+2iθ) ve e^(−2iθ)’dir: faz bilgisi özdeğerlere yazılmıştır. Q’ya Faz Tahmini uygulanıp 2θ okunursa M = N·sin²θ’dan çözüm sayısı çıkar; tam hâli Kuantum Sayma dersidir. A = “tüm kübitlere Hadamard”, M = 1 alındığında Q, Grover dönüşünün ta kendisidir; devre düzeyindeki karşılığı Grover Arama Algoritması dersinde ayrıntılıdır.

Mini Hesap: N = 4, M = 1

Somutlaştıralım: iki kübit, N = 4 aday, tek çözüm x = |11⟩. Hadamardlarla başlangıç genliklerinin hepsi ½’dir: |s⟩ = ½(|00⟩ + |01⟩ + |10⟩ + |11⟩). Buradan θ = arcsin√(1/4) = arcsin(½) = π/6 çıkar. Bir turu izleyelim:

1. Oracle S_f: hedef |11⟩’in genliği işaret değiştirir → genlikler (½, ½, ½, −½).
2. Ortalama: ā = (½ + ½ + ½ − ½)/4 = ¼.
3. Ortalamaya göre yansıtma (a → 2ā − a = ½ − a): ilk üç bileşen ½ − ½ = 0; hedef bileşen ½ − (−½) = 1.
4. Ölçüm: durum tam |11⟩’dir; P(1) = sin²(3·π/6) = sin²(π/2) = %100.

Tek tur yetti: iki kübitlik Grover aramasının neden tek turda bittiğinin kısa kanıtı budur. Aşırı turun bedelini de formül söyler: k = 2 için P = sin²(5π/6) = (½)² = %25 — ikinci tur başarıyı %100’den %25’e düşürür; k = 4’te P tekrar %100’e döner. Büyük N’de θ küçülür ve sin θ ≈ θ (radyan) yaklaşımı devreye girer: M = 1 için θ ≈ 1/√N, dolayısıyla tepeye varan tur sayısı k* ≈ π/(4θ) − ½ ≈ (π/4)·√N. Klasik aramanın M = 1’de ortalama N/2 denemesine karşı bu, karesel hızlanmanın ta kendisidir.

Sık Yapılan Hatalar ve Yanılgılar

• Genlik ile olasılığı karıştırmak. Müdahale genlikler üstünde toplanır; ölçülen şey |genlik|²’dir. Olasılık yükselmiyorsa zıt işaretli bileşenler birbirini yok ediyor olabilir.
• Oracle’ın listeyi “okuduğunu” sanmak. S_f yalnızca çözüm bileşenlerin işaretini çevirir. Hızlanma oracle’ın çağrı sayısından gelir; oracle’ın kendi iç maliyeti ayrıca hesaba katılmalıdır.
• Optimal turu geçmek. P(k) salınımlıdır; N = 4 örneğinde 2. tur başarıyı %25’e düşürdü. Körlemesine tur artırmak çözümden uzaklaştırabilir.
• M’i bilmeden tam tur sayısı seçmek. k* formülü M’e bağlıdır. Çözüm sayısı bilinmiyorsa büyüyen rastgele adımlı adaptif yöntemler ya da önce θ’yi tahmin eden kuantum sayma kullanılır.
• Normalizasyonu atlamak. Her adımda Σ|genlik|² = 1 korunmalıdır; S_f ve yansıtma üniter olduğundan hesap hatası yoksa bu kural kendiliğinden bozulmaz, elle hesapta yine de denetle.
• “Yalnızca eşit üst üste binmeyle çalışır” sanmak. A genel bir hazırlama operatörüdür; iyi bir başlangıç tahmini θ’yi büyütür, gereken tur sayısını doğrudan azaltır.

Kaynaklar ve İleri Okuma

Amplitude amplification — Wikipedia — genel Q operatörü, geometrik yorum ve tur sayısı sonuçlarının özlü özeti.

Quantum Amplitude Amplification and Estimation (Brassard, Høyer, Mosca, Tapp) — alanın kurucu makalesi; Q operatörünün tam analizi ve bilinmeyen M durumları.

A fast quantum mechanical algorithm for database search (Grover, 1996) — bu yapının özel durumunu doğuran özgün makalenin özeti.

IBM Quantum Learning — oracle tabanlı arama algoritmalarının adım adım devre anlatımları.

The Quantum Algorithm Zoo — genlik genişletmenin yapı taşı olarak kullanıldığı algoritmaların kataloğu.