Simon algoritması — üstel hızlanmanın ilk kanıtı

Simon algoritması, bir fonksiyonun gizli bir periyodik yapıya sahip olup olmadığını ve sahipse bu periyodun ne olduğunu bulma protokolüdür. Oracle, içine sakladığı $s$ maskesi sayesinde her $x$ değerine mutlaka bir "ikiz" $x \oplus s$ atfeder; algoritmanın görevi bu ikiz çiftlerin yapısını koklayıp $s$'i geri çıkarmaktır.

Bu sayfa, kuantum hesaplama tarihindeki ilk üstel klasik–kuantum ayrımını gösterir: aynı problemi klasik olarak çözmek doğum günü paradoksu yüzünden $\mathcal{O}(2^{n/2})$ sorgu gerektirirken, kuantum devresi tipik olarak yalnızca $\mathcal{O}(n)$ tekrar yapar.

Elimizde bir oracle fonksiyonu $f : \{0,1\}^n \to \{0,1\}^n$ bulunur. Bize verilen söz şudur: gizli bir $s \in \{0,1\}^n$ dizisi vardır ve $f$ şu özelliği sağlar:

Yani $f$ bire-bir değildir; her çıktının tam olarak iki ön-görüntüsü vardır ve bunlar $x$ ile $x \oplus s$ olarak tanımlanır. Eğer $s = 0^n$ ise $f$ tam bir bijeksiyondur (özel ama bilgilendirici bir kenar durum). Hedef, bu gizli $s$'i belirlemektir.

• Klasik yaklaşım

  Aynı sonucu veren iki farklı girdi $(x, y)$ bulana kadar deneme yaparsın. Doğum günü paradoksu nedeniyle ortalama $\mathcal{O}(2^{n/2})$ sorgu gerekir; $n=40$ için bu yaklaşık bir milyon çağrıdır.

• Kuantum yaklaşımı

  Algoritma yaklaşık $n-1$ kez koşturulur, her koşuda $s$'e dik bir $z$ vektörü örneklenir. Toplandığında bu vektörler doğrusal bir denklem sistemi kurar ve $s$ kesin biçimde çözülür.

• Söz problemi

  Algoritmanın işlemesi için $f$'in periyodik yapı sözünü tutması gerekir. Bu söz olmadan örneklenen $z$ vektörlerinin anlamı yoktur.

• Shor ile bağ

  Shor algoritmasının periyot bulma adımı aynı fikri tamsayı çarpanlamasının modüler kalan yapısına taşır. Simon, bu fikri bit düzeyinde anlamak için en sade ortamdır.

Simon algoritması $s$'i tek seferde söylemez. Bunun yerine her koşuda, $s$ ile dik olan rastgele bir $z$ vektörü örnekler — yani şu denklemi sağlayan vektörler:

1. 1

   Hazırlık

   İki adet $n$ kübitlik register kullanılır; tüm kübitler $|0\rangle$ durumundan başlar. Birinci register algoritmanın hesap düzlemi, ikinci register oracle çıktısının yazıldığı depodur.

2. 2

   Süperpozisyon

   İlk register Hadamard katmanından geçer. Sistem $\frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle |0\rangle$ haline gelir; yani tüm $x$ değerleri eşit genlikle barındırılır.

3. 3

   Oracle uygulaması

   Oracle ikinci register'a $f(x)$ değerini yazar: $|x\rangle |0\rangle \to |x\rangle |f(x)\rangle$. Bu adımdan sonra iki register dolanıktır.

4. 4

   İkinci register'ın çökmesi

   İkinci register ölçüldüğünde rastgele bir $f(x_0)$ değerine çökeriz. Dolanıklık nedeniyle birinci register artık yalnızca $\{x_0, x_0 \oplus s\}$ ikilisinin üst üste binmiş halidir: $\frac{1}{\sqrt{2}}\bigl(|x_0\rangle + |x_0 \oplus s\rangle\bigr)$.

