Gizli Alt Grup Problemi

Kuantum algoritmaların yıldızları — Simon'dan Shor'un çarpanlara ayırmasına kadar — görünüşte farklı problemleri tek bir çatı altında çözer: gizli alt grup problemi (hidden subgroup problem, HSP). Bu derste problemi sıfırdan tanımlayacak, kuantum çözümünün üç adımlı iskeletini kuracak ve 2 kübitlik bir örneği uçtan uca hesaplayacağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin.

Gizli Alt Grup Problemi Nedir?

Elimizde bir G grubu ve üzerinde tanımlı bir f fonksiyonu var: f, G'nin elemanlarını bazı etiketlere eşliyor. G, birleşmeli bir işleme sahip ve her elemanının tersi bulunan bir kümedir; bir alt grup H ise G'nin içinde aynı işleme kapalı kalan küçük bir kümedir (tamsayılarda çift sayılar gibi). f'in verili sözü şu: f(g) = f(g′) ancak ve ancak g ile g′ H'nin aynı sınıfındaysa — yani g′ = g + h olacak biçimde bir h ∈ H vardır. Bu sınıflara H'nin koseti (kalan sınıfı) denir.

Somut benzetme: f, grubu H'nin sınıflarına göre boyar; aynı sınıftakiler aynı renk, farklı sınıflar farklı renk alır. H yalnızca 0'dan oluşuyorsa f birebirdir; H büyüdükçe f çok sayıda elemanı aynı etikete yapıştırır. Kara kutu şurada: f'i yalnızca sorgulayabilirsin — bir g verirsin, f(g) döner — ama H verilmemiştir. Görev, f'i olabildiğince az sorgulayıp H'yi üreten elemanları bulmak.

Tanınmış Halleri: Deutsch'dan Shor'a

Bu ünitedeki algoritmaların çoğu, farklı gruplar üstünde kurulu aynı problemdir:

• Deutsch ve Deutsch–Jozsa: G = ℤ₂ⁿ. f sabitse H = G'nin tamamı, dengeliyse H yalnızca {0…0}'dır; vaat budur. Ayrıntı için Deutsch Algoritması ve Deutsch-Jozsa Algoritması derslerine bak.
• Bernstein–Vazirani: f(x) = s · x (bit düzeyinde iç çarpım, mod 2). f(x) = f(y) tam olarak x ⊕ y ∈ H iken doğrudur; H = {a : s · a = 0} kümesidir ve H'yi bilmek s'yi bilmek demektir. → Bernstein-Vazirani Algoritması
• Simon: G = ℤ₂ⁿ ve H = {00…0, s}; bulunacak şey XOR maskesi s'dir. → Simon Algoritması
• Periyot bulma: G = ℤ ve H = r'ın katları; f'in gizli periyodu r'dir. Shor bu hâli çarpanlara ayırmaya, ayrık logaritma ise G = ℤₚ × ℤₚ versiyonuna bağlar. → Shor Algoritması ve Faz Tahmini

Ortak motor ise Kuantum Fourier Dönüşümüdür: aşağıdaki iskelet Fourier olmadan işe yarar bilgi üretmez.

Kuantum Çözümün İskeleti: Üç Adım

Adım 1 — üniform süperpozisyon. Giriş kaydını G'nin tüm elemanlarının eşit genlikte olduğu duruma getir: |ψ₁⟩ = (1/√|G|) Σ_{g∈G} |g⟩|0⟩. Tek hamlede tüm g'ler f'e sorulmak üzere masaya gelir.

Adım 2 — f sorgusu. |g⟩|b⟩ → |g⟩|b ⊕ f(g)⟩ eşlemesini yapan üniteryen U_f'i uygula; durum |ψ₂⟩ = (1/√|G|) Σ_{g∈G} |g⟩|f(g)⟩ olur. Adım 3 — çıkış kaydını ölç. Ölçüm bir f değeri döndürür, diyelim v. Girişte yalnızca f(g) = v olan terler hayatta kalır ve bunlar tam olarak H'nin bir kosetidir; normalizasyonla durum |ψ₃⟩ = (1/√|H|) Σ_{h∈H} |g₀ + h⟩ hâline gelir. Paydada √|H| vardır çünkü kosette tam |H| teri bulunur ve olasılıkların toplamı 1 olmalıdır. H'yi henüz görmedik: g₀ her denemede değişir ve okunamaz; taşınan tek şey kosetin yapısıdır.

