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

الگوریتم های بکار رفته در محاسبات کوانتومی و دستاوردهای آن فهرست ‏مقدمه ‏الگوریتم های کوانتومی انواع الگوریتم های کوانتومی ‏معرفی چندین الگوریتم پایه ‏الگوریتم های تکاملی ‏الگوریتم ژنتیک کوانتومی ‏خالصه ‏منابع 2 مقدمه ‏هدف محاس+بات کوانت+ومی ی+افتن روش ه+ایی ب+رای ط+راحی مج+دد ادوات ش+ناخته ش+ده ی محاس+بات ( مانن+د گیت ه+ا و ترانزیس+تورها) ب+ه گون+ه ای اس+ت ک+ه بتوانن+د تحت اث+رات کوانت+ومی ،ک+ه در مح+دوده ی ابع+اد ن+انومتری و کوچک+تر بروز می کنند کار کنند. ورود ب+ه دنی+ای محاس+بات کوانت+ومی نیازمن+د دو پیش زمین+ه مهم اس+ت ،نخس+ت بای+د اص+ول اساس+ی و ب+رخی تع+ابیر مهم مکانی+ک کوانت+ومی را ب+ه ط+ور دقی+ق بررس+ی ک+رد س+پس مفه+وم اطالع+ات در فیزی+ک ن+یز ،چ+ه ب+ه ص+ورت کالس+یک و چه در معنای جدیدکوانتومی آن باید درک شود . ‏موارد مهم در محاس++بات کوانت++ومی :درهم ت++افتگی ،entanglement 3کی+وبیت ه+ا ،واهمدوس+یDecoherence الگوریتم های کوانتومی ‏هرگ+اه م+ا الگ+وریتم ه+ای کالس+یکی خودم+ان راب+ر روی ی+ک ک+امپیوتر کوانت+ومی مورداس+تفاده ق+راردهیم ،ب+ه س+ادگی محاس+بات را ب+ه طریق+ه مش+ابه ب+ا ی+ک ک+امپیوتر کالس+یک انجام و اجرا خواهدکرد. ‏به منظ+ور نش+ان دادن برت+ری آن و به+ره ب+رداری از پدی+ده ت+وازی کوانت+ومی م+ا نی+از داریم ت+ا الگ+وریتم ه+ا ی کوانت+ومی را پایه گذاری کنیم. 4 جعبه سیاه و توابع یک بیتی ‏جعبه سیاه Oracle هدف تعیین کامل تابع نیست ،بلکه یک خاصیت مشخص از تابع هم یافته شود کافی است. تابع ثابت :خروجی همواره ثابت ()f1,f4 تابع متوازن :خروجی به ازای نیمی از ورودی ها 0و نیمی دیگر 1 ()f2,f3 ‏انواع توابع تک بیتی ‏می خواهیم ببینیم با چند بار فراخوانی ،تابع fتعیین می گردد؟ با دو بار فراخوانی ‏یک بار با ورودی 0و یک بار با ورودی 1 5 توازی کوانتومی استفاده از توازی کوانتومی در الگوریتم های کوانتومی ‏اگر تابع fثابت باشد ‏اگر تابع fمتوازن باشد 6 انواع الگوریتم های کوانتومی الگوریتم کوانتومی برای مسئله دویچ ‏الگوریتم کوانتومی برای مسئله دویچ-جوزا ‏الگوریتم کوانتومی برای مسئله برنشتاین-وزیرانی ‏الگوریتم کوانتومی برای مسئله سیمن 7 الگوریتم کوانتومی برای مسئله دویچ ‏بردار حالت در مراحل مختلف: ‏اگر fتابع ثابت باشد اگر fتابع متوازن باشد ‏با یک فراخوانی مسئله حل می شود: ‏خروجی برای توابع ثابت 0و برای توابع متوازن 1 8 الگوریتم کوانتومی برای مسئله دویچ-جوزا مسئله دویچ جویزا تعمیمی از مسئله دویچ است از ما خواسته ثابت یا متوازن بودن مسئله را تعیین کنیم: ‏تعداد توابع ثابت 2تا ‏تعداد توابع متوازن ‏n-1 ‏در الگ+وریتم کالس+یک بای+د ب+ه تع+داد 1+ 2ب+ار ت+ابع fفراخ+وانی شود. ‏در الگ+وریتم کوانت+ومی تنه+ا ب+ا دو ب+ار فراخ+وانی ن+وع ت+ابع تع+یین می گردد. 9 الگوریتم کوانتومی برای مسئله دویچ-جوزا م+دار بک+ار رفت+ه در الگ+وریتم کوانت+ومی ب+رای مس+ئله دویچ- جوزا برای تابع ثابت nکیوبیت در حالت صفر و برای تابع متوازن nکیوبیت در هر حالتی غیر صفر قرار می گیرند فقط با یک بار فراخوانی ‏بردار حالت در مراحل مختلف 10 اگر fتابع ثابت اگر fتابع متوازن الگوریتم کوانتومی برای مسئله برنشتاین- وزیرانی ‏مس+ئله :ت+ابع fب+ه ص+ورت زی+ر و aی+ک ع+دد nبی+تی اس+ت .ب+ا چند بار فراخوانی aتعیین می گردد؟ فقط با یک بار فراخوانی 11 الگوریتم کوانتومی برای مسئله سیمن . . . ‏مسئله :تابع fبه صورت زیر می باشد ،با چند بار فراخوانی aتعیین می گردد؟ فقط با nبار فراخوانی 12 مهمترین الگوریتم های کوانتومی ‏الگ+وریتم ه+ای ارائ+ه ش+ده ،هیچ ک+دام کالس ح+ل مس+ئله را تغی+یر ن+داده اس+ت .یع+نی نتوانس+ته مس+ئله را از کالس نم+ایی به کالس چند جمله ای ببرد. ‏الگوریتم های مهم تغییر دهنده کالس حل مسئله: الگوریتم شور Shor’s Algorithm هدف این الگ+وریتم شکس+تن ی+ا تجزی+ه ی+ک ع+دد ب+زرگ ب+ه عام+ل ه+ای اول آن است ‏الگوریتم گراور Graver’s Algorithm 13 این الگوریتم می تواند عملیات مرتب کردن داده ها راازمیان الگوریتم های تکاملی در راستای بهبود عملکرد الگوریتم ،رویکردهای جدیدی به الگوریتم اضافه شده است که در یک نگاه کلی می توان آنها در قالب بهبود شناسایی و بهره برداری به عنوان دو رویکرد بسیار مهم در الگوریتم­های تکاملی تقسیم بندی کرد. ساختار الگوریتم تکاملی کوانتوم و عملگرهای استفاده شده در آن از یک طرف و رویه های اضافه شده به آن به گونه ای است که توازن بسیار خوبی را بین این دو رویکرد 14فراهم می آورد الگوریتم تکاملی کوانتوم بهبود یافته()IQEA الگوریتم کوانتوم را با استفاده از رویکردهای زیر بهبود داده می شود: .Iاستفاده از رویکرد اندازه گیری چندگانه در تبدیل حالت کوانتومی به باینری. .IIاستفاده از گیت چرخشی کوانتومی دیگری عالوه بر عملگر معمول که برای بروز رسانی مقادیر کیوبیتها در هر نسل بکار برده می شود. .IIIاستفاده از رویکرد کاهش حدود متغیرها بر اساس بهترین جوابهای بدست آمده در هر نسل. .IVورود افراد با مقادیر کوانتومی جدید ،طبق شرایط مساله 15 الگوریتم های تکاملی اصوًال روش های بهینه سازی و جستجوی تصادفی بر اساس اصول تکامل بیولوژیکی الگوریتم تکاملی کوانتوم بهبود یافته()IQEA در مقایسه با روش های بهینه سازی سنتی ،الگوریتم های تکاملی نیرومندتر و در عمل جامع نگرترند در هر مرحله از الگوریتم های تکاملی ،مجموعه جدیدی از جوابهای بروز رسانی شده وارد محدوده مشخصی از فضای جواب می شوند و بعد از اندازه گیری ها و محاسبات تابع برازندگی توسط عملگرهای متعدد،اعضای جدید برای نسل بعد را فراهم می کنند این روند به گونه ای طراحی می شود که افراد جمعیت در نسل جدید از مقادیر نسل جاری بدتر نباشند و حتی االمکان بهتر بوده و باعث هدایت اعضای جمعیت به سمت ناحیه جواب بهینه شوند ساختار الگوریتم تکاملی کوانتوم و عملگرهای استفاده شده در آن از یک طرف و رویه های اضافه شده به آن به گونه ای است که توازن بسیار خوبی را بین این دو رویکرد فراهم می آورد 16 الگوریتم های ژنتیک کوانتوم ‏QGA الگوریتم ژنتیک کوانتوم بر پایه دیدگاه محاسبات و کامپیوترهای کوانتومی شکل گرفته اند. این الگوریتم ها در مقایسه با روش های دیگر بهینه سازی مانند روش های محاسباتی و روش های مبتنی بر گرادیان، مقاوم تر هستند. بسیاری روش های دیگر ،از مشکل گیر کردن در قله های محلی رنج می برند ،حال آنکه الگوریتمهای تکاملی تا حدی با این مشکل کنار آمده اند. ‏در اینجا می کوشیم با کمک الگوریتم Simulated Annealingبه عنوان یک جستجوی محلی ،کارایی QGAرا بهبود بخشیم)SA-QGA(. 17 الگوریتم های ژنتیک کوانتوم از نمایش پاسخ ها در قالبی احتمالی استفاده می کنند نمونه کوانتوم -کروموزوم حالت این کوانتوم -کروموزوم احتمال رویداد حاالت >000>،001>،010>،011>،100>،101>،110>،111  1/16 3/16 1/16 3/16 1/16 3/16 1/16  3/16 18 روال یک الگوریتم ژنتیک کوانتومی مقداردهی .i دودویی کروموزوم .iii هایمجموعه ایجاد .ii اولیه دوم بدست آمده از مرحلههای کروموزوم برازندگی توسط تابع دودویی .ivبهترین جواب ارزیابی می شوند یافته شده ذخیره .vتا ارضای شرط می شود خاتمه ،الگوریتم اجرا شود .viجواب های دودویی) P(tبا مشاهده حالت­های) Q(t-1ایجاد شوند ارزیابی می .vii روزرسانی .viiiبه )P(t جواب ها کوانتوم بیت یافته .ixبهترین شده را در bذخیره می کنیم. 19 به کارگیری الگوریتم Simulated Annealing در الگوریتم های ژنتیک کوانتومی .xviیک جستجویی محلی Simulated Annealingروی ) P(tانجام می گیرد 20 Simulated Annealing 21 نتایج مقایسه روش پیشنهادی SA-QGAبا QGAدر مساله Trapبرای=20 ،NTtap نمودار بر حسب تعداد ارزیابی تابع رسم شده است. 22 مقایسه کارایی الگوریتم QGAبا الگوریتم SA-QGAدر مساله Trapبرای=40 ،NTtap نمودار بر حسب تعداد ارزیابی تابع رسم شده است خالصه الگوریتم های کوانتومی و انواع آن الگوریتم کوانتومی برای مسئله دویچ الگوریتم کوانتومی برای مسئله دویچ-جوزا الگوریتم کوانتومی برای مسئله برنشتاین-وزیرانی الگوریتم کوانتومی برای مسئله سیمن الگوریتم شور الگوریتم گراور الگوریتم های تکاملی الگوریتم ژنتیک کوانتومی روش+ی مبت+نی ب+ر جس+تجوی محلی Simulated Annealingرا ب+رای بهب+ود ک+ارایی م+ +.نت+ایج آ+زم+ایش+ی نش+ا+ن +م+ی +د+هن+د د +ر حا+لیک+ه ی + QGAار+ای+ه ک+ردی + م ه+ا + ا+لگ+وری+ت + ه +ک+ار +گی+ری +ر+وش +ه+ای ی ب +ه+ین+ه+ +س+ازی +می+ +با+ش+د +،ب+ + QGAا+ب+زا+ر +قدر+تمن+دی +ب+ر+ا + ج+س+تجو+ی مح+ل+ی +مانن+د Simulated Annealingم+و+جب اف+زا+یش ک+ار+ایی +این +ال+گوریت+م می ش+و+د +.در اینج+ا +تلفیق قاب+ل+یت ه+ا+ی ج+س+تج+وی م+حل+ی د+ر Simulated ک کو+ا+نت+وم م+وجب ب+اال Annealingب+ا +جس+تجوی عم+ومی در +الگ+و+ریتم ه+ا+ی ژنتی+ + رف+تن کارایی+می شود 23 24