Yazan : Şadi Evren ŞEKER
1996 yılında kuantum hesaplamalarının gelişimiyle birlikte, sıralanmamış bir veri tabanı üzerinde arama yapmak üzere geliştirilmiş algoritmadır.
Bilindiği üzere sıralanmamış bir verinin üzerinde arama yapmanın en basit ve en hızlı yolu doğrusal arama (linear search) algoritmasını kullanmaktır. Yani, en kötü ihtimalle, verinin tamamına bakmaktır. Bu algoritmanın büyük-O (growth rate, worst case analysis) değeri O(n)’dir.
Kuantum hesaplamaları, bize bu konuda daha başarılı bir sonuç verebilmektedir. Grover Algoritması sayesinde, sıralı olmayan bir veri kaynağında, veri aramak için, O(n ½) , yani n eleman için n’in karekökü kadar elemana bakmak yeterlidir.
Algoritma iki adımda düşünülebilir. İlk aşamada algoritmanın hazırlanması (setup) ikinci aşamada ise algoritmanın çalışmasını inceleyeceğiz.
Hazırlık aşaması (setup)
Algoritmanın kullanılabilmesi için öncelikle algoritmanın çalışacağı problem uzayını tanımlayalım. Problemimiz N adet sıralanmamış verinin içerisinden bir verinin aranarak bulunması olsun. Bu durumda Grover algoritması log2 N qubitten oluşan bir H durum uzayı oluşturur. Bu uzayın özelliği N boyutlu olmasıdır. Burada N boyutlu olması ile kastedilen, N adet birbirinden farklı eigen değeri içermesidir. Yani H uzayını aşağıdaki şekilde dirac gösterimiyle ifade edecek olursak
Uzayda bulunan her eleman için ilgili eigen değeri, aşağıdaki şekilde gösterilebilir:
Bu uzayda çalışan bir uniform işlem tanımlıyor olalım. Bu işlemi Uω, ile gösterelim. Bu işlem için basit bir arama kriteri belirlenmesi yeterlidir. Yani uzayımızda yapılacak olan arama veya daha başa dönersek sıralı olmayan veri tabanı üzerinde yapılan aramam kriteri bu kuantum işlemi Uω, üzerinde tanımlı olsun. Bu işlemin indis kısmında belirtilen omega değeri ( w ) aslında bu işlemin arama sonucunda bulunmasını istediğimiz değerin w olduğunu belirtir. Diğer bir deyişle, N adet veriyi aradıktan sonra bulmak istediğimiz ver w sırasında bulunan veri olsun.
Bu verinin eigen durumu (eigenstate) ise |w> şeklinde gösterilen durumdur. Aynı zamanda eigen değeri (eigen value) ise yukarıdaki tanımlamada lw ile gösterilen değerdir.
Diğer bir deyişle Uω
işleminin, aşağıdaki özelliği taşımasını istiyoruz:
Algoritmanın üzerinde çalıştığı ve algoritma için en kritik nokta olan Uω, aslında bir kara kutu (Blackbox) olarak düşünülebilir. Bu konuda quantum kapılarından (quantum Gates) tasarlanmış bir devre olarak da düşünülebilir.
Amacımız bu devrenin aradığımız değeri bulması halinde 1 döndürmesi ve bunun dışındaki bütün ihtimallerde 0 döndürmesi şeklinde tanımlanabilir.
Algoritmanın Çalışması
Yukarıdaki hazırlık işlemleri tamamlandıktan sonra, algoritmanın çalışmasına geçebiliriz. Kısaca, hazırlık aşamasında bir adet Uω, tasarlanmış ve aramanın yapılacağı bütün N değer için eigen halleri (eigenstates) ve eigen değerleri (eigenvalue) çıkarılmıştır.
Bu aşamada, algoritmanın ulaşmak istediği hedefi aşağıdaki şekilde tanımlayabiliriz:
- Anlık olarak durum bilgisi s değişkeninde tutulmak üzere:
değeri hesaplanır
-
Her bir r(N) işlemi, bir grover döngüsü olmak üzere (grover iteration),
- Uω İşlemi uygulanır
- Us İşlemi uygulanır
- Ω ölçümü yapıldığında, ölçüm sonucu 1’e yakın bir olasılıkla λω olarak bulunacaktır bulunan bu λω değerinden ω değerine ulaşılabilir.
Yukarıdaki algoritmada 1’e yakın olasılık kısmı özel olarak altı çizilmesi gereken kısımdır, bunun sebebi grover algoritmasının kesin sonuç değil olasılıksal sonuç üretmesidir.
Grover Algoritmaının Kuantum Kapıları ile gerçeklenmesi
Yukarıdaki algoritmada bulunan 2. adım, yani grover döngüsü (grover iteration) aşağıdaki şekilde temsil edilebilir.
Basit bir kahin makinesi (qunatum oracle machine), elimizde bulunan arama uzayında çalışmaktadır. Bu makine, yukarıdaki algoritmada Uω ile gösterilen dönüşüm işlemidir. Klasik bir kahin makinesinde olduğu gibi, aranan veri için özel olarak tersini alma işlemi yapmaktadır. Diğer bütün verileri olduğu gibi geçirmektedir.
Ayrıca sıfır durum hal kaydırması (Zero state phase shift) devresi ile de Hadamard kapıları arasında, kahin makinesinin işaretlediği kubitin değerini arttırıyoruz. Yani, kahin makinesi n adet kubitten bir tanesini işaretliyor, HZH kombinasyonu ise bu işaretli kubiti arttırıp, diğer kubitlerin değerlerini düşürüyor. Neticede tek bir kubit diğerlerinden daha yüksek değere sahip oluyor. Bu işlem sürekli olarak tekrar edildiğinde de işaretli kubit, diğerlerinden ayırt edilecek kadar (neredeyse, diğerleri 0 ve işaretli kubit ise 1 olacak kadar) belirgin oluyor.
Bunu hayal etmek biraz güç olabilir o yüzden görsel bir şekilde ifade etmeye çalışalım:
Örnek olarak, N adet kubit için yukarıdaki hadamard kapısı sonucunu ele alalım. Buradaki her kubitin genlik değeri (amplitude) düşey eksende gösterilmiştir ve ayrıca ilk grover döngüsü sırasında hepsi eşittir. Yani bütün genlikler eşit bir şekilde çalışmaya başlıyoruz.
İlk döngüden sonra kubitlerin değeri aşağıdaki hali alıyor:
Görüldüğü üzere bütün kubitlerin genliği azalırken, özel olarak seçilmiş olan bir kubitin genliği artmaktadır.
İstatistiksel olarak bu işlemin, n adet kubit için, n değerinin karekökü kadar tekrar edilmesi yeterlidir.