Temel Kuantum Fiziği ve Kuantum Teknolojilerine Giriş · 7. Ünite: Kuantum Hesaplama ve Kuantum Bilgi

Kuantum Fourier Dönüşümü ve Shor Algoritması

Peter Shor'un 1994'te verdiği algoritma, büyük bir tam sayıyı polinom zamanda asal çarpanlarına ayırarak kuantum hesaplamayı kuramsal bir meraktan stratejik bir teknolojiye dönüştürdü: bugün internetin büyük bölümünü koruyan RSA ve eliptik eğri kriptografisi bu problemin zorluğuna dayanır. Bu konuda önce kuantum Fourier dönüşümünü (QFT) klasik ayrık Fourier dönüşümüyle karşılaştıracak, çarpım biçimini türetip $O(n^2)$ kapılık devresini kuracak, faz kestirimi fikrini göreceksin. Ardından çarpanlara ayırmanın klasik bir indirgemeyle periyot (mertebe) bulmaya dönüştüğünü kanıtlayacak; modüler üs alma, ikinci yazmacın ölçümü, QFT sonrası $sQ/r$ civarındaki tepeler ve sürekli kesirlerle $r$'nin bulunmasını $N = 15$ ve $N = 21$ örnekleri üzerinde adım adım uygulayacaksın. Başarısızlık durumlarını, karmaşıklık karşılaştırmasını (polinom ile alt-üstel sayı cisim eleği), RSA'ya yönelik tehdidin bugünkü gerçek durumunu, küçük ölçekli deneysel gösterimleri ve kuantum sonrası kriptografiye geçişi tartışacaksın.

Öğrenme hedefleri

• Ayrık Fourier dönüşümü ile QFT'yi tanımlar, QFT'nin üniterliğini gösterir ve $q_0$ en anlamlı bit kuralıyla çarpım biçimini türetip $H$ ve kontrollü $R_k$ kapılarından oluşan $O(n^2)$ kapılık devreyi kurar.
• Faz kestirimi algoritmasının yapısını (kontrollü $U^{2^j}$, ters QFT) açıklar ve mertebe bulmanın $U_a|y\rangle = |ay \bmod N\rangle$ için bir faz kestirimi olduğunu gösterir.
• Çarpanlara ayırmanın mertebe bulmaya indirgenmesini kanıtlar: $r$ çift ve $a^{r/2}\not\equiv -1 \pmod N$ ise $\gcd(a^{r/2}\pm 1, N)$ aşikâr olmayan bir çarpandır; başarısız $a$ değerlerini $N = 15$ ve $N = 21$ için belirler.
• Kuantum mertebe bulma adımında QFT sonrası dağılımın $y \approx sQ/r$ civarında tepe yaptığını gösterir; ölçülen $y$'den sürekli kesir yakınsaklarıyla $r$'yi bulur ve $Q \ge N^2$ koşulunun rolünü açıklar.
• Shor algoritmasının polinom karmaşıklığını sayı cisim eleğinin alt-üstel karmaşıklığıyla karşılaştırır; RSA'ya yönelik tehdidi kaynak tahminleri, deneysel gösterimlerin sınırları ve kuantum sonrası kriptografi bağlamında değerlendirir.

Konu anlatımı

1. Bağlam: Çarpanlara Ayırma ve RSA

2. Ayrık Fourier Dönüşümü ve Kuantum Fourier Dönüşümü

3. Faz Kestirimi Fikri

4. Çarpanlara Ayırmanın Periyot Bulmaya İndirgenmesi (Klasik Kısım)

5. Kuantum Kısım: Modüler Üs Alma, Ölçüm ve QFT Tepeleri

6. Sürekli Kesirler, Başarı Olasılığı ve Başarısız Durumlar

7. Karmaşıklık, RSA'ya Tehdit ve Deneysel Durum

8. Çözümlü Örnekler

9. Sık Yapılan Hatalar ve Kavram Yanılgıları

Anahtar terimler

Kuantum Fourier dönüşümü (QFT)

$|x\rangle \to Q^{-1/2}\sum_k e^{2\pi ixk/Q}|k\rangle$; $n$ kubitte $O(n^2)$ kapıyla ($H$, kontrollü $R_k$, SWAP) kurulan üniter dönüşüm.

Faz kestirimi

$U|u\rangle = e^{2\pi i\varphi}|u\rangle$ için kontrollü $U^{2^j}$ ve ters QFT ile $\varphi$'nin ikili açılımını okuyan algoritma.

Mertebe (periyot)

$a^r \equiv 1 \pmod N$ sağlayan en küçük pozitif $r$; $f(x) = a^x \bmod N$ fonksiyonunun periyodu.

Modüler üs alma

$|x\rangle|1\rangle \to |x\rangle|a^x \bmod N\rangle$; Shor algoritmasının $O(n^3)$ kapılık en pahalı adımı.

Sürekli kesir yakınsağı

Bir kesrin sürekli kesir açılımının kesilmesiyle elde edilen en iyi rasyonel yaklaşımlar; $|y/Q - s/r| < 1/(2r^2)$ ise $s/r$ bunlardan biridir.

Shor algoritması

Çarpanlara ayırmayı mertebe bulmaya indirger, mertebeyi QFT ile polinom zamanda bulur; ayrık logaritmayı da çözer.

Genel sayı cisim eleği (GNFS)

En hızlı bilinen klasik çarpanlara ayırma algoritması; alt-üstel karmaşıklık $\exp[(1{,}923 + o(1))(\ln N)^{1/3}(\ln\ln N)^{2/3}]$.

RSA

Güvenliği $N = pq$'nun çarpanlarına ayrılmasının zorluğuna dayanan açık anahtarlı şifreleme; Shor algoritmasına karşı savunmasızdır.

Kuantum sonrası kriptografi

Klasik bilgisayarda çalışan ve bilinen kuantum saldırılarına dayanıklı kabul edilen algoritmalar; NIST 2024 standartları ML-KEM, ML-DSA, SLH-DSA.

Örnek soru

$N = 15$, $a = 7$ için $f(x) = 7^x \bmod 15$ fonksiyonunun periyodu (7'nin 15'e göre mertebesi) $r$ kaçtır?

1. $2$
2. $4$
3. $3$
4. $8$
5. $6$

Doğru cevap: B

Çözüm

1. $7^0 = 1$, $7^1 = 7$, $7^2 = 49 \equiv 4$, $7^3 = 28 \equiv 13$, $7^4 = 91 \equiv 1 \pmod{15}$.
2. İlk kez $7^r \equiv 1$: $r = 4$.
3. Kontrol: $\varphi(15) = 8$ ve $r$, 8'i böler.
"2" çeldiricisi $7^2 \equiv 4 \ne 1$ olduğunu gözden kaçırır; "8" $\varphi(N)$'nin kendisidir, mertebe onun bir bölenidir.

Temel Kuantum Fiziği ve Kuantum Teknolojilerine Giriş: tüm konular