Simon Algoritması

1994'te Daniel Simon'un keşfettiği Simon algoritması, bir fonksiyona gizlenmiş dönemeci — gizli maske s'yi — klasikte ancak üstel adımla bulunabilen bir problemi kuantum bilgisayarda doğrusal sayıda sorguyla çözer. Kuantum hesaplamanın klasik hesaplamadan üstel hızla üstün olabileceğine ilk somut kanıttır; iki yıl sonra Shor'un çarpanlara ayırma algoritmasına ilham verdi. Bu derste problemi sıfırdan tanımlayıp algoritmayı iki kübitlik minik bir örnekle izleyeceğiz; serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin.

Simon Problemi: Gizli Maske Nedir?

Elimizde {0,1}ⁿ kümesinden yine {0,1}ⁿ kümesine giden, yalnızca siyah kutu (oracle) olarak çağırabildiğimiz bir f fonksiyonu var. f hakkında söz şudur: ya bire birdir, ya da öyle bir n bitlik s dizisi vardır ki f(x) = f(y) ancak ve ancak y = x ⊕ s iken doğrudur. Burada ⊕, bit bit toplama mod 2, yani XOR'dur: 0110 ⊕ 0101 = 0011. s sıfırdan farklıysa f'nin her değeri tam iki kez üretilir: x ile x⊕s aynı sonuca gider. Amacımız s'yi bulmak. s = 00...0 ise koşul f'yi bire bir olmaya zorlar; algoritma böylece "fonksiyon bire bir mi?" sorusuna da cevap verir.

Klasik yoldan s'yi bulmak, f(x) = f(y) olacak bir çarpışma çifti bulmaya denktir: ilk yoklamalar hep farklı sonuç verir, aynı çıktıyı ikinci kez gördüğün an yapı ele verir. Doğum günü paradoksu mantığıyla bu yaklaşık √(2ⁿ) sorgu ister: 30 bitlik girdide 33 bin kadar, 60 bitlikte yaklaşık bir milyar sorgu. Simon algoritması aynı işi O(n) sorguda bitirir; üstel yerine doğrusal büyüme, algoritmanın asıl sürprizidir.

Algoritma Adım Adım

Devrede iki adet n kübitlik yazmaç var: girdi yazmacı ve çıktı yazmacı. İkisi de |0⟩ ile başlar:

1. Üst üste binme: Girdi yazmacına H⊗n uygula; tüm girdiler eşit genlikte durur: (1/√(2ⁿ)) Σₓ |x⟩|0⟩.
2. Oracle sorgusu: Uf kapısı |x⟩|0⟩'yı |x⟩|f(x)⟩'e çevirir; durum (1/√(2ⁿ)) Σₓ |x⟩|f(x)⟩ olur. Tüm f değerleri hesaplanmıştır ama henüz gizlidir.
3. Çıktı yazmacını ölç: Diyelim sonuç v çıktı. Çıktısı v olan iki girdi vardır: x₀ ve x₀⊕s. Girdi yazmacı (|x₀⟩ + |x₀⊕s⟩)/√2 durumuna çöker — ölçüm, iki-bir yapının izini üst üste binmiş bir çift olarak bırakır.
4. İkinci Hadamard: Girdi yazmacına yine H⊗n uygula. z'nin genliği (−1)^(x₀·z) + (−1)^((x₀⊕s)·z) olur; ortak çarpan atılınca kalan 1 + (−1)^(s·z)'dir. s·z = 1 ise terimler birbirini götürür, genlik sıfırlanır.
5. Girdi yazmacını ölç: Yalnızca s·z = 0 (mod 2) olan z'ler çıkar (· = bit bit çarpıp mod 2 toplamak). Her deneme böyle bir "denklem" üretir.
6. Klasik bitirme: Adımları yaklaşık n kez yinele. Toplanan z'ler için z·s = 0 denklemlerini GF(2), yani mod 2 aritmetiği üzerinde çöz: kısıtlar yeterince bağımsızsa sistemin sıfırdan farklı tek çözümü s'nin kendisidir.

Kuantum kısım her çalışmada "s'ye dik bir vektör" üretir; s'yi tek hamlede söylemez. Değerli olan okunan z'nin kendisi değil, z·s = 0 kısıtıdır; s ancak kısıtlar birleşince çıkar.

Küçük Bir Örnek: n = 2, s = 10

Somut f olarak f(00) = 01, f(01) = 10, f(10) = 01, f(11) = 10 alalım; maske s = 10'dur. Başlangıç: (|00⟩+|01⟩+|10⟩+|11⟩)/2 ⊗ |00⟩. Oracle'dan sonra: (|00⟩|01⟩+|01⟩|10⟩+|10⟩|01⟩+|11⟩|10⟩)/2. Çıktı yazmacını ölçüp 01 gördüğümüzü varsayalım: çıktısı 01 olan girdiler 00 ile 10'dur; girdi yazmacı (|00⟩+|10⟩)/√2 olur.

