Shor Algoritması

Bu derste Peter Shor'un 1994'te tanıttığı Shor algoritmasını sıfırdan kuracağız: problemin neden zor olduğunu görecek, klasik ve kuantum iki yarısını inşa edip 15 sayısını uçtan uca çarpanlarına ayıracağız. Serinin tamamı için Kuantum Hesaplama dersleri sayfasına bakabilirsin. Kalbindeki aracı henüz görmediysen Kuantum Fourier Dönüşümü dersine kısa bir göz atman işini kolaylaştırır.

Çarpanlara Ayırma Problemi: Neden Zor?

Problem şu: 2.761 gibi bir N sayısı verildiğinde N = p × q eşliğini sağlayan asal p ve q'yu bul. RSA anahtarlarında N birkaç yüz basamaklıdır; bilinen en iyi klasik yöntemler bile N'nin basamak sayısında yarı üstel maliyetle çalışır. İki dev asalı çarpmak saniyeler sürerken çarpımını çözmek klasik makineler için pratikte imkânsızdır; RSA gibi açık anahtarlı şifrelemelerin güvenliği bu asimetriye dayanır.

Shor'un fikri çarpanları doğrudan aramak değil, problemi periyot bulmaya çevirmekti: rastgele bir a'nın mod N aritmetiğindeki ritmini bul, çarpanlar bu ritmin içinden kendiliğinden düşsün. Algoritma iki yarılıdır: klasik kısım problemi periyot bulmaya indirger, kuantum kısım periyodu polinom zamanda bulur. Bu "gizli ritmi yakala" deseni ünitenin ortak deseni: Simon Algoritması bit dizilerinde gizli maske arıyordu, Shor aynı fikri sayıların çarpımsal ritmine taşır.

Klasik Kısım: Rastgele a ve Periyodun Çarpanlara Çevrilmesi

Elimizdeki N tek ve asal olmayan bir sayı olsun. 1 ile N−1 arasında rastgele bir a seçer, öklid algoritmasıyla g = EBOB(a, N) hesaplarız. g > 1 ise şansımıza bir çarpan bulduk; kuantuma gerek kalmadı. g = 1 ise a ile N aralarında asaldır ve iş çarpımsal periyot bulmaya kalır: r, aʳ ≡ 1 (mod N) eşliğini sağlayan en küçük pozitif tamsayıdır. Klasik makine bu r'yi ancak deneyerek bulabilir; asıl sorun budur ve Shor'un kuantum yarısı tam bunu çözer.

