Grover ayrıntılı: kâhin ve difüzyon

Grover algoritmasının iki parçasını ayrı ayrı incele: aranan cevabı işaretleyen kâhin ve onu büyüten difüzyon. Kâhini değiştirip başka bir cevabı bul.

İki adım: işaretle ve büyüt

Grover algoritması her turda iki şey yapar. Kâhin, aranan durumun fazını çevirir (genliğini eksi yapar); olasılıklar değişmez, işaret görünmezdir. Difüzyon adımı ise bütün genlikleri ortalamaları etrafında yansıtır: eksi olan genlik ortalamanın çok üstüne fırlar, diğerleri küçülür.

Bu “ortalama etrafında ters çevirme”, girişimin hesaplanmış bir kullanımıdır. Her tur doğru cevabın genliğini biraz daha büyütür.

Kâhini değiştirmek

İki kübitte CZ kapısı yalnızca 11 durumunun işaretini çevirir. Başka bir durumu işaretlemek için CZ’nin iki yanına X kapıları koyarız: q0’a X uygulayıp CZ’den sonra geri alırsak, q0’ı 0 olan durum 1’e çevrilip işaretlenir ve geri çevrilir. Böylece 10 işaretlenir.

Difüzyon kısmı (H, X, CZ, X, H) hangi cevabı aradığımızdan bağımsızdır. Algoritmayı yeni bir soruya uyarlamak için yalnızca kâhini değiştirmek yeter.

Kaç tur gerekir?

N seçenek varsa en iyi sonuç yaklaşık (π/4)·√N turda alınır. Dört seçenekte bu bir tura denk gelir ve sonuç %100’dür. Daha fazla tur yapmak sonucu bozar: genlik doğru noktayı geçip yeniden küçülür. Bu yüzden Grover’da tur sayısını doğru seçmek önemlidir.

Kendin dene

“10’u bul” örneğinde kâhindeki CZ’yi (dördüncü kapı) kaldır: hiçbir şey işaretlenmez ve dört sonuç da %25 kalır. Difüzyon tek başına bir şey bulamaz.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

Kâhin aranan durumun fazını çevirir; olasılıklar değişmez.
Difüzyon genlikleri ortalama etrafında yansıtarak işaretli durumu büyütür.
Başka bir cevabı aramak için yalnızca kâhin değişir.
N seçenekte yaklaşık (π/4)·√N tur gerekir; fazlası sonucu bozar.

Kendini sına

Grover’da kâhin tek başına uygulanıp ölçülürse ne görülür?

Aranan cevap %100
Bütün sonuçlar eşit olasılıkta
Hiçbir sonuç çıkmaz

Cevabı göster

Bütün sonuçlar eşit olasılıkta. Kâhin yalnızca fazı çevirir; olasılıklar değişmediği için difüzyon olmadan bütün sonuçlar eşit kalır.

← Bernstein–Vazirani: gizli diziyi tek seferde bul · Kuantum Fourier dönüşümü: periyodu yakala →