28. سرعت‌های کوانتومی واقعاً از کجا می‌آیند
28.1بدفهمی‌های جست‌وجوی خام
جرم‌بارترین جمله در محاسبات کوانتومی: «همهٔ 2ⁿ پاسخ را موازی امتحان می‌کند». اگر مکانیسم این بود، یک‌شبه NP را فرومی‌ریختیم — تخصیص رضایت‌بخش را از برهم‌نهی بیرون بخوان. نمی‌توانیم، چون اندازه‌گیری از توزیعی نمونه می‌گیرد که ساخته‌ایم، و ساختن توزیع درست خودِ مسأله است. موازی‌سازی در برهم‌نهی مجانی است؛ خواندنِ چیز مفیدی هزینه دارد. هر سرعت واقعی نه با بیشتر امتحان‌کردن، که با چیدن تداخل کار می‌کند تا دامنهٔ پاسخ در لحظهٔ اندازه‌گیری بزرگ شود — بهینه‌سازی محدودیت‌محور، نه بادِ جست‌وجوی خام. این بدفهمی را همین حالا بکشید؛ وگرنه در هر جلسه‌ای که تا ابد می‌نشینید سر برمی‌آورد.
28.2تداخل
مکانیسم جهانی. محاسبهٔ کوانتومی رقص دامنه‌هاست: مسیرهای منتهی به پاسخ‌های غلط فازهایی می‌گیرند که حذف می‌شوند؛ مسیرهای منتهی به پاسخ درست تقویت. الگوریتم دویچ کم‌ترین نمایش است — یک پرسش، دو مسیر، یک تداخل مخرب. گروور نسخهٔ صنعتی است: بازتاب حول میانگین، بازتاب حول حالت نشانه‌دار، چرخش دامنه به موضع دلخواه، 2ⁿ/² بار. QFT تداخل به‌مثابه خوانش است: فازهای انباشته‌شده روی یک ثبات بازترکیب می‌شوند به برآورد تناوب. پرسش طراحی هرگز «چگونه همه را امتحان کنم؟» نیست، بلکه «کدام فازها را کجا بپرانم تا هیستوگرام قله بگیرد؟» است — و برای این پرسش فقط چند تکنیک شناخته‌شده وجود دارد.
28.3تقویت دامنه
تنها عنصر عمومی: با یک رویهٔ بررسی (اوراکل) و هر آماده‌سازی از فضای جست‌وجو، دامنهٔ خوب را √۲ سریع‌تر از نمونه‌گیری تصادفی تقویت کنید — O(√(N/M)) پرسش برای M مورد نشانه‌دار، به‌طور اثبات‌شده بهینه. تعمیم‌هایش بیشترِ «سرعت‌های کوانتومی» پیشنهادی در طبیعت را پوشش می‌دهند: شمارش کوانتومی (برآورد M)، جست‌وجوی نقطه‌ثابت، برآورد دامنه (مونت‌کارلو با مزیت √ — محبوب‌ترین ادعای مالی، فصل ۵۰)، و تقویت. محدودیت‌هایش هم عمومی‌اند: فقط درجه‌دو، هزینهٔ اوراکل حساب می‌شود، و ورودی باید قابل آماده‌سازی باشد. هنگام ارزیابی هر الگوریتم کوانتومی پیشنهادی، نخست جایگاهش را نسبت به تقویت دامنه پیدا کنید؛ بیشترشان همین‌اند، با لباس مبدل.
28.4ساختار پنهان
سرعت‌های نمایی اینجا زندگی می‌کنند و دروازه تنگ است: مسأله باید ساختار جبری‌ای داشته باشد که QFT بتوان آشکار کند — تناوب (شور: f(x+r) = f(x))، زیرگروه پنهان (تعمیم؛ برای گروه‌های آبلی کارا، برای ناآبلی باز — و به همین دلیل وضعیت ایزومرفیسم گراف و مسائل شبکه در سمت کلاسیک مانده)، انتقال پنهان، برآورد فاز یونیتی‌های دسترسی‌پذیر. به غایبان توجه کنید: هیچ مسألهٔ NP-کاملی شناخته نشده که به زیرگروه پنهانِ آبلی کاهیده شود. درس مهندسی: مزیت نمایی کوانتومی کمیاب و ساختاری است، نه شتاب‌دهندهٔ همه‌کاره. ادعاهای «سرعت نمایی برای صنعت شما» در نقشه‌های راه باید همین‌جا ممیزی شوند.
28.5مسائل نمونه‌گیری
جداسازی‌های قابل‌اثبات بدون ساختار: نمونه‌گیری از توزیع‌هایی که کوانتومی آماده‌کردنش آسان و کلاسیکی باوراً سخت است. نمونه‌گیری مدار تصادفی (گوگل ۲۰۱۹)، نمونه‌گیری بوزونی (فتونی)، مدارهای IQP. معیار شواهد: جداسازی تحت فرض‌های پیچیدگی برقرار است (سلسله‌مراتب چندجمله‌ای فرونمی‌ریزد) و داستان راستی‌آزمایی آماری است (XEB)، نه مطلق — منتقدانی چون کلایی دقیقاً همین‌جا فشار داده‌اند. بازده عملی فعلاً صفر است: توزیع‌های نمونه‌گیری‌شده کاربرد شناخته‌شده‌ای ندارند. بازده علمی عظیم است: این‌ها تنها آزمایش‌های کنترل‌شده‌ای هستند که می‌سنجند آیا ماشین‌های BQP اصلاً از کلاسیکی جلو می‌زنند. مقالات عصر برتری را به‌عنوان آزمایش‌های فیزیک با حاشیهٔ خطای نظریهٔ پیچیدگی بخوانید.
28.6مسائل شبیه‌سازی
فاینمن ۱۹۸۲: طبیعت کلاسیک نیست، پس فیزیک را با ماشین‌کاری کوانتومی شبیه‌سازی کن. مدافع‌ترین کلاس سرعت است، چون جبر پنهانی نمی‌خواهد — بازنمایی کلاسیک حالتِ سیستم n-ذره‌ای ساختاراً فضای نمایی می‌خواهد (بخش پنجم!)، درحالی‌که 2n کیوبیت بومی‌اش را دارد. شیمی کوانتومی (انرژی‌های حالت پایه برای کاتالیز، فصل ۴۸)، مواد (ابررسانایی دمای بالا)، دینامیک هسته‌ای و مادهٔ چگال، و — رو به رشد — راستی‌آزمایی فیت‌سخت‌افزاری با خود سخت‌افزار. اما دقت است: دقت شیمیایی به تصحیح خطا در مقیاس نیاز دارد، و به همین دلیل شبیه‌سازی کاربردِ نقشهٔ راه است، نه NISQ. فصل ۴۸ وضعیت صادقانه را می‌گوید.
28.7ساختار جبری
از بالا نگاه کنید و الگو تیز می‌شود: هر سرعت نمایی از جبر می‌گذرد — تبدیل فوریه روی گروه‌ها، تناوب، دسترسی به مقدار ویژه. این هم‌زمان نقشه است (کجا برای الگوریتم جدید شکار کنید: گذر کوانتومی روی ساختارها، مسائل دستگاه-خطی با اوراکل‌های ساختاری — احتیاط‌های HHL داستان عبرت است، فصل ۴۹) و دیوار است (مسائل بی‌ساختار از نظر کوانتومی خسته‌کننده‌اند: BBBV). ماجرای کوانتومی‌زدایی همان دیوار در حرکت است: الگوریتم کلاسیکی تانگ (۲۰۱۹) سرعت‌های ادعاشده برای جبرخطیِ سیستم-توصیه‌مانند را با بهره‌گیری از همان ساختار به‌صورت کلاسیکی به‌اضافه دسترسی نمونه خورد. بهترین رویهٔ کنونی: تا وقتی ادبیات پنج سال اخیر را چک نکرده‌اید، هر ادعای ساختار-محور کوانتومی را با رقیب کلاسیکی فرض کنید.
28.8نظریهٔ پیچیدگی کوانتومی
نظریهٔ زندهٔ فراتر از BQP: QMA (NP کوانتومی — هامیلتونی‌های محلی QMA-کامل‌اند؛ احتیاطِ «حتی برای رایانه‌های کوانتومی در بدترین حالت سخت» شیمی کوانتومی)، کلاس‌های کوانتومی-کوانتومی و آدیاباتیک، کران‌های پایین پیچیدگی پرسش (روش چندجمله‌ای، روش رقیب — ابزارهایی که بهینه بودن گروور را اثبات می‌کنند)، و پیوند با رمزنگاری (شبکه‌ها در برابر حملات کوانتومی شناخته‌شده مقاوم‌اند — بنیان رمزنگاری پساکوانتومی، فصل ۴۶). اگر پژوهش صدایت می‌کند (بخش چهاردهم)، این زیرحوزه همان‌جایی است که مهارتِ پیاده‌سازی و تجربه‌گرایی مهندس نرم‌افزار با نظریهٔ باز روبه‌رو می‌شود: تکنیک‌های کران پایین به‌ویژه از نظر محاسباتی کم‌کاوشیده‌اند و برهان به‌کمک-ماشین جوان است.
28.9سرعت مجانبی در برابر عملی
صافی نهایی. مجانبی: برای n به‌اندازهٔ کافی بزرگ، کوانتوم می‌برد. عملی: در اندازه‌هایی که کسی می‌خواهد، روی سخت‌افزار واقعی، با سربار تصحیح خطا. شکاف میان این دو همان‌جایی است که careers و شرکت‌ها سوخته‌اند. مشخصاً: مزیت مجانبی شور نمایی است، اما فاکتورگیری RSA-2048 حدود ۴٬۰۰۰ کیوبیت منطقی و ~10⁹ دروازهٔ منطقی می‌خواهد — ماشینی که هنوز وجود ندارد (کلاس استارلینگ، ~۲۰۲۹+، و استارلینگ ۱۰۰ کیوبیت منطقی هدف می‌گیرد نه ۴٬۰۰۰ را). گروور در برابر AES-128 حدود ۳٬۰۰۰ کیوبیت منطقی می‌خواهد که 2⁶⁴ تکرار را روزها اجرا کند. تحلیل صادقانه‌ای که هر مهندس به ذی‌نفعانش بدهکار است: کل پشته را لوله‌کشی کنید — الگوریتم → کیوبیت منطقی → کیوبیت فیزیکی → ساعت → دلار — پیش از نقل هر سرعتی. بخش نوزدهم همین صفحه‌گسترده را می‌سازد.