Deutsch Algoritması

Kuantum algoritmaları ünitesine, tarihteki ilk kuantum algoritması olan Deutsch algoritmasıyla başlıyoruz. Bu derste sabit mi dengeli mi ayrımını tek sorguyla veren bu algoritmayı, Hadamard kapısı ve faz geri tepmesi (phase kickback) hilesiyle adım adım elle hesaplayacağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin; anlatım, önceki ünitelerde gördüğün süperpozisyon, kapılar ve ölçüm kavramlarının üstüne kurulur.

Problem: f Sabit mi, Dengeli mi?

Elimizde kara kutu (oracle) olarak verilmiş bir fonksiyon var: f: {0,1} → {0,1}. Dört olasılık vardır: f(x)=0 ve f(x)=1 (bunlar sabit fonksiyonlardır), f(x)=x ve f(x)=1−x (bunlar dengeli fonksiyonlardır). Bize bir söz (promise) verilir: f ya sabittir, yani f(0)=f(1); ya da dengelidir, yani f(0)≠f(1). Sorumuz şudur: f’nin içini açmadan, yalnızca oracle’a sorgu göndererek bu ayrımı en az kaç sorguda yapabiliriz? Dikkat et: f(0)’ın değerini değil, iki değerin eşit olup olmadığını soruyoruz.

Klasik bilgisayar için cevap bellidir: iki sorgu. f(0) ile f(1)’i hesaplayıp karşılaştırır; tek sorgu yetmez, çünkü görmediğin f(1) hâlâ iki farklı değer alabilir. Deutsch algoritması ise tek sorguda, olasılık 1 ile doğru cevabı verir. İki katlık fark başta değersiz görünse de algoritmanın asıl değeri kavramsaldır; içindeki faz geri tepmesi tekniğini sonraki derslerde hep yeniden göreceğiz.

İki Araç: Hadamard Kapısı ve Faz Geri Tepmesi

Kapı Hadamard’dır: matrisi H = (1/√2)·[[1, 1], [1, −1]] şeklindedir ve |0⟩’yu |+⟩ = (|0⟩+|1⟩)/√2 durumuna, |1⟩’i |−⟩ = (|0⟩−|1⟩)/√2 durumuna taşır. H kendi tersidir (H·H = I); geri dönüş de geçerlidir: H|+⟩ = |0⟩, H|−⟩ = |1⟩. Bu ters dönüş bir girişim olayıdır: iki bileşen bir yönde aynı fazda birleşirken öbür yönde birbirini yok eder.

Hile, faz geri tepmesidir. Oracle U_f, |x⟩|y⟩ durumunu |x⟩|y ⊕ f(x)⟩ durumuna taşır; burada ⊕, mod 2 toplamadır. İkinci kübiti (ancilla) |−⟩’ye hazırlarsan oracle’ın işi değişir: f(x)=0 iken durum hiç değişmez; f(x)=1 iken (|0⟩−|1⟩)/√2 → (|1⟩−|0⟩)/√2 = −|−⟩ olur. Genel kural: U_f: |x⟩|−⟩ → (−1)^f(x)|x⟩|−⟩. Yani f’nin değeri ancilla’ya hiç yazılmaz; birinci kübitin genliklerinin işaretine (fazına) “teper”. Ölçüm fazı göremez; girişim ise göreli fazı ölçülebilir sonuca çevirir.

Algoritma Adım Adım: Devre ve Hesap

Devre iki kübitlidir: birincisi girdi kübiti (x), ikincisi ancilla (y). Başlangıç durumu |0⟩|1⟩’dir ve akış şöyledir:

1. H⊗H uygula: |ψ₁⟩ = [(|0⟩+|1⟩)/√2] ⊗ [(|0⟩−|1⟩)/√2]. Birinci kübit artık iki girdinin üst üste binmesini taşıyor; ancilla faz geri tepmesi için |−⟩’de.
2. Oracle’ı bir kez çağır: faz geri tepmesiyle |ψ₂⟩ = [(−1)^f(0)|0⟩ + (−1)^f(1)|1⟩]/√2 ⊗ |−⟩. Ortak çarpan (−1)^f(0)’ı global faz olarak dışarı alırsak: |ψ₂⟩ = [ |0⟩ + (−1)^(f(0)⊕f(1)) |1⟩ ]/√2 ⊗ |−⟩.
3. Birinci kübite H uygula: f sabitse f(0)⊕f(1)=0’dır, durum |+⟩’dır ve H|+⟩=|0⟩; f dengeliyse durum |−⟩’dır ve H|−⟩=|1⟩.
4. Ölç: birinci kübit 0 okursan f sabittir; 1 okursan f dengelidir. Gürültüsüz devrede doğru olasılığı 1’dir.

