Deutsch–Jozsa algoritması — tek sorguda fonksiyon karakteri

Oracle algoritması deyince, fonksiyonun iç yapısına ya da kapalı formuna doğrudan erişemediğimiz; onu yalnızca izin verilen bir alt rutin aracılığıyla sorgulayabildiğimiz hesaplama modeli kastedilir. Kuantum bağlamında bu rutin çoğunlukla $U_f$ ile temsil edilir ve performans çoğu zaman kaç oracle çağrısı gerektiği üzerinden ölçülür. Deutsch–Jozsa, işte bu sorgu çerçevesinde gizli bir fonksiyonun küresel olarak sabit mi yoksa dengeli mi olduğunu ayırt eden; klasik en kötü duruma kıyasla sorgu sayısında üstünlük sağlayan tarihsel bir oracle algoritmasıdır.

Burada oracle problemin kendisi değil, fonksiyonu devreye gömen kara kutu ünitedir—sayfadaki devre şemasında ortadaki oracle bloğu ve onu çevreleyen Hadamard–ölçüm akışı tam da bunu somutlaştırır. Deutsch–Jozsa'nın görevi, her giriş için ayrı ayrı ölçüm yapmak yerine bu kutuyu yalnızca bir kez kullanarak küresel kararı vermektir. Sabit ve dengeli sınıfların kesin tanımları bir sonraki bölümde; faz girişimi, phase kickback ve oracle ünitesinin cebiri ise aşağıda, özellikle mantık ve reçete bölümlerinde açılı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)

  Oracle'a hangi $x$ ile sorarsanız sorun, cevap değişmez: tüm girişler için ya hep $f(x)=0$ ya hep $f(x)=1$. Kara kutunun tek tutarlı davranışı budur; ara değerler veya karışık bir örüntü yoktur.

• Dengeli (balanced)

  Olası girişlerin tam yarısı için $0$, diğer yarısı için $1$ döner; yani oracle farklı $x$ değerlerine sorulduğunda iki cevap da eşit sıklıkta görülür. Fonksiyon, $\{0,1\}^n$ uzayını iki eşit büyüklükteki parçaya böler.

• Klasik maliyet

  Klasik tarafta $f$'ye yalnızca tek tek erişilir: bir $x$ seçilir, oracle $f(x)$ döndürür; bu bir sorgudur. Kesin karar için en kötü durumda $2^{n-1} + 1$ sorgu gerekir: ilk $2^{n-1}$ yanıtın hepsi aynı olsa bile dengeli bir fonksiyon, kalan yarıda tek bir farklı değerle gizlenebilir; sabitlik ancak bir sorgu daha ile kesinleşir.

• Kuantum maliyet

  Aynı kara kutu $f$, giriş register'ı süperpozisyondayken tek bir $U_f$ uygulamasıyla sorgulanır; Deutsch–Jozsa bu yüzden tek oracle çağrısına indirger. Ölçüm yalnızca giriş kübitlerine yapılır: sonuç $|00\ldots0\rangle$ ise fonksiyon sabit; en az bir kübit $1$ ölçülürse 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übitinden oluşan ana register $|0\rangle$ durumunda başlar; yani klasik olarak tüm girişler sıfırdır. Buna eklenen tek yardımcı (ancilla) kübit $|1\rangle$ yapılır—bu, oracle'ın $f(x)$ çıktısını ölçümde doğrudan okutmak yerine phase kickback ile ana hatta faz işareti olarak geri yansıtacak standart Deutsch–Jozsa düzenidir.

2. 2

   Süperpozisyon

   Her kübite Hadamard (H) uygulanır; böylece giriş hattı üzerindeki bilgi klasik tek bir bit dizesi değil, tüm $2^n$ olası $x$ değerinin eş genlikli süperpozisyonudur. Ancilla ise $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$ olur; bu “eksi” durum, bir sonraki adımda XOR ile yazılan $f(x)$ bilgisinin fazda $\pm 1$ çarpanına dönüşmesini sağlar.

3. 3

   Oracle (kara kutu)

   Oracle, gizli fonksiyonu kuantum olarak $U_f|x,y\rangle = |x, y \oplus f(x)\rangle$ ile uygular: giriş kübitleri $x$ olduğunda yardımcı hatta $f(x)$ XOR ile yazılır. Ancilla $|-\rangle$ olduğundan bu XOR, ana register'daki her $x$ bileşenine $(-1)^{f(x)}$ faz çarpanı olarak “geri teper”; yani oracle tek seferde tüm $x$ için fonksiyonu klasik anlamda tek tek okumadan işaretler.

4. 4

   Girişim ve ölçüm

   Giriş register'ına ikinci bir Hadamard katmanı uygulanır; bu, süperpozisyondaki genlikleri tekrar toplayıp çıkaran ters Fourier benzeri bir adımdır ve fazlardaki küresel uyum ya da uyumsuzluğu klasik bit desenine çevirir. Sabit $f$ için tüm $x$ aynı faz işaretini taşır; girişim yapıcı olur ve ölçümde $|00\ldots0\rangle$ (tüm sıfırlar) baskın çıkar. Dengeli $f$ için eşit büyüklükteki artı ve eksi fazlar birbirini yıkıcı girişimle söndürür; tam sıfır dizesi olasılığı sıfırlanır, dolayısıyla en az bir kübit $1$ olarak ölçülür.

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