5. 5

   Girişim ve ölçüm

   Birinci register'a yeniden Hadamard uygulanır. Girişim, yalnızca $s \cdot z = 0 \pmod 2$ şartını sağlayan $z$ vektörlerinin genliğini hayatta bırakır. Bu yüzden ölçüm her seferinde $s$'e dik rastgele bir $z$ döner.

6. 6

   Klasik son işlem

   Yeterince doğrusal bağımsız $z$ vektörü toplandığında (tipik olarak $n-1$ tane), klasik Gauss eliminasyonuyla $s \cdot z_i = 0$ denklem sistemi çözülerek $s$ kesin biçimde bulunur.

Derin sezgi · neden ölçtüğümüz z vektörleri s'e dik?

Kritik fikir Devrenin ortasında ikinci register ölçülünce, bir anda sadece bir “ikiz çift” kalır: |x⟩ + |x ⊕ s⟩. Son Hadamard katmanı bu iki terimi girişim ettirir ve ölçüm, rastgele bir z üretir ama şu koşulu zorunlu kılar: $z \cdot s = 0 \ (\mathrm{mod}\ 2)$. Bu yüzden her ölçüm “s’e dik” bir denklem verir; yeterince farklı z toplayınca klasik tarafta lineer cebirle s çözülür.

Qiskit tarafında devre $2n$ kübit ve $n$ klasik bit kullanır. İlk $n$ kübit hesap register'ı, sonraki $n$ kübit ise oracle'ın depolama register'ıdır. Klasik register yalnızca ilk register'ı ölçmek içindir; $z$ vektörlerini buradan toplarız.

• Başlangıç

  $|0\rangle^{\otimes n} |0\rangle^{\otimes n}$ hazırlanır. Qiskit kodunda QuantumCircuit(2 * n, n) bu yapıyı doğrudan kurar.

• Hadamard katmanı

  qc.h(range(n)) ile yalnızca ilk register süperpozisyona alınır. Sistem $\frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle |0\rangle$ haline gelir.

• Oracle

  simon_oracle(s) ile inşa edilen devre ana devreye eklenir. Bu blok, $f(x)$ değerini ikinci register'a yazar ve iki register'ı dolanık hale getirir.

• Son Hadamard ve ölçüm

  İlk register'a yeniden Hadamard uygulanır ve sadece bu register ölçülür. Her shot, $s$ ile dik bir $z$ vektörü üretir.

  $$\Pr[z] \neq 0 \iff s \cdot z = 0 \pmod 2$$

Aşağıdaki örnek $s = 11$ için Simon devresini kurar. Birden fazla shot alarak $s$'e dik farklı $z$ vektörlerinin istatistiğini toplar; sonuçta yalnızca $00$ ve $11$ değerleri görünmelidir, çünkü iki bitlik bir uzayda $s = 11$'e dik vektörler tam olarak bunlardır.

import numpy as np
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator


def simon_oracle(s):
    n = len(s)
    qc = QuantumCircuit(2 * n)
    # Basit bir Simon oracle tasarımı (s=11 için).
    # Bu kısım s dizisine göre fonksiyonel olarak değişir.
    for i in range(n):
        qc.cx(i, i + n)
    if s == "11":
        qc.cx(0, 3)
        qc.cx(1, 2)
    return qc


def simon_algorithm(s):
    n = len(s)
    qc = QuantumCircuit(2 * n, n)

    # 1. Hadamard katmanı (ilk register)
    qc.h(range(n))
    qc.barrier()

    # 2. Oracle ekleme
    oracle = simon_oracle(s)
    qc.append(oracle, range(2 * n))
    qc.barrier()

    # 3. Son Hadamard katmanı (ilk register)
    qc.h(range(n))

    # 4. Ölçüm
    qc.measure(range(n), range(n))
    return qc


s_secret = "11"
qc = simon_algorithm(s_secret)

# Simülasyon
simulator = AerSimulator()
# Birkaç kez çalıştırıp farklı z vektörleri topluyoruz.
result = simulator.run(qc, shots=1024).result()
counts = result.get_counts()

