نظریه پیچیدگی کوانتومی

نظریه پیچیدگی کوانتومی قسمتی از نظریه پیچیدگی محاسباتی در علوم نظری کامپیوتر است که کلاس‌های پیچیدگی محاسباتی را با استفاده از کامپیوتر کوانتومی و نظریه اطلاعات کوانتومی که هر دو مدل‌های محاسباتی بر مبنای مکانیک کوانتومی هستند مدل سازی می‌کند. نظریه پیچیدگی کوانتومی درجه سختی مسائل را با توجه به کلاس‌های پیچیدگی و روابط بین کلاس‌های پیچیدگی کوانتومی و کلاسیک بررسی می‌کند.

یک کلاس پیچیدگی مجموعه‌ای از مسائل است که می‌تواند تحت یک مدل محاسباتی و با توجه به محدودیت منابع حل شود. به عنوان مثال کلاس P مجموعهٔ تمام مسائل حل‌پذیر توسط یک ماشین تورینگ در زمان چندجمله‌ای است. به‌طور مشابه کلاس پیچیدگی کوانتومی را با استفاده از یک مدل محاسباتی کوانتومی مثلاً کامپیوتر کوانتومی یا ماشین تورینگ کوانتومی تعریف می‌کنیم. بنابراین کلاس پیچیدگی BQP به عنوان مجموعه مسائلی که توسط یک کامپیوتر کوانتومی و در زمان چندجمله‌ای با سقف مشخصی از خطا می‌توان حل نمود تعریف می‌شوند.

دو مورد از مهمترین کلاس‌های پیچیدگی BQP و QMA هستند که با سقف خطا مشابه کلاس‌هایP و NP هستند. یکی از اهداف نظریه پیچیدگی محاسبات کوانتومی این است که روابط بین این کلاس‌ها را با کلاس‌های پیچیدگی کلاسیک مانند P، NP ،PP، PSPACE و غیره پیدا کند.