Deutsch-Jozsa Algoritması

Kimi fonksiyonlar tüm girdilere aynı cevabı verir, kimi cevapları tam yarı yarıya böler; hangi türde olduğunu anlamak klasik bir bilgisayarı en kötü durumda üstel sayıda sorguya iter. Deutsch-Jozsa algoritması bu ayrımı tek bir sorguda ve hatasız yapan ilk kuantum algoritmadır; kuantum üstünlüğü fikrinin kanıtlanmış ilk örneğidir. Bu ders Kuantum Hesaplama dersleri serisinin Kuantum Algoritmaları ünitesine aittir; tek kübitlik özel durumu gördüysen Deutsch Algoritması dersi iyi bir hazırlıktır.

Problem: Sabit mi, Dengeli mi?

Problem şöyle tanımlanır: elimizde f: {0,1}ⁿ → {0,1} diye yazılan bir Boolean fonksiyonu var; n bitlik bir girdi alıp tek bitlik cevap döndürüyor. Fonksiyonu bir siyah kutu (oracle) olarak kullanabiliriz: girdi verirsin, çıktıyı görürsün; ama iç tablosuna bakamazsın. Bize bir söz (promise) verilir: f ya sabittir — hep 0 ya da hep 1 der — ya da dengelidir: girdilerin tam yarısına 0, tam yarısına 1 der. Görevimiz, f’nin türünü mümkün olan en az sorguyla belirlemek.

Klasik tarafın hesabı açıktır. İki farklı girdiyi sorgulayıp farklı cevaplar alırsan fonksiyon kesin dengelidir; ama cevaplar aynı çıkarsa iş bitmemiştir. Dengeli bir fonksiyon girdilerin tam yarısına 1 dediği için, 2ⁿ⁻¹ + 1 farklı girdinin hepsi aynı cevabı verirse fonksiyonun sabit olduğu kesinleşir — deterministik klasik algoritmanın en kötü durum maliyeti budur. Kuantum bilgisayar aynı soruyu tek sorguyla yanıtlar; fark, problem büyüdükçe katlanarak açılır.

Kuantum Tarif: Hadamard, Oracle ve Faz Geri Tepmesi

Algoritmanın ilk malzemesi Hadamard kapısıdır: H|0⟩ = (|0⟩ + |1⟩)/√2 ve H|1⟩ = (|0⟩ − |1⟩)/√2. İkinci malzeme, klasik f’nin kuantum devresine çevrilmiş hâli olan üniteryen oracle Uf’dir: n kübitlik girdi kaydı ve bir yardımcı kübit üzerine Uf, |x⟩|y⟩ durumunu |x⟩|y ⊕ f(x)⟩ durumuna taşır. Buradaki ⊕ iki bitin mod 2 toplamıdır; çıktı yardımcıya XOR’landığı için işlem geri alınabilir ve üniteryenlik korunur.

Sihrin kendisi yardımcı kübitten gelir: onu |1⟩’den Hadamard geçirerek |−⟩ = (|0⟩ − |1⟩)/√2 durumuna getirirsin. Bu durumda Uf, f(x)’i yardımcıya yazmak yerine girdiye işaret olarak yansıtır: |x⟩|−⟩ → (−1)ᶠ⁽ˣ⁾|x⟩|−⟩. f(x) = 0 ise hiçbir şey değişmez; f(x) = 1 ise bileşenin işareti döner. f’nin değeri görünmez ama genliklere bulaşmıştır; bu etkiye faz geri tepmesi (phase kickback) denir. Asıl amaç, bu işaretleri sonraki Hadamard katmanıyla girişime sokup f’nin küresel özelliğini tek cevapta okumaktır; faz geri tepmesi ileride Faz Tahmini dersinde çok daha güçlü roller üstlenir.

Algoritma Adım Adım

Devre şöyle kurulur:

1. n girdi kübitini |0⟩’da, yardımcı kübiti |1⟩’de hazırla; başlangıç durumu |0…0⟩|1⟩ olsun.
2. Tüm kübitlere Hadamard uygula: girdi kaydı 2ⁿ girdinin eşit genlikli üst üste binmesine, (1/√(2ⁿ)) Σₓ |x⟩’e döner; yardımcı |−⟩’ya iner.
3. Uf’yi tam bir kez çağır — algoritmanın bütün oracle maliyeti budur. Durum, faz geri tepmesiyle (1/√(2ⁿ)) Σₓ (−1)ᶠ⁽ˣ⁾|x⟩ ⊗ |−⟩ olur.
4. Girdi kaydına ikinci Hadamard katmanı (H⊗ⁿ) uygula; yardımcıya dokunma.
5. Girdi kaydını ölç: sonuç |0…0⟩ ise f sabit; en az bir 1 içeriyorsa f dengelidir.

