Bernstein–Vazirani — gizli bit dizisini tek sorguda oku

Bernstein–Vazirani algoritması, Ethan Bernstein ve Umesh Vazirani'nin klasik kuantum çalışmalarından birine dayanan ve sıklıkla ilk kuantum üstünlük örnekleri arasında anılan bir oracle öğrenme problemini çözer: kara kutunun içinde sabit bir yapı gizlidir; amacımız bu yapıyı izin verilen sorgu modelinde mümkün olduğunca az çağrıyla yeniden üretmektir. Burada fonksiyon sınıfı özellikle seçilmiştir—çıktı, gizli bir bit vektörü ile girişin mod 2 iç çarpımıdır—bu yüzden sorun hem öğretimde ( Deutsch–Jozsa ile aynı Hadamard–oracle–Hadamard iskelesi) hem de karmaşıklık teorisinde ( oracle altında klasik ve kuantum sorgu karmaşıklığının karşılaştırılması) düzenli olarak kullanılır.

Deutsch–Jozsa, kara kutunun sabit mi dengeli mi olduğunu ayırır; Bernstein–Vazirani ise bir adım daha hedef odaklıdır ve doğrudan gizli bit dizisinin kendisini bulur. Vaadın tam metni, klasik en kötü durumda kaç sorgu gerektiği ve kuantum tarafının neden tek sorguda yettiği bir sonraki "Problem tanımı" bölümünde toparlanır; burada yalnızca oracle'ın matematiksel sözünü sabitleştiriyoruz. Gizli dizi $s$ ise, oracle her giriş $x$ için şu fonksiyonu uygular:

Buradaki iç çarpım klasik anlamda bit bit çarpma ve mod 2 toplama demektir. Örneğin $s=110$ ise oracle, girişin ilk iki anlamlı bitini kontrol eder ve bunların parity bilgisini döndürür. Kuantum devresi ise bu fonksiyonun cevabını tek tek okumak yerine, gizli dizinin hangi konumlarında $1$ olduğunu faz değişimlerinden geri inşa eder.

Bernstein–Vazirani problem tanımı şunu varsayar: elimizde $n$ bitlik girişlere tek bit dönen bir kara kutu $f : \{0,1\}^n \to \{0,1\}$ vardır ve bu kutunun davranışı, bilmediğimiz bir $s \in \{0,1\}^n$ için tam olarak mod 2 iç çarpım kuralına uyar: her $x$ için $f(x)=s\cdot x \pmod 2$. Görev, bu vaade güvenerek $s$'nin tüm $n$ bitini eksiksiz çıkarmaktır (tek bir evet/hayır kararı değil, gizli kelimenin tamamı). Performans, kara kutuya kaç kez sorulabildiği üzerinden ölçülür.

Deutsch–Jozsa'da vaat farklıdır: $f$ ya sabit ya dengeli olmak zorundadır ve hedef iki sınıftan hangisinin geçerli olduğunu söylemektir. Bernstein–Vazirani ise doğrusal bir yapıyı parametre $s$ olarak kodlar; çıktı olarak ölçülen nesne doğrudan bu kelimedir. Aşağıdaki kutular bu BV özgü vaadi ve maliyetleri özetler.

• Doğrusal oracle (BV vaadi)

  Oracle, bilinmeyen $s$ için $f(x)=s\cdot x \pmod 2$ hesaplar: bit düzeyinde çarpımların mod 2 toplamı—yani parite (XOR) ile seçilmiş koordinatların toplamı. Koordinatlar mod 2 ile işlendiği için bu kural doğrusal bir Boolean fonksiyondur; Deutsch–Jozsa'daki “herhangi sabit veya dengeli $f$” ailesinden daraltılmış bir alt vaattir ve tek parametre $s$ ile etiketlenir.

• Klasik taban stratejisi

  Her sorguda bir $x$ seçilir ve tek bit $f(x)$ okunur—bu, mod 2 tek bir doğrusal denklemdir. Standart taban vektörleriyle (ör. $100$, $010$, $001$) sorgulayınca $f(e^{(k)}) = s_k$ olduğundan en fazla $n$ deterministik sorguda tüm $s$ çıkar; daha az sorguyla genel konumda kelimeyi kesin çözmek mümkün değildir.

