سال انتشار: ۱۳۹۱

محل انتشار: دومین کنفرانس ملی مهندسی نرم افزار

تعداد صفحات: ۷

نویسنده(ها):

علی شکیبا – آزمایشگاه پردازش اطلاع کوانتومی و رمزنگاری، دانشگاه یزد، ایران
محمدرضا هوشمند اصل، – دانشکده ریاضی، دانشگاه یزد، ایران

چکیده:

برای بررسی محاسبه پذیری و پیچیدگی محاسباتی کوانتومی، نیاز به ارائه مدلی از رایانش کوانتومی است که می توان به مدل های ماشین تورینگ کوانتومی، مدار کوانتومی و ماشین تورینگ کوانتومی تعمیم یافته اشاره کرد. در مقایسهمدل های تورینگ کوانتومی و تورینگ کوانتومی تعمیم یافته، مشاهده می شود که ماشین تورینگ کوانتومی نمی تواند برای مسائل-NP کامل در مدل جعبه سیاه نسبت به مدل های کلاسیک محاسباتی، تسریعی در حد نمایی ایجادکند در صورتی که یک ماشین تورینگ کوانتومی تعمیم یافته غیرخطی، چنین امکانی را فراهم می آورد. از طرف دیگر، با توجه به اینکه ماشین تورینگکوانتومی تعمیم یافته دارای رفتار غیر خطی است و مکانیک کوانتومی تا به امروز در آزمایش های متعدد با دقت بالا، رفتار خطی از خود نشان داده است می توان نتیجه گرفت که حل مسائلNP کامل در زمان چندجمله ای در مدل جعبه سیاه، نیاز به برخی اصول فیزیکی غیر متعارف دارد و از این رو، باید از ساختار این مسائل برای حل آن ها پرداخت. در این مقاله توان محاسباتی ماشین تورینگ کوانتومی و ماشین تورینگ کوانتومی تعمیم یافته مورد بررسی قرارگرفته و با یکدیگر در مدل جعبه سیاه برای حل مسائل ردهNP کامل مقایسه شده اند