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

Grover Algoritması, sıralanmışlıktan veya ek yapıdan yararlanılamayan bir arama uzayında tek bir “işaretlenmiş” çözümü bulmayı hedefleyen kuantum genlik artırma (amplitude amplification) düzeneklerinin önde gelen örneğidir; sırasız veri tabanı aramasının kara kutu modeline doğrudan oturur. 1996 yılında Lov Grover tarafından önerilmiştir. Klasik tarafta tek tek deneme doğası gereği ortalama ölçekte doğrusal deneme sayısı gerektirirken, Grover doğru cevabın ölçüm olasılığını her iterasyonda sistematik biçimde yükseltir; buradaki kazanç, ölçümden önce olasılık dağılımını yeniden kurmaya dayanır — veriyi paralel “satır satır okumak” değil, doğru sonuca taşıyan genliği büyütmektir.

Soyut çerçevede arama tipik olarak bir kara kutu oracle ile yazılır: oracle, sorulan adayın doğru olup olmadığını (veya eşdeğer bir karar fonksiyonunu) kuantum durumuna işler; Grover döngüsü de tam bu işareti büyütür. Karmaşıklık tartışmasında çoğu zaman oracle çağrısı sayısı esas alınır; kuantum tarafında beklenen ölçek O(√N), klasik rastgele aramaya göre kare kök düzeyinde bir iyileşmedir. Somut rakamlar ve klasikle karşılaştırma problem tanımı bölümünde; oracle ile diffüzörün birlikte nasıl çalıştığı ise bir sonraki bölümde açılır.

Okuma ipucu Bu giriş, sayfanın en üstündeki kısa özeti derinleştirir; “neden √N?” geometrisi ve durma noktası ayrı başlıklarda işlenir. Pratikteki duvarlar (oracle maliyeti, gürültü, derin devre süresi) ise kod analiziyle ilişkilidir.

Kuantum paralelliğiyle ilgili yaygın yanlış anlayış burada düzelir: Grover “tüm elemanları birden okuyup” doğru olanı listeden çekmez. Bunun yerine oracle doğru cevabı fazdan işaretler, diffüzör bu işareti ortalama etrafında yansıtarak güçlendirir; ölçüm yalnızca akışın sonunda yapılır ve öncesinde biriken bilgi, tam da bu iki operatörün tekrarında saklıdır.

Önceki bölümde çerçeve kuruldu; burada ölçüt somutlaşır: N aday içinden tek bir doğruyu bulmak için klasik ve kuantum tarafta hangi deneme / oracle çağrısı ölçeğinde konuştuğumuz. Üstteki “kara kutu” resmini burada sayılara döküyoruz — oracle ile diffüzörün devre içi tanımı ise bir sonraki başlıkta yer alır.

Elinizde yapısal ipucu vermeyen N elemanlı bir liste (ör. bir milyon kayıt) ve tam olarak bir doğru sonuç olduğunu düşünün. Liste sıralı değildir; dolayısıyla indeks sırasına göre atlama gibi kısayollar yoktur.

• Klasik yaklaşım

  Doğruyu bulmak için adayları sırayla veya rastgele denersiniz; yapı olmadığı için beklenen maliyet doğrusal ölçektedir: ortalamada yaklaşık N/2, en kötü durumda N kontrol (O(N)).

• Kuantum yaklaşımı (Grover)

  Kuantum protokolü tek tek listeyi “okumak” yerine oracle çağrılarını üst üste koyar; doğru cevabın ölçüm olasılığını artırmak için yaklaşık √N ölçeğinde tekrar yeterli olur (O(√N) oracle karmaşıklığı).

• Klasik maliyet

  Sırasız aramada yapısal ek bilgi yoksa deneme sayısı ile başarı şansı arasında doğrusal ölçek ilişkisi kaçınılmazdır; üstteki kart bunun sezgisini verir. Bu yüzden klasik sorgu karmaşıklığı da beklenen ölçekte O(N) düzeyinde kalır.

• Kuantum maliyet

  Grover bir Grover adımında bir oracle ve bir diffüzör uygular; toplam oracle çağrısı yaklaşık k ≈ (π/4)·√N olduğunda hedef genliği büyür (O(√N)). Sabit π/4 faktörü iki boyutlu döndürme geometrisinden gelir — ince açı “mantık” bölümünde.

• Neden “tam √N” değil?

  İterasyon bir döndürme gibi davranır; fazla tekrar hedefi geçirip genliği yeniden düşürebilir. Bu yüzden doğru durma noktası hem sabit katsayıda (π/4) hem de gürültülü donanımda kritiktir.

• Bu kartların sınırı

  Burada tek işaretli çözüm (M = 1) ve güvenilir oracle varsayılır; çoklu çözüm (M > 1) için k ≈ (π/4)·√(N/M) ölçeği “mantık” bölümünde geçer. Oracle + diffüzörün tanımı ve devre düzeni bir sonraki başlıkta açılır — burada yalnızca maliyet tablosuna odaklanıyoruz.

Sonraki adım Rakamların arkasındaki mekanizma (işaret ve yansıtma) genlik artırma bölümünde parçalanır; orada tekrar eden “oracle çağrısı” sayımını bu tabloyla birlikte düşünün.

