پاورپوینت الگوریتم های بکار رفته در محاسبات کوانتومی و دستاوردهای آن

بخشی از پاورپوینت

اسلاید 1 :

الگوریتم های بکار رفته در محاسبات کوانتومی و دستاوردهای آن

اسلاید 2 :

فهرست
مقدمه
الگوریتم های کوانتومی
انواع الگوریتم های کوانتومی
معرفی چندین الگوریتم پایه
الگوریتم های تکاملی
الگوریتم ژنتیک کوانتومی
خلاصه

اسلاید 3 :

مقدمه
هدف محاسبات کوانتومی یافتن روش هایی برای طراحی مجدد ادوات شناخته شده ی محاسبات ( مانند گیت ها و ترانزیستورها) به گونه ای است که بتوانند تحت اثرات کوانتومی ، که در محدوده ی ابعاد نانومتری و کوچکتر بروز می کنند کار کنند.
ورود به دنیای محاسبات کوانتومی نیازمند دو پیش زمینه مهم است، نخست باید اصول اساسی و برخی تعابیر مهم مکانیک کوانتومی را به طور دقیق بررسی کرد سپس مفهوم اطلاعات در فیزیک نیز، چه به صورت کلاسیک و چه در معنای جدیدکوانتومی آن باید درک شود .
موارد مهم در محاسبات کوانتومی: درهم تافتگی entanglement، کیوبیت ها، واهمدوسیDecoherence دشمن محاسبات کوانتومی

اسلاید 4 :

الگوریتم های کوانتومی
هرگاه ما الگوریتم های کلاسیکی خودمان رابر روی یک کامپیوتر کوانتومی مورداستفاده قراردهیم، به سادگی محاسبات را به طریقه مشابه با یک کامپیوتر کلاسیک انجام و اجرا خواهدکرد.

به منظور نشان دادن برتری آن و بهره برداری از پدیده توازی کوانتومی ما نیاز داریم تا الگوریتم ها ی کوانتومی را پایه گذاری کنیم.

اسلاید 5 :

جعبه سیاه و توابع یک بیتی
جعبه سیاه Oracle
هدف تعیین کامل تابع نیست، بلکه یک خاصیت مشخص از تابع هم یافته شود کافی است.
تابع ثابت: خروجی همواره ثابت (f1,f4)
تابع متوازن: خروجی به ازای نیمی از ورودی ها 0 و نیمی دیگر 1 (f2,f3)
انواع توابع تک بیتی

می خواهیم ببینیم با چند بار فراخوانی، تابع f تعیین می گردد؟
با دو بار فراخوانی
یک بار با ورودی 0 و یک بار با ورودی 1

اسلاید 6 :

توازی کوانتومی
استفاده از توازی کوانتومی در الگوریتم های کوانتومی

اگر تابع f ثابت باشد

اگر تابع f متوازن باشد

اسلاید 7 :

انواع الگوریتم های کوانتومی
الگوریتم کوانتومی برای مسئله دویچ

الگوریتم کوانتومی برای مسئله دویچ-جوزا

الگوریتم کوانتومی برای مسئله برنشتاین-وزیرانی

الگوریتم کوانتومی برای مسئله سیمن

اسلاید 8 :

الگوریتم کوانتومی برای مسئله دویچ
بردار حالت در مراحل مختلف:
اگر f تابع ثابت باشد
اگر f تابع متوازن باشد

با یک فراخوانی مسئله حل می شود:
خروجی برای توابع ثابت 0 و برای توابع متوازن 1

اسلاید 9 :

الگوریتم کوانتومی برای مسئله دویچ-جوزا
مسئله دویچ جویزا تعمیمی از مسئله دویچ است
از ما خواسته ثابت یا متوازن بودن مسئله را تعیین کنیم:
تعداد توابع ثابت 2 تا
تعداد توابع متوازن
در الگوریتم کلاسیک باید به تعداد 2 +1 بار تابع f فراخوانی شود.
در الگوریتم کوانتومی تنها با دو بار فراخوانی نوع تابع تعیین می گردد.
n-1

اسلاید 10 :

الگوریتم کوانتومی برای مسئله دویچ-جوزا
مدار بکار رفته در الگوریتم کوانتومی برای مسئله دویچ-جوزا

بردار حالت در مراحل مختلف
اگر f تابع ثابت
اگر f تابع متوازن

اسلاید 11 :

الگوریتم کوانتومی برای مسئله برنشتاین-وزیرانی
مسئله: تابع f به صورت زیر و a یک عدد n بیتی است. با چند بار فراخوانی a تعیین می گردد؟

اسلاید 12 :

الگوریتم کوانتومی برای مسئله سیمن
مسئله: تابع f به صورت زیر می باشد، با چند بار فراخوانی a تعیین می گردد؟
.

اسلاید 13 :

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

الگوریتم های مهم تغییر دهنده کلاس حل مسئله:
الگوریتم شور Shor’s Algorithm
هدف این الگوریتم شکستن یا تجزیه یک عدد بزرگ به عامل های اول آن است