Somut örnek olarak dengeli fonksiyonu alalım: f(x) = x. Adım 1’den sonra durum (1/2)(|00⟩ − |01⟩ + |10⟩ − |11⟩)’dür. U_f, |x⟩|y⟩’yi |x⟩|y⊕x⟩’ye taşıdığı için |10⟩ ile |11⟩’nin yerleri değişir: (1/2)(|00⟩ − |01⟩ + |11⟩ − |10⟩). Bu, [(|0⟩−|1⟩)/√2] ⊗ [(|0⟩−|1⟩)/√2]’ye eşittir; birinci kübit |−⟩’dedir. H uygulayıp ölçünce sonuç 1 çıkar → dengeli. Şimdi sıra sende: f(0)=f(1)=1 sabit fonksiyonu için adımları elle tekrarla; oracle’dan sonra durum (−|0⟩−|1⟩)/√2 ⊗ |−⟩ olur, bu global faz dışında |+⟩’dır ve ölçüm 0 verir → sabit.

Neden İşe Yarıyor: Girişim ve “Paralellik” Yanılgısı

En yaygın yanılgı şudur: “Kuantum bilgisayar f(0) ile f(1)’i aynı anda hesapladığı için hızlıdır.” Paralel hesap kısmı doğrudur ama tek başına işe yaramaz; U_f’ten sonra birinci kübiti hemen ölçersen yarı olasılıkla 0, yarı olasılıkla 1 görürsün — yani tek bir rastgele değer ve hiçbir şey öğrenmezsin. Deutsch algoritmasının ustalığı şurada: iki değeri okumaya çalışmak yerine, yalnızca ikisinin karşılaştırılmasından doğan tek bitlik küresel özelliği (f(0)⊕f(1)) göreli fazda kodlar ve Hadamard girişimiyle ölçülebilir hâle getirir. Kuantum hızlanması paralellikten değil, doğru sorunun girişimle tek bitlik bir cevaba indirgenmesinden gelir.

Bu fikrin serüveni sonraki derslerde açılır: Deutsch algoritması n bitlik girdili fonksiyonlara genellendiğinde Deutsch-Jozsa Algoritması doğar; klasik tarafın en kötü durum maliyeti 2ⁿ⁻¹+1 sorguya fırlarken kuantum tek sorguyla yetişir. Aynı faz geri tepmesi tekniği Bernstein-Vazirani Algoritması’nda gizli bir bit dizisini okumak için, Faz Tahmini’nde ise bir üniteryenin özdeğer fazını ölçmek için yeniden kullanılır; Faz Tahmini ileride Shor Algoritması’nın çekirdeğini oluşturacaktır.

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

• Ancilla’yı |0⟩’da bırakmak. İkinci kübit |0⟩’da kalırsa faz geri tepmesi olmaz; oracle bilgiyi ancilla’ya yazar, birinci kübit |+⟩ olarak kalır ve ölçüm 0 ile 1’i yarı yarıya verir. |−⟩ hazırlığı zorunludur.
• Ölçmeden önce son Hadamard’ı atlamak. |+⟩ ile |−⟩ ikisi de ölçüde 0 ve 1’i %50 olasılıkla verir; ikisini ayıran tek şey göreli fazdır. Girişim, ölçümden hemen önceki H ile kurulur.
• Global faza anlam yüklemek. (−1)^f(0) gibi tüm duruma ortak çarpanlar ölçüme etkisizdir; karar yalnızca iki bileşenin göreli işaretine bağlıdır.
• Bu hızlanmayı abartmak. Deutsch ayrımı 2 sorguya karşı 1 sorgudur; pratik bir kazanç sağlamaz. Değeri kavramsaldır: sorgu karmaşıklığını tanıtır ve sonraki algoritmaların tekniğini kurar.

Algoritmayı gerçek donanımda denemek istersen önce Backend ve Cihaz Kavramı dersiyle uygun cihazı seç; gürültü yüzünden %90–95 civarı doğruluk görürsün. Sonuçları güvenle yorumlamak için Sonuçların İstatistiksel Analizi dersindeki çekim sayısı ve güven aralığı hesaplarını uygula.

Kaynaklar ve İleri Okuma

Deutsch–Jozsa algorithm (Wikipedia) — Deutsch algoritmasını tek kübitlik özel durum olarak işleyen ve devre hesabını adım adım veren madde.

David Deutsch (Wikipedia) — Algoritmayı 1985’te öneren ve kuantum evrensel Turing makinesi fikrini ortaya koyan fizikçi hakkında madde.

Quantum Algorithms Revisited (arXiv:quant-ph/9708016) — Cleve, Ekert, Macchiavello ve Mosca’nın erken kuantum algoritmalarını sorgu sayısı çerçevesinde ele alan klasik makalesi.

Fundamentals of Quantum Algorithms (IBM Quantum Learning) — Oracle tabanlı kuantum algoritmalarını ve Deutsch-Jozsa’yı devre düzeyinde anlatan resmî IBM ders serisi.