Deutsch–Jozsa algoritması — tek sorguda fonksiyon karakteri

Deutsch–Jozsa, kuantum hesaplamanın klasik hesaplamaya göre ilk temiz ayrımlarından birini gösteren oracle algoritmasıdır. Elimizde içeriğini doğrudan görmediğimiz bir fonksiyon vardır; bu fonksiyon yalnızca sabit ya da dengeli olabilir. Algoritmanın görevi, fonksiyonu tek tek örneklemek yerine, onun küresel karakterini tek bir oracle çağrısıyla anlamaktır.

Bu algoritmanın öğretici gücü şuradadır: kuantum bilgisayar sonucu "tüm girdileri deneyerek" değil, tüm girdilerin fazlarını aynı hesaplama içinde çarpıştırarak bulur. Sabit fonksiyonda fazlar başlangıç durumunu geri toplar; dengeli fonksiyonda ise fazlar birbirini söndürür ve ölçümde en az bir $1$ görülür.

$n$ bitlik bir giriş alan ve tek bitlik sonuç üreten bir fonksiyon düşünelim: $f : \{0,1\}^n \to \{0,1\}$. Bu fonksiyonun söz verdiğimiz iki sınıftan birine ait olduğunu biliyoruz; bilmediğimiz tek şey hangisi olduğudur.

• Sabit (constant)

  Giriş ne olursa olsun sonuç hep aynıdır. Yani tüm $x$ değerleri için $f(x)=0$ ya da tüm $x$ değerleri için $f(x)=1$.

• Dengeli (balanced)

  Olası girişlerin tam yarısı için $0$, diğer yarısı için $1$ sonucunu verir. Fonksiyon evreni iki eşit parçaya böler.

• Klasik maliyet

  Kesin karar için en kötü durumda $2^{n-1} + 1$ sorgu gerekir. Çünkü ilk $2^{n-1}$ cevap aynı gelirse, hâlâ fonksiyonun sabit mi yoksa dengeli mi olduğu kesinleşmemiş olabilir.

• Kuantum maliyet

  Deutsch–Jozsa devresi oracle'ı yalnızca bir kez çağırır. Ölçümde $|00\ldots0\rangle$ görülürse fonksiyon sabit, aksi halde dengelidir.

Algoritmanın kalbinde kuantum girişimi vardır. Klasik bir bilgisayar girdileri tek tek denerken, Deutsch–Jozsa tüm girdileri aynı genlik içinde taşır. Oracle, fonksiyon sonucunu doğrudan ölçüme yazmak yerine faza kodlar; son Hadamard katmanı da bu faz bilgisini ölçülebilir bit desenine dönüştürür.

1. 1

   Hazırlık

   $n$ giriş kübiti $|0\rangle$ durumunda başlar. Yardımcı (ancilla) kübit ise $|1\rangle$ yapılır. Bu ancilla, oracle sonucunu faza çevirmek için kullanılır.

2. 2

   Süperpozisyon

   Tüm kübitlere Hadamard uygulanır. Giriş register'ı bütün $2^n$ olası girdiyi aynı anda temsil eder; ancilla ise $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$ durumuna geçer.

3. 3

   Oracle (kara kutu)

   Oracle, $U_f|x,y\rangle = |x, y \oplus f(x)\rangle$ dönüşümünü uygular. Ancilla $|-\rangle$ durumunda olduğu için fonksiyon sonucu ana register'ın fazına $(-1)^{f(x)}$ olarak yansır.

4. 4

   Girişim ve ölçüm

   Giriş kübitlerine yeniden Hadamard uygulanır. Sabit fonksiyonda fazlar yapıcı girişimle $|00\ldots0\rangle$ sonucunu güçlendirir; dengeli fonksiyonda ise bu sonuç yıkıcı girişimle kaybolur.

Derin sezgi · oracle fazı nasıl taşır?

Qiskit tarafında devre $n+1$ kübit ve $n$ klasik bit ile kurulur. Son kübit ancilla'dır; ölçüm yalnızca giriş register'ına yapılır. Çünkü karar, oracle'ın ancilla'da bıraktığı değerden değil, giriş register'ında oluşan girişim deseninden okunur.

• 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 süperpozisyona alır hem de ancilla'yı $|-\rangle$ durumuna taşır.

• Oracle

  Sabit fonksiyon için oracle ya hiçbir şey yapmaz ya ancilla'yı çevirir. Dengeli örnekte her giriş kübitinden ancilla'ya CNOT zinciri kurulur. Böylece $f(x)$ bilgisi faza kodlanır.

• Son Hadamard ve ölçüm

  Giriş register'ına yeniden Hadamard uygulanır ve yalnızca ilk $n$ kübit ölçülür. Ölçüm sonucu $0^n$ ise sabit; $0^n$ dışında herhangi bir desen ise dengeli kararını verir.

  $$\text{ölçüm} = 0^n \Rightarrow \text{sabit}, \qquad \text{ölçüm} \ne 0^n \Rightarrow \text{dengeli}$$

