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

Simon algoritması, oracle modelinde gizlenmiş bir bit vektörünü $s$ ortaya çıkarmak için kullanılan kuantum protokoldür. Fonksiyon $f : \{0,1\}^n \to \{0,1\}^n$ XOR toplamasına göre şöyle bir periyot taşır: iki giriş ancak ve ancak birbirinden $s$ kadar ötelenmişlerse aynı çıktıyı verir (bu ilişkinin tam matematiksel yazımı bir sonraki bölümde). Sezgisel olarak, kara kutu her $x$ için “aynı görüntünün ikinci kaynağı”ni $x \oplus s$ olarak saklar—ama bu ikizleme, özel durum $s = 0^n$ iken çökerek kaybolur ( $x \oplus s = x$). Görev, bu periyodu koklayıp $s$'yi öğrenmektir.

Deutsch–Jozsa ve Bernstein–Vazirani örneklerinde olduğu gibi burada da mesele tek bitlik bir tahmin oyunu değil, çıktıların ortak yapısından gizli parametreyi çıkarma vardır; fakat Simon'un vaadi doğrusal iç çarpım ( BV) ya da sabit/dengeli sınıf (DJ) değil, XOR alt grubu $\{0,s\}$ üzerinde çarpışan çiftler ilişkisidir. Bu yüzden algoritma genelde tekrarlı bir kuantum alt rutini ve klasik doğrusal cebir ( örneğin Gauss eliminasyonu) ile çalışır; tek ölçümde bit-string düşmez—maliyet özeti aşağıdaki paragrafta.

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.

Bu problemde kara kutunun içinde göremediğiniz sabit bir vektör var; kutunun kuralı şöyle düşünülebilir: İki farklı istek ancak birbirine XOR ile aynı öteleme mesafesi kadar uzaksa aynı cevabı verir. Yani her çıktı—bu yapı geçerliyken—doğal olarak “hangi çift girişler aynı görüntüyü paylaşıyor?” sorusuna bağlanır; klasik tarafta bu çiftlerden birini rasgele ararken doğum günü paradoksu devreye girer ve maliyet kabarıyor. Kuantum tarafı ise bilerek çakışma avlamak yerine, periyotla uyumlu doğrusal kısıtlar üretip $s$'yi cebirsel olarak çözer. Aşağıdaki satırlar bu vaadi matematiksel olarak sabitler; altındaki dört kutu da maliyet ve sözü tek bakışta toparlar.

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:

$s \neq 0^n$ olduğu sürece $f$ iki-ye-bir bir fonksiyondur; 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.

Problem tanımında yazdığımız $f$ vaadi burada devreye konduğu anda yaşamaya başlar; amaç kara kutunun içindeki “hangi çiftler çarpışıyor?” bilgisini tek tek sızmak değil, bunun doğrusal sonuçlarını örnekleştirmektir. Bir Simon koşusu, özetle şunu yapar: tüm girişleri süperpozisyona alır, oracle çıktısını ikinci bir hatta saklar, sonra ölçümle o çıktıya bağlı yalnızca küçük bir ikili yapıyı (aynı çıktıyı paylaşan iki girişi) birinci hatta bırakır ve Hadamard girişimiyle mod 2 doğrusal bir filtre geçirirsiniz. Çıkan örnek, doğrudan $s$'yi vermez; fakat onun için tek tek doğrusal kısıt oluşturur. Aşağıdaki adımlar tek bir böyle koşunun fotoğrafıdır — klasik Gauss adımı zaten listenin sonunda, satır satır kod ise daha sonraki bölümlerde bağlanır.

Dolayısıyla Simon protokolü $s$'yi tek seferde söylemez. Her koşuda üretilen rasgele $z$, bit düzeyinde iç çarpımla $s$ ile mod 2 iç çarpımında ortogonal olur (yani aşağıdaki denklemin çözüm uzayından seçilir):

Bu kısıtın kolektif olarak ne işe yaradığını mod 2 cebiri ile düşünün: $s$ sabit bilinmese bile her başarılı koşu bilinmeyen çözüm için mod 2 üzerinde bir doğrusal kısıt ekler; yeterince bağımsız örnek birikince bu kısıtların çözüm uzayı daralır ve gizli maskeyi tekilleştirmeye yetecek kadar bilgi birikir — böylece $s$ klasik tarafta yeniden kurulur. Şimdi aynı olayı kapılar sırasıyla izleyelim.

