N/M ile iki kübitli Grover araması: oracle'ı kurun, sonucu sınayın

Tek bir Grover iterasyonu tam olarak ne yapar?

Grover algoritması, N aday arasından işaretlenmiş bir girdiyi arar. Bunun için iki parçaya ihtiyaç duyar: işaretli durumun genliğinin işaretini çeviren bir oracle ve bu işaret farkını olasılık farkına dönüştüren bir difüzyon adımı. İki kübitte N = 4 aday vardır; bu, her genliği elle kontrol edebileceğimiz kadar küçük bir örnektir.

Bu rehberde devreyi N/M ile kuruyor, çıktısını tahmin ediyor ve ardından her seferinde tek bir parçasını değiştiriyoruz. Her şey yerel ve gürültüsüz bir simülatörde çalışır; burada fiziksel bir kuantum işlemcisi üzerinde ölçüm yapılmaz.

Devreyi çalıştırın

Deneme Alanı (Playground) sayfasını açın, aşağıdaki programı yapıştırın ve yerel durum vektörü simülatörüyle çalıştırın:

module blog_grover2;
@seed(31);
fn main() {
  let q = qreg[2];
  sample 512 {
    H(q[0]);
    H(q[1]);
    CZ(q[0], q[1]);
    H(q[0]);
    H(q[1]);
    X(q[0]);
    X(q[1]);
    CZ(q[0], q[1]);
    X(q[0]);
    X(q[1]);
    H(q[0]);
    H(q[1]);
    let c0 = measure(q[0]);
    let c1 = measure(q[1]);
  }
  return q;
}

İdeal modelde 512 örneğin tamamı 11 sonucunu verir. Tohum değeri örneklemeyi tekrar edilebilir kılar; ancak burada tekrar edilecek bir yayılım yoktur, çünkü tek bir sonucun olasılığı 1'dir.

Kodu okuyalım

Bu yazıdaki sonuçlar Deneme Alanı'nın gösterim kuralını izler: q[0] en sağdaki rakamdır. Yani 10, q[1] = 1 ve q[0] = 0 anlamına gelir; tek başına X(q[0]); çalıştırırsanız 01 görürsünüz. Başka araçlar bitleri farklı sıralayabilir; 01 ile 10'u karşılaştırmadan önce kuralı kontrol edin.

İlk iki H kapısı üniform süperpozisyonu oluşturur: 00, 01, 10 ve 11 durumlarının her birinin genliği 1/2'dir.

CZ(q[0], q[1]) oracle'ın kendisidir. 11 durumunun genliğini −1 ile çarpar, diğer üç duruma dokunmaz. Bütün olasılıklar hâlâ 1/4'tür; değişen yalnızca göreli fazdır.

Sonraki dokuz kapı difüzyon adımını oluşturur. X–CZ–X dizisi yalnızca 00 durumunun işaretini çevirir; çevresindeki Hadamard katmanları bunu üniform süperpozisyon etrafında bir yansımaya dönüştürür. Bu, standart "ortalama etrafında tersleme" işleminin −1 ile çarpılmış hâlidir. Aradaki fark küresel bir fazdır ve hiçbir ölçüm olasılığını değiştirmez.

Peki tek iterasyon neden yeterli? Başlangıç durumunu, işaretsiz durumların üniform süperpozisyonunun cos θ katı ile işaretli durumun sin θ katının toplamı olarak yazalım. N = 4 durum arasında M = 1 işaretli durum varken sin θ = √(M/N) = 1/2 olur; yani işaretli durumun başlangıç genliği 1/2, θ ise π/6'dır. Her Grover iterasyonu durumu bu iki boyutlu düzlemde 2θ kadar döndürür. Bu yüzden t iterasyondan sonra işaretli durumun olasılığı sin²((2t + 1)θ) olur. t = 1 için bu değer sin²(π/2) = 1'dir.