• Tek çağrıda s ölçümü

  Bernstein–Vazirani devresi aynı kara kutuyu ($U_f$) yalnızca bir kez uygular. Hadamard öncesi/sonrası düzen, faz geri tepmesini toplayıp girişimde çözer; ideal devrede ölçüm doğrudan $s$ bit dizisini verir. Çıktı Deutsch–Jozsa'daki “tamamen sıfır dizesi mi değil mi?” ayırımından farklıdır: burada okunan şey gizli parametrenin kendisidir.

• Sorun türü ve ölçek

  Problem boyutu $n$ ile büyürken klasik kesin çözümün sorgu sayısı doğrusal ( $\Theta(n)$), kuantum tarafında ise oracle başına yalnızca $1$ çağrı gerekir — kısaca " $n$ yerine 1" özeti budur. Deutsch–Jozsa ise farklı bir karar sorusunda klasik en kötü durumu üstel sorguya çıkarabilir; iki algoritmanın üstünlükleri doğrudan kıyaslanmadığı sürece birbirinin yerine geçmez.

Üst bölümlerde vaadin ve sorgu maliyetinin özeti verildi; burada ise yalnızca devre içinde ne olduğu var: doğrusal oracle $f(x)=s\cdot x \pmod 2$, fazda $(-1)^{s\cdot x}$ biçiminde kodlanır ve ikinci Hadamard katmanı bu faz örüntüsünü tekrar hesaplama tabanına çevirir. Bernstein–Vazirani'nin ayırt edici özelliği, Deutsch–Jozsa'daki gibi tek bir küresel karar üretmek değil; her giriş hattında $s$'nin ilgili bitini ayrı ayrı okuyabilmesidir.

Aşağıdaki dört adım soyut akışı sıralar; kapı isimleri ve satır düzeni bir sonraki "Algoritmanın Qiskit reçetesi" bölümünde dosyalanır. Odak: faz geri tepmesi ( phase kickback) ile $s$ bilgisinin giriş register'ına nasıl işlendiği ve ölçümle nasıl okunduğu.

1. 1

   Süperpozisyonun gücü

   Her giriş kübitine H uygulanınca register, tüm $x \in \{0,1\}^n$ için eş genlikli bir süperpozisyon taşır—klasik taban sorgularını sırayla yapmak yerine oracle tek hamlede bu üst üste binmiş girdilerle çağrılacaktır. Yardımcı kübit $|1\rangle$ ile başlatılıp ardından H ile $|-\rangle$ yapılır; böylece XOR tabanlı oracle çıktısı ölçümde okunmak yerine fazda $\pm 1$ çarpanına dönüşebilir.

2. 2

   Oracle etkileşimi

   Standart yapıda her $s_i=1$ için $i$. giriş kübitinden ancilla'ya bir CNOT bağlanır; bu, taklit ettiğimiz $U_f$ oracle'ının doğrusal özel durumudur; genel dengeli fonksiyonlar için her zaman bu kadar seyrek bir kapı listesi yetmez. Ancilla $|-\rangle$ iken bu CNOT zinciri, giriş süperpozisyonunda her $x$ bileşeninin fazına $(-1)^{s\cdot x}$ işaretini basar—yani parite fonksiyonu klasik olarak tek tek okunmadan tüm $x$'ler için eşzamanlı olarak fazda kodlanmış olur.

3. 3

   Hadamard ile geri dönüş

   Giriş hatlarına yeniden H uygulanması, mod 2 doğrusal bir faz örüntüsünün Hadamard dönüşümünü almakla eşdeğerdir: BV oracle'ının doğrusal özel yapısı yüzünden bu dönüşüm tek katmanda çözülür ve gürültüsüz devrede genlik tam olarak tek klasik bit dizisinde toplanır. Sonuç olarak her hat için $s_i=0$ ise ölçümde $|0\rangle$, $s_i=1$ ise $|1\rangle$ beklenir; tüm hatların ölçümü birleşince doğrudan gizli kelime $s$ okunmuş olur.

4. 4

   Tek ölçüm

   Yalnızca ilk $n$ kübit ölçülür; ancilla genelde klasik register'a yazılmaz çünkü karar bilgisi giriş hatlarında toplanmıştır ( bkz. "Problem tanımı" notları). Ölçüm dizisi, vaade uygun ideal devrede kesin olarak doğrudan $s$'nin kendisidir; olasılıksal bir tahmin üretmez, tek shot ile gösterilebilir ( donanım gürültüsü ayrı bir konudur).