1. 1

   Hazırlık

   İki adet $n$ kübitlik register kullanılır; tüm kübitler $|0\rangle$ durumundan başlar. Birinci blok “hesap düzlemi”: süperpozisyonda taşınan girişler burada yaşar. İkinci blok ise klasik olarak $f(x)$ değerini geri döndürülebilir biçimde saklamak için gereken kuantum bellek şerididir; Simon XOR oracle mimarisinde genişlikler eşit seçilir ki her çıktı etiketi kendi kübit dizisiyle yer kaplasın.

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. Bernstein–Vazirani kurulumunda çıktı tek kübitlik faz kabına sığdığı için bir Hadamard zinciri yeterliydi; burada ise çıktı tam bir $n$ bitlik dizidir — dolayısıyla ikinci register önce boşta bekler, sonra oracle tam çarpışma adresini oraya kopyalar.

3. 3

   Oracle uygulaması

   Oracle ikinci register'a $f(x)$ değerini yazar: $|x\rangle |0\rangle \to |x\rangle |f(x)\rangle$. Ünite oracle olduğu için ilk bloktaki $x$ etiketi yerinde kalır; ikinci blok ise çarpışmanın gözle görülür izidir ve iki blok birbirine bağlanır — ölçüm yapmadan önce hangi $x$'in hangi $f(x)$ ile eşleştiği artık kuantum olarak kodlanmıştır.

4. 4

   İkinci register'ın çökmesi

   İkinci register ölçüldüğünde rastgele bir $f(x_0)$ değerine çökeriz. Altta yatan Simon yapısında $s \neq 0$ olduğu sürece her çıktı etiketi tam iki farklı girdiyle ilişkilidir; dolayısıyla dolanıklık nedeniyle birinci register genelde 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)$. Özel olarak $s = 0$ durumunda çarpışma kaybolur ve ölçüm sonrası birinci blok tek bir $|x_0\rangle$ ketine sıkışır — problem tanımında belirttiğimiz biçimde bu rejim ayrıca ele alınır.

5. 5

   Girişim ve ölçüm

   Birinci register'a yeniden Hadamard uygulanır; bu, üzerinde çalıştığımız Boolean vektör uzayında bir Hadamard (Walsh) dönüşümüdür ve ölçüm öncesi olarak hesaplama tabanından mod 2 Fourier karşıtına geçiş yapar. İki terimli süperpozisyon üzerinde 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; döngü başına örnek sayısı ve kuantum maliyeti problem tanımındaki kuantum yaklaşımı kartıyla örtüşür.

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

Bu alt başlıktaki kutular, üstteki adım listesini yeniden yazmıyor; kapı sırasını zaten taradınız. Buradaki mesele, ölçüm sonrası çıkan z'nin neden doğrudan s olmadığı halde s hakkında zorunlu bir mod 2 doğrusallık taşıdığını — ve bunun faz/girişim dilinde nereden süzüldüğünü göstermek.

Faz dengesi (burayı adım listesi vermez) İkinci hat sabitlendikten sonra birinci hat için iki terim vardır; Hadamard öncesi genlikler eşit olduğundan, ikinci Hadamard katmanında her çıktı etiketi $z$ için iki yolun katkısı $(-1)^{z\cdot x}$ + $(-1)^{z\cdot(x\oplus s)}$ olarak yazılır; üstlerdeki iç çarpımlar mod 2 paritesini kodlar. Bu toplam yalnızca $z \cdot s \equiv 0 \pmod 2$ iken sıfırdan farklıdır; aksi halde iki terim birbirini götürür. Ölçüm böylece mod 2 iç çarpımında s ile ortogonal kalan etiketler arasından rastgele bir z döndürür; Bernstein–Vazirani kurulumundaki tek atışlık faz kodunun aksine burada bilgi, bu kısıtları çoğaltarak birikir.

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}")

Editördeki s_secret = "11" ile oluşturulan qc = simon_algorithm(s_secret) için Qiskit metin çizimi solda; sağda aynı olayın şematik özeti yer alır. Oracle simon_oracle(s) append ile gömüldüğünden terminalde tek blok olarak görünür; iç CNOT ayrışımı Qiskit sürümüne göre değişebilir. Klasik hat c: 2/ yalnızca hesap register ölçümünü taşır.

     ┌───┐ ░ ┌──────────────┐ ░ ┌───┐┌─┐   
q_0: ┤ H ├─░─┤0             ├─░─┤ H ├┤M├───
     ├───┤ ░ │              │ ░ ├───┤└╥┘┌─┐
q_1: ┤ H ├─░─┤1             ├─░─┤ H ├─╫─┤M├
     └───┘ ░ │  circuit-158 │ ░ └───┘ ║ └╥┘
q_2: ──────░─┤2             ├─░───────╫──╫─
           ░ │              │ ░       ║  ║ 
q_3: ──────░─┤3             ├─░───────╫──╫─
           ░ └──────────────┘ ░       ║  ║ 
c: 2/═════════════════════════════════╩══╩═
                                      0  1 

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.

Bu şema 6 · Aynı Devre (İki Temsil) bölümündeki akışı korur; $s = 11$ için Simon devresinin ana hatlarını yineleyerek 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.