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

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

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

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

 مروری بر کلاس های پیچیدگی کوانتومی 
+کلاس پیچیدگیمعیارهامثالهاPolynomial time Pمسائلی که توسط یک کامپیوتر کلاسیک و در زمان چندجمله‌ای می‌توان حل نمود.مسئله یافتن کوتاه‌ترین مسیرQuantum polynomial time QP or Exact quantum polynomial time EQPمسائلی که توسط یک کامپیوتر کوانتومی و در زمان چندجمله‌ای می‌توان حل نمود.مسئله دویچ-جوژا به کلاس QP تعلق دارد ولی به کلاس P تعلق ندارد.
الگوریتم سایمون به کلاس QP تعلق ندارد. Bounded-error probabilistic polynomial time BPPمسائلی که توسط یک کامپیوتر کلاسیک و در زمان چندجمله‌ای با سقف مشخصی از خطا می‌توان حل نمود.مسئله دویچ-جوژا به کلاس BPP تعلق دارد.Bounded-error quantum polynomial time  BQPمسائلی که توسط یک کامپیوتر کوانتومی و در زمان چندجمله‌ای با سقف مشخصی از خطا می‌توان حل نمود.الگوریتم سایمون به کلاس BQP تعلق دارد. ولی به کلاس BPP‌ تعلق ندارد.
مسئله تجزیه عددها به عوامل اول (حل شده با استفاده از الگوریتم شور) 

 جستارهای وابسته 
 نظریه پیچیدگی محاسباتی
 برتری کوانتومی

 منابع 


رده:علوم اطلاعات کوانتومی
رده:علوم نظری رایانه
رده:نظریه پیچیدگی محاسباتی