Oracle Modelleri
Oracle — yani "kâhin" — kuantum algoritmalarının siyah kutusudur: fonksiyonun içini görmeden onu üniteryen bir kapı olarak sorgularsın. Bu derste bit-flip ve phase olmak üzere iki temel oracle modelini, aralarındaki faz geri tepmesi köprüsünü ve klasik fonksiyonun tersinirleştirilmesini sıfırdan işleyeceğiz. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına; oracle'ı ilk kez Grover içinde görmek istersen Kuantum Hesaplama 101 dersine bak.
Oracle Nedir? Siyah Kutu Sözleşmesi
Karmaşıklık teorisinde oracle, uygulaması elimizde olmayan ama x verildiğinde f(x) döndüren bir alt yordamdır. Maliyet sözleşmesi şudur: oracle'ın içindekileri hesaba katmayız, yalnızca kaç kez çağırdığımızı sayarız; bu düzene sorgu modeli denir, ayrıntısı Sorgu Karmaşıklığı dersindedir. Kuantumda oracle bir kapı — üniteryen dönüşüm olmak zorundadır: girdi süperpozisyonadaysa kapı tüm dallara bileşen bileşen uygulanır. Peki hangi kapıyı vereceğiz?
İki Temel Model: Bit-Flip ve Phase Oracle
Bit-flip (standart) oracle cevabı ikinci bir kayda yazar: O_f |x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩. Burada ⊕ mod 2 toplamıdır; x değişmez, cevap y'ye XOR'lanır. Phase oracle ek kayıt kullanmaz, cevabı işarete gömer: O_f |x⟩ = (−1)^{f(x)} |x⟩; f(x) = 0 ise hiçbir şey değişmez, f(x) = 1 ise genlik −1 olur. Grover'da "çözümün genliğini ters çeviren" kapı tam olarak buydu:
- Bit-flip: cevabı klasik kayda yazar; f(x)'i yazdırmak isteyen görevlerin modelidir, temizlik için uncompute ister.
- Phase: kayıt açmaz, bilgiyi göreli fazda taşır; girişim temelli algoritmaların (Deutsch–Jozsa, Simon, Grover) dilidir.
İki model, faz geri tepmesi (phase kickback) hilesiyle bağlanır. Adım adım:
- Y kaydını |−⟩ = (|0⟩ − |1⟩)/√2 yap; bit-flip oracle'ı uygula.
- f(x) = 0 ise y değişmez; durum |x⟩|−⟩ kalır, çarpan +1'dir.
- f(x) = 1 ise y bit-flip görür: (|0⟩ − |1⟩)/√2 → (|1⟩ − |0⟩)/√2 = −|−⟩.
- Tek ifadede: O_f |x⟩|−⟩ = (−1)^{f(x)} |x⟩|−⟩ — cevap, x'in fazına "geri tepti".
Somut örnek: f(x₁x₂) = x₁ VE x₂, yalnızca |11⟩ girdisinde 1 verir. Eşit süperpozisyona (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2 phase oracle'ı uygulayınca çıktı (|00⟩ + |01⟩ + |10⟩ − |11⟩)/2 olur; norm hâlâ 1'dir, çünkü |−1|² = |1|² = 1. Ama tek başına ölçsen dört çıktıyı da aynı olasılıkla görürdün: eser, Hadamard gibi girişim kapılarıyla fazlar olasılıklara çevrilmeden görünmez — Deutsch–Jozsa'dan Grover'a sırrın özü budur.
Oracle Neden Üniteryen Olmak Zorunda?
Klasik fonksiyonlar çoğu zaman bilgi kaybeder: VE kapısı iki bitten tek bit üretir; x₁ = 1 ve f = 0 gören biri, x₂'nin değerini bilemez. Birçok-bire giden bu eşleme tersine çevrilemeyeceği için üniteryen olamaz. Çözüm Bennett'in tekniğidir: temiz |0⟩ yardımcı kübitler açılır, hesap O_f |x⟩|0⟩ = |x⟩|f(x)⟩ biçiminde kurulur ve çöp kübitler, kopyalar uncompute edilerek temizlenir. Toffoli kapısı VE'yi tersinir gerçeklediğinden her klasik devre, polinom ek yükle tersinir devreye çevrilir. Bunu Shor Algoritması dersinde gördün: modüler üstel hesabın sonunda ara kayıtların sıfıra dönmesi, aynı mantıktır.
Pratik bir kural: kapının kontrollü sürümüne erişim de tanımda yazılmalıdır; Kuantum Sayma gibi teknikler Grover yinelemesinin kontrollü hâlini ister. Bu kapı Kuantum Sayma dersinde karşına çıkar.
Sorgu Sayısı Çalışma Zamanı Değildir
Sorgu modeli ayırışları tertemiz gösterir: Bernstein–Vazirani'de f(x) = a·x (mod 2) oracle'ından a'yı bulmak klasikte en az n sorgu isterken, Hadamard + tek sorgu + Hadamard kesin cevabı verir. Simon problemi, oracle modelinde üstel ayırış örneğidir; ayrıntısı Gizli Alt Grup Problemi dersindedir. Ama gerçek makinede oracle bir devredir: Grover'ı "N öğeli listede arama" diye sunan anlatının bilinen tuzağı budur — çözümü işaretleyen devreyi kurmak, çoğu pratik problemde aramadan zordur. Kuantum aramanın vaadi, oracle'ı bir kez kurup yaklaşık (π/4)√N kez çağırmaktır; kurulum maliyeti bu vaadin dışındadır. Sonuçlarını Kuantum Hızlanması dersinde işleyeceğiz.
Model ayrıntısı sonuçları değiştirir: f değerini kayda yazdırmak yalnızca bit-flip modelinde doğaldır; bu yüzden bir alt sınır kanıtı, hangi modelin hangi erişimle verildiğini açıkça yazar. Kanıt tarafında da temkin gerekir: Baker–Gill–Solovay (1975), öyle A ve B oracleları göstermiştir ki P^A = NP^A iken P^B ≠ NP^B olur. Yani relativize dünyada bile P ile NP iki türlü sonuçlanabilir; ayırış bir tekniğin sınırını gösterir, soruyu kapatmaz. BQP'nin bu haritadaki yeri Kuantum Karmaşıklık Sınıfı BQP dersinin konusudur.
Sık Yapılan Hatalar ve Akılda Kalanlar
Sık yapılan hatalar
- "Oracle tüm girdilere cevabı dağıtır." Hayır; kapı işaret yazar veya XOR yapar, ölçülebilir bilgi sızdırmaz; bilgi girişimle okunur.
- Global fazı fiziksel sanmak. Tek başına |x⟩ → −|x⟩ ölçülemez; gücü, dallara farklı işaretler vurarak göreli faz yaratmasındadır.
- Tersinirliği atlamak. Klasik VE/VEYA kapılarını olduğu gibi devreye koymak üniteryenliği bozar; yardımcı kübit + uncompute şarttır.
- Oracle maliyetini sıfır saymak. Sorgu sayısı ile devre derinliği farklı metriklerdir; pratikte baskın maliyet çoğu zaman oracle kurulumudur.
- "Oracle kanıtı büyük soruları çözer." Relativizasyon (Baker–Gill–Solovay) tersini öğretir: oracle dünyasında bile tutarlı iki tablo çizilebilir.
Akılda kalanlar
- Oracle, f(x) sorusunu üniteryen kapıyla soran siyah kutudur; maliyeti çağrı sayısıdır.
- İki model: bit-flip O_f |x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩; phase O_f |x⟩ = (−1)^{f(x)} |x⟩.
- Bit-flip oracle + |−⟩ kaydı, faz geri tepmesiyle phase oracle verir.
- Klasik fonksiyon üniteryen değildir; yardımcı kübitler ve uncompute ile tersinirleşir.
- Sorgu sayısı çalışma zamanı değildir; erişim türü tanımda yazılmalıdır.
(−1)^{f(x)} işareti hem algoritmanın aracı hem hata kaynağıdır: faz çeviren her kusur istemeden aynı kapıyı uygular. Bu kırılganlığı sonraki ünitede Bit Flip ve Phase Flip Hataları ve Tekrarlama Kodları derslerinde işleyeceğiz; içindekiler için Konu Anlatımı sayfasına bak.
Sık Sorulan Sorular
Kuantum oracle nedir?
Oracle, f fonksiyonunu üniteryen bir kapı olarak sunan siyah kutu modelidir. Bit-flip modeli cevabı kayda XOR'lar: O_f |x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩; phase modeli cevabı işarete gömer: O_f |x⟩ = (−1)^{f(x)} |x⟩. Karmaşıklık analizi oracle'ın içini değil, çağrı sayısını ölçer.
Bit-flip oracle ile phase oracle arasındaki fark nedir?
Bit-flip oracle cevabı klasik bir kayda yazar; phase oracle genliklerin işaretine yansıtır. Kaydı |−⟩ = (|0⟩ − |1⟩)/√2 durumuna koyup bit-flip oracle'ı uygulamak, faz geri tepmesiyle (−1)^{f(x)} çarpanını ilk kayda geçirir; iki model sorgu sayısı bakımından büyük ölçüde eşdeğerdir.
Oracle'ın maliyeti algoritmanın karmaşıklığına dahil mi?
Sorgu modelinde dahil değildir: her çağrı bir birim sayılır, oracle'ın içi soyutlanır. Gerçek donanımda oracle bir devredir; Grover'da çözümü işaretleyen devreyi kurmak çoğu zaman aramadan pahalıdır. Sorgu sayısı teorik üst sınır; devre derinliği ayrı bir pratik maliyettir.
Oracle ayırışları P ile NP sorununu çözer mi?
Çözmez. Baker–Gill–Solovay (1975), öyle A ve B oracleları göstermiştir ki P^A = NP^A iken P^B ≠ NP^B olur. Aynı temkin kuantum sınıfları için de geçerlidir: relativize kanıtlar hangi tekniklerin yetmeyeceğini gösterir; üniversel soruyu kapatmaz.
Kaynaklar ve İleri Okuma
Oracle machine — Vikipedi — Oracle modelinin klasik tanımı ve kuantum oracle kavramı.
Grover, A fast quantum mechanical algorithm for database search (1996) — √N aramanın orijinal makalesi.
Bernstein–Vazirani algoritması — Vikipedi — Tek oracle sorgusuyla gizli doğrusal fonksiyon.
Simon's algorithm — Vikipedi — Oracle modelinde üstel ayırış örneği.
P versus NP problem — Vikipedi — Baker–Gill–Solovay relativizasyon sonuçlarının bağlamı.