Aşağıdaki örnek $n=3$ giriş kübiti için Deutsch–Jozsa devresini kurar. type="constant" yerine type="balanced" yazıldığında oracle dengeli fonksiyon gibi davranır ve ölçümde $000$ dışında bir sonuç beklenir.

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


def deutsch_jozsa_circuit(n, type="constant"):
    # n giriş kübiti + 1 yardımcı kübit
    qc = QuantumCircuit(n + 1, n)

    # 1. Hazırlık: yardımcı kübiti |1> yap ve hepsine H uygula.
    qc.x(n)
    qc.h(range(n + 1))
    qc.barrier()

    # 2. Oracle (kara kutu) kısmı
    if type == "constant":
        # Sabit fonksiyon: hiçbir şey yapma veya ancilla'yı çevir.
        if np.random.randint(2) == 1:
            qc.x(n)
    else:
        # Dengeli fonksiyon örneği: CNOT zinciri.
        for i in range(n):
            qc.cx(i, n)

    qc.barrier()

    # 3. Son işlem: giriş kübitlerine H uygula ve ölç.
    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc


n = 3
qc = deutsch_jozsa_circuit(n, type="constant")

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

print(f"\nÖlçüm Sonucu: {counts}")
if "0" * n in counts:
    print("Sonuç: Fonksiyon SABİT (Constant)")
else:
    print("Sonuç: Fonksiyon DENGELİ (Balanced)")

QuantumCircuit(n + 1, n) satırı, $n$ giriş kübiti ve bir ancilla oluşturur; klasik register ise yalnızca $n$ bittir. Çünkü ancilla algoritmanın iç mekanizmasıdır, sonuç kararını giriş kübitleri taşır.

qc.x(n) ancilla'yı $|1\rangle$ durumuna getirir. Ardından qc.h(range(n + 1)) bütün kübitlere Hadamard uygular. Bu iki adım birlikte ancilla'yı $|-\rangle$ durumuna taşır; phase kickback için gereken hassas ayar budur.

Sabit oracle kısmında devre ya hiçbir şey yapmaz ya da yalnızca ancilla'ya $X$ uygular. Her iki durumda da giriş register'ındaki faz deseni tüm girdiler için aynıdır; son Hadamard katmanı $000$ sonucunu geri toplar.

Dengeli oracle örneği ise her giriş kübitinden ancilla'ya CNOT gönderir. Bu seçim $f(x)=x_0 \oplus x_1 \oplus \cdots \oplus x_{n-1}$ gibi davranan dengeli bir fonksiyon üretir. Son Hadamard katmanı, $000$ sonucunu yıkıcı girişimle bastırır.

Daha somut bakarsak: koddaki CNOT zinciri klasik anlamda parity (eşlik) fonksiyonudur. Girdilerin yarısı $1$ bitlerinin sayısı tek olduğu için $f(x)=1$, diğer yarısı için $f(x)=0$ döner. Bu simetrik yapı, faz geri tepmesinin ardından genliklerin tam olarak yarı yarıya ters işaret kazanmasını sağlar; son Hadamard katmanı bu eşit ama zıt katkıları topladığında $0^n$ sonucu sıfırlanır. Yani dengeli oracle örneği, kuantum bilgisayarın yıkıcı girişim (destructive interference) yeteneğinin matematiksel bir kutlamasıdır — klasik bilgisayarın asla taklit edemediği iptal mekanizması burada karar vermenin aracı olur.

Aşağıdaki şema $n=3$ için sabit oracle akışını gösterir. Dengeli oracle seçildiğinde orta oracle bloğunun içine giriş kübitlerinden ancilla'ya giden CNOT kapıları eklenir; karar kuralı değişmez.

Şemayı adım adım oku

1. 1

   En altta ancilla önce X ile |1⟩ yapılır; ardından tüm kübitlere H uygulanarak giriş register’ı süperpozisyona, ancilla ise |−⟩ durumuna alınır.

2. 2

   Ortadaki Oracle bloğu, fonksiyonun “sabit mi dengeli mi” karakterini giriş genliklerinin fazlarına işler (phase kickback).

3. 3

   Son H katmanı bu faz desenini girişimde birleştirir: sabitte 0…0 geri toplanır, dengelide dağılıp “0…0” dışına kaçar.

4. 4

   Giriş kübitleri ölçülür: 0^n ise sabit, aksi halde dengeli kararı verilir.

• Klasik karşılaştırma

  $n=3$ için klasik en kötü durum maliyeti $2^{2}+1=5$ sorgudur. Deutsch–Jozsa aynı sınıflandırmayı tek oracle sorgusuyla yapar.

• Oracle tasarımı

  Kodda verilen balanced oracle yalnızca örnek bir dengeli fonksiyondur. Deutsch–Jozsa'nın vaadi, hangi balanced oracle seçilirse seçilsin $000$ sonucunun kaybolmasıdır.

• Neden ancilla ölçülmüyor?

  Ancilla fonksiyon değerini faza taşımak için kullanılır; karar bilgisi son durumda giriş register'ındadır. Bu yüzden klasik register yalnızca $n$ bit içerir.