Kuantum Sayma

Bir arama probleminde kaç çözüm olduğunu bilmeden Grover’ı doğru sayıda tur çalıştıramazsın; kuantum sayma tam bu boşluğu doldurur: f(x) fonksiyonunun kaç girdide 1 verdiğini, yani çözüm sayısı M’yi, çözümleri tek tek bulmadan kestirir. Kalbi, Grover işlecinin özdeğerinde saklı faz açısını ölçüp oradan M’yi hesaplamaktır. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin.

Sayma Problemi: Listelemeden Saymak

Elimizde N aday ve her adaya 0 ya da 1 döndüren bir f fonksiyonu olsun; sayma problemi, kaç adayın çözüm olduğunu, yani M = |{x : f(x) = 1}| değerini bulmaktır. Klasik bilgisayar bunu en kestirmeden N sorguyla, listeyi baştan sona tarayarak yapar. Rastgele örneklemeyle kestirim de mümkündür: tesadüfi seçilen adayların yaklaşık M/N kadarı çözümdür ve göreli hatası ε olan kestirim için kabaca N/(ε²·M) örnek gerekir. Bu, Olasılıksal Karmaşıklık BPP dersindeki rastgeleleşmiş yöntemlerin doğal uygulamasıdır; ama örnek sayısı N/M ile ölçeklendiği için M küçükse iş tam taramaya yaklaşır.

Sayma neden önemli? Birincisi, Grover’ın tur sayısı M’ye bağlıdır: optimal tur sayısı yaklaşık (π/4)·√(N/M)’dir; M’yi bilmiyorsan bu sayıyı seçemezsin. İkincisi, “hiç çözüm var mı?” sorusu da bir sayma sorunudur: M = 0 mı? Klasikte “yok” demenin en kötü durumdaki yolu N adayın hepsini denemektir.

Anahtar Fikir: Sayı, Fazda Saklıdır

Grover Arama Algoritması dersindeki kurulumu hatırla: arama yazmacı, tüm adayların eşit üst üste binmesi |u⟩ ile başlar. Bu durumu iki özel yönle yazmak her şeyi açar: |u⟩ = sin θ·|w⟩ + cos θ·|r⟩; burada |w⟩ M çözümün, |r⟩ N−M çözüm olmayan adayın eşit karışımıdır ve açı sin²θ = M/N koşulunu sağlar. Her Grover turu, bu iki boyutlu düzlemde durumu |w⟩ yönüne tam 2θ kadar döndürür; k tur sonunda çözümlerin toplam genliği sin((2k+1)θ) olur. Demek ki M, dönüş açısına, dolayısıyla Grover işlecinin özdeğerine kodlanmıştır.

İki boyutlu düzlemde 2θ’lik döndürme, özdeğerleri e^(+2iθ) ve e^(−2iθ) olan bir birimsel işlemcidir; yani M’yi öğrenmek, Grover işlecinin fazını ölçmekle eşdeğerdir. M = 0 ise θ = 0, faz da 0’dır; M büyüdükçe açı büyür. Fazı ölçmek için de hazır bir alet vardır.

Algoritma: Grover’a Faz Tahmini Uygulamak

Yöntem, Faz Tahmini dersindeki makinenin Grover işlecine takılmasından ibarettir; son adımdaki Kuantum Fourier Dönüşümünün tersi, faz bilgisini ölçülebilir bir tamsayıya çevirir. Adımlar şunlardır:

1. t kübitlik kontrol yazmacını |0⟩ durumunda, n kübitlik arama yazmacını Hadamard kapılarıyla eşit üst üste binme |u⟩’da hazırla.
2. Kontrol kübitlerinin hepsine Hadamard uygula.
3. Kontrol kübitlerine Grover işleci G’nin kontrollü kuvvetlerini uygula: k’inci kübit G’nin 2ᵏ’inci kuvvetini çalışsın. G, Genlik Genişletme işlemcisinin özel hâlidir.
4. Kontrol yazmacına ters QFT uygula.
5. Kontrol yazmacını ölç: 0 ile 2ᵗ−1 arasında bir m okursun; açı θ ≈ π·m/2ᵗ ve nihayet M ≈ N·sin²θ çıkar, sonucu en yakın tamsayıya yuvarla.

Peki ölçüm hep aynı fazı mı verir? |u⟩, iki özvektörün (|w⟩ ± i|r⟩)/√2 bileşimi olduğundan ölçüm fazı +2θ ya da −2θ (2π modunda) verir; iki sonuç yaklaşık eşit olasılıkla gelir. Teselli şu: −2θ okununca hesaplanan açı π−θ’ya karşılık gelir ve sin²(π−θ) = sin²θ olduğundan her iki okuma da aynı M’yi verir. Ayrıca M = 0 iken ölçüm her seferinde m = 0 döndürür; algoritma aynı anda “çözüm var mı?” dedektörü olarak da çalışır.