Küçük bir hesapla teyit edelim. n = 1 için dengeli bir fonksiyon olan f(x) = x’i seçelim:

• Başlangıç: |0⟩|1⟩.
• Hadamard’lar: (|0⟩ + |1⟩)/√2 ⊗ (|0⟩ − |1⟩)/√2.
• Uf: |0⟩’ın işareti korunur (f(0) = 0), |1⟩’in işareti döner (f(1) = 1); durum (|0⟩ − |1⟩)/√2 ⊗ |−⟩ olur.
• Son Hadamard: (|0⟩ − |1⟩)/√2 bileşimi |1⟩’e dönüşür.
• Ölçüm: kesinlikle 1 çıkar — fonksiyon dengeli, tek sorguda bitti.

f = 0 (sabit) seçseydik Uf hiçbir işareti değiştirmez, aynı hesap kesinlikle |0⟩ sonucunu verirdi. Genel n için de sonuç ya tamamen 0’lardır ya da en az bir 1 içerir; ara durum yoktur.

Neden Tek Sorgu Yeter? İki Satırlık Matematik

Bütün algoritma şu tek satıra yaslanır: son Hadamard katmanından sonra |0…0⟩’ın genliği, tüm girdilerin faz çarpanlarının ortalamasıdır: a = (1/2ⁿ) Σₓ (−1)ᶠ⁽ˣ⁾.

f sabitse çarpanların hepsi aynıdır ve toplam ±2ⁿ çıkar; genlik ±1, dolayısıyla |0…0⟩’ı görme olasılığı tam 1’dir. f dengeliyse 2ⁿ⁻¹ tane +1 ile 2ⁿ⁻¹ tane −1 birbirini götürür; toplam 0, genlik 0, olasılık tam 0’dır. |0…0⟩ ya kesin çıkar ya hiç çıkmaz: iki senaryo birbirini dışlar ve tek ölçüm kesin ayırt eder. Süperpozisyon f’yi tüm girdilerde aynı anda değerlendirir ama cevapları tek tek okumaya çalışmaz; girişim hepsini tek bir evet/hayır bitine indirger. Bir kuantum kaydından ölçümle en fazla kayıt büyüklüğü kadar klasik bilgi çıkar; 2ⁿ sonucun hepsini okumak zaten imkânsızdır — Deutsch-Jozsa okumaz, doğru soruyu sorar.

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

En sık karşılaşılan yanılgıları düzeltelim:

• “Kuantum bilgisayar 2ⁿ cevabın hepsini aynı anda okuyor.” Hesaplar ama okuyamaz; ölçüm tek bir rastgele sonucu verir. Güç okumada değil, girişimdedir.
• “Klasik bilgisayar bu problemde mutlaka üstel iş yapar.” Üstel maliyet, kesin garanti isteyen deterministik klasik algoritma içindir. Rastgelelik serbestse klasik taraf k sorguda en fazla 1/2ᵏ⁻¹ hata olasılığıyla yetinir; Deutsch-Jozsa’nın özgünlüğü “tek sorgu + sıfır hata” birleşimidir.
• “Oracle bedavadır.” Sorgu karmaşıklığı yalnızca oracle çağrılarını sayar; Uf’nin kendisi f’yi geri alınabilir kapılardan kurulur ve kapı sayısı ile devre derinliği ayrıca hesaba katılır.
• “Sonuç gürültüden sapıyor, algoritma bozuk.” Teoride olasılıklar tam 1 ve 0’dır; gürültülü donanımda |0…0⟩’ı “neredeyse hep” görürsün. Devreyi gerçek cihazda çalıştırmak için Backend ve Cihaz Kavramı, ölçüm dağılımını yorumlamak için Sonuçların İstatistiksel Analizi dersi yol gösterir.

Deutsch-Jozsa ailenin ilk halkasıdır: aynı teknik bir sonraki derste Bernstein-Vazirani Algoritması’nda gizli bir bit dizisini okumak için, Simon Algoritması’nda ise üstel hızlanmanın ilk kez net görüldüğü gizli periyot problemi için kullanılır. Genel resmi Kuantum Karmaşıklık Sınıfı BQP dersi tamamlar.

Kaynaklar ve İleri Okuma

Deutsch & Jozsa — Rapid solution of problems by quantum computation (Proc. R. Soc. Lond. A 439, 1992) — Algoritmanın tanıtıldığı özgün makale.

Deutsch–Jozsa algorithm (Wikipedia) — Problem tanımı, devre ve klasik karşılaştırma.

IBM Quantum Learning — The Deutsch–Jozsa Algorithm — Sorgu modeli çerçevesinde ders anlatımı.

Quantum algorithm (Wikipedia) — Diğer kuantum algoritmalarıyla birlikte genel bakış.