18. پارادایم الگوریتمی
18.1چه چیزی یک الگوریتم را کوانتومی می‌کند؟
نه استفاده از برهم‌نهی — هر ایدهٔ ساده‌انگارانهٔ «همهٔ ورودی‌ها را موازی امتحان کن» در لحظهٔ اندازه‌گیری می‌میرد (۱.۷). الگوریتم وقتی سزاوار این نام است که تداخل کار منطقی انجام دهد: مدار، ورودی را به حالتی می‌برد که دامنه‌های پاسخ‌های غلط در فازهای متفاوت قرار دارند و یکدیگر را حذف می‌کنند، در حالی که دامنه‌های پاسخ درست هم‌راستا می‌شوند. سه عنصر در سراسر این بخش تکرار می‌شود: کدگذاریِ همدوسِ ساختار (توازی، دوره، نشانه‌گذاری) در فازها از طریق اورکل (oracle)؛ یک تغییر پایه — هادامارد یا تبدیل فوریه — که آن فازها را به تمرکز قابل اندازه‌گیریِ دامنه تبدیل می‌کند؛ و یک گام پس‌پردازش کلاسیک (جبر خطی، کسر مسلسل، gcd) که پاسخ را از نمونه‌ها بیرون می‌کشد. هر یک را حذف کنید و الگوریتم از کار می‌افتد؛ بقیهٔ بخش هفتم همین سه عنصرند که بازترکیب شده‌اند.
18.2الگوریتم‌های مبتنی بر اورکل
بیشتر شتاب‌های کوانتومیِ اثبات‌پذیر در مدل اورکل زندگی می‌کنند: تابع f فقط به‌صورت جعبه‌سیاهِ یکانی در دسترس است، Uf: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩، و به‌جای زمان خام، *پرس‌وجو*ها — فراخوانی‌های Uf — شمرده می‌شوند. این کار ایدهٔ الگوریتمی را از مسئله‌های بارگذاری داده جدا می‌کند و کران‌های پایین را اثبات‌پذیر می‌سازد (روش چندجمله‌ای و روش حریف، بخش هشتم). دویچ، دویچ–یوزا، برنشتاین–وازیرانی، سایمون و گروور همه این‌جا زندگی می‌کنند:
| الگوریتم | مسئله | پرس‌وجوهای کوانتومی | پرس‌وجوهای کلاسیک |
|---|---|---|---|
| دویچ | ثابت یا متوازن، ۱ بیت | ۱ | ۲ |
| دویچ–یوزا | ثابت یا متوازن، n بیت | ۱ | 2ⁿ⁻¹+1 (قطعی) |
| برنشتاین–وازیرانی | رشتهٔ پنهان a | ۱ | n |
| سایمون | دورهٔ پنهان s | O(n) | Θ(2^{n/2}) |
| گروور | یافتن آیتم نشانه‌گذاری‌شده در میان N | Θ(√N) | Θ(N) |
بند صداقت: اورکل وعده‌ای است که Uf به‌طور همدوس ارزان پیاده‌سازی می‌شود. اگر ساختنش گران‌تر از الگوریتم کلاسیک تمام شود، «شتاب» داستان است — موضوع ۲۸.۹ و نتایج dequantization.
18.3تداخل به‌مثابه محاسبه
سازوکار تکرارشونده پس‌زنی فاز (phase kickback) است: کیوبیت کمکی (ancilla) را در |−⟩ = (|0⟩−|1⟩)/√2 آماده کنید و اورکل مقادیر تابع را به فاز تبدیل می‌کند — Uf|x⟩|−⟩ = (−1)^{f(x)}|x⟩|−⟩. فازها برای اندازه‌گیری نامرئی‌اند؛ اطلاعات نسبی و ساختاری‌اند. کارِ الگوریتم چرخاندن فازها به دامنه است: هادامارد (یا QFT) اعمال کنید تا جمله‌های (−1)^{f(x)} برای برخی خروجی‌ها سازنده و برای بقیه ویرانگر جمع شوند. شما هرگز f(x) را برای x خاصی نمی‌آموزید؛ یک خاصیت سراسری را می‌آموزید که هیچ پرس‌وجوی منفردی آشکارش نمی‌کند. همین یک ترفند، با بزرگ‌شدن مقیاس، دویچ است (یک بیت)، برنشتاین–وازیرانی (یک فرم خطی)، سایمون (یک دوره) و اورکل فازی گروور. یک‌بار این‌جا یاد بگیرید و هر مدار فصل‌های ۱۹ تا ۲۶ به «فازها به‌علاوهٔ تغییر پایه» تجزیه می‌شود.
18.4تقویت دامنه
قالبی که ارزش نام‌گذاری زودهنگام دارد. فرض کنید یک روش کلاسیک احتمالاتی A با احتمال p موفق می‌شود؛ تکرار آن k بار موفقیت را به حدود 1−(1−p)^k می‌رساند، پس خطای ε هزینهٔ O(1/ε) تکرار دارد. تقویت دامنه (amplitude amplification) (براسار–هویر–موسکا–تپ، ۲۰۰۰) نسخهٔ کوانتومی را اجرا می‌کند — A را اعمال کن، دربارهٔ زیرفضای موفقیت بازتاب بگیر، دربارهٔ حالت اولیه بازتاب بگیر — و با O(1/√p) فراخوانی به موفقیت ≈ 1 می‌رسد. این یک شتاب درجهٔ دو نسبت به بهترین تکرار کلاسیک ممکن است و تقریباً روی هر الگوریتم احتمالاتی کار می‌کند: تخمین مونت‌کارلو، نمونه‌برداری، جست‌وجوی بازگشتی. الگوریتم گروور حالت خاصی است که در آن A لایهٔ هادامارد است؛ ماشین‌آلات کامل در ۲۵.۶.
18.5تخمین فاز
قالب دوم: با یکانی U و یکی از بردارهای ویژه‌اش |u⟩ و توانایی اعمال U کنترل‌شده، φ را تخمین بزنید که U|u⟩ = e^{2πiφ}|u⟩، با دقت m بیت. مدار، فازهای e^{2πi·2^k·φ} را در یک ثبات (register) شمارش می‌نویسد و با QFT وارونه می‌خواند. تخمین فاز موتور درون الگوریتم شور است (یافتن مرتبه، تخمین فاز روی یکانی ضرب پیمانه‌ای) و مسیر پذیرفته‌شده برای انرژی‌های حالت پایه در شیمی. هزینه‌اش t = m + O(log(1/ε)) کیوبیت و t بار اعمال توان‌های کنترل‌شدهٔ U است؛ بخش سخت همیشه خودِ U است. فصل ۲۴ به‌طور کامل بررسی‌اش می‌کند.
18.6پیاده‌روی‌های کوانتومی
همتای پیاده‌روی تصادفی: پیمانک روی گراف با گام‌های یکانی حرکت می‌کند، در زمان گسسته (پیاده‌روی سکه‌ای یا Szegedy) یا زمان پیوسته (e^{−iHt}). روی مسئله‌های بدون ساختار، شتاب درجهٔ دوی گروور را بازتولید می‌کنند. روی مسئله‌های ساختاردار می‌توانند فراتر روند: تمایز عناصر (element distinctness) با O(N^{2/3}) پرس‌وجو حل می‌شود (امبینیس/Ambainis) و چایلدز (Childs) مسئلهٔ اورکلی را نشان داد که پیاده‌روی زمان‌پیوسته روی آن به‌طور نمایی از هر الگوریتم کلاسیک روی همان گراف سریع‌تر است. پیاده‌روی‌های کوانتومی همچنین زیربنای عملی شبیه‌سازی همیلتونی روی گراف‌های خلوت‌اند. از ماشین‌آلات QFT/QPE این بخش کمتر محوری‌اند، اما فلسفه‌شان یکی است: ساختار گراف یا طیف را به تداخل تبدیل کنید، بعد نمونه‌برداری کنید.
18.7تبدیل‌های فوریهٔ کوانتومی
Primitive استخراجی پشت نتایج بزرگ: حالتی که دامنه‌هایش دوره‌ای است، بعد از QFT به حالتی می‌رود که روی چند حالت پایه متمرکز است — دوره‌ها به قله‌هایی تبدیل می‌شوند که می‌توان نمونه‌برداری‌شان کرد. مدار فقط O(n²) گیت برای N = 2ⁿ بعد هزینه دارد، در برابر O(N log N) برای FFT کلاسیک — اما ریزنویسی ۲۳.۷ را بخوانید: QFT یک حالت کوانتومی مصرف می‌کند، نه فهرستی از اعداد، و حالتی برمی‌گرداند که نمونه‌برداری می‌کنید نه جدولی. اسکلت مشترک سایمون، یافتن دورهٔ شور و تخمین فاز است؛ برای همین پیش از الگوریتم‌های وابسته به آن، فصل مخصوص خودش (۲۳) را دارد.