آشنایی با کامپیوترهای کوانتومی (قسمت سوم)
کامپیوترهای کوانتومی فقط الگوریتم های احتمالی را می توانند اجرا کنند. در نتیجه رده  مسائل BQP در کامپیوترهای کوانتومی معادل با رده مسائل BPP در کامپیوترهای کلاسیک است.
  • مهرداد تاجدینی
  • 1395/5/16
  • 0
  • 635

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

مسائلی که به صورت کارا توسط کامپیوترهای کوانتومی قابل حل هستند در رده BQP قرار دارند.
BQP سرنام  "Bounded error, Quantum, Polynomial time" است. کامپیوترهای کوانتومی فقط الگوریتم های احتمالی را می توانند اجرا کنند. در نتیجه رده  مسائل BQP در کامپیوترهای کوانتومی معادل با رده مسائل BPP در کامپیوترهای کلاسیک است.

BQP

در صورتی می گوییم یک کامپیوتر کوانتومی می تواند یک مسئله را حل کند که برای هر نمونه (Instance) از آن مسئله، جواب صحیح را با احتمال بالا به ما بدهد. اگر یک کامپیوتر کوانتومی بتواند این جواب را با یک پیچیدگی زمانی چندجمله ای (polynomial time) بدست آورد، آنگاه این مسئله در رده BQP قرار دارد.
BQP و NP کامل (NP-Complete) از هم مجزا هستند. همچنین مسائل موجود در P به طور کامل در BPQ قرار دارند. (P زیر مجموعه  محض BQP است). هم مسئله تجزیه اعداد و هم مسئله لگاریتم های پیوسته (discrete log) در BQP قرار دارند (پس به طور کارآمد توسط کامپیوترهای کوانتومی قابل حل هستند). هر دو مسئله ذکر شده جز مسائل NP هستند و خارج از BPP در نظر گرفته می شوند و درنتیجه خارج از P. البته این دو مسئله NP کامل نیستند.

یک تصور غلط وجود دارد که کامپیوترهای کوانتومی مسائل NP کامل را می توانند در یک زمان چندجمله ای حل کنند، ولی در حالت کلی چنین چیزی صحیح نیست. همچنین، اگر چه این کامپیوترها سریعتر از کامپیوترهای کلاسیک هستند ولی این کامپیوتر ها همچنان نمی توانند مسائلی که برای کامپیوترهای کلاسیک لاینحل است را حل کنند.

یک ماشین تورینگ می تواند کامپیوترهای کوانتومی را شبیه سازی کند. بنابراین چنین کامپیوتر کوانتومی ای هرگز نمی تواند یک مسئله که تصمیم پذیر نیست (undecidable problem) را حل کند. کامپیوتر های کوانتومی نظریه چرچ-تورینگ را نقض نمی کنند.
این طور به نظر می رسد که تئوری های گرانش کوانتومی (quantum gravity) مانند تئوری M و یا چرخه گرانش کوانتومی (loop quantum gravity) می توانند به ما اجازه دهند که حتئ کامپیوترهای سریعتری نیز بسازیم.

منبع: سایت ویکی پدیا
مترجم: مهرداد تاجدینی 

مهرداد تاجدینی

مهرداد تاجدینی هستم. فوق لیسانس رشته علوم کامپیوتر و در شرکت رهیاب رایانه گستر به عنوان برنامه نویس مشغول به کار می باشم.

نظرات0
برای ارسال دیدگاه وارد حساب کاربری خود شوید.

ورود به حساب کاربریایجاد حساب کاربری