Yukarıdaki mantık ve reçeteyle aynı fizik burada yalnızca Qiskit indeksleri ve QuantumCircuit çağrılarına çevrilir; tekrar yerine “hangi satır neye karşılık gelir?” sorusuna odaklanırız. Devre $n+1$ kubit ($0$–$n-1$ giriş, $n$ ancilla) ve $n$ klasik bit ile kurulur. Ölçüm yalnızca giriş hatlarına yazılır: karar, oracle'ın ancilla üzerinden $U_f$ ile kodladığı faz bilgisinin, son Hadamard sonrası girişim deseninde nasıl göründüğünden okunur. Satır satır gerekçe, bir sonraki “Kod analizi” bölümünde genişletilir.

• Başlangıç

  Kuantum durumu $|0\rangle^{\otimes n}|1\rangle$ olacak şekilde kurulur: Qiskit'te kübit $n$ son hat olduğundan qc.x(n) doğrudan ancilla'yı $|1\rangle$ yapar; diğer hatlar varsayılan $|0\rangle$ ile başlar.

• Hadamard katmanı

  qc.h(range(n + 1)) tüm hatlara birden Hadamard uygular: girişler eş genlikli süperpozisyona girer, ancilla ise $|-\rangle$ olur. Bu, bir sonraki blokta $U_f$ çalıştığında XOR'un fazda $(-1)^{f(x)}$ olarak görünmesi için gereken standart hazırlıktır.

• Oracle

  Oracle, soyut $U_f$ ünitesini kapılara çevirir; kodda type="constant" dalında ya devreye hiç dokunulmaz ya da yalnızca qc.x(n) ile ancilla çevrilir (global faz farkı, okunan kararı değiştirmez); type="balanced" dalında ise her $i$ için qc.cx(i, n) ile girişten ancilla'ya CNOT zinciri kurulur. Böylece kara kutu hâlâ “fonksiyonu tek tek listelemek” değil, tek geçişte $f(x)$ bilgisini giriş fazına işler (örnek dengeli fonksiyonun cebiri analiz bölümünde açılır).

• Son Hadamard ve ölçüm

  Oracle'dan sonra yalnızca giriş hatlarına ikinci Hadamard uygulanır: qc.h(range(n)) — ancilla bu aşamada tekrar dönüştürülmez; karar, onun son kuantum durumundan değil, ilk $n$ kübitteki girişimden okunur. Ardından qc.measure(range(n), range(n)) ile yalnızca bu $n$ hat klasik register'a yazılır. Ölçüm $0^n$ ise sabit; aksi takdirde dengeli sonucu 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)")

Editördeki n = 3, type="constant" senaryosuyla üretilen qc için Qiskit metin çizimi solda; sağda aynı akışın şematik özeti yer alır. Sabit oracle dalında kod ara sıra ancilla üzerinde ek bir X ekleyebilir (np.random); tutarlı bir terminal örneği için burada np.random.seed(0) ile aynı çağrıdan alınmış print(qc) kullanıldı (oracle bölümünde yalnızca çift barrier() arası boşluk). Dengeli modda ortaya CNOT zinciri çıkar; metin çizimi de buna göre uzar.

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

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.

Bu şema 6 · Aynı Devre (İki Temsil) bölümündeki akışı korur; $n=3$ için sabit oracle örneğini yineleyerek 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

  Klasik modelde her sorgu bir $x$ seçip $f(x)$ döndürmektir. Sabit veya dengeli olduğunu kesin bilmek için en kötü durumda $2^{n-1}+1$ klasik sorgu gerekir. Örnek: $n=3$ iken bu $2^{2}+1=5$ demektir. Deutsch–Jozsa aynı ayrımı tek kuantum oracle uygulaması—tek bir $U_f$ çağrısı—ile tamamlar; fark, sorgu karmaşıklığında üstel düzeydedir.

• Oracle tasarımı

  Koddaki CNOT zinciri, dengeli sınıftan yalnızca bir örnek üretir; başka geçerli dengeli oracle’lar da aynı algoritma iskelesine takılabilir. Vaat şudur: sabit $f$ için ölçümde $0^n$ (tüm sıfırlar) baskın çıkar; dengeli $f$ için bu desen yıkıcı girişimle ortadan kalkar—hangi dengeli oracle seçilirse seçilsin. $n=3$ örneğinde $0^n$ klasik dizide $000$ olarak görünür.

• Neden ancilla ölçülmüyor?

  Ancilla, standart $U_f$ tanımında XOR’u taşıyıp $f(x)$ bilgisini phase kickback ile giriş register’ının fazına aktarmak için kullanılır. Karar, son Hadamard’dan sonra giriş hatlarındaki girişim örüntüsünde toplanır; ancilla’nın klasik olarak okunması ek bir karar kuralı sunmaz. Bu yüzden devre QuantumCircuit(n + 1, n) biçiminde kurulur: yalnızca ilk $n$ kübit ölçülür.

• Söz ve güvenilir ölçüm

  Karar kuralı, $f$’nin mutlaka sabit veya dengeli olduğu sözüne dayanır; bu vaat yoksa $0^n$ ölçmek dengeli sınıfa kesin kanıt vermez. Gürültüsüz simülasyonda ve ideal devrede sonuç deterministiktir; shots=1 yeterlidir. Gerçek donanımda okuma ve kapı hataları için shots artırılabilir veya hata azaltımı düşünülür.