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

نظریه پیچیدگی کوانتومی (به انگلیسی: 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‌ تعلق ندارد. مسئله تجزیه عددها به عوامل اول (حل شده با استفاده از الگوریتم شور) ^[۳]

جستارهای وابسته ویرایش

منابع ویرایش

↑ Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 166-168. ISBN 978-0-262-03925-3. Retrieved 2023-01-14.
↑ Aaronson, Scott (2010-06-05). BQP and the polynomial hierarchy. New York, NY, USA: ACM. doi:10.1145/1806689.1806711.
↑ Shor, Peter W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). 26 (5): 1484–1509. doi:10.1137/s0097539795293172. ISSN 0097-5397.

[Bernhardt_2019_p._7-1] Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 166-168. ISBN 978-0-262-03925-3. Retrieved 2023-01-14.

[Aaronson_2010_p.-2] Aaronson, Scott (2010-06-05). BQP and the polynomial hierarchy. New York, NY, USA: ACM. doi:10.1145/1806689.1806711.

[Shor_1997_pp._1484–1509-3] Shor, Peter W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). 26 (5): 1484–1509. doi:10.1137/s0097539795293172. ISSN 0097-5397.

[۱]

[۲]

[۳]