27. پیچیدگی محاسباتی
27.1P
کلاس P مسائل تصمیم قابل‌حل در زمان چندجمله‌ای است — جایی که توان، ثابتِ ثابت و اندازهٔ ورودی n متغیر است. مرتب‌سازی، کوتاه‌ترین مسیر، اول بودن (AKS، ۲۰۰۲)، برنامه‌ریزی خطی: همه در P. «چندجمله‌ای» صورت‌بندی رسمی «مقیاس‌پذیر» است: O(n²) شاید دردناک باشد، اما O(2ⁿ) ناامیدکننده است، و کلاس طبیعی‌ای میان آن‌ها نیست. هشدار عمل‌گرا که هرگز فراموش نکنید: الگوریتم «چندجمله‌ایِ» O(n¹⁰⁰) بی‌ارزش است و ثابت‌های سخت‌افزاری مهم‌اند — P گزاره‌ای دربارهٔ وجود مجانبی است و مهندسی (بخش دوازدهم) دربارهٔ ثابت‌هایی است که P نادیده می‌گیرد. پیچیدگی کوانتومی تمام این هشدارها را به ارث می‌برد.
27.2NP
مسائلی که پاسخ «بله»شان گواه کوتاهِ سریع‌قابل‌راستی‌آزمایی دارد — یافتن گواه شاید سخت باشد، چک‌کردنش آسان. SAT، فاکتورگیری-به‌صورت-تصمیم، دور هامیلتونی، عزیزان سخت بهینه‌سازی. مسائل NP-کامل (کوک–لوین: SAT جهانی است) سخت‌ترین‌های NPاند؛ حل چندجمله‌ای یکی، حل همه است. دو روشنی که مطبوعات دائم اشتباه می‌گیرند: NP یعنی «غیرچندجمله‌ای» نیست، و P در برابر NP باز است — دهه‌ها تلاش، مانع‌های اثبات فهرست‌شده (نسبی‌سازی، برهان‌های طبیعی، جبری‌سازی)، بی‌نتیجه. اینکه رایانه‌های کوانتومی به NP دست می‌زنند پرسشی دقیق و پاسخ‌پذیر است — بنگرید به 27.10 — و پاسخ، منفی‌ترین نتیجهٔ پرمخاطب حوزه است.
27.3زمان چندجمله‌ای
چرا پرستش چندجمله‌ای‌ها؟ سه دلیل. بسته‌شدگی: چندجمله‌ای‌ها ترکیب می‌شوند — زیرروال چندجمله‌ای که چندجمله‌ای بار صدا شود چندجمله‌ای می‌ماند، و همین کلاس‌ها را در برابر کاهش بسته نگه می‌دارد. استواری: کلاس تحت هر مدل ماشین معقول ناوردا است (RAM، تورینگ، لامبدادرصد — خواهر کمّیِ اصل چرچ–تورینگ، یعنی «اصل چرچ–تورینگ تعمیم‌یافته»، دقیقاً ادعای آن است که ماشین‌های کوانتومی هم آن را عوض نمی‌کنند — و شور مصداقِ در انتظار داوری است). صداقت: مجانبی‌ها بینش یگانه‌ای را رمزگذاری می‌کنند که از چرخهٔ سخت‌افزار جان سالم به در می‌برد. ترجمهٔ مهندس: کلاس‌های پیچیدگی می‌گویند کدام نبردها ارزش جنگیدن دارند؛ توان و ثابت‌ها می‌گویند امسال برنده می‌شوید یا نه.
27.4زمان نمایی
EXP و هم‌خانواده‌ها: قابل‌حل با منابع 2^poly(n). هر مسأله در EXP تصمیم‌پذیر است، بیشتر مسائل جالب حملهٔ brute-force نمایی دارند، و کل درام الگوریتم‌ها شکاف میان EXP و P است. محاسبات کوانتومی به‌عنوان کوچک‌کنندهٔ جزئی همان شکاف وارد می‌شود: گروور به هر مسألهٔ جست‌وجو-شکل سرعت عمومی √ می‌دهد (2ⁿ → 2^(n/2))، که واقعی و جهانی است و — این دقیقاً ناامیدی است — جایی نیست که EXP را به P فرو بریزد. درس ساختاری: سرعت‌های کوانتومی یک پدیده نیستند؛ سرعت عمومی جست‌وجو (درجه‌دو)، سرعت ساختاری (نمایی، اما فقط برای مسائل با جبر پنهان درست) و سرعت‌های نمونه‌گیری سه جاندار متفاوت‌اند. بخش ۲۸ رده‌بندی‌شان می‌کند.
27.5کاهش‌ها
کاهش ترجمه‌ای است: مسألهٔ A به B کاهیده می‌شود اگر حل‌کنندهٔ B با سربار چندجمله‌ای به شما حل‌کنندهٔ A بدهد. تنها میکروسکوپ نظریهٔ پیچیدگی است — برهان‌های مستقیم سختی فراتر از تکنیک‌های کنونی‌اند، اما کاهش‌ها سختی را روی نقشه پخش می‌کنند. برای شما: وقتی کسی برای مسألهٔ X سرعت کوانتومی ادعا کرد، نخستین پرسش‌تان این است که «از چه کاهیده، یا به چه؟» کاهش از مسألهٔ سختِ شناخته‌شده نشانهٔ عمق است؛ کاهش به ساختارِ آسان‌شناخته همان‌جایی است که ادعاهای سرعت کوانتومی معمولاً می‌میرند (نمونهٔ ساختاری شاید به دلایلی که کاهنده هرگز چک نکرده کلاسیکی آسان باشد). سواد کاهش، تفاوت میان خواندن مقالهٔ برتری کوانتومی و خوانده‌شدن توسط آن است.
27.6کلاس‌های پیچیدگی
نقشه، صادقانه کشیده‌شده: P ⊆ BQP ⊆ PSPACE (اثبات‌شده)؛ NP ⊆ PSPACE؛ برخورد BQP با قلمرو NP-کامل: نامعلوم و عمدتاً باور به «نه» (برای مسائل تصمیم)؛ P در برابر BQP: باز — شور شاهد جدایی است، نه برهان. همتایان کوانتومی را بیفزایید: QMA (گواه‌های کوانتومی — کلاس مسائل انرژی حالت پایه، 28.6)، QIP، BQC (محاسبهٔ سپرده‌شدهٔ راستی‌آزمایی‌شده). تصویر ماندگار: محاسبات کوانتومی به‌پهلو از نقشه می‌گذرد — مسائل باوراً سختِ کلاسیک (فاکتورگیری، که در NP∩co-ND نشسته، بیرون Pِ باورشده اما نه NP-کامل) را به BQP می‌برد و مسائل NP-کامل را سر جایشان می‌گذارد.
27.7BQP
مسائل قابل‌حل روی رایانهٔ کوانتومی در زمان چندجمله‌ای، با خطای حداکثر 1/3، به‌طور یکنواخت. اجزای تعریف توجه می‌خواهند: خطای کران‌دار (با تکرار تا 1/3ᵏ تقویت‌شدنی — ماشین‌پذیرشِ استدلال‌های تکرار بخش هفتم)، یکنواختی (یک خانوادهٔ الگوریتم، نه مشورت به‌ازای ورودی)، چندجمله‌ای در تعداد کیوبیت و زمان. هر آنچه در نقشه‌های راه IBM و گوگل است تلاشی است برای ساختن ماشین BQP فیزیکی در مقیاس؛ هر آنچه در بخش هفتم است بهترین‌های BQP است. کلاس نسبت به مجموعه‌دروازه (هر مجموعهٔ جهانی معقول همان BQP را می‌دهد) و فرض‌های نویزِ متعادل استوار است — و همین آن را به هدفی مهندسی تبدیل می‌کند.
27.8سرعت‌های کوانتومی
رده‌بندی، پیش از اشتیاق. نمایی، ساختاری: فاکتورگیری، لگاریتم گسسته، مسائل برآورد-فازمحور — ساختار جبری پنهان لازم دارند؛ سرعت از آشکارسازی تناوب توسط QFT می‌آید (فصل ۲۳). درجه‌دو، عمومی: گروور/تقویت دامنه — روی هر جست‌وجو کار می‌کند، تضمینی، و درجه‌دو بودنش برای جست‌وجوی جعبه‌سیاه به‌طور اثبات‌شده بهینه است (کران BBBV). نمونه‌گیری: نمونه‌گیری مدار تصادفی، نمونه‌گیری بوزونی — جداسازی‌های قابل‌اثبات تحت فرض‌های پیچیدگی، اما خودِ راستی‌آزمایی سخت است. شبیه‌سازی: شیمی کوانتومی، مواد — پیشنهاد اصلی فاینمن؛ ادعای سرعت بر نمایاندنِ سیستم کوانتومی با سیستم کوانتومی تکیه دارد. چهار جاندار متفاوت؛ چهار معیار شواهد متفاوت؛ هر چهار به یک شکل بازاریابی می‌شوند، و دقیقاً به همین دلیل رده‌بندی لازم دارید.
27.9جداسازی‌های اوراکلی
فناوری برهان اصلی حوزه، و بیش از همه بداستفاده. اوراکل O تابعی جعبه‌سیاه است؛ جداسازی نسبت به O نشان می‌دهد با O مجانی‌داده‌شده، ماشین‌کوانتومی کاری را با پرسش کمتری از کلاسیکی حل می‌کند. جداسازی اوراکلی سایمون (۱۹۹۴) مستقیماً شور را الهام بخشید. اما جداسازی نسبت به اوراکل خودِ کلاس‌ها را جدا نمی‌کند — اوراکل شاید ساختار را در خود بپخت باشد. قضیهٔ BBBV اوراکل‌هایی می‌سازد که در آن‌ها درجه‌دوی گروور بهینه است؛ اوراکل‌های بازگشتی (آرونسون–کوپربرگ) QMA را از QCMA در هر دو جهت جدا می‌کنند. قاعده: نتایج اوراکلی شاهدِ *تکنیک*اند، نه جهان. وقتی مقاله‌ای جداسازی اوراکلی را تیتر می‌کند، قدردان باشید، بعد بپرسید با اوراکلِ تجسدیافته چه می‌شود.
27.10آنچه محاسبات کوانتومی اثبات نمی‌کند
نتایج منفی به‌اندازهٔ مثبت‌ها تکیه‌گاه‌اند. یک: BQP ⊆ PSPACE — رایانه‌های کوانتومی همهٔ محاسبات کلاسیکی را نمی‌زنند، فقط محاسبات کلاسیکیِ کارا را. دو: سرعت شناخته‌شده‌ای برای NP-کامل‌ها نیست؛ درجه‌دوی گروور سقف جست‌وجوی بی‌ساختار است و BBBV می‌گوید هیچ ترفند کوانتومی از آن عبور نمی‌کند. سه: عدمronوشت «همهٔ پاسخ‌ها را موازی امتحان کن و بخوان» را ممنوع می‌کند — سوءفهمِ زیربنایی نیمی از اغراق‌ها. چهار: P در برابر NP و P در برابر BQP بازند؛ الگوریتم شور اشاره‌گر است، نه برهان. پنج: سرعت‌های نمونه‌گیری بر فرض‌های پیچیدگی اثبات‌نشده تکیه دارند. تسلط بر این پنج، دفاع شما در برابر اغراق و واکنش‌اضافی به آن است.