Şimdi H⊗2 uygulayalım. H⊗2|00⟩ = (|00⟩+|01⟩+|10⟩+|11⟩)/2'dir. H⊗2|10⟩ = (|00⟩+|01⟩−|10⟩−|11⟩)/2'dir, çünkü 10·z çarpımı z'nin ilk bitine eşittir ve o bit 1 olan terimler − alır. Toplayıp √2'ye bölünce (|00⟩+|01⟩)/√2 kalır; ölçüm %50 |00⟩, %50 |01⟩ verir. İki sonuç da 0 ile başlıyor: s = 10 iken s·z = 1·z₁ ⊕ 0·z₂ = z₁ olduğundan her ölçüm z₁ = 0 kısıtı verir.

Kısıt s'ye nasıl çevrilir? Diyelim başka bir denemede z = 01 okuduk; o zaman s·01 = s₂ = 0. s ∈ {00, 10} kaldı; f iki-bir olduğu için s ≠ 00, dolayısıyla s = 10. Oyuncak örnekte tek kısıt yetti; genel n'de n−1 bağımsız kısıt yeter. Denklemler bazen birbirinin kopyası çıkar; beklenen tekrar sayısı bu yüzden n'in hemen üstündedir. f bire birse (s = 0) ölçümler tüm z'ler üzerinde düzgün dağılır, sistem sıfır dışında çözüm vermez — f'nin bire bir olduğunun işaretidir.

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

Yeni öğrenenlerde en sık gördüğümüz kaymalar şunlar:

• "Ölçtüğüm z, s'nin kendisidir." Değil; z yalnızca s·z = 0 kısıtını taşır. s, kısıtlar toplandıktan sonra doğrusal cebirle çıkar.
• "İkinci yazmacı ölçmek hesabı bozar." Tam tersi: ölçüm girdi yazmacını tam da istediğimiz (|x₀⟩+|x₀⊕s⟩)/√2 durumuna çöker; ölçüm burada bilgi silmek değil, yapı filtrelemektir.
• "Birkaç ölçüm yeter." Her ölçüm tek bir doğrusal kısıt verir; bağımsız kısıt sayısı yetmezse sistem çok çözümlü kalır ve s belirsizliğini korur.
• "s = 0 algoritmayı bozar." Bozmaz; "fonksiyon bire birdir" bilgisini verir, söz bunu ayrı bir sonuç sayar.
• "Bu, tam sayı dönemeç bulmadır." Buradaki dönemeç XOR anlamındadır, grup (Z₂)ⁿ'dir; tam sayı dönemeçleri ise Kuantum Fourier Dönüşümü ile bulunur ve hikâye Shor Algoritması'nda doruğa çıkar.

Neden Önemli? BV, Shor ve BQP'ye Miras

Simon algoritması bir ailenin orta halkasıdır. Öncesinde Deutsch-Jozsa Algoritması aynı H – Uf – H iskeletini karar problemi için kullanmıştı; Bernstein-Vazirani Algoritması'nda ise f(x) = s·x doğrusal fonksiyonunun önemli stringi tek sorguda okunuyordu. Simon'da yapı daha derindedir: s doğrudan okunmaz, her ölçüm bir kısıt verir, n kısıt birleşince cevap çıkar. Sonrasında Shor bu fikri tam sayı dönemeçlerine ve çarpanlara ayırmaya genelledi; Gizli Alt Grup Problemi çerçevesi de ikisini aynı şemsiyeye koydu: Simon (Z₂)ⁿ üzerinde, Shor tam sayılar grubu üzerinde özel durumdur.

Karmaşıklık tarafındaki yeri de özeldir: Simon problemi, Olasılıksal Karmaşıklık BPP dersindeki klasik olasılıksal hesaplamadan oracle modelinde üstel biçimde ayrışan ilk örnektir; BQP'nin klasik simülasyonla açıklanamayacağına dair ilk kanıt budur. Pratik uygulaması az olsa da "kuantum ne zaman klasikten kökten üstün olur?" sorusunun ilk ikna edici cevabıdır; devamını Kuantum Karmaşıklık Sınıfı BQP dersinde okuyacaksın.

Özetle: gizli maskeyi bulmak, üst üste binme + oracle + girişim + ölçüm + biraz doğrusal cebirin ortak işidir. Aynı iskeletin tam sayı dönemeçlerinde nasıl genişlediğini görmek istersen Shor dersine geçebilirsin.

Kaynaklar ve İleri Okuma

Simon's algorithm — Wikipedia — problemin tanımı, algoritmanın adımları ve klasik alt sınır için özet madde.

Hidden subgroup problem — Wikipedia — Simon'ın özel durum olarak göründüğü genel çerçeve ve diğer örnekler.

The Quantum Algorithm Zoo — Simon'ı kapsayan abelyen gizli alt grubu algoritmalarının derlendiği katalog.