الگوریتم گراور Graver’s Algorithm
این الگوریتم می تواند عملیات مرتب کردن داده ها راازمیان پایگاه های اطلاعاتی بزرگ ونامرتب انجام دهد.

اسلاید 14 :

الگوریتم های تکاملی
در راستای بهبود عملکرد الگوریتم، رویکردهای جدیدی به الگوریتم اضافه شده است که در یک نگاه کلی می توان آنها در قالب بهبود شناسایی و بهره برداری به عنوان دو رویکرد بسیار مهم در الگوریتم­های تکاملی تقسیم بندی کرد.

ساختار الگوریتم تکاملی کوانتوم و عملگرهای استفاده شده در آن از یک طرف و رویه های اضافه شده به آن به گونه ای است که توازن بسیار خوبی را بین این دو رویکرد فراهم می آورد

اسلاید 15 :

الگوریتم تکاملی کوانتوم بهبود یافته(IQEA)
الگوریتم کوانتوم را با استفاده از رویکردهای زیر بهبود داده می شود:
استفاده از رویکرد اندازه گیری چندگانه در تبدیل حالت کوانتومی به باینری.
استفاده از گیت چرخشی کوانتومی دیگری علاوه بر عملگر معمول که برای بروز رسانی مقادیر کیوبیتها در هر نسل بکار برده می شود.
استفاده از رویکرد کاهش حدود متغیرها بر اساس بهترین جوابهای بدست آمده در هر نسل.
ورود افراد با مقادیر کوانتومی جدید، طبق شرایط مساله
الگوریتم های تکاملی اصولاً روش های بهینه سازی و جستجوی تصادفی بر اساس اصول تکامل بیولوژیکی طبیعت هستند

اسلاید 16 :

الگوریتم تکاملی کوانتوم بهبود یافته(IQEA)
در مقایسه با روش های بهینه سازی سنتی، الگوریتم های تکاملی نیرومندتر و در عمل جامع نگرترند
در هر مرحله از الگوریتم های تکاملی، مجموعه جدیدی از جوابهای بروز رسانی شده وارد محدوده مشخصی از فضای جواب می شوند و بعد از اندازه گیری ها و محاسبات تابع برازندگی توسط عملگرهای متعدد،اعضای جدید برای نسل بعد را فراهم می کنند
این روند به گونه ای طراحی می شود که افراد جمعیت در نسل جدید از مقادیر نسل جاری بدتر نباشند و حتی الامکان بهتر بوده و باعث هدایت اعضای جمعیت به سمت ناحیه جواب بهینه شوند
ساختار الگوریتم تکاملی کوانتوم و عملگرهای استفاده شده در آن از یک طرف و رویه های اضافه شده به آن به گونه ای است که توازن بسیار خوبی را بین این دو رویکرد فراهم می آورد

اسلاید 17 :

الگوریتم های ژنتیک کوانتوم QGA
الگوریتم ژنتیک کوانتوم بر پایه دیدگاه محاسبات و کامپیوترهای کوانتومی شکل گرفته اند.
این الگوریتم ها در مقایسه با روش های دیگر بهینه سازی مانند روش های محاسباتی و روش های مبتنی بر گرادیان، مقاوم تر هستند.
بسیاری روش های دیگر، از مشکل گیر کردن در قله های محلی رنج می برند، حال آنکه الگوریتمهای تکاملی تا حدی با این مشکل کنار آمده اند.
در اینجا می کوشیم با کمک الگوریتم Simulated Annealing به عنوان یک جستجوی محلی، کارایی QGA را بهبود بخشیم.(SA-QGA)

اسلاید 18 :

الگوریتم های ژنتیک کوانتوم
از نمایش پاسخ ها در قالبی احتمالی استفاده می کنند

نمونه کوانتوم- کروموزوم

حالت این کوانتوم- کروموزوم

احتمال رویداد حالات
000>،001>،010>،011>،100>،101>،110>،111>
1/16 3/16 1/16 3/16 1/16 3/16 1/16 3/16

اسلاید 19 :

روال یک الگوریتم ژنتیک کوانتومی
i. مقداردهی اولیه
ii. ایجاد مجموعه کروموزوم های دودویی
iii. کروموزوم های دودویی بدست آمده از مرحله دوم توسط تابع برازندگی ارزیابی می شوند
iv. بهترین جواب یافته شده ذخیره می شود
v. تا ارضای شرط خاتمه، الگوریتم اجرا شود
vi. جواب های دودوییP(t) با مشاهده حالت­هایQ(t-1) ایجاد می شوند
vii. ارزیابی P(t)
viii. به روزرسانی کوانتوم بیت ها
ix. بهترین جواب یافته شده را در b ذخیره می کنیم.

اسلاید 20 :

به کارگیری الگوریتم Simulated Annealing در الگوریتم های ژنتیک کوانتومی
xvi. یک جستجویی محلی Simulated Annealing روی P(t) انجام می گیرد