Küçük Bir Örnek: 16 Aday, 4 Çözüm

N = 2⁴ = 16 aday ve M = 4 çözüm olsun. sin²θ = 4/16 = 1/4 → sin θ = 1/2 → θ = π/6 ≈ 0,524 radyan; ölçülecek faz 2θ = π/3’tür. Fazı tam okuyabilseydik M = 16·sin²(π/6) = 16·(1/2)² = 4 der, birebir doğru sayıyı bulurduk.

Gerçekte faz, t kübitlik yazmacın çözünürlüğünde okunur: m ≈ 2ᵗ·(θ/π). t = 8 alalım: m ≈ 256·(1/6) ≈ 42,7; ölçümde 43 çıktı diyelim. Geri hesap: θ ≈ π·43/256 ≈ 0,527 → M ≈ 16·sin²(0,527) ≈ 4,05 → yuvarla: 4 ✓. Şimdi t = 3: m ≈ 8·(1/6) ≈ 1,3 → 1; θ ≈ π/8 → M ≈ 16·sin²(π/8) ≈ 2,3 → 2 bulursun, yanılırsın. Ders: yazmacı kısa kalırsa kestirim kayar; göreli hata ε için 2ᵗ kabaca (1/ε)·√(N/M) mertebesinde olmalı. Maliyet de hızla büyür: en büyük kontrollü kuvvet G’nin 2ᵗ⁻¹’incisidir ve toplam ~2ᵗ Grover çağrısı yapılır.

Gücü, Sınırları ve Sık Yapılan Hatalar

Neyi kazandırır?

• Karesel hızlanma: göreli hata ε için klasik örnekleme ~N/(ε²·M) sorgu isterken kuantum sayma ~(1/ε)·√(N/M) Grover çağrısıyla yetinir; M küçükken klasik ~N, kuantum ~√N mertebesindedir.
• Varlık testi: M = 0 ise okuma daima 0’dır; M ≥ 1 iken açı büyür. Klasikte en kötü durum N sorgu isteyen “çözüm yok” kararı kuantumda ~√N mertebesinde verilir.
• Grover’a kalibrasyon: M’yi kestirdikten sonra tam (π/4)·√(N/M) tur çalıştırırsın; bilinmeyen M’de kör denemeye (BBHT tarzı adaptif aramaya) gerek kalmaz.

Sınırları nerede başlar?

• Sonuç olasılıksaldır: temel faz tahmini analizi en az 4/π² ≈ %40, ayrıntılı analiz en az 8/π² ≈ %81 olasılık verir; kalan durumda sayı birkaç birim kayabilir. Ölçümleri tekrarlayıp dağılımına bakmak gerekir; bunun yöntemi Sonuçların İstatistiksel Analizi dersindedir.
• M ≥ N/2 iken θ → π/2’ye yaklaşır ve kestirim zorlaşır; o zaman sorunu tümleyene çevirip “çözüm olmayan kaç aday var?” diye saymak daha akıllıdır.
• Yöntem hatasız (fault-tolerant) donanım ister: kontrollü Grover kuvvetleri derin devrelerdir, gürültülü cihazlarda kestirim hemen bozulur.

Sık yapılan hatalar

• Fazı θ sanmak: özdeğer e^(±2iθ) olduğundan okunan faz 2θ’dır; M = N·sin²θ formülünde açının yarısını almayı unutursan sonucu sistematik şaştırırsın.
• −2θ okumasını hata saymak: ikinci okuma θ yerine π−θ’ya karşılık gelir; sin²(π−θ) = sin²θ olduğundan sonuç değişmez.
• Önce bul, sonra say: sayım, çözümleri listelemeyi gerektirmez; algoritmanın bütün gücü listelemeden sayabilmesindedir.
• Tek ölçüme güvenmek: kısa kontrol yazmacı ve tek ölçüm, yanıltıcı bir “kesin sayı” hissi verir; kestirimi bir olasılık dağılımı olarak oku.

Kaynaklar ve İleri Okuma

Brassard, Høyer, Tapp — Quantum Counting — Algoritmanın özgün makalesi.

Grover — A fast quantum mechanical algorithm for database search — Saymanın üzerine kurulduğu Grover arama algoritmasının özgün makalesi.

Wikipedia: Quantum counting algorithm — Problemin tanımı ve algoritma adımlarının kısa özeti.

Wikipedia: Quantum phase estimation algorithm — Saymanın motoru olan faz tahmininin adımları ve başarı olasılığı sınırları.

Qiskit Textbook: Quantum Counting — Algoritmanın Qiskit devreleriyle adım adım kurulduğu uygulama not defteri.