Mantık bölümündeki dört soyut adımın aynısı burada yalnızca Qiskit kübit indeksleri ve çağrılara çevrilir; faz cebirini yeniden açmıyoruz. QuantumCircuit(n + 1, n) ile $0$–$n-1$ giriş, $n$ ancilla ve $n$ klasik bit tanımlanır. Tek Python parametresi secret_bitstring uzunluğu $n$'yi verir; ölçüm yalnızca giriş hatlarına yazılır. Bit sırası / reversed(...) ayrıntısı "Qiskit kodu" ve "Kod analizi" bölümlerinde işlenir.

• Başlangıç

  Kuantum durumu $|0\rangle^{\otimes n}|1\rangle$ olacak şekilde kurulur: varsayılan $|0\rangle$ başlangıcı üzerinde qc.x(n) son kübiti ( indeks $n$, ancilla) $|1\rangle$ yapar.

• Hadamard katmanı

  qc.h(range(n + 1)) tüm hatlara H uygular: giriş register'ı üzerinde eş genlikli süperpozisyon oluşturur, ancilla ise $|-\rangle$ olur—mantık bölümünün ilk iki adımının doğrudan karşılığıdır.

• Oracle

  Örnek kodda dizi üzerinde döngü kurulur; her $1$ için ilgili giriş kübitinden ancilla'ya qc.cx(i, n) eklenir. Bu, matematiksel $U_f$'nin BV doğrusal özel durumunu kapılara çevirir; çıktı ölçüm string'i olarak değil, giriş fazında birikir. Gerçek kaynakta dizinin reversed ile taranması, Qiskit'in kübit sıralamasıyla kullanıcı yazımını hizalar ( kod analizi bölümünde açıldığı gibi).

• Geri dönüş ve ölçüm

  İkinci Hadamard yalnızca giriş kübitlerine uygulanır: qc.h(range(n)) — ancilla bu katmanda yeniden dönüştürülmez. Ardından qc.measure(range(n), range(n)) ile klasik sonuç doğrudan okunur; ideal devrede bit deseni gizli $s$'dir ( Deutsch–Jozsa'daki $0^n$ / sıfır olmayan ayrımından farklı olarak burada ölçülen nesnenin kendisi kelimedir).

  $$\text{ölçüm sonucu} = s$$

Aşağıdaki örnekte gizli dizi 110 olarak seçildi. Qiskit'in bit sıralaması nedeniyle oracle içinde dizi ters çevrilerek okunur; böylece ölçüm çıktısı kullanıcıya verdiğimiz gizli diziyle aynı yönde yorumlanır.

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator


def bv_algorithm(secret_bitstring):
    n = len(secret_bitstring)
    # n giriş kübiti + 1 yardımcı (ancilla) kübit
    qc = QuantumCircuit(n + 1, n)

    # 1. Hazırlık: ancilla'yı |1> yap ve hepsine H uygula.
    qc.x(n)
    qc.h(range(n + 1))
    qc.barrier()

    # 2. Oracle: gizli diziyi devreye işle.
    # secret_bitstring içindeki "1" olan yerlere CNOT ekle.
    for i, bit in enumerate(reversed(secret_bitstring)):
        if bit == "1":
            qc.cx(i, n)

    qc.barrier()

    # 3. Girişim ve ölçüm
    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc


secret = "110"
qc = bv_algorithm(secret)

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

print(f"Gizli Dizi: {secret}")
print(f"Kuantumun Bulduğu Sonuç: {list(counts.keys())[0]}")

Yukarıdaki editörde secret = "110" ile üretilen qc için Qiskit metin çiziminin tam karşılığı aşağıdadır. Kablolar q_0 … q_2 giriş register'ını, q_3 ancilla'yı temsil eder; ░ satırları barrier() ile oracle öncesi ve sonrasını ayırır. Sağdaki SVG aynı akışı renkli görsel dilde özetler.

     ┌───┐      ░            ░ ┌───┐┌─┐      
q_0: ┤ H ├──────░────────────░─┤ H ├┤M├──────
     ├───┤      ░            ░ ├───┤└╥┘┌─┐   
q_1: ┤ H ├──────░───■────────░─┤ H ├─╫─┤M├───
     ├───┤      ░   │        ░ ├───┤ ║ └╥┘┌─┐