Ortalama etrafında tersleme aynı sonuca basit bir aritmetikle de ulaşır. Oracle'dan sonra genlikler 1/2, 1/2, 1/2 ve −1/2'dir; ortalamaları 1/4'tür. Her a genliğini ortalamaya göre yansıttığınızda, yani 2 · 1/4 − a hesabını yaptığınızda, 0, 0, 0 ve 1 elde edersiniz.

Değiştirin ve tahmin edin

Her çalıştırmadan önce tahmininizi yazın. Sonucu histogramdan ve ölçüm öncesi olasılıklardan okuyun. Son durum göstergesi, yazmacın son ölçümle çöktükten sonraki hâlini gösterir; bu yüzden burada her zaman tek bir sonuç bildirir.

1. Başka bir durumu işaretleyin. Oracle'daki CZ satırının hemen öncesine ve hemen sonrasına X(q[0]); ekleyin, difüzyon adımını olduğu gibi bırakın. X kapıları q[0] üzerinde 0 ile 1'in rolünü değiştirir; böylece işaret çevirme artık q[1] = 1, q[0] = 0 durumuna, yani ekranda 10 olarak görünen sonuca düşer. Tek iterasyon 10 sonucunu 1 olasılıkla verir. CZ'yi bunun yerine X(q[1]); ile çevrelerseniz 01, iki kübiti birden çevrelerseniz 00 işaretlenir.
2. Difüzyon adımını kaldırın. Oracle ile ölçümler arasındaki dokuz kapıyı silin. Oracle yalnızca fazı değiştirir ve hesaplama bazında yapılan bir ölçüm bu değişikliği göremez: dört sonucun her biri 1/4'te kalır.
3. İki iterasyon uygulayın. Ölçümden önce oracle'ı ve difüzyon adımını bir kez daha tekrarlayın. Dönme hedefi aşar: sin²(5θ) = sin²(5π/6) = 1/4 olur; aslında dört sonucun hepsi yeniden 1/4'e döner. Daha fazla iterasyon kendiliğinden daha iyi sonuç vermez; tek işaretli durum içeren N = 4 için en uygun sayı birdir.

Bu neyi göstermez?

Kuadratik avantaj, yapılandırılmamış aramadaki oracle sorgusu sayısıyla ilgilidir: klasik bir aramanın N mertebesinde sorguya ihtiyaç duyduğu yerde √N mertebesinde sorgu yeterlidir. Bu, çalışma süresi hakkında genel bir iddia değil, sorgu sayısıyla ilgili bir ifadedir.

Buradaki oracle, cevap önceden bilinerek yazıldı. CZ, 11 durumunu işaretliyor çünkü 11'i biz seçtik. Bu bir oyuncak örnektir; işe yarar bir oracle, çözümleri içinde barındırmadan tanıyabilmelidir ve bu devreyi kurmak çoğu zaman işin zor kısmıdır.

İki kübitte pratik bir hızlanma yoktur. Klasik bir program dört adayı zahmetsizce kontrol eder.

Gerçek maliyete oracle devresi ve gürültü de dahildir. Donanımda oracle ve difüzyon kapıları hata biriktirir; devre derinliği de kübit sayısıyla hızla artar. Bunların hiçbiri bu gürültüsüz modelde görünmez.

Sonraki adımlar ve kaynaklar

• N/M algoritmaları: incelenecek başka algoritma devreleri.
• N/M ile Bell durumu oluşturma: burada kullanılan iki kübitli örnekleme ve bit sırası alışkanlıkları.
• N/M belgeleri: H, X ve CZ dahil kapı başvurusu.
• Grover, "A fast quantum mechanical algorithm for database search" (1996): özgün algoritma ve O(√N) adım sayısı.
• IBM Quantum Learning: Grover algoritması, analiz: 2θ'lık dönme ve sin²((2t + 1)θ) formülü.
• IBM Quantum eğitimi: Grover algoritması: X kapılarıyla açık kontrol, en uygun iterasyon sayısı ve iki kübitli kapı derinliğinin büyümesi.

Bu yazıdaki olasılıklar, belirtilen ideal devrenin yerel ve gürültüsüz simülasyonunu anlatır; bir donanım deneyini bildirmez.