بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
شبیه سازی الگوریتم کوانتومی شور با استفاده از تبدیل فوریه کوانتومی
خلاصه:
در این مقاله به بررسی شبیه سازی الگوریتم شور با استفاده از کامپیوترهای کوانتومی می پردازیم، این الگوریتم نشان دهندهی افزایش نمایی سرعت در محاسبات کلاسیک می باشد. همچنین شور نشان داد که کامپیوترهای کوانتومی قادر به محاسبه عوامل اعداد خیلی بزرگ در یک زمان کوتاه هستند. شبیه سازی کوانتومی بوسیله الگوریتم شور در واقع یکی از کاربردهای کامپییوترهای کوانتومی برای حل مسایلی که بیش از حد برای کامپیوترهای کلاسیک مشکل هستند، استفاده میشود. شبیه سازی این الگوریتم را با استفاده از نرم افزار Matlab انجام دادهایم و در ادامه مراحل پیاده سازی آن را بیان می کنیم. این الگوریتم از خاصیت بر هم نهی کوانتومی و توازی کوانتومی و تبدیل فوریه کوانتومی (QFT) استفاده می کند. در پایان شبیه سازی با استفاده از تبدیل فوریه کوانتومی، عوامل اول را بدست می آوریم.
کلمات کلیدی: کامپیوترهای کوانتومی، کیوبیت، الگوریتم شور، تبدیل فوریه کوانتومی
۱ - مقدمه
شبیه سازی کوانتومی بوسیله الگوریتم شور یکی از کاربردهای مهم کامپیوترهای کوانتومی است. شبیه سازی کوانتومی در حقیقت اولین کاربرد پیشنهاد شده برای کامپیوترهای کوانتومی است. در سال ۱۹۸۲ فایمن متذکر شد شبیه سازی دینامیک کوانتومی در یک کامپیوتر کوانتومی ذاتا سخت است. بنابراین ایده ساخت "شبیه سازی کوانتومی جهانی" را داد. از چنین دستگاهی که او ساخت می توان به عنوان کامپیوتر کوانتومی که قادر به شبیه سازی رفتار هر سیستم کوانتومی است، اشاره کرد. شور ثابت کرد، مساله تجزیه به عوامل اول یک عدد و مسئلهی معروف لگاریتم گسسته بطور کارآمد در کامپیوترهای کوانتومی قابل حل است. نتایج شور [1,2] نشان دهندهی برتری کامپیوترهای کوانتومی بر کامپیوترهای کلاسیک است. نکتهی قابل توجه آن است که تکنولوژی کوانتومی نه تنها میتواند با افزایش تعداد بیتهای یک چیپ سیلیکونی سرعت ریز پردازهها را افزایش دهد، بلکه روش جدیدی برای محاسبات با استفاده از الگوریتمهایی که اساس آنها مکانیک کوانتومی است، ارائه میدهد.
۲- شبیه سازی محاسبات کوانتومی
روی کامپیوترهای کلاسیک تعدادی از محیطهای برنامه نویسی برای محاسبات کوانتومی اخیرا پیشنهاد شده اند، که عمدتا در شبیه سازی کامپیوترهای کوانتومی استفاده میشوند. با این حال شبیه سازی کوانتومی در حال حاضر بر اساس نرم افزار جبر خطی، نیاز به یک حافظه چند جمله ای و تعدادی کیوبیت محدود شده در حافظه RAM دارد. چنین شبیه سازی، که تکنیکهای جبر خطی را پشتیبانی می کند فوق العاده مفید است. گیت های کوانتومی به عنوان ماتریس نمایش داده می شوند و اعمال را به حالتهای کوانتومی با استفاده از ماتریس ضرب برداری تبدیل می کند. روش شبیه سازی مستقیم از عملیات جبر خطی استفاده می کند و می توانند به سرعت با ابزارهای تعاملی نظیر Matlab و Octave پیاده سازی شود. مشکل اصلی این روش این است که حالت های کوانتومی، ماتریس و گیت باید به طور صریح ذخیره شوند و در نتیجه نیاز به حافظه نمایی دارند. به عنوان مثال برای ۲۰ کیوبیت مستلزم x220 220 ماتریس مختلط است، که فراتر از حافظه موجود در کامپیوترهای امروزی است. بهینه سازی هوشمندانه در جبر خطی شامل اجرای گیتهای 2x2 در بردارهای حالت بدون محاسبات پیچیده 220 x 220 ماتریس است. یکی از تکنیکهای شبیه سازی سطح بالا نظیر Matlab ، شامل فشرده سازی اطلاعات است که انجام ماتریس ضرب برداری بدون Decompressing دشوار است.
٣- کیوبیت
کامپیوترهای کوانتومی نسبت به کامپیوترهای کلاسیک از بیت، یک سلول دو حالته و کامپیوترهای کوانتومی از کیوبیت [3] با عنوان حافظهی اطلاعاتی استفاده میکنند، که یک کیوبیت میتواند همزمان هم وا باشد. یک بیت کوانتومی، یا کیوبیت، عبارت است از یک ذره دو ترازه که یک حالت به آن منتسب میشود، که این حالت بوسیله یک بردار یکه در فضای برداری دو بعدی در میدان اعداد مختلط بیان میگردد. در حقیقت حاصل بر هم نهی دو حالت منطقی ۰ و ۱ است. یک کامپیوتر کوانتومی از مزیت موجود در مکانیک کوانتومی یعنی بر هم نهی استفاده میکند. که این قابلیت اجرای عملیات منطقی بر روی بر هم نهی کوانتوم مکانیکی اعداد به زبان ریاضی باعث میشود:
به این ترتیب، اگر تعداد کیوبیتهای حافظهی کوانتومی را زیاد کنیم، ظرفیت ذخیره اطلاعات روی آن زیاد میشود، یعنی n کیوبیت، "2 عدد را میتوانند همزمان ذخیره کنند، و همزمان روی تمام آنها عملیات محاسباتی به صورت موازی انجام داد. اما یک کامپیوتر کلاسیک برای عمل مشابه بايد 27 بار یک مرحلهی محاسباتی را برای ورودیهای مختلف تکرار کند. پس کامپیوترهای کوانتومی از نظر سرعت و میزان حافظهی لازم بر کامپیوترهای کلاسیک ارجحیت دارند. از مواردی که کامپیوترهای کوانتومی را از کلاسیک متمایز می کند، د رهم تنیدگی کوانتومی است. و پدیدهی دیگری که باعث تمایز دنیای کوانتومی و کلاسیک میشود، "تکثیر ناپذیری بیتهای کوانتومی" است. مسألهی دیگر در محاسبات کوانتومی مهم است، "تصحیح خطای کوانتومی است ". [4] که این تئوری، انواع مشخصی از خطاها را آشکار می کند و قادر به بازسازی حالت کوانتومی بدون خطا میباشد.
۴- توازی کوانتومی
توازی کوانتومی به کامپیوترهای کوانتومی اجازه میدهد تا به طور همزمان به محاسبه ی تابع (f(x به ازای مقادیر مختلف X بپردازد. فرض کنید تبدیل یکانی ,U ای داریم که دو کیوبیت را به کیوبیت دیگر تبدیل می کند:
,U یک تبدیل خطی است، روی تمام بردارهای پایه موجود در ورودی بر هم نهاده به صورت همزمان عمل کرده و بر هم نهی از نتایج تولید می کند، از این روش، محاسبه (f(x برای N مقدار از X در بکارگیری را امکان پذیر است. این خاصیت، " توازی کوانتومی" ، نامیده میشود. این خاصیت وجه تمایز یک کامپیوتر کوانتومی و کلاسیک را میتواند انجام دهد، که در کامپیوتر کلاسیکی باید دو بار f را بکار برد تا یک تابع متوازن را از یک تابع ثابت تمیز دهد، اما کامپیوترهای کوانتومی این کار را در یک مرحله انجام میدهد. اگر تابع متوازن باشد همواره (+I ، و اگر ثابت باشد (-) خواهد شد، اگر باشد ، (f(x ثابت و اگر باشد، متوازن خواهد شد. توجه کنید که N کیوبیت قادرند همزمان با 22 حالت کار کند، "توازن کوانتومی" با استفاده از خاصیت نمایی فضای محاسباتی در یک فضای کوانتومی، از توازن فضا- زمانی برتری میجوید.
۵- الگوریتم شور
محاسبات کوانتومی، و عده افزایش توان محاسباتی را نوید می دهد . پیتر شور [5] توانست از توازن وسیع موجود در کامپیوترهای کوانتومی به منظور عامل یابی اعداد با استفاده از یک روش در نظریه اعداد استفاده کند. الگوریتم عملا بسیار ساده بود . یک عدد برای عامل یابی دریافت می شود (N). مقداری کمتر از N برای a انتخاب می شود این مقدار باید نسبت به N نیز اول باشد، اما با فرض اینکه N حاصلضرب دو عدد اول است متعاقبا محل انطباق را با شماره های متوالی شروع شده از 1 بارگذاری می کنیم و هر یک از آن مقادیر را از طریق تابع می دهیم .تمام این عملیات با جادوی محاسبات کوانتومی می تواند در واحد زمان انجام شود. یک الگوی تکرار در نتایج تابع وجود دارد و دوره این تکرار را باید پیدا کرد . خوشبختانه این کار را میتوان به سرعت روی کامپیوترهای کوانتومی با یک تغییر شکل تبدیل فوریه کوانتومی (QFT) انجام داد. دوره را با r نشان می دهیم. سپس مقادیر و محاسبه میشوند (تابع gcd بزرگترین مقسوم علیه مشترک میباشد). مقدار عمومی N را عامل یابی می کنیم. در این مورد N برابر با 143 است. سپس مقداری برای a انتخاب می شود که نسبت به N اول و از آن کوچکتر باشد، پس a برابر 21 می شود . به این ترتیب تابع به شکل زیر خواهد شد:
هر مقدار متوالی که از 1 شروع شده و به بزرگترین عددی که کامپیوتر کوانتومی اجازه می دهد، در این تابع قرار داده خواهد شد. جهت کوتاه نگه داشتن مثال، فرض می کنیم که کامپیوتر کوانتومی دارای سه کیوبیت است، لذا آرایه انطباق می تواند 8 مقدار را نگهداری کند.
در اینجا دوره را می توان به سادگی محاسبه کرد: ۳ برابر 4 است. با در اختیار داشتن این اطلاعات، دو عبارت و باید حداقل یکی از عامل ها را تولید کنند چون لذا هر دو عامل تولید می شوند.
۶-شبیه سازی الگوریتم کوانتومی شور :
شبیه سازی این الگوریتم با استفاده از نرم افزار صورت گرفته است که در ادامه مراحل پیاده سازی آن آمده است. در این الگوریتمها از خاصیت برهم نهی کوانتومی استفاده میشود که اجازه می دهد n کیوبیت در یک لحظه تمام "2 حالت ممکن را داشته باشند. نتیجهی جالبی که شور بدان دست یافت این بود که یک کامپیوتر کوانتومی میتواند در یک زمان چند جمله ای عمل تجزیه را انجام دهد. مسالهی تجزیه به عوامل اول از دیدگاه تئوری پیچیدگی محاسبه، مسالهی جالبی است و از اهمیت عملی خاصی برخوردار است، زیرا دشواری مساله ی تجزیه، پایههای طرحهایی برای رمزنگاری کلید عمومی است. الگوریتم شور جهت پیدا کردن عوامل اول عدد صحيح N میباشد. شور نشان داد که کامپیوترهای کوانتومی قادر به محاسبه عوامل اعدد خیلی بزرگ در یک زمان کوتاه هستند. این الگوریتم وابسته به توازی کوانتومی و تبدیل فوریه کوانتومی میباشد. مدارات کوانتومی برای این الگوریتم طراحی شده که جهت انتخاب یک عدد N بصورت تصادفی بکار رفته در رابطه میباشد. با انتخاب عدد صحیح فرد N مراحل پیاده سازی الگوریتم شور جهت پیدا کردن عوامل اول آن به شرح زیر میباشد. برای درک بیشتر از شبیه سازی الگوریتم طراحی شده، از یک مثال عددی استفاده می کنیم بطور مثال با انتخاب 15=N ، مراحل شبيه سازی الگوریتم شور را شرح میدهیم.
1. محاسبه رجیسترهای ورودی و خروجی جهت محاسبه این رجیترها ابتدا باید عدد صحیح Q را انتخاب کرده که توانی از ۲ بوده و باشد برای مثال 256=Q. سپس انتخاب عدد صحیح a که کوچکتر از N بوده و نسبت به آن اول باشد برای مثال 7=a. ایجاد دو رجیستر کوانتومی بنام رجیستر ورودی و رجیستر خروجی. رجیستر ورودی باید تعداد کافی کیوبیت جهت نگهداری اعدادی به بزرگی باشد بنابراین نیاز به ۸ کیوبیت داریم و رجیستر خروجی باید تعداد کافی کیوبیت جهت نگهداری اعدادی به بزرگی -N 14=1 باشد بنابراین نیاز به ۴ کیوبیت داریم.
سپس بارگذاری رجیسترهای ورودی با تمام مقادیر صحیح 0 تا 1-Q و بارگذاری رجیستر خروجی با مقادیر 0. مجموع حالتهای مقادیر اولیه رجیسترهای کوانتومی سیستم در این نقطه برابر :
اجرای تابع mod N "» برای هر عدد ذخیره شده در رجیستر ورودی و ذخیره سازی نتایج آن در رجیستر خروجی بدلیل توازی کوانتومی این مرحله در یک گام اجرا میشود. کامپیوتر کوانتومی فقط تابع mod N (ه را محاسبه میکند که (3)، سوپر پوزیشن حالتهای بدست آمده در مرحله چهارم میباشد. این مرحله روی کامپیوتر کوانتومی اجرا میشود. وضعیت رجیسترهای کوانتومی در این نقطه :
بدست آوردن رجیستر خروجی با ملاحظه مقادیر K . در اینطرف با تاثیر رجیستر ورودی روی مقادیر بین در معادله
جدول (1): مقادیر رجیسترهای خروجی
