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

دهه‌های پایانی قرن بیستم میلادی شاهد تلاش دانشمندان و پژوهشگران برای ادغام دو نظریه انقلابی و موثر قرن، یعنی نظریه اطلاع و مکانیک کوانتومی بوده است و ایجاد دانش پردازش اطلاعات کوانتومی شاهدی بر موفقیت آنان است. دانش پردازش اطلاعات کوانتومی شامل رشته‌های محاسبات کوانتومی، رمزنگاری کوانتومی، انتقال اطلاعات کوانتومی، بازی‌های کوانتومی و مانند این‌ها است و از دید قواعد مکانیک کوانتومی به اطلاعات و محاسبات می‌نگرد، دیدی که برای همیشه رابطه بین اطلاعات، محاسبات و فیزیک را با ابداع الگوریتم‌ها، قراردادهای ارتباطاتی غیر معمول و بدیع و مانند آن‌ها تغییر داد.

نظریه اطلاع، به عنوان انتزاعی از جهان فیزیکی، امکان بحث و بررسی در مورد بهینگی محاسبات، صحت عملکرد سامانه‌های اطلاعاتی و مانند این‌ها را در چارچوب علم ریاضیات بدون در نظر گرفتن جزئیات فیزیکی و نحوه پیاده‌سازی ابزارهای محاسباتی و مخابراتی فراهم می‌کند. چنین انتزاعی از جهان فیزیکی به قدری منطقی و پرکاربرد به نظر می‌رسد که برخی پیش‌فرض‌های آن از جمله وابستگی آن به قواعد مکانیک کلاسیک از یاد برده شده‌اند. تا به امروز، نظریه اطلاع، مانند ماشین تورینگ، خود را به تبعیت از قواعد مکانیک کلاسیک ملزم می‌دانسته است. اما با ورود مکانیک کوانتومی به دنیای محاسبات و اطلاعات، وضعیت متفاوت شده است.

مکانیک کوانتومی در توسعه و ابداع ابزارهای محاسباتی و مخابراتی دقیق‌تر، قوی‌تر، سریعتر و در عین حال، کوچکتر نقشی بی‌بدیل را ایفا کرده است. اما تا ابداع دانش پردازش اطلاعات کوانتومی، نقش آن صرفا محدود به قلمرو پیاده‌سازی ابزارهای کلاسیک محاسبات و مخابرات بوده است و هیچ تاثیری در نحوه مطالعه و یا تدریس نظریه محاسبات و نظریه اطلاع نداشته است.

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

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

این پایان نامه به راهنمایی آقای دکتر محمد رضا هوشمند اصل (علوم کامپیوتر - محاسبات کوانتومی) و تحت مشاوره آقای دکتر سید ابوالفضل شاهزاده فاضلی (علوم کامپیوتر - جبر خطی عددی) انجام شده و در تاریخ 29 شهریور ماه 1391 با نمره 19.5 با داوری آقای دکتر محمد فرشی (علوم کامپیوتر - هندسه محاسباتی) و آقای دکتر محمد کاظم توسلی (فیزیک - اپتیک کوانتومی)، دفاع شده است. اسلایدهای جلسه دفاع از اینجا قابل دریافت هستند.