Bernstein–Vazirani — gizli bit dizisini tek sorguda oku

Bernstein–Vazirani, Deutsch–Jozsa ailesinin bir adım daha hedef odaklı versiyonudur: oracle'ın sabit mi dengeli mi olduğunu sormaz; oracle'ın içinde saklanan gizli bit dizisini doğrudan bulmaya çalışır. 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.

Elimizde $n$ bitlik bir giriş alan ve tek bitlik sonuç döndüren bir fonksiyon vardır: $f : \{0,1\}^n \to \{0,1\}$. Fonksiyonun içinde bilinmeyen bir $s \in \{0,1\}^n$ dizisi saklıdır ve amaç bu diziyi eksiksiz bulmaktır.

• Fonksiyonun yapısı

  Oracle, $f(x)=s \cdot x \pmod 2$ kuralını uygular. Sonuç, giriş dizisinin gizli dizideki $1$ konumlarıyla yaptığı mod 2 toplamdır.

• Klasik yaklaşım

  $s$ dizisi $n$ bit uzunluğundaysa klasik kesin çözüm $n$ sorgu ister: $100$, $010$, $001$ gibi taban girdilerle her bit ayrı ayrı test edilir.

• Kuantum yaklaşımı

  Kuantum devresi oracle'ı yalnızca bir kez çağırır. Son Hadamard katmanı faz işaretlerini tekrar bit değerlerine çevirir ve ölçüm doğrudan $s$ dizisini verir.

• Ölçeklenebilirlik

  Klasik sorgu sayısı $N$ gibi büyürken kuantum sorgu sayısı $1$ kalır. Bu yüzden Bernstein–Vazirani, "N vs 1" ayrımını en sade gösteren oracle örneklerinden biridir.

Bernstein–Vazirani'nin güzelliği, fonksiyonu çok kez çalıştırmak yerine fonksiyonun yapısını faz geri tepmesiyle tersine okumasındadır. Oracle, $s$ dizisindeki her $1$ için ilgili giriş kübitine faz işareti bırakır; son Hadamard katmanı da bu işaretleri tekrar $0/1$ durumlarına çevirir.

1. 1

   Süperpozisyonun gücü

   Giriş kübitleri Hadamard kapılarıyla tüm olası bit dizilerinin süperpozisyonuna getirilir. Yardımcı kübit $|1\rangle$ durumundan $|-\rangle$ durumuna taşınır.

2. 2

   Oracle etkileşimi

   Gizli dizide $1$ olan her pozisyon için ilgili giriş kübitinden ancilla'ya CNOT eklenir. Ancilla $|-\rangle$ durumunda olduğu için bu CNOT'lar bit değerini değil, faz işaretini değiştirir.

3. 3

   Hadamard ile geri dönüş

   İkinci Hadamard katmanı faz değişimlerini tekrar ölçülebilir bit desenine çevirir. Gizli dizide karşılığı $0$ olan kübitler $|0\rangle$, karşılığı $1$ olanlar $|1\rangle$ olarak döner.

4. 4

   Tek ölçüm

   Giriş register'ı ölçülür ve sonuç doğrudan $s$ dizisidir. İdeal simülatörde bu sonuç deterministiktir; olasılık dağılımı değil, kesin cevap üretir.

Qiskit devresi $n$ giriş kübiti, bir ancilla ve $n$ klasik bitten oluşur. Kodun tek parametresi gizli bit dizisidir; oracle bu dizide $1$ olan pozisyonları CNOT kapılarıyla devreye işler.

• Başlangıç

  $|0\rangle^{\otimes n}|1\rangle$ hazırlanır. Qiskit kodunda qc.x(n) satırı ancilla'yı $|1\rangle$ durumuna çevirir.

• Hadamard katmanı

  qc.h(range(n + 1)) hem giriş kübitlerini tüm $x$ değerlerinin süperpozisyonuna alır hem de ancilla'yı $|-\rangle$ durumuna taşır.

• Oracle

  secret_bitstring içindeki $1$ bitleri için qc.cx(i, n) uygulanır. Bu CNOT'lar gizli diziyi ölçüme değil, faz desenine yazar.

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

  Giriş kübitlerine ikinci kez Hadamard uygulanır. Ölçüm sonucu doğrudan gizli dizi $s$ olur.

  $$\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]}")

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.

Aşağıdaki şema $s=110$ için devrenin ana akışını 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?

  Oracle tüm $x$ değerlerine aynı anda faz işareti bıraktığı için gizli dizinin bütün bitleri aynı ölçüm desenine taşınır.

• Klasik fark

  Klasik çözümde $s$ dizisinin her biti ayrı sorguyla öğrenilir. Kuantum çözümde sorgu sayısı sabit kalır; yalnızca devre genişliği artar.

• Gerçek donanım notu

  İdeal simülatörde tek sonuç görülür. Gerçek cihazda kapı ve okuma gürültüsü nedeniyle küçük oranlarda hatalı bit dizileri gözlenebilir.