Grover — genlik artırma ile karekök hızlanma

Grover Algoritması, sıralanmamış bir veri tabanında belirli bir öğeyi klasik bilgisayarlardan çok daha hızlı bulan bir kuantum genlik artırma protokolüdür. 1996 yılında Lov Grover tarafından önerilmiştir. Buradaki hızlanma, doğru cevabın olasılığını ölçümden önce yükseltmeye dayanır.

Bu yaklaşım, kuantum paralelliğinin sıkça yanlış anlaşılan noktasını netleştirir: Grover “tüm elemanları aynı anda okuyup” doğru olanı sihirli şekilde çekmez. Bunun yerine, oracle ile doğru cevabı fazdan işaretler, diffüzör ile bu işareti ortalama etrafında yansıtıp büyütür. Ölçüm, yalnızca en sonunda yapılır.

Elinizde N elemanlı (ör. 1 milyon) karışık bir liste olduğunu ve aradığınız tek bir doğru sonuç olduğunu düşünün.

• Klasik yaklaşım

  Elemanları tek tek kontrol edersiniz. En kötü durumda N, ortalamada N/2 deneme gerekir (O(N)).

• Kuantum yaklaşımı (Grover)

  Süperpozisyon ve girişim sayesinde doğru sonuç yaklaşık √N adımda bulunur (O(√N)).

• Klasik maliyet

  Sıralanmamış aramada tek tek deneme doğası gereği baskındır: ortalama N/2, en kötü N kontrol (O(N)).

• Kuantum maliyet

  Grover, oracle + diffüzör döngüsünü yaklaşık k ≈ (π/4)·√N kez çalıştırarak hedef genliği büyütür (O(√N)).

• Neden “tam √N” değil?

  İterasyon sayısı bir döndürme gibi davranır. Fazla iterasyon, hedef genliği tepe noktayı geçip tekrar düşürebilir; bu yüzden doğru durma noktası kritiktir.

Grover’ın sırrı “aramak” değil, doğru sonucun olasılığını yükseltmektir. Algoritma iki ana operatörün sürekli tekrarından oluşur (Grover Iteration).

• Oracle (işaretleyici)

  Aranan elemanı belirler ve onun fazını tersine çevirir (ona bir eksi işareti takar). Diğer tüm elemanlar aynı kalır.

• Diffüzör (yansıtıcı)

  Tüm durumların genliklerini ortalama genlik etrafında “aynalar”. Bu işlem, oracle tarafından işaretlenen (eksi fazlı) elemanın genliğini büyütürken, yanlış sonuçların genliklerini sönümler.

Oracle ve diffüzör birlikteliğini iki aynalı bir sistem gibi düşünebilirsiniz. Oracle, doğru cevabı bulup onu “eksi” düzlemine iten ilk aynadır; diffüzör ise tüm sistemi kendi ortalaması etrafında katlayan ikinci aynadır. Bu ardışık iki yansıma, doğru cevabın genliğini her adımda geometrik olarak artırırken, yanlış cevapları birbirini sönümlemeye zorlar.

Grover iterasyonu, tüm Hilbert uzayında “karmaşık” görünse de, pratikte iki boyutlu bir düzlemde döndürme gibi düşünülebilir: hedef durum(lar)ın oluşturduğu altuzay ve geri kalan “hedef olmayan” altuzay. Her iterasyon hedef genliğini biraz daha büyüten kontrollü bir açı ekler.

Bu yüzden en kritik tasarım sorusu şudur: Kaç iterasyon? Yaklaşık kural, tek hedef için k ≈ (π/4)·√N; birden çok hedef varsa k ≈ (π/4)·√(N/M) (M: işaretli çözüm sayısı).

1. 1

   Hazırlık

   n kübit ile N=2^n durumluk arama uzayı kurulur. Başlangıç durumu |0…0⟩.

2. 2

   Süperpozisyon

   Tüm giriş kübitlerine Hadamard uygula ve “eşit dağılımlı” başlangıç genliklerini elde et.

3. 3

   Grover döngüsü (oracle + diffüzör)

   Oracle hedef(leri) fazdan işaretler (phase flip). Diffüzör bu işareti ortalama etrafında yansıtır. Bu ikiliyi k kez tekrarla.

4. 4

   Ölçüm ve yorum

   Ölçümde hedef bit dizisinin baskın gelmesini beklersin. Gürültülü donanımda histogram “tam 1” yerine yüksek bir oran verir.

