20. الگوریتم دویچ–یوزا (Deutsch–Jozsa)

20.1تعریف مسئله

حالا f: {0,1}ⁿ → {0,1}، موعودشده که یا روی همهٔ 2ⁿ ورودی ثابت است یا متوازن — دقیقاً 2ⁿ⁻¹ ورودی مقدار ۱ می‌گیرند. تعیین کنید کدام. دویچ و یوزا (Deutsch–Jozsa) در ۱۹۹۲ این مسئله را مطرح و حل کردند؛ نخستین جدایی نمایی میان پیچیدگی پرس‌وجوی کلاسیک و کوانتومی: کلاسیکاً ممکن است لازم باشد 2ⁿ⁻¹+1 ورودی را ببینید، کوانتومی یک فراخوانی اورکل، با قطعیت. مثل نسخهٔ دویچ، مسئلهٔ موعود (promise problem) است: روی توابع بیرون از موعود، خروجی الگوریتم بی‌معناست. این ستاره را تا ۲۰.۶ جلوی چشم نگه دارید.

20.2مدل اورکل

جعبه‌سیاه Uf: |x⟩|y⟩ ↦ |x⟩|y ⊕ f(x)⟩ روی n+1 کیوبیت است — همان قرارداد اورکل دویچ، یک یکانی به‌ازای هر پرس‌وجو، و دقیقاً یک پرس‌وجو اعطا شده. مثل قبل، تغذیهٔ کیوبیت کمکی با |−⟩ = (|0⟩−|1⟩)/√2 اورکل را به عملگر فازی قطری (−1)^{f(x)} روی ثبات ورودی تبدیل می‌کند: اورکل فازی. هیچ‌چیز در این ساختار به آنچه f درونش محاسبه می‌کند وابسته نیست — این نقطهٔ قوت و (۲۰.۶) نقطهٔ ضعف مدل است.

20.3ساخت مدار

q0 … q(n-1):  |0> ─H─●─H─M     read 0…0 ⟺ f constant (deterministic)
                  │
q_n:          |1> ─H─Uf──      Uf: |x>|y> ↦ |x>|y ⊕ f(x)>

هادامارد روی هر n+1 کیوبیت، یک فراخوانی اورکل، هادامارد روی n کیوبیت ورودی، اندازه‌گیری ورودی‌ها. به‌صورت شبه‌کد، روی شبیه‌ساز بردار حالتی که دارید:

psi = |0…0>|1>
apply H to all n+1 qubits
psi = Uf @ psi              # the single query
apply H to the n input qubits
answer = "constant" if measured(input register) == 0…0 else "balanced"

20.4تداخل

دامنهٔ خروجی همه‌صفر را دنبال کنید. پس از اورکل و هاداماردهای نهایی برابر است با (1/2ⁿ)·Σ_x (−1)^{f(x)} — میانگین (−1)^{f(x)} روی همهٔ ورودی‌ها. اگر f ثابت باشد، همهٔ جمله‌ها +1 یا همه −1‌اند: جمع ±2ⁿ، دامنه ±1، و قطعاً همه‌صفر می‌خوانید. اگر f متوازن باشد، دقیقاً نصف جمله‌ها +1 و نصف −1‌اند: جمع ۰. هر 2ⁿ مسیر محاسباتی برای نابودکردن آن یک خروجی تداخل می‌کنند — و چون نرم حالت ۱ است، جرم احتمال باید جای دیگری بنشیند، روی رشته‌هایی که *متوازن*بودن را گواهی می‌کنند. یک پرس‌وجو، 2ⁿ جملهٔ سازنده/ویرانگر، صفر محاسبهٔ عددی احتمال.

20.5پیچیدگی

کوانتومی: ۱ پرس‌وجو، O(n) گیت هادامارد به‌علاوهٔ اورکل، احتمال موفقیت دقیقاً ۱. کلاسیک قطعی: 2ⁿ⁻¹+1 پرس‌وجو در بدترین حالت — ورودی‌ها را بپرسید تا هر دو مقدار را ببینید (متوازن) یا 2ⁿ⁻¹+1 مقدار برابر دیده باشید (ثابت، چون تابع متوازن فقط 2ⁿ⁻¹ صفر دارد). کلاسیک تصادفی: ۲ پرس‌وجو برای احتمال موفقیت ≈ 3/4 کافی است و O(log(1/δ)) پرس‌وجو برای خطای δ — پس جدایی نمایی فقط در برابر الگوریتم‌های کلاسیک قطعی است و قرائت منصفانه، جدایی صادقانه را «یک پرس‌وجو در برابر تعداد ثابتی پرس‌وجو» می‌گذارد. این هم جداییِ اثبات‌پذیر است؛ فقط تیتری که مقالهٔ ۱۹۹۲ القا می‌کرد نیست.

20.6محدودیت‌های نتیجه

سه محدودیت، همگی ساختاری. موعود: توابع واقعی نه ثابت‌اند نه متوازن، و بیرون از موعود خروجی دلخواه است — هیچ تکلیف محاسباتی طبیعی‌ای به این شکل نمی‌رسد. اورکل: شتاب فرض می‌کند Uf هزینه‌اش یک «واحد» است؛ برای هر f موعودشدهٔ مشخصی که بنویسید، الگوریتم کلاسیک می‌تواند به‌جای پرس‌وجو، تعریف مدارش را بازرسی کند. نوع جدایی: در برابر الگوریتم‌های تصادفی کلاسیک محو می‌شود (۲۰.۵)؛ پس ارزش ماندگار نتیجه آموزشی است — قالب «اورکل فازی به‌علاوهٔ هادامارد» و مفهوم پیچیدگی پرس‌وجو را معرفی کرد که برنشتاین–وازیرانی و سایمون بی‌درنگ به جدایی‌هایی رساندند که از تصادفی‌سازی جان می‌دهند. دویچ–یوزا را تمرین اول حوزه بدانید، نه نتیجهٔ اولش.