Periyot neden çarpan verir? r çift ve a^(r/2) ≢ −1 (mod N) ise: N, aʳ − 1 = (a^(r/2) − 1) · (a^(r/2) + 1) çarpımını tam böler; ama a^(r/2) ≢ ±1 olduğundan (birincisi r'nin en küçüklüğünden, ikincisi koşuldan) hiçbir çarpana tek başına bölmez. Asal bölenler bu yüzden iki çarpan arasında bölünmüştür: EBOB(a^(r/2) − 1, N) ve EBOB(a^(r/2) + 1, N), 1 ile N arasında gerçek çarpanlardır. N iki farklı tek asalın çarpımıysa, rastgele a'nın bu iki koşulu sağlama olasılığı en az 1/2'dir; tutmazsa yeni bir a ile denersin, birkaç denemede başarı gelir.

Kuantum Kısım: Üst Üste Binme, QFT ve Sürekli Kesirler

İki kayıt açarız: birinci kayıt n kübitliktir ve Q = 2ⁿ değeri N² ≤ Q < 2N² koşulunu sağlar (N = 15 için Q = 256); ikinci kayıt sıfırdadır. Birinci kayda H kapılarını uygular, tüm x'lerin eşit genlikli süperpozisyonunu üretiriz:

ψ₁ = (1/√Q) Σₓ |x⟩|0⟩

Sonra ikinci kayıtta aˣ mod N'i kapılarla hesaplarız; kayıtlar bu sırada dolanır:

ψ₂ = (1/√Q) Σₓ |x⟩|aˣ mod N⟩

Burada aˣ mod N değerleri r adımlı bir tarak gibi davranır: x her r arttığında aynı değer geri gelir. İkinci kaydı ölçersen birinci kayıt, birbirinden r uzaklıkta x'lerin üst üste binmesine iner: ψ₃ = (1/√C) Σₖ |x₀ + kr⟩; C ≈ Q/r terim vardır ve 1/√C, olasılık toplamını 1'de tutan normalizasyondur. Periyot artık tarakta gizlidir; ama ölçüm tek bir x'i klasik değere çöker, gözle okunmaz.

Tarağı frekansa çeviren araç Kuantum Fourier Dönüşümüdür: birinci kayda QFT uygulayıp ölçersen sonuç yaklaşık y ≈ k · Q/r çıkar; k, 0 ile r−1 arasında rastgele bir tamsayıdır. Q ≥ N² seçimi sayesinde y/Q kesri k/r'ye 1/(2r²)'den iyi yakınsar ve sürekli kesir açılımı, paydası N'den küçük olan kesi tek başına belirler. EBOB(k, r) = 1 ise payda r'nin kendisidir; değilse küçültülmüş kesir gelir. Bu yüzden her sonucu sınanır: aʳ ≡ 1 (mod N) tutuyorsa bittik, tutmuyorsa yeniden ölçülür; birkaç tekrar başarıyı 1'e yaklaştırır.

Soyut okuma Faz Tahmini dersini bağlar: x ↦ a · x mod N permütasyonunu gerçekleyen U kapısının özdeğerleri e^(2πit/r) sayılarıdır (t = 0, …, r−1); fazın paydası periyodu taşır. Shor, periyot bulmayı faz tahminine indirgeyen bu makinenin en ünlü uygulamasıdır.

Uçtan Uca Örnek: 15'i Çarpanlarına Ayırmak

Gerçek deneylerin de ilk hedefi N = 15 olmuştur; a = 7 seçelim:

1. EBOB kontrolü: EBOB(7, 15) = 1; aralarında asal, kuantuma devam.
2. Periyot: 7¹ ≡ 7, 7² = 49 ≡ 4, 7³ ≡ 13, 7⁴ ≡ 1 (mod 15); yani r = 4. İkinci kayıt 7, 4, 13, 1, 7, 4, … diye tekrarlanır.
3. Koşullar: r = 4 çift; 7² ≡ 4 ≢ −1 ≡ 14 (mod 15). İki koşul da sağlanıyor.
4. Çarpanlar: EBOB(7² − 1, 15) = EBOB(48, 15) = 3 ve EBOB(7² + 1, 15) = EBOB(50, 15) = 5. Sonuç: 15 = 3 × 5.

Kuantum tarafı da sayılarla gelir: N² = 225 ≤ Q için Q = 2⁸ = 256 (n = 8 kübit) alınır. İkinci kayıtta 4 ölçüldüğünü düşün: bu değeri aˣ mod 15 eşitliğiyle veren x'ler 2, 6, 10, …, 254 kümesidir; uzaklıkları tam r = 4'tür. QFT sonrası ölçüm Q/r = 64'ün katlarına yığılır: y ∈ {0, 64, 128, 192}. y = 64 ise y/Q = 1/4 çıkar; sürekli kesirler r = 4'ü verir. y = 128 ise kesir 1/2'ye sadeleşir: aday r = 2'dir ama 7² ≡ 4 ≢ 1 (mod 15) sınaması bunu eler. Doğrulama süs değil, algoritmanın parçasıdır.

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

• "Her ölçüm doğru periyodu verir." Vermez: ölçüm, küçültülmüş k/r kesrini verebilir; bu yüzden aʳ ≡ 1 (mod N) sınaması ve gerektiğinde tekrar ölçüm zorunludur.
• "Shor, NP-tam problemleri çözer." Bilinmiyor ve sanılmıyor: çarpanlara ayırma NP'de ve co-NP'dedir; NP-tam olduğu düşünülmez, Shor'un varlığı P = NP demek değildir. Sınıfların ilişkisini Klasik Karmaşıklık Sınıfları P ve NP ve Kuantum Karmaşıklık Sınıfı BQP derslerinde işleyeceğiz.
• "Tüm şifreler kırılır." RSA ve eliptik eğri şifrelemesi büyük ölçekli bir kuantum makineye karşı savunmasızdır; ama AES gibi simetrik şifrelerde en hızlı kuantum saldırı Grover'dır ve yalnızca karesel hızlanma verir — anahtar uzunluğunu iki katına çıkarmak savunmaya yeter.

Bugünkü cihazlarda Shor, 15 ve 21 gibi küçük sayılar için gösterilmiştir; RSA-2048 ölçeği ise hata düzeltmesiyle korunan milyonlarca fiziksel kübit demektir ve henüz yoktur — cihaz sınırlarını Backend ve Cihaz Kavramı dersinde görmüştün. Algoritmanın genel çatısı Gizli Alt Grup Problemi dersinde kurulur; ardından kuantum hesaplamayı klasikle karşılaştıran karmaşıklık ünitesi gelir.

Kaynaklar ve İleri Okuma

Shor algoritması — Vikipedi (Türkçe) — algoritmanın adımlarını ve RSA etkisini özetleyen Türkçe madde.

Shor's algorithm — Wikipedia (English) — periyot bulma ve deneysel uygulamalar içeren ayrıntılı madde.

P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (arXiv:quant-ph/9508027) — algoritmanın yazarının kendi derleme makalesinin özeti.

IBM Quantum Learning — Fundamentals of Quantum Algorithms — faz tahmini ve Shor'u devre düzeyinde işleyen ücretsiz ders serisi.