Grover Arama Algoritması

Kuantum algoritmaların en ünlüsü Grover arama algoritması, sıralanmamış N adayın içinden tek çözümü karesel hızlanmayla çıkarır: klasik arama ortalama N/2 deneme yaparken Grover yaklaşık (π/4)·√N turda yetişir. Bu derste oracle’ı tanımlayacak, bir Grover turunu iki kübitlik minik örnekte elle hesaplayacak, gereken tur sayısını çıkaracak ve sık yanılgıları ayıklayacağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bak; oracle ve faz geri tepmesi kavramlarını ilk kez görüyorsan önce Deutsch Algoritması dersine dönmek faydalıdır.

Problem: Yapılandırılmamış Arama ve Oracle

Elimizde N aday ve f fonksiyonu var: x çözümse f(x) = 1, değilse 0. Adaylar sıralı ya da sayısal düzende olmadığı için ikili arama yapılamaz; buna yapılandırılmamış arama denir. Klasik bilgisayar adayları tek tek sorgular: en kötü durumda N, ortalama (N+1)/2 sorgu gerekir.

Oracle, önceki derslerin tanıdığı araçtır: ancilla |−⟩’deyken U_f: |x⟩ → (−1)^f(x)|x⟩ biçimindedir; f’nin değeri durum üzerine bir işaret olarak teper. Grover’ın sorusu Deutsch-Jozsa Algoritması’ndaki “sabit mi, dengeli mi” ya da Simon Algoritması’ndaki gizli dizgi sorusundan farklıdır: bu kez çözümün kendisini istiyoruz. Söz problemlerinde birkaç sorgu yeterken burada sorgu sayısı N ile büyür; hedef, büyümeyi üstel yerine √N düzeyinde tutmaktır.

Bir Grover Turu: Oracle ve Ortalamaya Göre Yansıtma

Grover, tüm adayların eşit genlikli üst üste binmesiyle başlar: n kübitlik kayıtta N = 2ⁿ ve başlangıç durumu |s⟩ = (1/√N)·Σₓ |x⟩’dir; toplam x = 0, 1, …, N−1 üstüne alınır. Bu durumu n Hadamard ile hazırlarız: (H⊗⋯⊗H)|0⟩⋯|0⟩. Tek bir tur iki adımdır:

1. Oracle (O): yalnızca çözüm bileşeninin işaretini ters çevirir: f(x) = 1 iken genlik aₓ → −aₓ; çözümün genliği ortalamanın altına iner.
2. Yayılım (D): D = 2|s⟩⟨s| − I her genliği ortalamaya göre yansıtır: aᵢ → 2ā − aᵢ (ā = genlik ortalaması). Ortalamanın altına inen çözüm genliği yansıyınca üstüne fırlar; diğerleri hafifçe küçülür.

İki adımın bileşkesi, olasılığı çözümün üstünde toplayan genlik yükseltmedir. Geometrik okuma: durum vektörü, “tüm adaylar eşit” yönü |s⟩ ile “yalnız çözüm” yönü |w⟩ düzleminde kalır; bu yönler arasındaki açı θ için sin θ = 1/√N. Oracle bir eksende, yayılım öbür eksende birer yansıtmadır; iki yansıtma, 2θ’luk sabit bir döndürmedir. k turdan sonra başarı olasılığı P(k) = sin²((2k+1)θ)’dir; her tur durumu çözüm yönüne döndürür.

Minik Hesap: İki Kübit, Tek Tur, %100 Sonuç

En küçük tam örnek N = 4 adaylı kayıttır (n = 2 kübit); hedef |11⟩ olsun. Başlangıç genlikleri, |00⟩, |01⟩, |10⟩, |11⟩ sırasıyla (1/2, 1/2, 1/2, 1/2)’dir. Adımları izle:

1. Oracle |11⟩’nin işaretini çevirir: genlikler (1/2, 1/2, 1/2, −1/2) olur.
2. Ortalama genlik ā = (1/2 + 1/2 + 1/2 − 1/2)/4 = 1/4; yansıtma aᵢ → 1/2 − aᵢ genlikleri (0, 0, 0, 1) yapar.
3. Durum tam olarak |11⟩’dir: tek turda olasılık %100.

Formülle kontrol: sin θ = 1/√4 = 1/2 → θ = 30°. Tek tur 2θ = 60° döndürür; 30°’lik açı 90°’ye, tam çözüm yönüne ulaşır ve P(1) = sin²(3·30°) = sin²(90°) = 1. Uyarı: N = 4’te tek turun yetmesi kural değildir; gereken tur N ile (π/4)·√N gibi büyür.

