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

Grover Arama Algoritması

Yapısı olmayan bir arama problemi, $N$ olasılık arasından bir koşulu sağlayanı bulmaktır ve klasik olarak ortalama $N/2$ deneme gerektirir. Lov Grover'ın 1996'da verdiği kuantum algoritması aynı işi yaklaşık $(\pi/4)\sqrt N$ orakl sorgusuyla yapar. Bu konuda oraklın işaretli öğelerin genliğini nasıl ters çevirdiğini, yayılım operatörü $2|s\rangle\langle s| - I$'nin neden "ortalama etrafında yansıma" olduğunu ve bu iki yansımanın bileşkesinin iki boyutlu bir düzlemde $2\theta$ açılı bir dönme olduğunu türeteceksin. $\sin\theta = \sqrt{M/N}$ ile başarı olasılığını $\sin^2((2k+1)\theta)$ olarak hesaplayacak, optimal iterasyon sayısını bulacak, fazla döndürmenin olasılığı neden düşürdüğünü göreceksin. Karekök hızlanmanın optimal olduğunu (BBBV alt sınırı), $M$ bilinmediğinde ne yapıldığını, "veri tabanı araması" ifadesinin neden yanıltıcı olduğunu ve simetrik şifrelerde anahtar uzunluğunu iki katına çıkarma önerisini tartışacaksın.

Öğrenme hedefleri

• Yapısız arama problemini orakl modelinde tanımlar; faz oraklının $O|x\rangle = (-1)^{f(x)}|x\rangle$ biçiminde $U_f$ ve $|-\rangle$ yardımcısıyla kurulduğunu gösterir.
• Yayılım operatörü $D = 2|s\rangle\langle s| - I$'nin her genliği $a_x \to 2\bar a - a_x$ biçiminde ortalama etrafında yansıttığını türetir ve bir iterasyon sonrası genlikleri hesaplar.
• $G = DO$'nun $\{|w\rangle, |s'\rangle\}$ düzleminde $2\theta$ dönme olduğunu, $\sin\theta = \sqrt{M/N}$ ve $P_k = \sin^2((2k+1)\theta)$ olduğunu gösterir; optimal $k \approx (\pi/4)\sqrt{N/M}$ değerini ve fazla döndürmenin etkisini hesaplar.
• Karekök hızlanmanın BBBV alt sınırıyla optimal olduğunu ve bunun NP-tam problemler için anlamını açıklar; $M$ bilinmediğinde üstel artışlı rastgele $k$ stratejisini ve kuantum saymayı nitel olarak tanımlar.
• Grover algoritmasının uygulamalarını ve sınırlarını (orakl kurulumu, QRAM, paralelleştirme, hata düzeltme maliyeti) değerlendirir; simetrik şifrelerde etkin güvenliğin yarıya indiğini ve anahtar uzunluğunun iki katına çıkarılması önerisini açıklar.

Konu anlatımı

1. Bağlam: Yapısız Arama Problemi

2. Orakl ve Faz Çevirme

3. Yayılım Operatörü: Ortalama Etrafında Yansıma

4. Geometrik Yorum: İki Boyutlu Düzlemde Dönme

5. Optimallik, Bilinmeyen M ve Genlik Büyütme

6. Uygulamalar, Sınırlar ve Kriptografi

7. Çözümlü Örnekler

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

Anahtar terimler

Yapısız arama

Yalnızca orakl sorgusuyla erişilen bir $f$ için $f(x) = 1$ olan bir $x$'i bulma; klasik olarak $\Theta(N/M)$ sorgu gerektirir.

Faz oraklı

$O|x\rangle = (-1)^{f(x)}|x\rangle$; işaretli öğelerin genlik işaretini çevirir, $U_f$ ve $|-\rangle$ yardımcısıyla kurulur.

Yayılım operatörü

$D = 2|s\rangle\langle s| - I$; her genliği $a_x \to 2\bar a - a_x$ ile ortalama etrafında yansıtır.

Grover iterasyonu

$G = DO$; $\{|w\rangle, |s'\rangle\}$ düzleminde durumu $|w\rangle$'ye doğru $2\theta$ döndürür.

Grover açısı θ

$\sin\theta = \sqrt{M/N}$; başlangıç durumunun işaretsiz eksenle yaptığı açı. $k$ iterasyonda başarı $\sin^2((2k+1)\theta)$.

Aşırı döndürme

Optimal $k^* \approx (\pi/4)\sqrt{N/M}$ aşılınca başarı olasılığının yeniden düşmesi.

BBBV alt sınırı

Yapısız arama için her kuantum algoritmasının $\Omega(\sqrt N)$ sorgu gerektirdiği sonucu; Grover asimptotik olarak optimaldir.

Genlik büyütme

Başarı olasılığı $p$ olan bir algoritmayı $O(1/\sqrt p)$ tekrarda yüksek başarıya çıkaran genel yöntem; Grover özel durumudur.

QRAM

Kayıtları süperpozisyonda adresleyebilen varsayımsal kuantum bellek; klasik veri tabanında Grover için gereklidir, bugün ölçekli bir gerçekleşmesi yoktur.

Örnek soru

$N = 16$ öğelik yapısız bir aramada tek bir işaretli öğe var ($M = 1$). Başarı olasılığını en büyük yapan Grover iterasyon sayısı $k$ kaçtır?

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

Doğru cevap: C

Çözüm

1. $\sin\theta = \sqrt{1/16} = 1/4 \Rightarrow \theta = 14{,}48°$.
2. $k^* = \pi/(4\theta) - 1/2 = 3{,}11 - 0{,}5 \approx 2{,}6$; aday tam sayılar 2 ve 3.
3. $P_2 = \sin^2(5\theta) = \sin^2(72{,}4°) = 0{,}908$; $P_3 = \sin^2(7\theta) = \sin^2(101{,}3°) = 0{,}961$.
4. $k = 3$. ($(\pi/4)\sqrt{16} = 3{,}14$ yaklaşımı da 3'e yuvarlanır.)
"4" çeldiricisi $\sqrt N$'yi kullanmaktır ($P_4 = 0{,}582$, aşırı döndürme); "8" klasik ortalama sorgu sayısı $N/2$'dir.

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