print(f"Gizli Maske (s): {s_secret}")
print(f"Ölçülen z vektörleri (s.z = 0 olanlar): {counts}")

QuantumCircuit(2 * n, n) satırı iki ayrı register'ı tek bir kübit hattı üzerinde temsil eder. İlk $n$ kübit Simon'un hesap düzlemi, sonraki $n$ kübit ise oracle'ın depolama register'ıdır. Klasik kayıt yalnızca $n$ bit içerir, çünkü ölçüm sadece ilk register'da yapılır.

simon_oracle(s) bu örnekte kabaca iki adımdan oluşur: önce her giriş kübitinden hizalı depolama kübitine CNOT (yani $f$'in bire-bir bir kopyalama tabanı) ve ardından $s = 11$ olduğunu söylediğin için seçilmiş ek CNOT'lar. Bu ek CNOT'lar, $x$ ve $x \oplus s$ ikilisini aynı $f$ değerine eşleyen periyodik yapıyı kurar.

qc.h(range(n)) ifadesi algoritmada iki kez geçer. İlk Hadamard katmanı tüm $x$ değerlerini eşit genlikle barındırır; ikincisi ise ikinci register'ın çökmesinden sonra geriye kalan $\{x_0, x_0 \oplus s\}$ üst üste binmesini, $s$'e dik $z$ vektörlerinin ölçülebilir genliğine çevirir.

shots=1024 seçimi Bernstein–Vazirani'den farklı bir gerekçeye dayanır. Simon deterministik tek bir cevap vermez; her shot $s$'e dik rastgele bir $z$ döndürür. Yeterince doğrusal bağımsız $z$ toplandığında klasik bir lineer denklem sistemiyle $s$ çözülür.

Aşağıdaki şema $s = 11$ için Simon devresinin ana akışını gösterir. İlk iki kübit hesap register'ı, alttaki iki kübit ise depolama register'ıdır. Oracle bloğu içindeki CNOT yapısı, gizli maskenin değerine göre değişir.

Şemayı adım adım oku

1. 1

   Üstteki “hesap” register’ına H uygulanır; tüm x değerleri tek süperpozisyonda taşınır.

2. 2

   Oracle bloğu, her x için sonucu alt “depo” register’ına yazar. Simon vaadi yüzünden çıktılar “ikiz” girdileri eşler: x ve x ⊕ s.

3. 3

   Oracle’dan sonra hesap register’ına tekrar H uygulanır. Bu girişim, ölçümde yalnızca z · s = 0 koşulunu sağlayan desenlerin görünmesine neden olur.

4. 4

   Hesap register’ı ölçülür ve farklı z örnekleri toplanır. Klasik tarafta bu denklemlerden s çözülür.

• Neden $00$ ve $11$?

  İki bitlik uzayda $s = 11$'e dik vektörler XOR toplamı sıfır olan desenlerdir. $00$ ve $11$ bu şartı sağlarken $01$ ve $10$ ideal devrede genlik kazanmaz.

• $s$'in çözümü

  Pratikte bir veya iki doğrusal bağımsız $z$ toplanır: $z_1 = 11$ ile $s \cdot 11 = 0$. Buradan $s_0 = s_1$ çıkar; sıfırdan farklı tek olasılık $s = 11$'dir.

• Daha büyük $n$

  $n$ büyüdükçe daha fazla shot ile yaklaşık $n - 1$ doğrusal bağımsız $z$ toplamak gerekir. Toplama sayısı yine polinomdur; bu, klasik çözümün üstel büyümesine karşı asıl avantajdır.

• Donanım notu

  Gerçek cihazda gürültü, $01$ ve $10$ desenlerine küçük olasılıklar sızdırabilir. Klasik denklem çözümü bu gürültüye karşı dayanıklıdır; gürültülü vektörler basit çoğunluk veya doğrusal bağımsızlık filtreleriyle elenir.