19. الگوریتم دویچ (Deutsch)

19.1مسئله

تابع تک‌بیتی f: {0,1} → {0,1} به‌صورت جعبه‌سیاه به شما داده شده است. تابع موعود شده که یا ثابت باشد (f(0) = f(1)) یا متوازن (f(0) ≠ f(1)). پرسش: کدام؟ مسئله بی‌اهمیتی به نظر می‌رسد و هست — نکته همین است. کوچک‌ترین فضایی است که در آن «خاصیت سراسری f» از «مقادیر f» جدا می‌شود؛ پس تمیزترین جا برای دیدن این است که تداخل چگونه یک شاهکار محاسباتیِ پرس‌وجویی انجام می‌دهد. دویچ در ۱۹۸۵ آن را مطرح و حل کرد — نخستین الگوریتم کوانتومی نوشته‌شده؛ همه‌چیز در این بخش نوادهٔ آن است.

19.2راه‌حل کلاسیک

به‌طور قطعی باید دو بار f را پرس‌وجو کنید: f(0) به‌تنهایی با هر دو حالت سازگار است و f(1) به‌تنهایی هم. دو پرس‌وجو همیشه تصمیم می‌گیرد — اگر پاسخ‌ها برابر بودند، ثابت؛ وگرنه متوازن. تصادفی‌سازی کمک نمی‌کند: با یک پرس‌وجو f(x) را برای یک x می‌بینید و آن تک‌بیت با همِ یک تابع ثابت و همِ یک تابع متوازن سازگار است؛ پس هیچ راهبردی از سکه‌انداختن بهتر نمی‌شود. پیچیدگی پرس‌وجوی کلاسیک: دقیقاً ۲. الگوریتم کوانتومی، خواهیم دید، دقیقاً ۱ لازم دارد. ضریب ۲ — کوچک‌ترین جدایی ممکن — اما جدایی با سازوکار، نه برحسب تصادف.

19.3مدار کوانتومی

q0: |0> ──H──■──H──M        outcome 0 → constant
            │               outcome 1 → balanced
q1: |1> ──H──Uf──            Uf: |x>|y> ↦ |x>|y ⊕ f(x)>

دو کیوبیت. ثبات ورودی q0 از |0⟩ شروع می‌شود؛ کیوبیت کمکی q1 از |1⟩. به هر دو H اعمال کنید، یک بار اورکل را اعمال کنید (کنترل q0، هدف q1)، دوباره H روی q0 و فقط q0 را اندازه بگیرید. کیوبیت کمکی هرگز اندازه‌گیری نمی‌شود — کارش، که در ادامه توضیح داده می‌شود، این است که در |−⟩ بماند تا اورکل به‌صورت فاز عمل کند. یک پرس‌وجوی اورکل، یک اندازه‌گیری، پاسخی قطعی.

19.4تداخل

پس از هاداماردها حالت (|0⟩+|1⟩)/√2 ⊗ |−⟩ است. چون |−⟩ بردار ویژهٔ هر X-flip است، اورکل f را به‌صورت فاز پس می‌زند: Uf(|x⟩|−⟩) = (−1)^{f(x)}|x⟩|−⟩. ثبات ورودی اکنون ((−1)^{f(0)}|0⟩ + (−1)^{f(1)}|1⟩)/√2 را نگه می‌دارد. H نهایی به دامنه‌های — برای |0⟩: ((−1)^{f(0)}+(−1)^{f(1)})/2 و برای |1⟩: ((−1)^{f(0)}−(−1)^{f(1)})/2 — نگاشت می‌کند. اگر f ثابت باشد دو جمله به ±1 جمع می‌شوند: قطعاً ۰ می‌خوانید. اگر متوازن باشند دقیقاً به ۰ حذف می‌شوند: قطعاً ۱ می‌خوانید. تداخل ویرانگر میان دو پرس‌وجو تمامِ محاسبه است؛ کیوبیت کمکی این را ممکن کرد که مقادیر را به فاز تبدیل کرد.

19.5پیاده‌سازی

بردار حالت دو کیوبیت را به‌صورت آرایهٔ numpy به طول ۴ بسازید (اندیس = 2·x + y)، اورکل را ماتریس جایگشت و هاداماردها را همان ماتریس ۲×۲ آشنا. کل الگوریتم:

import numpy as np

H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

def deutsch(f):
    psi = np.array([0, 1, 0, 0], dtype=complex)      # |0>|1>
    psi = np.kron(H, H) @ psi                        # H روی هر دو کیوبیت
    U = np.zeros((4, 4))                             # اورکل به‌صورت جایگشت
    for x in (0, 1):
        for y in (0, 1):
            U[(x << 1) | (y ^ f(x)), (x << 1) | y] = 1
    psi = U @ psi
    psi = np.kron(H, np.eye(2)) @ psi                # H نهایی روی q0
    p0 = abs(psi[0]) ** 2 + abs(psi[1]) ** 2         # P(q0 = 0)
    return "constant" if p0 > 0.5 else "balanced"

ماتریس جایگشت متقارن است چون y ↦ y ⊕ f(x) وارونِ خودش است — رحمتی که با اورکل‌های عمومی نصیبتان نخواهد شد.

19.6راستی‌آزمایی تجربی

oracles = {"f=0": lambda x: 0, "f=1": lambda x: 1,
           "f=x": lambda x: x, "f=1-x": lambda x: 1 - x}
for name, f in oracles.items():
    answer = deutsch(f)                    # از 19.5
    truth = "constant" if name in ("f=0", "f=1") else "balanced"
    print(name, "->", answer, "| expected:", truth)