q_2: ┤ H ├──────░───┼────■───░─┤ H ├─╫──╫─┤M├
     ├───┤┌───┐ ░ ┌─┴─┐┌─┴─┐ ░ └───┘ ║  ║ └╥┘
q_3: ┤ X ├┤ H ├─░─┤ X ├┤ X ├─░───────╫──╫──╫─
     └───┘└───┘ ░ └───┘└───┘ ░       ║  ║  ║ 
c: 3/════════════════════════════════╩══╩══╩═
                                     0  1  2 

QuantumCircuit(n + 1, n) satırı, $n$ giriş kübiti ve bir ancilla oluşturur. Klasik register yalnızca $n$ bittir, çünkü ancilla ölçülmez; gizli dizi giriş register'ında okunur.

qc.cx(i, n) oracle'ın kalbidir. Gizli dizide $1$ olan her konum için ilgili giriş kübitinden ancilla'ya CNOT eklenir. Ancilla $|-\rangle$ durumunda olduğu için bu CNOT, hedef kübiti kalıcı olarak değiştirmekten çok kontrol kübitinin fazına eksi işareti teptirir.

reversed(secret_bitstring) Qiskit'in küçük endian bit sıralamasıyla uyum sağlamak için kullanılır. Böylece secret = "110" seçildiğinde devre ilgili fiziksel kübitlere doğru CNOT kapılarını ekler ve çıktı kullanıcı tarafında yine 110 olarak okunur.

shots=1 algoritmanın deterministik olduğunu gösterir. İdeal Bernstein–Vazirani devresinde sonuç olasılıksal bir dağılım değildir; oracle doğru kurulduysa tek ölçüm gizli diziyi verir.

Bu şema 6 · Aynı Devre (İki Temsil) bölümündeki akışı korur; $s=110$ örneğinin ana hatlarını yineleyerek gösterir. Oracle bloğu içinde gizli dizide $1$ olan konumlar CNOT kapılarıyla ancilla'ya bağlanır. Son Hadamard katmanı bu bağlantıların faz izini ölçülebilir bit dizisine çevirir.

• Neden tek sorgu?

  Bernstein–Vazirani kurulumunda tek bir $U_f$, süperpozisyonda taşınan bütün $x$ bileşenleri üzerinde doğrusal faz deseni $(-1)^{s\cdot x}$ olarak yazılır; sonra ikinci Hadamard bu faz kodunu çözüp her hat için $s_i$'yi ayrıştırır. Yani bilgi tek oracle çağrısında "birbirine bağlı parça parça" değil, doğrusal özel yapının tamamı olarak gelir.

• Klasik fark

  Burada klasik taraf n bitlik kelimeyi $s$'yi çıkarmak zorunda olduğu için (ör. taban girdileriyle) genelde $\Theta(n)$ ayırıcı sorgu ister; kuantumda oracle başına çağrı sayısı $1$'dir ve ölçek büyüdükçe artan şey kaynak kullanımıdır ( kübit sayısı ve kapı derinliği). Deutsch–Jozsa ise tamamen başka bir söz problemi üzerinde çalışır; klasik–kuantum farkının şekli orada doğrudan bu kutunun özetiyle örtüşmez.

• Gerçek donanım notu

  İdeal simülatörde çıkan dizinin doğrudan $s$ olduğu varsayımına yakınız. Gerçek donanımda tek kübitlik kapı ve okuma hataları birikerek bazı ölçümlerde yanlış bit kombinasyonları üretir; güven artırmak için çoklu shot, kalibrasyon veya hata azaltımı düşünülür—BV için doğrusal vaadin gerçekten sağlanıp sağlanmadığı buradan bağımsız bir doğruluk sorunu olarak kalır.

• Ölçüm neyi döndürür?

  Bu algoritmada klasik register doğrudan $n$ bitlik bir dizi taşır ve iş hedefi bu diziyi $s$ ile eşlemektir. Deutsch–Jozsa örneğinde ise tek ölçüm çoğu anlatımda küresel "sıfır deseni mi?" kararına indirgenir; yani iki örnekte okuduğunuz nesne ( tam kelime ile iki sınıf kararı) farklıdır—dolayısıyla çıktı yorumlarını birbirinin yerine koymayın.