İlk algoritman: Grover araması

Dört seçenek içinden işaretli olanı tek adımda bulan Grover algoritmasını adım adım kur ve çalıştır. Kuantum hızlanması ne kadar büyük, neyi hızlandırmaz?

Problem: ödül hangi kutuda?

Dört kapalı kutudan birinde ödül var. Bir kutuyu açmadan içine bakamazsın ama bir “kontrol cihazına” sorup cevap alabilirsin. Klasik olarak en şanslı durumda 1, en kötü durumda 3 soru gerekir (üçü boşsa dördüncüyü sormana gerek kalmaz); ortalama 2,25 soru.

Grover algoritması bu problemi tek bir soruyla, kesin olarak çözer. Bu derste kutular 00, 01, 10 ve 11 diye numaralandırıldı. Ödül 11 numaralı kutuda.

Adım 1: tüm kutuları süperpozisyona al

İki kübitin her birine H uygularız. Artık dört sonucun her biri %25 olasılıklıdır. Bu noktada ölçseydik rastgele bir kutu seçmiş olurduk.

Adım 2: doğru cevabı işaretle (oracle)

Kontrol cihazı (oracle) doğru kutunun genliğinin işaretini çevirir: +0,5 olan genlik −0,5 olur. Bu örnekte bunu CZ kapısı yapar, çünkü CZ yalnızca iki kübit de 1 iken işaret değiştirir.

Dikkat et: olasılıklar hâlâ %25. İşaret değişikliği görünmez, ama bir önceki derste öğrendiğin gibi girişimde fark yaratacak.

Adım 3: ortalamaya göre yansıt (yayılım)

Yayılım adımı (H, X, CZ, X, H kapıları), her genliği tüm genliklerin ortalamasına göre aynalar. Ortalama +0,25’tir. Diğer üç kutunun +0,5’lik genlikleri yansıyınca 0 olur. İşaretli kutunun −0,5’lik genliği ise yansıyınca +1 olur.

Sonuç: 11 numaralı kutunun olasılığı %100. Tek bir oracle sorgusuyla ödülü kesin olarak bulduk.

Ne kadar hızlı?

N seçenek varsa klasik arama ortalama N/2 soru ister. Grover yaklaşık 0,785 × √N soruda bulur. Bir milyon seçenekte bu, 500.000 yerine yaklaşık 785 soru demektir.

Dürüst olmak gerekirse bu “karesel” bir hızlanmadır, sınırsız değildir. Bugünkü gürültülü cihazlarda büyük aramalar için henüz pratik değildir. Bazı problemlerde (örneğin Shor algoritmasıyla çarpanlara ayırmada) kuantum bilgisayarların çok daha büyük, üstel bir avantaj sağlaması beklenir.

Sırada ne var?

Tebrikler, ilk kuantum algoritmanı çalıştırdın! Deneme alanında “Bu devrenin Qiskit kodu” bağlantısına tıklayarak aynı programı kendi bilgisayarında da çalıştırabilirsin.

Devam etmek için mağazadaki “İlk kuantum algoritmaları”, 3 kübitlik Grover araması içeren “Qibo ile Grover araması” ve “Shor algoritmasıyla 15’i çarpanlarına ayır” paketlerine bak ya da “Kuantum programlamaya sıfırdan başla” öğrenme yolunu takip et.

Kendin dene

1000 kez ölç: sonuç her seferinde 11. Sonra devredeki üçüncü kapıyı (ilk CZ, yani oracle) tıklayarak kaldır ve yeniden ölç. İşaretleme olmadan algoritma hiçbir kutuyu öne çıkaramaz ve dört sonucun hepsi %25 olur.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

Grover algoritması süperpozisyon, işaretleme (oracle) ve yayılım adımlarından oluşur.
Oracle doğru cevabın genliğinin işaretini çevirir; yayılım bunu girişimle büyütür.
4 seçenekte tek bir sorgu yeter; N seçenekte yaklaşık √N sorgu gerekir.
Grover’ın hızlanması kareseldir; bazı problemlerde kuantum avantajı çok daha büyüktür.

Kendini sına

Grover algoritmasında oracle adımı ne yapar?

Doğru cevabı ölçer ve ekrana yazar
Doğru cevabın genliğinin işaretini çevirir
Yanlış cevapları devreden siler

Cevabı göster

Doğru cevabın genliğinin işaretini çevirir. Oracle, olasılıkları değiştirmeden doğru cevabın genliğini negatif yapar. Yayılım adımı bu işaret farkını girişimle büyük bir olasılığa dönüştürür.

← Girişim: kuantum bilgisayarın gizli gücü · Öğrenme yollarına geç →