Shor algoritması: faz tahminiyle çarpanlara ayırma

Periyot bulmanın kuantum kısmı faz tahminidir. Ölçülen fazdan periyodu sürekli kesirlerle çıkar, Shor algoritmasının bugünkü durumunu ve şifreleme için ne anlama geldiğini öğren.

Periyot bir fazda saklıdır

Shor algoritması “y’yi a ile çarp, N’e böl, kalanı al” işini yapan bir U kapısı kurar. Bu kapıyı r kez uygulamak başa döndürür, çünkü aʳ mod N = 1’dir. Böyle bir kapının özdurumlarının fazları s/r biçimindedir; yani periyot doğrudan fazın içine yazılmıştır.

Orta seviye kursta gördüğün faz tahmini tam da bu fazı sayaç kübitlerinde ikili sayı olarak okur. Sayaçta önce H kapıları, ardından U’nun kontrollü kuvvetleri, en sonda da ters kuantum Fourier dönüşümü vardır. Ölçülen sayı m ise faz yaklaşık m / 2ⁿ olur.

Fazdan periyoda: sürekli kesirler

15 ve a = 7 için 3 sayaç kübiti yeterlidir. Ölçümde 0, 2, 4 ve 6 sayıları eşit olasılıkla çıkar; fazlar 0, 1/4, 1/2 ve 3/4 olur. Kesri sadeleştirince paydası periyot adayıdır: 1/4 ve 3/4 doğrudan r = 4 verir. 1/2’den çıkan 2 periyodun bir bölenidir, 0 ise bilgi vermez; o durumda algoritma bir kez daha çalıştırılır.

Büyük sayılarda ölçülen kesir sadeleşmiş hâliyle gelmez; doğru paydayı bulmak için sürekli kesirler denen klasik bir yöntem kullanılır. Python’daki Fraction sınıfı bunu limit_denominator ile yapar.

from fractions import Fraction

# 3 sayaç kübiti: ölçülen sayı m ise faz yaklaşık m / 8
for m in [0, 2, 4, 6]:
    faz = Fraction(m, 8)
    print(m, faz, 'r adayı:', faz.denominator)
# 0 0 r adayı: 1
# 2 1/4 r adayı: 4
# 4 1/2 r adayı: 2
# 6 3/4 r adayı: 4

Bugün nerede?

15 = 3 × 5, 2001’de yedi kübitlik bir kuantum bilgisayarda Shor algoritmasıyla ayrıldı. O günden beri gösterilen örnekler hâlâ çok küçük sayılardır; çünkü gerçek bir RSA anahtarını kırmak binlerce hatasız mantıksal kübit ve milyarlarca kapı gerektirir.

Craig Gidney’in 2025 tahminine göre 2048 bitlik bir RSA anahtarını bir haftadan kısa sürede kırmak için bir milyondan az gürültülü fiziksel kübit yeterli olabilir. Bugünkü en büyük cihazların bu sayının çok altında olması, tehdidin uzak ama gerçek olduğunu gösterir.

Şifreleme ne olacak?

Saldırganlar bugün şifreli verileri toplayıp yıllar sonra bir kuantum bilgisayarla çözmeyi bekleyebilir (“şimdi topla, sonra çöz”). Bu yüzden geçiş şimdiden başladı: ABD’nin standartlar kurumu NIST, 2024’te kuantum bilgisayarlara dayanıklı ilk şifreleme standartlarını (ML-KEM, ML-DSA ve SLH-DSA) yayımladı.

Bu yeni yöntemler klasik bilgisayarlarda çalışır ve kafes problemleri gibi Shor algoritmasının çözemediği matematiğe dayanır. Kuantum kriptografi ve post-kuantum şifreleme, okulun ileriki kurslarından birinin konusu.

Kendin dene

Bu faz tahmini devresi S kapısının fazını 01 / 4 = ¼ tur olarak okur. Shor algoritması aynı iskeleti kullanır; tek fark, S yerine “a ile çarp, N’e böl” kapısının gelmesidir ve okunan s/r kesrinin paydası periyodu verir.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

Shor algoritması aˣ mod N’in periyodunu faz tahminiyle bulur: fazlar s/r biçimindedir.
Ölçülen fazın paydası sürekli kesirlerle bulunur ve periyot adayını verir.
Gerçek RSA anahtarlarını kırmak için bugünkü cihazlardan çok daha büyük, hata düzeltmeli bilgisayarlar gerekir.
Post-kuantum şifreleme standartları (ML-KEM, ML-DSA, SLH-DSA) bu tehdide karşı şimdiden yayımlandı.

Kendini sına

Sayaçta ölçülen faz 3/4 ise periyot adayı nedir?

Cevabı göster

4. Faz s/r biçimindedir; sadeleşmiş kesrin paydası periyot adayıdır: 3/4 için r = 4.

← Periyot bulma: Shor algoritmasının kalbi · VQE: bir molekülün en düşük enerjisini bulmak →