Aşağıdaki örnek, n=2 kübit ile 4 elemanlı uzayda |11⟩ durumunu hedefler. Basit bir oracle olarak cz kullanıyoruz.

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator


def grover_iteration(qc, qubits):
    # 1. ORACLE: |11⟩ durumunu işaretle (phase kickback)
    qc.cz(qubits[0], qubits[1])
    qc.barrier()

    # 2. DIFFUSER: genliği ortalama etrafında yansıt
    qc.h(qubits)
    qc.z(qubits)
    qc.cz(qubits[0], qubits[1])
    qc.h(qubits)
    qc.barrier()


# 2 kübitlik devre (4 elemanlı liste)
n = 2
qc = QuantumCircuit(n, n)

# Adım 0: Tüm durumları süperpozisyona al (eşit olasılık)
qc.h(range(n))
qc.barrier()

# Adım 1: Grover iterasyonu (n=2 için 1 tekrar yeterlidir)
grover_iteration(qc, [0, 1])

# Adım 2: Ölçüm
qc.measure(range(n), range(n))

# Simülasyon
simulator = AerSimulator()
result = simulator.run(qc, shots=1024).result()
counts = result.get_counts()

print("\\nÖlçüm Sonuçları (|11⟩ en yüksek çıkmalı):")
print(counts)

qc = QuantumCircuit(n, n) satırı, n adet kuantum kübit ve n adet klasik bit (ölçüm için) oluşturur. Bu örnekte n=2 olduğu için arama uzayı N=2^n=4 elemanlıdır.

qc.h(range(n)) adımı, başlangıçtaki |00⟩ durumunu eşit süperpozisyona taşır. Bu noktada devre “hangi elemanın doğru olduğunu” bilmez; tüm adaylar aynı genlikte başlar. Grover’ın büyüsü, bu genlikleri ölçümden önce yeniden dağıtmaktır.

qc.cz(q0, q1) burada minimal oracle’dır: yalnızca |11⟩ durumunun fazını çevirir. Yani hedef durumu (-1) ile işaretlerken diğer durumlara dokunmaz. Bu “işaret” tek başına ölçümde görünmez; diffüzör bu faz bilgisini olasılığa çevirmek için vardır.

diffüzör bloğu, genlikleri ortalama etrafında yansıtır. Kodda bu fikir, H → Z → CZ → H dizisiyle temsil ediliyor. Bu kombinasyon, “hedef olmayan” altuzay ile “hedef” altuzay arasındaki açıyı biraz daha hedefe doğru döndürür; bu yüzden iterasyonlar biriken bir kazanç değil, kontrollü bir salınım üretir.

qc.measure(...) ölçüm anıdır: genlik artırma başarılı olduysa 11 bit dizisi histogramda baskın çıkar. Simülasyonda shots=1024 seçmek, dağılımın görünür olmasını sağlar; ideal gürültüsüz modelde hedef çıktı çok yüksek olasılıkla gözlemlenir.

Grover Algoritması, Hilbert uzayında yapılan hassas bir vektör döndürme operasyonu gibi okunabilir. Başlangıçta tüm durumların süperpozisyonu olan vektörümüz, doğru cevabı temsil eden eksenden uzaktadır. Her iterasyon, bu vektörü doğru cevaba doğru hesaplanmış bir açıyla (2θ) yaklaştırır. Aşağıdaki şema, 2 kübitlik minimal Grover akışını gösterir: süperpozisyon → oracle (CZ) → diffüzör → ölçüm.

Şemayı adım adım oku

1. 1

   İlk H katmanı tüm durumları eşit genlikle başlatır (uniform süperpozisyon).

2. 2

   Oracle (CZ) hedef durumu (örn. |11⟩) fazdan işaretler; olasılığı hemen değiştirmez.

3. 3

   Diffüzör, “ortalama etrafında yansıtma” ile bu faz işaretini genliğe çevirir ve hedefin payını büyütür.

4. 4

   Ölçüm en sonda yapılır; iterasyon doğru seçildiyse hedef bit dizisi baskın çıkar.

• “Olasılık dalgalarını yönetmek” vurgusu

  Grover’ın veriyi “okumadığını”, sadece doğru cevabın “sesini yükseltip” yanlış cevapların “sesini kıstığını” anlatan bir metafor sezgiyi güçlendirir.

• Hızlanma kıyasını görselleştirme

  Yan sütunda N ve √N ölçeklerini yan yana veren küçük bir karşılaştırma paneli (mini-metrik), algoritmanın “devrimsel” yanını matematikle görünür kılar.