نظریه پیچیدگی کوانتومی (به انگلیسی: Quantum complexity theory) قسمتی از نظریه پیچیدگی محاسباتی در علوم نظری کامپیوتر است که کلاسهای پیچیدگی محاسباتی را با استفاده از کامپیوتر کوانتومی و نظریه اطلاعات کوانتومی که هر دو مدلهای محاسباتی بر مبنای مکانیک کوانتومی هستند مدل سازی میکند. نظریه پیچیدگی کوانتومی درجه سختی مسائل را با توجه به کلاسهای پیچیدگی و روابط بین کلاسهای پیچیدگی کوانتومی و کلاسیک بررسی میکند.[۱]
یک کلاس پیچیدگی مجموعهای از مسائل است که میتواند تحت یک مدل محاسباتی و با توجه به محدودیت منابع حل شود. به عنوان مثال کلاس P مجموعهٔ تمام مسائل حلپذیر توسط یک ماشین تورینگ در زمان چندجملهای است. بهطور مشابه کلاس پیچیدگی کوانتومی را با استفاده از یک مدل محاسباتی کوانتومی مثلاً کامپیوتر کوانتومی یا ماشین تورینگ کوانتومی تعریف میکنیم. بنابراین کلاس پیچیدگی BQP به عنوان مجموعه مسائلی که توسط یک کامپیوتر کوانتومی و در زمان چندجملهای با سقف مشخصی از خطا میتوان حل نمود تعریف میشوند.
دو مورد از مهمترین کلاسهای پیچیدگی BQP و QMA هستند که با سقف خطا مشابه کلاسهایP و NP هستند. یکی از اهداف نظریه پیچیدگی محاسبات کوانتومی این است که روابط بین این کلاسها را با کلاسهای پیچیدگی کلاسیک مانند P، NP ،PP، PSPACE و غیره پیدا کند.[۲]
کلاس پیچیدگی | معیارها | مثالها |
---|---|---|
مسائلی که توسط یک کامپیوتر کلاسیک و در زمان چندجملهای میتوان حل نمود. | مسئله یافتن کوتاهترین مسیر | |
Quantum polynomial time QP |
مسائلی که توسط یک کامپیوتر کوانتومی و در زمان چندجملهای میتوان حل نمود. | مسئله دویچ-جوژا به کلاس QP تعلق دارد ولی به کلاس P تعلق ندارد. الگوریتم سایمون به کلاس QP تعلق ندارد. |
Bounded-error probabilistic polynomial time |
مسائلی که توسط یک کامپیوتر کلاسیک و در زمان چندجملهای با سقف مشخصی از خطا میتوان حل نمود. | مسئله دویچ-جوژا به کلاس BPP تعلق دارد. |
Bounded-error quantum polynomial time |
مسائلی که توسط یک کامپیوتر کوانتومی و در زمان چندجملهای با سقف مشخصی از خطا میتوان حل نمود. | الگوریتم سایمون به کلاس BQP تعلق دارد. ولی به کلاس BPP تعلق ندارد. مسئله تجزیه عددها به عوامل اول (حل شده با استفاده از الگوریتم شور) [۳] |