مهندس کوانتومی›الگوریتم‌های کوانتومی›فصل 21

21. الگوریتم برنشتاین–وازیرانی (Bernstein–Vazirani)

پنج سطح این فصل

شهود — f(x) = a·x ⊕ b رشته‌ای را به‌صورت فرم خطی پنهان می‌کند؛ یک پرس‌وجوی کوانتومی a را دقیقاً می‌خواند.
ریاضیات — H^{⊗n}·اورکل·H^{⊗n} الگوی فازی (−1)^{a·x} را دقیقاً به حالت پایه |a⟩ با دامنهٔ ۱ می‌نگارد.
پیاده‌سازی — numpy با تبدیل والش–هادامارد؛ بازیابی دقیق برای هر n که در حافظه جا شود.
مهندسی — همان منابع دویچ–یوزا (n+1 کیوبیت، یک فراخوانی اورکل)؛ اورکل زنجیره‌ای از CNOT است.
پژوهش — یادگیری توازی کوانتومی و نمونه‌برداری فوریه از این‌جا شروع می‌شوند؛ گونه‌های اورکل نویزی هنوز زمین بازِ آموزنده‌ای‌اند.

21.1رشته‌های پنهان

برنشتاین و وازیرانی (Bernstein–Vazirani) در ۱۹۹۳ به‌جای گزاره، رشته‌ای را پنهان کردند: f(x) = a·x ⊕ b = (a₁x₁ ⊕ … ⊕ aₙxₙ) ⊕ b، و تکلیف، بازیابی رشتهٔ پنهان a است. ثابت b در اورکل لانه کرده و خواهیم دید که قرارداد کیوبیت کمکی بی‌اثرش می‌کند. این نتیجه از نظر تاریخی مهم است چون نخستین جدایی در برابر الگوریتم‌های کلاسیک خطای محدود بود — BQP در برابر BPP در جهان اورکل — و حلقه‌ای را که دویچ–یوزا باز گذاشته بود بست. همچنین نخستین الگوریتمی است که خروجی‌اش یک رشته است نه یک حکم تک‌بیتی.

21.2ساخت اورکل

Uf: |x⟩|y⟩ ↦ |x⟩|y ⊕ a·x ⊕ b⟩ از گیت‌های کلاسیک برگشت‌پذیر ساخنی است: برای هر i که aᵢ = 1، یک CNOT از کیوبیت ورودی i به کیوبیت کمکی توازی را حساب می‌کند، به‌علاوه یک X روی کمکی اگر b = 1. حالا کمکی را در |−⟩ بگذرانید. هر CNOT آن‌وقت فازی پس می‌زند: CNOT_{i→a}|x⟩|−⟩ = (−1)^{aᵢxᵢ}|x⟩|−⟩ — باز هم پس‌زنی فاز — پس کل اورکل روی ثبات ورودی به‌صورت (−1)^{a·x ⊕ b} = (−1)^b·(−1)^{a·x} عمل می‌کند. ضریب سراسری (−1)^b مشاهده‌ناپذیر است؛ b با قرارداد کمکی پاک شده و فقط الگوی فازی a می‌ماند.

21.3راه‌حل کوانتومی

q0 … q(n-1):  |0> ─H─●─H─M     readout = a, with certainty
                 │
q_n:          |1> ─H─Uf──      Uf: |x>|y> ↦ |x>|y ⊕ (a·x ⊕ b)>

مدار عیناً همان دویچ–یوزاست — فقط ساختار موعودشدهٔ f عوض شده. پس از اورکل ثبات ورودی (1/√2ⁿ)·Σ_x (−1)^{a·x}|x⟩ را نگه می‌دارد. اعمال H^{⊗n} (که |x⟩ → (1/√2ⁿ)·Σ_y (−1)^{x·y}|y⟩) دامنهٔ حالت پایهٔ y را چنین می‌دهد: (1/2ⁿ)·Σ_x (−1)^{x·(a⊕y)} — جمعی از ±1 روی 2ⁿ جمله که اگر y = a برابر ۱ و در غیر این صورت ۰ است، با همان حذفِ ۲۰.۴. اندازه‌گیری هر بار، دقیقاً a را برمی‌گرداند؛ بدون shot.

21.4مقایسهٔ کلاسیک

هر پرس‌وجوی کلاسیک یک معادلهٔ خطی a·x = c در بیت‌های مجهول a₁…aₙ برمی‌گرداند؛ پیش از معین‌شدن a به n معادلهٔ مستقل خطی نیاز است — کران پایین اطلاعات‌نظری، نه آرتیفکت طراحی الگوریتم. الگوریتم کوانتومی هر n بیت را در یک پرس‌وجو استخراج می‌کند. توضیح صادقانه این نیست که «همهٔ 2ⁿ ورودی را موازی پرس‌وجو کرد»: یک بار پرس‌وجو کرد، اما روی برهم‌نهی، و عمل هم‌زمان اورکل روی همهٔ ورودی‌هاست که اجازه می‌دهد یک اندازه‌گیری سراسری، تابع خطی را آشکار کند. این نخستین جدایی اورکلی BQP در برابر BPP بود و جامعه را قانع کرد که کران‌های پایین کلاسیکِ تصادفی، مزیت کوانتومی را حل نمی‌کنند.

21.5پیاده‌سازی

import numpy as np
n, a, b = 4, 0b1011, 1
N = 2 ** n
H1 = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
Hn = H1
for _ in range(n - 1):
    Hn = np.kron(Hn, H1)                       # والش–هادامارد روی n کیوبیت
f = np.array([(bin(x & a).count("1") + b) % 2 for x in range(N)])
psi = np.ones(N, dtype=complex) / np.sqrt(N)   # H روی همهٔ ورودی‌ها
psi *= (-1.0) ** f                             # اورکل به‌صورت فاز (کمکی |->)
psi = Hn @ psi                                 # هاداماردهای نهایی
y = int(np.argmax(np.abs(psi)))
print(f"recovered a = {y:04b}   expected a = {a:04b}   exact: {y == a}")

میان‌بُر را ببینید: وقتی کیوبیت کمکی را تحلیلی و به‌صورت |−⟩ دنبال می‌کنیم، اورکل عین فاز قطری (−1)^{f(x)} است — نیازی به شبیه‌سازی 2n بعدی نیست. Hn که از کرونکرکردن بلوک‌های ۲×۲ ساخته می‌شود تبدیل والش–هادامارد است، نه FFT؛ برای f(x) = a·x روی ضرب داخلی بیتی این دو با هم فرق دارند.