Sorgu Karmaşıklığı
Bir algoritmanın hızını ölçmenin birden çok yolu var; kuantum karmaşıklığının en temiz ölçütlerinden biri sorgu karmaşıklığıdır: algoritmanın girdisine eriştiği siyah kutuya (oracle’a) kaç kez sorduğunu sayarız. Bu derste sorgu modelinin ne olduğunu, klasik ve kuantum sorgu sayılarının nasıl hesaplandığını, Grover aramasının Θ(N) sorgudan Θ(√N) sorguya nasıl indiğini ve “daha iyisi imkânsız” diyen alt sınır fikrini sıfırdan işleyeceğiz. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin.
Sorgu Modeli: Girdiye Siyah Kutu Gibi Bakmak
Sorgu modelinde girdi bir liste ya da bir f fonksiyonudur; algoritma bu girdiyi kopyalayıp okuyamaz, yalnızca soru sorabilir: “x değerini ver; f(x) ne?” Bu siyah kutuya oracle denir ve algoritmanın bedeli, oracle’ı kaç kez çağırdığıyla ölçülür — buna sorgu karmaşıklığı deriz. Kapının devre düzeyindeki yapısını Oracle Modelleri dersi ayrıca inceler; bu derste oracle’ı birim maliyetli tek bir soru olarak alıyoruz.
Bu ölçüt neden bu kadar seviliyor? Çünkü algoritmanın iç ayrıntılarından bağımsızdır ve “bundan iyisi imkânsız” cümlesini kanıtlamayı kolaylaştırır: sorgu sayısı için bir alt sınır gösterirsen, oracle’ı kim, hangi teknolojiyle uygularsa uygulamalı hiçbir algoritma o sınırın altına inemez. Dikkat edilecek tek ayrıntı: sorgu sayısı, oracle’ın içinde yapılan işin bedelini kapsamaz; o bedel zaman karmaşıklığının konusudur.
Klasik Taraf: Aramada N Sorgudan İyisi Yok
Deterministik klasik arama, en kötü durumda tam N sorgu yapar: çözüm son sırada olabilir. Ortalamada N/2 yeter; ama kötü girdiye karşı direnç istiyorsan N’den küçüğünü garantileyemezsin. Alt sınırın fikri basittir: algoritma bir elemanı hiç sormadıysa, o elemanı gizlice çözüm yap; algoritma fark edemez ve yanlış cevap verir. Yani N sorgunun altı, hiçbir deterministik algoritma için yeterli değildir.
Olasılık eklersen tablo kökten değişmez: hata oranı %33’ün altında kalan rastgele klasik bir algoritma bile (bu tür sınıflar için bkz. Olasılıksal Karmaşıklık BPP) aramada yine Θ(N) sorguya ihtiyaç duyar. Karesel değil, kökten bir kazanç arıyorsan klasik taraf bunu vermez; P ve NP gibi sınıfların büyük resmi için Klasik Karmaşıklık Sınıfları P ve NP dersine bakabilirsin.
Kuantum Sorgu: Faz Oracle’ı ve Θ(√N)
Kuantum sorgusunda oracle, üniteryen bir kapıdır: U_f, temel durumları |x⟩ → (−1)^(f(x))|x⟩ diye eşler; çözüm olan bileşenin işaretini çevirir, öbürlerine dokunmaz. Buna faz oracle’ı denir. Genlik işareti ölçümde tek başına görünmez; kazancı, onu izleyen girişim adımları yaratır. Kuantum sorgu karmaşıklığı, U_f’in kaç kez uygulandığıdır.
Grover algoritması aramayı bu kapıyla Θ(√N) sorguda çözer; Bennett–Bernstein–Brassard–Vazirani (BBBV) çalışması ise √N’den az sorguyla bu işi yapan hiçbir kuantum algoritması olamayacağını göstermiştir. Üst ve alt sınır çakışır: karesel hızlanma, sorgu modelinde kanıtlanabilir bir kesinliktir. Hızlanma kavramının bütün resmi için Kuantum Hızlanması dersine bakabilirsin. Dört ölçütü yan yana koyarsak:
- Deterministik klasik: en kötü durum N sorgu; alt sınır Θ(N).
- Olasılıksal klasik: hata oranı %33’ün altındayken yine Θ(N) sorgu.
- Kuantum: Θ(√N) sorgu — yaklaşık (π/4)·√N tur.
- Ölçek: N 4 katına çıkınca klasik iş 4 katına çıkar, kuantum sorgusu yalnızca 2 katına.
Adım Adım Örnek: N = 4’te Tek Sorgu Yeter
Küçük bir uzayı elle hesaplayalım: N = 4, tek çözüm x = 2. Başlangıç durumu eşit genliklidir: |ψ⟩ = (|0⟩ + |1⟩ + |2⟩ + |3⟩)/2; her genlik 1/2’dir, çünkü olasılıkların toplamı 4·(1/2)² = 1 olmalıdır.
1) Oracle: f(2) = 1 olduğundan ikinci bileşenin işareti çevrilir: (1/2, 1/2, −1/2, 1/2). 2) Diffusion: her genliği ortalamaya göre yansıt: aᵢ → 2·ā − aᵢ. Ortalama ā = (1/2 + 1/2 − 1/2 + 1/2)/4 = 1/4. Hedef genliği 2·(1/4) − (−1/2) = 1, diğerleri 2·(1/4) − 1/2 = 0 olur. Durum tam olarak |2⟩’dir: tek sorgu, olasılık 1. Geometrik kontrol: sin θ = √(M/N) = 1/2 olduğundan θ = 30°; her tur 2θ döndürür ve r = 1 için açı 3θ = 90°’ye ulaşır. (π/4)·√4 ≈ 1,57 formülü de tek tura yuvarlanır — küçük uzayda algoritmanın mekaniğini elle görmek, genel resmi kavramanın en iyi yolu.
Alt Sınırlar ve Sık Yapılan Yanılgılar
Üst sınır “şu kadar sorgu yeter” der; alt sınır “daha azıyla olmaz”. Sorgu modelinin gücü, ikisini birden kesin verebilmesidir. BBBV hibrit argümanı, √N’den az sorgu yapan bir kuantum algoritmasının sorulmamış bölgeleri ayırt edemediğini söyler: çözümü görülmemiş bir bölgeye taşırsan algoritma aynı davranır ve yanılgıya düşer. Ama her problemde kazanç yoktur: N bitin tek-çift denetimi (parity) kuantumda da tam N sorgu ister; Beals ve arkadaşlarının polinom yöntemi bunu kesinleştirir. Karesel kazanç aramanın özel sonucudur, genel kural değildir. Çözüm sayısını sayma problemi için Kuantum Sayma, sınıf düzeyindeki büyük resim için Kuantum Karmaşıklık Sınıfı BQP derslerine bakabilirsin; en büyük bilinen hızlanmaların sorgu modelinden değil sayı teorisinden geldiği bir başka örnek de Shor Algoritması’dır. Ayrıca dört yaygın yanılgı:
- Sorgu sayısı, zaman değildir: oracle’ı gerçek devre olarak uygulamak pahalı olabilir; sorgu modeli bu bedeli saymaz.
- “Her problemde √N kazancı” yanlıştır: parity örneğinde kazanç sıfırdır.
- Alt sınır algoritma değildir: “Θ(√N) yeterli ve daha azı imkânsız” demek, pratik cihazda bu hızın bedava çıkacağı anlamına gelmez.
- İşaret, ölçülebilirlik değildir: faz oracle’ının −1’i ölçümde tek başına görünmez; kazanç girişimden gelir.
Sorgu modeli oracle’ı kusursuz varsayar; gerçek cihazlarda kapılar hata yapar. Hatalarla yüzleşmenin ilk adımı için serinin sonraki ünitesindeki Bit Flip ve Phase Flip Hataları dersine geçebilirsin. Temelleri tazelemek istersen Kuantum Hesaplama 101 dersine dönebilir, tüm derslerin içindekiler için konu anlatımı sayfasına göz atabilirsin.
Sık Sorulan Sorular
Sorgu karmaşıklığı nedir?
Sorgu karmaşıklığı, bir algoritmanın girdisine yalnızca siyah kutu (oracle) soruları üzerinden eriştiği modelde, o soruların en kötü durum sayısıdır. Algoritmanın kendi işlem adımları ve oracle’ın iç maliyeti bu ölçüye girmez; sayılan yalnızca kaç kez sorduğudur.
Sorgu karmaşıklığı ile zaman karmaşıklığı arasındaki fark nedir?
Zaman karmaşıklığı toplam işlem adımını (kapı sayısını, oracle’ın içini dâhil) sayar; sorgu karmaşıklığı yalnızca oracle çağrılarını sayar. Bu yüzden sorgu tarafında kanıtlanan Θ(√N) hızlanma, oracle’ın devre maliyeti büyürse gerçekte daha küçük bir kazanca dönüşebilir.
Grover algoritması neden en fazla karesel hızlanma verir?
Çünkü BBBV olarak bilinen alt sınır, aramayı √N’den az oracle sorgusuyla çözen hiçbir kuantum algoritmasının olamayacağını gösterir; Grover’ın Θ(√N) sorgusu bu sınıra tam oturur. Üst ve alt sınırın çakışması, sonucun kesin olduğunu kanıtlar.
Kuantum bilgisayar her problemde sorgu sayısını azaltır mı?
Hayır. Arama Θ(N)’den Θ(√N)’ye iner; ama örneğin N bitin parity’sini hesaplamak kuantumda da N sorgu ister, Beals ve arkadaşlarının polinom yöntemi bunu kesinleştirir. Kazanç probleme bağlıdır ve hangi problemlerde ne kadar olduğunun incelendiği alan, kuantum sorgu karmaşıklığı teorisidir.
Kaynaklar ve İleri Okuma
A fast quantum mechanical algorithm for database search (L. Grover) — Grover aramasını tanıtan ve Θ(√N) sorgu üst sınırını getiren özgün makalenin özeti.
Strengths and Weaknesses of Quantum Computing (Bennett, Bernstein, Brassard, Vazirani) — sorgu modelinde √N alt sınırını ve kuantum hızlanmanın sınırlarını koyan klasik çalışma.
Quantum complexity theory (Wikipedia) — BQP dâhil kuantum karmaşıklık sınıflarına ve klasik sınıflarla ilişkilerine genel bakış.
IBM Quantum Learning — kuantum algoritmaları ve oracle temelli teknikler için resmî ders ve eğitici materyaller.