İşte bu yüzden dördüncü, klasik adım şarttır: koset durumlarına QFT uygula, ölç, tekrarla. ℤ₂ⁿ üstünde QFT, Hadamard kapıları dizisidir ve her ölçüm y · s = 0 biçiminde bir denklem düşürür; ℤ üstünde ise olasılıklar r'nin katlarında pik yapar ve devamlı kesirlerle r çıkar. Kuantum kısmın işi H'yi doğrudan vermek değil, H hakkında kısa yoldan denklem üretmektir.

Küçük Bir Örnek: 2 Kübitlik Simon Adımı

G = ℤ₂² olsun; gizli maske s = 10, dolayısıyla H = {00, 10}. f şöyle verilsin: f(00) = f(10) = 5 ve f(01) = f(11) = 2. Akışı adım adım izle:

1. Üniform durum: (1/2)(|00⟩ + |01⟩ + |10⟩ + |11⟩)|0⟩; U_f'ten sonra çıkış kaydında f(x) değerleri belirir.
2. Çıkışı ölç; 5 geldi diyelim. Giriş, 5'e eşlenen kosete çöker: (|00⟩ + |10⟩)/√2. Koset iki terli olduğu için katsayı 1/√2'dir.
3. Her iki kübite Hadamard uygula: |00⟩ → (1/2)(|00⟩ + |01⟩ + |10⟩ + |11⟩) ve |10⟩ → (1/2)(|00⟩ + |01⟩ − |10⟩ − |11⟩). Toplam: (1/√2)(|00⟩ + |01⟩); |10⟩ ve |11⟩ bileşenleri tamamen silinir.
4. Ölç: sonuç ya 00 (bilgisiz, olasılığı 1/2) ya da 01'dir. 01 gördüğünde denklem elindedir: y · s = 0 → 01 · 10 = 0 → s'nin ikinci biti 0'dır. s ≠ 00 olduğundan s = 10 çıkar; n = 2 için tek bağımsız denklem yeterlidir.

Sonucu doğrula: her x için f(x ⊕ 10) = f(x) gerçekten sağlanıyor. Büyük n'de her ölçüm, y · s = 0 koşulunu sağlayan rastgele bir y verir; yaklaşık n − 1 bağımsız y, lineer sistemi s'ye çözer. 00 gibi bilgisiz sonuçlar yeniden deneme gerektirir.

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

• “Devre H'yi doğrudan yazdırır.” Hayır; kuantum kısmı rastgele kosetler ve denklemler üretir; son adım klasiktir: Simon'da lineer sistem, periyot bulmada devamlı kesirler.
• “Tek ölçüm yeter.” Hayır; 00 gibi bilgisiz sonuçlar düzenli gelir, denemeler bağımsız tekrarlanır; olasılıkları Sonuçların İstatistiksel Analizi dersindeki çerçeveyle oku.
• “Koset durumunda g₀'ı okuyabilirim.” Ölçtüğünde yalnızca rastgele bir g₀ + h görürsün; faydalı bilgi genliklerin yapısındadır. Hadamard ya da QFT olmadan koset durumu boşa gider.
• “HSP'nin tamamı çözülmüştür.” Yalnızca abelian (değişmeli) gruplarda polinom zamanda verimliyiz. Non-abelian durumda genel çözüm açık bir sorundur; simetrik grupta çözüm, graf izomorfizmini de çözerdi; dihedral grupta Kuperberg'in alt-üstel zamanlı algoritması bilinir.

Kuramsal yerini merak ediyorsan: HSP, BQP sınıfının bayraktar örneklerindendir — sınırlarını Kuantum Karmaşıklık Sınıfı BQP dersinde, klasik tarafı ise Klasik Karmaşıklık Sınıfları P ve NP dersinde işliyoruz. Özet: süperpozisyon kur, tek toplu sorgu sor, koset topla, Fourier ile denklemlere çevir, gerisi klasik.

Kaynaklar ve İleri Okuma

Hidden subgroup problem — Wikipedia — problemin tanımı ile abelian ve non-abelian durumunun karşılaştırması.

Simon's problem — Wikipedia — ℤ₂ⁿ üzerindeki özel hâlin algoritmik çözümü.

D. R. Simon, “On the Power of Quantum Computation”, SIAM J. Comput. 26(5):1474–1483 (1997) — bu çatıyı başlatan 1994 makalesinin dergi sürümü.

P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” (arXiv:quant-ph/9508027) — periyot bulmayı çarpanlara ayırmaya bağlayan klasik makale.

IBM Quantum Learning — kuantum algoritmaların genel çatısını anlatan ücretsiz ders serisi.