Problem tanımında maliyeti saydık; burada protokolün mantıksal omurgası devreye girer. Grover’ın sırrı listeyi “aramak” değil, doğru sonucun ölçüm olasılığını artırmaktır. Bunu da iki ünite işlemin — oracle ve diffüzörün — tekrarladığı Grover iterasyonu ile yapar. Bu başlıkta işlemleri devre telgrafı düzeyinde tanımlıyoruz; iki boyutlu döndürme ve π/4 katsayısının nereden çıktığı bir sonraki başlıkta geometrik olarak açılır; kapı sırası ise Qiskit reçetesinde dosyalanır.

• Oracle (işaretleyici)

  Hesaplama tabanında çalışırsanız oracle, “hangi indeks doğru?” sorusunun kara kutusu olarak düşünülür: hedef durumlarda fazı π kaydırır, diğer taban durumlarında kimlik gibi davranır — özetle hedefe − işareti, ötekilere + (aynı genlik büyüklüğü). Ünite olduğu için olasılıkları doğrudan “çalıp” büyütmez; yalnızca doğru adayı diğerlerinden fazda ayırır.

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

  Diffüzör, ortalama genlik etrafında yansıtma (inversion about the mean) yapar: her genlik, o anki ortalamadan uzaklığının eksiği kadar kaydırılır. Böylece oracle’ın eksi fazladırdığı hedef, ortalamadan sapmış tek “çıkıntı” gibi davranır ve bir sonraki adımda mutlak genliği büyür; yanlış adayların genlikleri ise birbirine ve ortalamaya göre yeniden dağıtılır. Başlangıçta eşit süperpozisyondaysanız bu adım, kütle merkezini koruyarak işaretli terimi öne çıkarır.

• Grover adımı · bileşik operatör

  Tek bir Grover turu tipik olarak G = D · O biçiminde yazılır: önce oracle O, ardından diffüzör D. Sıra önemlidir; tek başına oracle ancak faz işareti koyar, tek başına diffüzör evrene göre belirsiz bir “ortalama” seçer — ikisi birlikte olunca girişimle genlik aktarımı başlar. Kaç kez G uygulanacağı problem tablosunda tartışılmıştı; optimum durma bir sonraki başlıkta geometriden okunur.

• Bu başlığın sınırı

  Burada “neyin çarpıldığı” netleşir; “neden kare kök ölçeği çıkar?” ve iki yansımanın bir döndürme gibi davrandığı resim mantık bölümündedir. Hangi kapılarla diffüzörün kurulduğu Qiskit reçetesinde satır satır verilir — burada soyut üniteyi bir kutuya koymak yeter.

İki yansıma ≈ kontrollü döndürme Üst üste gelen iki yansıma (önce hedefi işaretleyen, sonra tüm vektörü ortalamaya göre katan), geometride tek bir düzlemde sabit açılı döndürme gibi davranır; bu yüzden iterasyon sayısı “daha fazla her zaman daha iyi” değildir. Tam açı ve π/4 konusunu bir sonraki başlıkta işliyoruz — burada yalnızca iki operatörün birlikte neden tek başına yetmediğini görün.

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ı).

Bu başlık bir kontrol listesi: soyut G = D·O bloğunu hangi sırayla devreye dökersiniz. k seçimi ve geometri bir önceki başlıkta; oracle/diffüzörün ne işe yaradığı genlik bölümünde — burada yalnızca akış. Satır satır kod hemen alt başlıkta.

1. 1

   Hazırlık

   n kübit → N = 2^n durumluk uzay; başlangıç |0…0⟩. Qiskit’te tipik olarak QuantumCircuit(n, n): ikinci kayıt klasik ölçüm bitleri içindir.

2. 2

   Süperpozisyon

   qc.h(range(n)) ile eşit süperpozisyon — teorideki “tüm indekslere aynı genlik” adımının doğrudan karşılığıdır.

3. 3

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

   Bir tur: oracle (faz işareti) → diffüzör (ortalama etrafında yansıtma). Aynı bloğu k kez uygula; sayıyı önceki başlıktan alırsınız. İsterseniz bir grover_iteration(qc, …) yardımcı fonksiyonuna toplayın — döngü mantığı değişmez.

4. 4

   Ölçüm ve yorum

   measure + yeterli shots: simülatörde hedef bit dizisi sıklıkla tepe görünür; gerçek donanımda %100 yerine belirgin bir zirve bekleyin.

Sonraki bölüm aynı akışın kopyalanabilir Python iskeletini verir; burada durduysanız teoriyi sıkmadan Qiskit tarafına geçebilirsiniz.

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)

Yukarıdaki editörde n = 2, |11⟩ hedefi ve tek grover_iteration ile kurulan qc için Qiskit metin çizimi solda; sağda aynı akışın şematik özeti yer alır. ░ satırları barrier() ayırıcılarını gösterir; diffüzör içindeki H → Z → CZ → H dizisi metin çıktısında üst üste okunur.

     ┌───┐ ░     ░ ┌───┐┌───┐   ┌───┐ ░ ┌─┐   
q_0: ┤ H ├─░──■──░─┤ H ├┤ Z ├─■─┤ H ├─░─┤M├───
     ├───┤ ░  │  ░ ├───┤├───┤ │ ├───┤ ░ └╥┘┌─┐
q_1: ┤ H ├─░──■──░─┤ H ├┤ Z ├─■─┤ H ├─░──╫─┤M├
     └───┘ ░     ░ └───┘└───┘   └───┘ ░  ║ └╥┘
c: 2/════════════════════════════════════╩══╩═
                                         0  1 

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.

Bu şema 7 · Aynı Devre (İki Temsil) bölümündeki akışı korur; 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.