Kaç Tur Gerekli? (π/4)·√N Kuralı

P(k) eğrisi (2k+1)θ ≈ 90° iken tepe yapar; buradan optimal tur k ≈ (π/4)·√N çıkar. Somut sayılar: N = 16’da θ = arcsin(1/4) ≈ 14,5°; optimal seçim 3 turdur ve P(3) = sin²(7 × 14,5°) ≈ %96. Aynı durumda 4. tur olasılığı ≈ %58’e düşürür: Grover hedefi geçebilir (overshoot). Büyük ölçekte fark açılır: N = 2²⁰ ≈ 1.048.576 adayda √N = 1024, gereken tur ≈ 804; klasik ortalama ≈ 524.288 deneme.

Çözüm birden fazlaysa (M adet) açı değişir: sin θ = √(M/N), optimal tur k ≈ (π/4)·√(N/M). M/N = 1/4’te tek tur kesin başarı verir; M/N 1/2’ye yaklaşınca hiç tur atmadan ölçmek bile yeterlidir. Pratikte M bilinmez; tur sayısı da seçilemez ama operatörün fazları ölçülerek M sayılabilir: G = D·O’nun |w⟩–|s⟩ düzlemindeki özdeğerleri e^(±2iθ)’dir ve bu fazları Faz Tahmini ile okumak Kuantum Sayma’nın konusudur. Yansıtma çiftinin genel kurulumu Genlik Genişletme’de ayrıntılanır.

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

• Kareseli üstel sanmak. Kazanç N → √N türündedir, üstel değildir. Bennett–Bernstein–Brassard–Vazirani (BBBV), oracle sorgularıyla aramanın Ω(√N)’den iyi yapılamayacağını gösterdi: Grover optimaldir. Karmaşıklık bağlamı için Kuantum Karmaşıklık Sınıfı BQP ile Klasik Karmaşıklık Sınıfları P ve NP derslerine bak.
• Oracle’ın bedelini unutmak. Grover oracle çağrılarının sayısını azaltır; oracle’ın devre derinliği ayrı bir maliyettir. f hesaplanabilir bir sürecin değil de erişilemez bir belleğin içindeyse hızlanma kâğıtta kalır.
• Tur sayısını kaçırmak. Optimalden çok tur başarıyı düşürür; sinüs tepe yapıp iner. M bilinmiyorsa optimal tur da bilinmez — bu ihtiyaç, kuantum saymayı ve adaptif stratejileri doğurur.
• Başlangıç durumunu es geçmek. Eşit genlikli |s⟩, D = 2|s⟩⟨s| − I biçimini ve “ortalamaya göre yansıtma” yorumunu mümkün kılar; başka bir durumdan başlarsan bu geometri konuşmaz.
• Tek ölçümle karar vermek. Donanımda olasılık %96 bile olsa tek çekim yanıltır; yüzlerce çekim alıp frekanslara bakmak gerekir — yöntem Sonuçların İstatistiksel Analizi dersinde.

Haritadaki yeri: ünitenin ilk yarısındaki algoritmalar oracle’a az sorgu atıp tek bir küresel özellik okurken Grover aynı aracı tekrar eden yansıtma çiftine çevirip çözümü inşa eder. Shor Algoritması gibi üstel hızlanmalar problem yapısı isterken Grover yalnızca doğrulanabilir bir çözüm ister; bu yüzden kaba kuvvetin girdiği her yerde — anahtar arama, doyurulabilirlik, çakışma bulma — ilk akla gelen kuantum araçtır.

Kaynaklar ve İleri Okuma

A fast quantum mechanical algorithm for database search (arXiv:quant-ph/9605043) — Lov Grover’ın 1996’daki özgün makalesi; O(√N) sorgu sonucunun kaynağı.

Tight bounds on quantum searching (arXiv:quant-ph/9605034) — Boyer, Brassard, Høyer ve Tapp’ın tur sayısı analizini ve M çözümlü durumu ele alan makalesi.

Strengths and Weaknesses of Quantum Computing (arXiv:quant-ph/9701001) — Bennett, Bernstein, Brassard ve Vazirani’nin Ω(√N) alt sınırını gösterdiği makale; Grover’ın optimal olduğunun dayanağı.

Grover's algorithm (Wikipedia) — devre, geometrik yorum ve genelleştirmeler için genel bakış maddesi.

Fundamentals of Quantum Algorithms (IBM Quantum Learning) — yapılandırılmamış arama ve Grover’ı devre düzeyinde anlatan resmî IBM ders kitabı.