optimal mohasebat kountomi

صفحه 1:
کاربرد محاسبات کوانتومي در حل مسائل بهینه سازي 

صفحه 2:
تسس در 0 * مسائل بهینه سازي ** محاسبات کوانتومي | ** کاربرد محاسبات کوانتومي در حل مسائل بهینه سازي 

صفحه 3:
مساتل بهینه سازي * مقدمه ** نمونه هايي از مسائل بهینه سازي 

صفحه 4:
مسائل بهینه سازي امقدمه در علوم رياضي و کامپیوتر . مساله بهینه سازي . مساله یافتن بهترین راه حسل از میسان تمسامي راه ممکن مي باشد. در حقیقت يك مساله بهینه سسازي مانضد 0 یسك چهسار تسايي بمصورت (,1,۸,۳) مي باشد که در آن : 7 مجموعه اي از نمونه ها. 7 اگر « نمونه اي در 1 باشد. (:)8 مجموعه راه حلهاي ممکن براي «است. 7 اگر « يك نمونه و مر يك راه حل ممگن براي « باشد. (میس که معمولا عددي مثبت اسست, معیار سنجش مرمي باشد. > و تابع هدف مي باشد که »+ يا هه مي باشد. هدف یافتن يك راه حل بهینه مانند مربراي برخي نمونه ها مي باشد بطوریکه: AX Y) = Fx, (| ۳ ۶9( « @.0eeke Onna onl Opmemnain, (2002) ‏وی‎ 1300 ۵۵6660۵۵6 

صفحه 5:
کلاس <) شامل آن دسته از مسائلي است که در يك زمان چند جمله اي قابل حل هستند مسائلي که مي توانند در زمان (0)09 حل شوند كه در آن > بسك عسددثابت و «انسدازه ورودي مساله مي باشد.) کلاس 1 شسامل آن دسته از مسائلي اسست كه در يسك زمسان چنسد جملسه اي, تصدیق پذپر(ط(سه هستند( ممکن است خود مساله در يكث زمان چند جمله اي قابل حل نباشد. اما اگر يك ‎oly‏ حل براي آن ارائه شود. مي توان در يك زمان چندجمله اي صحت آن راه حل را مشخص نمود.) عمده مسائل بهينه سازي. در كلاس 0002 قرار مي گیرند چرا که حل مساله در يك زمان چند جمله اي قابل انجام نمي باشد. ولي مي نوان صحت يك راه حل ارائه شده را در بسكت زمسان چندجماسه اي بررسي نمود. ‎ame‏ 0۷۲ (0000) سا سمل وا مک سس :مس و66 ‎9 ‎ 

صفحه 6:
کاربرد محاسبات کوانتومي در حل مسانل هينه سازي مسائل بهینه سازي| نمونه هايي از مسائل ‎(DP) gles Ainge‏ أن مساله فروشنده دوره گرد تعیین مسيري با حداقل وزن کل روي یالها بطوریکه از هر راس فقط یکبار عبور کند. لأ مساله کوله پشتي صفر و يك تعیین حداکثر ارزش کلي که از قراردادن اشیاء در يك کوله پشتي به دسست مي آیسد. با اين فرض که هر شی داراي وزن و ارزش مشخص بوده. کوله پشتي تحمل حداکثر وزن 0 را داشته پاشد. ‎I‏ مساله رنگ آميزي گراف ‏تعیین حداقل تعداد رنگهاي مورد نماز براي رنگ آمپزي گرافي که در آن هیچ دو راس مجاوري 0 ‏سر 01۳ (0000) سکیا الماک مق 6 سس , بسحا 0 , سوق 8 9 ‎ 

صفحه 7:
بهینه سازي محاسیات کوانتومي * مقدمه ** تاربخچه محاسبات کوانتومي * مفاهیم اولیه محاسبات کوانتومي ** بيجيدكي محاسباتي الكوريتمهاي كلاسيك در برابر الكوربتمهاي كوانتومي *** كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي ** برخي از ابزارهاي شبيه سازي محاسبات كوانتومي 

صفحه 8:
فا کوانتومي در حل مسائل بمینه سازي محاسبات کوانتومي | مقدمه Electrons per device 2004 2008 2012 16 0 Miniaturization of computer technology as a function of time تمایل به کوچکتر شدن (مينياتوري شدن) منجر به استفاده از مقياسهاي کوانتومي شده است. در این مقیاسها قادر به استفاده از پدیده هاي کوانتومي خواهیم بود. 

صفحه 9:
کاربرد محاسبات کوانتومي در حل مسائل بهمینه سازي محاسیات كوانتومي | تاريخججه ‎quoctua systews‏ اه مسق : (98) م۲ -(00) هط ‎@ewcPP (OC) — Deusck (OS) : ATO‏ اه ‎Orutsck (89) — Yur (O92) : G‏ دم هه 0۵ : ‎®rccet (OO)‏ ‎ersten — Ouziru (OQ) : Q rowplenity‏ وه ‎boyd (9) : GQ veltar‏ ‎(OP) : @antorizativa ood disorete oypritha‏ باق ‎Grover (99) : GQ seach‏ ‎Wek (CODS) : Pets equation‏ ‏یهت 9 ‎ 

صفحه 10:
کاربره محاسبات کوانتومی در حل مسائل بیسته سازی محاسبات کوانتومي | مفاهیم اولیه يك رایانه کوانتومي, وسیله اي محاسباتي است که مستقیما از پدیده هاي فيزيك کوانتوم اسستفاده مي نماید. تفاوت رایانه هاي کوانتومي با رایانه هساي کلاسسيك آنسسنکه رابانسه هساي کوانتسومي از ويژگيهاي کوانتومي براي ذخیره داده ها و اعمال روي آنها استفاده مي کنند. يك رابانه کلاسپك داراي حافظه اي است که شامل تعدادي بیث مي باشد. هر بيت مي تواند 1 يا 0 را نمایش دهد. در این نوع رایانه 2 بیت مي تواند در هر لحظه فقط يکي از چهار حسالت 1,1001,00ارا نمایش دهد. يك رایانه كواندومي داراي حافظه اي است که شامل تعدادي #طج مي باشد. هر #طنج مي تواند 0 با 1 یا هر ابرمکان (0ح) ديگري را نمایش دهد. در این نوع رایانه 2 #طب مي تواند در هسر لحظه تمام چهار حالت 11,10,01,00 را نمایش دهد. ‎qubt ch,‏ 39 حقیقت نشاندهنده يك حالت مي باشد که این حالت بصورت بردار زیر نشان داده می شود: ‏(۰۱+(0م» = ‎lw)‏ ‏بطوریکه شرط در آن 1< و + مه برقرار است. ‎wo Qrtrly ok rt ia: acca ha aig, nn ae Chaser nnn, Creme oP Ono ‎aeRO DUNS ‏ال‎ 30-000 ‎ ‎ 

صفحه 11:
فا محاسیات کوانتومي | مفاهیم اوليه. ee QUANTUM bp ‏ید‎ se) +a تسس در 0 Zero and One حالتهايي که يك #طج نشان مي دهد را مي توان به عنوان اسبين ها فوتونهاي قطبي شده بسا سطوح انسرژي اتمه تعبیر تمود. «a Qrtrly ok rt ia: acca ha aig, nn ae Chaser nnn, Creme oP Ono aeRO DUDE ۵ 90۵000 

صفحه 12:
کاربرد محاسبات کوانتومي در حل مسانل هينه سازي محاسبات كوانتومي / مفاهيم اوليه... ‎Ib‏ ‏7 سور ‎Cowpuciond buts — {|()).|1)} 7 ١‏ ‎One: |!) = 0/0) 43/1) asec Cl‏ | = 3 Po) = lal? ۳ Pry =|8P ‎lal? + (8/2 =1‏ >= [عجهترسه ‎(covsirutct) ‎ ‎ ‎© Orne her rr ear ‏مها‎ rot ia: acca aha aig, nn ae Chaser nnn, Creme oP Ono aeRO DUDE ۵ 90۵000 ‎ ‎ ‎ ‎ 

صفحه 13:
محاسبات كوانتومي / مفاهيم اوليه. خروجي #طدج ها توسط معادله شرودینگر تعیین مي گردد. 0 م11 يك اپراتور هرميتي. و ج ثابت جهاني پلانك مي باشد. et | (t)) = T(E, to) (to) ‏خواهيم داشت:‎ Ultsto) & exp ۳ ‘Dak |e(t)) U(t, to) |vo(to)) سم روسهت تفن (/600) مت مس ناملا 9 ‎Aha, LiPo, © Drees‏ © 9 

صفحه 14:
500 محاسبات کوانتومي | گيتهاي كوانتومي يك کیت كوانتومي. عملگري است که روي يك يك یا دو #طج عمسل مي کنسد. گيتهساي كوانتسومي. بلوكهاي سازنده عدارات كولتومي موب مي شوند. أبن كينها غحوما توسط بك تريس تم ای داده مي شوند. 0 يعني اثر خروجي #طج ها و كيتهاي عمل كننده به آنهسا مشسخص باشند. مي توان ورودي #طدج ها را معين كرد. هاي خودي یر ‎Oe ee DOR‏ سوت تور معکوسپذیر مي باشد. تسس در 0 

صفحه 15:
این کیت روي يك #طچ عمل کرده. معادل یت 00/۳ مي باشد. (0| به (1| (1 به (0 مي نكارد. ابن كيت بصورت ماتريس زير نشان داده مي شود. 1 ‎١‏ ۳ 0 1 اما - مه ۲ ]سس ها اين كيت روي يك #طدي عمل كرده؛ حالت مبناي ‏ (0)| به 013-117[ جلت مينني (1|رابه ‎ze‏ (11- (10 مي برد این گیت بصورت ماتریس زير نشان داده مي شود. دو كيت 3-ه-دلمرا1 كه بطور متوالي روي يك #طدب عمل كنند» 1 ‎a=)‏ ‏حالت اوليه آن #طدج را بدست مي دهند. - ۷/211 ی ‎SE ey a‏ 

صفحه 16:
محاسبات كوانتومي | كيتهاي كوانتومي.. کت میت این گیت محتواي دو »لب را با هم عوض مي کند و بصورت ماتریس زیر نشان داده مي شود. کیت 0000/0 با 201 ساموت اين كيت روي دو #ادج عمل نمودهء اگر اولین وتپ برابر . (1|د عمل 00416 را روي #طج دوم انجام مي دهد» در غیراینصورت سب دوم بدون تغییر باقي مي ماند. 1 0 0 0 0 1 0 0 CNOT = ‏و‎ 001 0 0 1 0 ‏:پسهجست مسق مان سس یله 0ك م6‎ Crom lar Ohplrae Chet Gist, (2008) OBO Creme 

صفحه 17:
محاسبات گوانتومي | پيچيدگي محاسباتي الگور ينمهاي کلاسيك در برابر الگورينمهاي کوانتومي بيك الكوريتم كوانتومي. فراپندي گام به گام است که هر گام آن روي بك رابانسه کوانتصومي اچسرا مي شود. همه مسائلي که توسط يك رایانه کوانتومي قابل حل هستند توسط رایانه کلاسيك نیز قابمل حسل مي باشند. مسائلي که روي رایانه هاي کلاسيك. تصمیم ناپذیرند همچنان روي رایانه هاي كوانتومي نسیز تصمیم ناپذیر مي باشند. اهمیت الگوريتمهاي كوانتومي در آن است که در حل برخي مسائل. نسبت به الكو ربتمياي كلاسسيك سریع تر مي باشند. ae ‏و6‎ Orn phe uk een (C900) “arto hurd oP Thaortd Phe 

صفحه 18:
محاسیات کوانتومي | پيچيدگي محاسباتي الگوريتميهاي کلاسيك در برابر انگوريتمهاي کوانتومي... الگوریتم ات تابع نامعلوم (0,0) «- (0,0) : ۶ داده شده است (يك بیت را به يك بیت مي نگارد.) مي خواهیم ببینم که ۴ ثابت است ( (۳)0(2)0 ) با ‎POF) Jobs‏ = تعداد دفعاتي که باید ۴ بررسي شود به روش كلاسيك 2. و به روش کوانتومي 1 مي باشد. الگوریتم ‎Derieck=loe ze‏ تابع نامحلوم (0,0) + "(0,0) : ذا داده شده است (يك بيت را به يك بيت مي فكارد.) مي خواهیم ببینم که ۶ ثابت است یا متعادل (بسراي نيمي از ورودیهسا. 1 و بسراي نيمي دیگسر از ورودیها. 0( تعداد دفعاني که باید ‏ بررسي شود به روش کلاسيك +60۳۹ و به روش كوانتومي 1 مي باشد. سيج رصسمه 0 فسض0 [60002) بسعجي0 ‎Chen‏ فسها 02 - مسج0 0 سسسجاظ انا 0 6 5 

صفحه 19:
کاربرد محاسبات کوانتومي در حل مسانل هينه سازي محاسبات کوانتومي | پيچيدگي محاسباتي الگوريتمهاي کلاسيك در برابر الگوريتمهاي کوانتومي.. الگوریتم تا تابع نامعلوم 0,0(۳) ج- 00,0(۳) ‎ :‏ داده شده است . رشته اي مانند ,د.. دروت« وجود دارد كه ‎SITs SIPPY)‏ بکد یا ۶ )اک تعداد دفعاتي که باید ۴ بررسي شود تا «معین شود. به روش کلاسيكت. +0۳ و به روش کوانتومي, مي باشد. الگوریتم عمط تابعنامعلوم (0,0) +- "(0,0) : داده شده است بطوربکه براي يسك رشسته مطلسوب مانتسد . < 20( و براي هر رشته دیگر مانند ۳0( « > تعداد دفعاتي که باید ۴ بررسي شود تا « یافت شود. بسه روش كلاسسيك "2 و بسه روش کوانتسومي ©" مي باشد. سيج رصسمه 0 فسض0 [60002) بسعجي0 ‎Ghent‏ فسها 92 ‎Aha, LiPo, © Drees‏ © 6 

صفحه 20:
کاربره محاسبات کوانتومی در حل مسائل بیسته سازی محاسبات کوانتومي | پيچيدگي محاسباتي الگوريتمهاي کلاسيك در برابر الگوريتمهاي کوانتومي.. ا اين الكوريتم براي تجزيه اعداد به عاملهاي اول. مورد استفاده قرار مي كيرد كه اين امر در دو مرحله انجام مي پذیرد: مرحله1- تهدیل مساله تجزیه به مساله یافتن رتبه (-4طج) که بصورت کلاسيك انجام مي شود. مرحله2- الگوربتمي گوانتومي براي حل مساله یافتن رتبه (طسط) بصورت زپر: يك عدد صحیح » و يك تابع > «- 2 ‎ :‏ داده شده است بطوریکه تناوبي مانند که وجود دارد کسه پسراي همسه »و مرها (ب2() اکسر و تنهسا اگسر مر متعلسق بسه مجموعسه 26۰ بره...] باشد. هدف یافتن هاست. مرتبه زماني بافتن عاملهاي اول يك عدد به روش گلاسبلت. ‎day 249 wera)‏ گوانتومي ( ۳ مي باشد. eo Oa! Oodor— Goer Orapreoy btn, (DOS) he Dhy & re 

صفحه 21:
کاربرد محاسبات کوانتومي در حل مسانل هينه سازي معاسبات گوانتومي | پيچيدگي محاسباتي الگور يتم‌هاي گلاسيك در برابر الگوريتعهاي کوانتوهي... ‎errs‏ الگوریتمها ‎Orutsch 9 0‏ ‎QOeutsck-dosza 5+0 0‏ ‎Givod ent a‏ ‎Grover oe en‏ ما ‎Chor ems?)‏ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 22:
کاربرد محاسیات کوانتومي در حل مسائل بهینه سازي قابليتهاي محاسبات کوانتومي سیب شده است که در تکنيكهاي حل مسائل بهینسه سسازي, نظسیر موارد زیر از آنها استفاده شود. ‎Oeceir Dhprikcos |‏ و6 ‎al Onley 1‏ موس ‎Qvedue Pate Owarn 1 ‏تا وه سسه ‏آنچه قصد بررسي و انجام آن داریم. بكارگيري محاسبات کوانتومي براي حل يكي از مسائل بهینه سازي نظیر 1808 يا “0809© . به منظور يافتن راه حلي با مرتبه زماني بهتر براي مساله مورد نظر مي باشد. صحت راه حل ارائه شده. با شبيه سازيهاي انجام شده مورد بررسي قرار خواهد كرفت. ‎ ‎ ‎ee ‎ 

صفحه 23:
کاربره محاسبات کوانتومی در حل مسائل بیسته سازی کاربرد محاسبات گوانتومي در حل مسائل بهینه سازي OB : Crodasd oediay ‏-كاهش انرزي -* تغيبر يذيرفته مي شود.‎ ‏تغییر در پيكربندي سبپ‎ -افزیش انزي بهمیزان ۵0 ‎et‏ احتعال جع ۸00 (77-پذپرفته مي‌شود. اين فرايند به دفعات تكرار مي شود نا زمانيكه تعادل ترمود يناميك حاصل شود. ‎OO cy jo‏ قابليت انعطاف آن با نوجه به تکامل مساله و سادگي پیاده سازي ايراد 09 . بالا بودن زمان انجام محاسبات (پیاده سازي موازي پیشنهاد مي گردد) ‏م0 ‎ 

صفحه 24:
کاربرد محاسبات کوانتومي در حل مسانل هينه سازي کاربرد محاسبات گوانتومي در حل مسائل بهینه سازي در حل مساله ‎TOP‏ به روش کوانتومي . باید روي دو موضوع کار شود: 1نحوه نمایش تورها بصورت حالتهاي يك سیستم کوانتومي 2-تعيين عملگر مناسب. بطوريكه با اعمال اين عملكر روي تورها . تور بهينه بدست آید. 00 رم 7 11 W(t) = Ut, to) ۵) = Ale) هو 

صفحه 25:
کاربره محاسبات کوانتومی در حل مسائل بیسته سازی برخي از ابزارهاي شبیه سازي محاسبات کوانتومي ججیان ل لاخ :۵2 ( وولو بووین قوب و ربمم 6068 QGOOG (Gute Gur Gul Dew ewe ‏(جلیظ)‎ ‎hap /Ikexopohire extulopevior hepa bicol Ohor's Okertie Ororkava (etonkeor oP qracker Ghor's ckertivo) ‏ایام هجو مد مها‎ دول 2 مه صمت ومتخدصيب صف صادا) ا کم سس قم |صمجيروام- ادكج. صاخ لجا كيج بنممى]|/ :مقا امام سنوی مب مومس ) عم اسداس لسو ‎ip iw. padre EPP‏ ‎ean porters‏ مه ‎ 

صفحه 26:
کاربرد محاسبات کوانتومي در حل مسانل هينه سازي .. ‏برخي از ابزارهاي شبیه سازي محاسبات کوانتومي‎ ‏لد‎ Odewure Queue Turtey Oatiar Orouktor (bolt b vowinwt, rus, vad research quackeo Tar woh) hip: ‏/صماع 0 اجمجدوخام مجه مج خا رممسجا‎ 0 00| (دصشجصمه «سفديب وما سوا «يوج امم دجقدح اه (1) أن 6 اط ما قبت سوج اليه دوه تن ( وت مج مت مها لوا وا بجسامی) عامی 660/۲ موم ماه الاو موه لاه رها او ها - حصنت سحن ‎Quackeo “IPoradion cdviatras) hi!‏ ۳ نما 09۲۷۵۵ م) ‎Qhb‏ ‏اما طواطاو امس 660 ‏سمسق)‎ Ovwputey Protow Por Oukb) ۱ ‏|وسلججات- لحك جه ءوس جامحام سدم //:ج‎ ‎ean porters‏ مه ‎ 

صفحه 27:
5 تسس در 0 انيد از نوجه شما مه 

كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي 1 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي مسائل بهينه سازي محاسبات كوانتومي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي 2 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي مسائل بهينه سازي مقدمه نمونه هايي از مسائل بهينه سازي 3 مسائل بهينه سازي/مقدمه در علوم رياضي و كامپيوتر ،مساله بهينه سازي ،مساله يافتن بهترين راه ح,,ل از مي,,ان تم,,امي راه حلهاي ممكن مي باشد .در حقيقت يك مساله بهينه س,,ازي مانن,,د Aي,,ك چه,,ار ت,,ايي بص,,ورت ( )I,f,m,gمي باشد كه در آن : I مجموعه اي از نمونه ها. اگر xنمونه اي در Iباشد f(x) ،مجموعه راه حلهاي ممكن براي xاست. اگر xيك نمونه و yيك راه حل ممكن براي xباشد m(x,y) ،كه معموال عددي مثبت اس,,ت، معيار سنجش yمي باشد. g تابع هدف مي باشد كه minيا maxمي باشد. هدف يافتن يك راه حل بهينه مانند yبراي برخي نمونه ها مي باشد بطوريكه: })m(x, y)  g{m(x, y') | y' f (x ‏G.Ausiello -Complexity and Approximation , (2003) Springer,ISBN 9783540654315 4 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي مسائل بهينه سازي /مسائل NP كالس Pشامل آن دسته از مسائلي است كه در يك زمان چند جمله اي قابل حل هستند (.مس,,ائلي كه مي توانند در زمان ) O(nkحل شوند كه در آن kي,,ك ع,,ددثابت و nان,,دازه ورودي مس,,اله مي باشد). كالس NPش,,امل آن دس,,ته از مس,,ائلي اس,,ت ك,,ه در ي,,ك زم,,ان چن,,د جمل,,ه اي ،تص,,ديق پذير( )verifiableهستند (.ممكن است خود مساله در يك زمان چند جمله اي قابل حل نباش,,د ،ام,ا اگر يك راه حل براي آن ارائه شود ،مي توان در يك زمان چندجمله اي صحت آن راه حل را مشخص نمود). عمده مسائل بهينه سازي ،در كالس NPقرار مي گيرند چرا كه حل مساله در يك زمان چند جمل,,ه اي قابل انجام نمي باشد ،ولي مي توان صحت يك راه حل ارائه شده را در ي,,ك زم,,ان چندجمل,,ه اي بررسي نمود. ‏T.Corman , C.Leiserson , R.Rivest , C.Stein –Introduction to Algorithms , (2002) MIT Press 5 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي مسائل بهينه سازي /نمونه هايي از مسائل بهينه سازي ()NP مساله فروشنده دوره گرد تعيين مسيري با حداقل وزن كل روي يالها بطوريكه از هر راس فقط يكبار عبور كند. مساله كوله پشتي صفر و يك تعيين حداكثر ارزش كلي كه از قراردادن اشياء در يك كوله پشتي به دس,,ت مي آي,,د ،ب,,ا اين فرض كه هر شئ داراي وزن و ارزش مشخص بوده ،كوله پشتي تحمل حداكثر وزن Wرا داشته باشد. مساله رنگ آميزي گراف تعيين حداقل تعداد رنگهاي مورد نياز براي رنگ آميزي گرافي كه در آن هيچ دو راس مجاوري همرنگ نباشند. ...  ‏T.Corman , C.Leiserson , R.Rivest , C.Stein –Introduction to Algorithms , (2002) MIT Press 6 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي مقدمه تاريخچه محاسبات كوانتومي مفاهيم اوليه محاسبات كوانتومي پيچيدگي محاسباتي الگوريتمهاي كالسيك در برابر الگوريتمهاي كوانتومي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي برخي از ابزارهاي شبيه سازي محاسبات كوانتومي 7 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /مقدمه تمايل به كوچكتر شدن (مينياتوري شدن) منجر به استفاده از مقياسهاي كوانتومي شده است .در اين مقياسها قادر به استفاده از پديده هاي كوانتومي خواهيم بود. 8 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي تاريخچه/ محاسبات كوانتومي Manin (80)- Feynman (82) : Simulation of quantum systems Benioff (82) – Deutsch (85) : QTM Deutsch (89) – Yao (93) : Q circuit Bennett (93) : Q teleportation Bernstein – Vazirani (93) : Q complexity Loyd (93) : Q cellular automata Shor (94) : Factorization and discrete algorithm Grover (96) : Q search Hallgren (2002) : Pell’s equation 9 www.wikipedia.org كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /مفاهيم اوليه يك رايانه كوانتومي ،وسيله اي محاسباتي است كه مستقيما از پديده هاي فيزيك كوانتوم اس,,تفاده مي نمايد .تفاوت رايانه هاي كوانتومي با رايانه ه,,اي كالس,,يك آنس,,تكه رايان,,ه ه,,اي كوانت,,ومي از ويژگيهاي كوانتومي براي ذخيره داده ها و اعمال روي آنها استفاده مي كنند. يك رايانه كالسيك داراي حافظه اي است كه شامل تعدادي بيت مي باشد .هر بيت مي تواند 1يا 0را نمايش دهد .در اين نوع رايانه 2بيت مي تواند در هر لحظه فقط يكي از چهار ح,,الت 11,10,01,00را نمايش دهد. يك رايانه كوانتومي داراي حافظه اي است كه شامل تعدادي qubitمي باشد .هر qubitمي تواند 0يا 1 يا هر ابرمكان ( )superpositionديگري را نمايش دهد .در اين نوع رايانه qubit 2مي تواند در ه,,ر لحظ,,ه تمام چهار حالت 11,10,01,00را نمايش دهد. يك qubitدر حقيقت نشاندهنده يك حالت مي باشد كه اين حالت بصورت بردار زير نشان داده مي شود: بطوريكه شرط در آن برقرار است. ‏Artur Ekert,Patrik Hayden,Hitoshi Inomori , Basic concepts in quantum computation, Center for Quantum Computation , University of Oxford, ‏quant-ph0011013 v1 2Nov2000 10 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /مفاهيم اوليه... حالتهايي كه يك qubitنشان مي دهد را مي توان به عنوان اسپين ها ،فوتونهاي قطبي شده ي,,ا س,,طوح ان,,رژي اتمها تعبير نمود. ‏Artur Ekert,Patrik Hayden,Hitoshi Inomori , Basic concepts in quantum computation, Center for Quantum Computation , University of Oxford, ‏quant-ph0011013 v1 2Nov2000 11 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي ... مفاهيم اوليه/ محاسبات كوانتومي Computational basis State: Measurement non-deterministic collapse Two possible outputs (constraint) 12 Artur Ekert,Patrik Hayden,Hitoshi Inomori , Basic concepts in quantum computation, Center for Quantum Computation , University of Oxford, quant-ph0011013 v1 2Nov2000 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /مفاهيم اوليه... خروجي qubitها توسط معادله شرودينگر تعيين مي گردد. معادله شرودينگر جواب معادله شرودينگر Hيك اپراتور هرميتي ،و hثابت جهاني پالنك مي باشد. خواهيم داشت: با فرض خروجي الگوريتم ورودي ‏P.Kaye, L.Laflamme, M.Mosca - An Introduction to Quantum Computing (2007) Oxford University Press 13 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /گيتهاي كوانتومي يك گيت كوانتومي ،عملگري است كه روي يك يك يا دو qubitعم,,ل مي كن,,د .گيته,,اي كوانت,,ومي، بلوكهاي سازنده مدارات كوانتومي محسوب مي شوند .اين گيتها عموما توسط يك م,,اتريس نم,,ايش داده مي شوند. گيتهاي كوانتومي ،معكوسپذيرند .يعني اگر خروجي qubitها و گيتهاي عمل كننده به آنه,,ا مش,,خص باشند ،مي توان ورودي qubitها را معين كرد. اغلب گيتهاي عمومي كالس,,يك نظ,,ير AND , OR , NAND , NOR , XORمعكوس,,پذير نيستند .گيت NOTمعكوسپذير مي باشد. ‏Mikio Nakahara, Tetsuo Ohmi- Quantum Computing : From Linear Algebra to Physical Realization , (2008) CRC Press ‏David McMahon – Quantum Computing Edplained, (2008) John Wiley & Sons 14 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /گيتهاي كوانتومي... گيت Pauli-Xيا NOTكوانتومي اين گيت روي يك qubitعمل كرده ،معادل گيت NOTمي باشد. را به و را به مي نگارد .اين گيت بصورت ماتريس زير نشان داده مي شود. گيت Hadamard اين گيت روي يك qubitعمل كرده ،حالت مبناي را به و حالت مبناي را به مي برد .اين گيت بصورت ماتريس زير نشان داده مي شود. دو گيت Hadamardكه بطور متوالي روي يك qubitعمل كنند، حالت اوليه آن qubitرا بدست مي دهند. ‏Mikio Nakahara, Tetsuo Ohmi- Quantum Computing : From Linear Algebra to Physical Realization , (2008) CRC Press ‏David McMahon – Quantum Computing Edplained, (2008) John Wiley & Sons 15 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /گيتهاي كوانتومي... گيت Swap اين گيت محتواي دو qubitرا با هم عوض مي كند و بصورت ماتريس زير نشان داده مي شود. گيت CNOTيا Controled NOT باشnnد عمnnل NOTرا روي qubitدوم اين گيت روي دو qubitعمnnل نمnnوده ،اگnnر اولين qubitبرابnnر انجام مي دهد ،در غيراينصورت qubitدوم بدون تغيير باقي مي ماند. ‏Mikio Nakahara, Tetsuo Ohmi- Quantum Computing : From Linear Algebra to Physical Realization , (2008) CRC Press ‏David McMahon – Quantum Computing Edplained, (2008) John Wiley & Sons 16 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /پيچيدگي محاسباتي الگوريتمهاي كالسيك در برابر الگوريتمهاي كوانتومي يك الگوريتم كوانتومي ،فرايندي گام به گام است كه هر گام آن روي يك رايان,,ه كوانت,,ومي اج,,را مي شود. همه مسائلي كه توسط يك رايانه كوانتومي قابل حل هستند توسط رايانه كالسيك نيز قاب,,ل ح,,ل مي باشند .مسائلي كه روي رايانه هاي كالسيك ،تصميم ناپذيرند همچنان روي رايانه هاي كوانتومي ن,,يز تصميم ناپذير مي باشند. اهميت الگوريتمهاي كوانتومي در آن است كه در حل برخي مسائل ،نسبت به الگوريتمهاي كالس,,يك سريع تر مي باشند. ‏R.Feynman- Simulating physics with computers (1982) International Journal of Theoritical Physics 17 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /پيچيدگي محاسباتي الگوريتمهاي كالسيك در برابر الگوريتمهاي كوانتومي... الگوريتم Deutsch تابع نامعلوم } f : {0,1} → {0,1داده شده است (يك بيت را به يك بيت مي نگارد). مي خواهيم ببينم كه fثابت است ( ) ) f(0)=f(1يا متعادل ( ). ) f(0)≠f(1 تعداد دفعاتي كه بايد fبررسي شود به روش كالسيك ،2و به روش كوانتومي 1مي باشد. الگوريتم Deutsch-Josza تابع نامعلوم } f : {0,1}n → {0,1داده شده است (يك بيت را به يك بيت مي نگارد). مي خواهيم ببينم كه fثابت است يا متعادل (ب,,راي نيمي از وروديه,,ا 1 ،و ب,,راي نيمي ديگ,,ر از وروديها.)0 ، تعداد دفعاتي كه بايد fبررسي شود به روش كالسيك ،2n-1+1و به روش كوانتومي 1مي باشد. ‏P.Kaye, L.Laflamme, M.Mosca - An Introduction to Quantum Computing (2007) Oxford University Press 18 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /پيچيدگي محاسباتي الگوريتمهاي كالسيك در برابر الگوريتمهاي كوانتومي... الگوريتم Simon تابع نامعلوم f : {0,1}n → {0,1}nداده شده است .رشته اي مانند s=s1s2..snوج,,ود دارد ك,,ه ) f(x)=f(yاگر و تنها اگر x=yيا .x=y XOR s تعداد دفعاتي كه بايد fبررسي شود تا sمعين شود ،به روش كالسيك 2n/3+1 ،و به روش كوانتومي، nمي باشد. الگوريتم Grover تابع نامعلوم } f : {0,1}n → {0,1داده شده است بطوريكه براي ي,,ك رش,,ته مطل,,وب مانن,,د s ، f(s)=1و براي هر رشته ديگر مانند .x ≠ s ، f(x)=0 تعداد دفعاتي كه بايد fبررسي شود تا sيافت شود ،ب,,ه روش كالس,,يك ،2nو ب,,ه روش كوانت,,ومي 2n/2مي باشد. ‏P.Kaye, L.Laflamme, M.Mosca - An Introduction to Quantum Computing (2007) Oxford University Press 19 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /پيچيدگي محاسباتي الگوريتمهاي كالسيك در برابر الگوريتمهاي كوانتومي... الگوريتم Shor اين الگوريتم براي تجزيه اعداد به عاملهاي اول ،مورد استفاده قرار مي گيرد كه اين امر در دو مرحله انجام مي پذيرد: مرحله -1تبديل مساله تجزيه به مساله يافتن رتبه ( )order-findingكه بصورت كالسيك انجام مي شود. مرحله -2الگوريتمي كوانتومي براي حل مساله يافتن رتبه ( )order-findingبصورت زير: يك عدد صحيح nو يك تابع f : z → zداده شده است بطوريكه تناوبي مانند a≤nوجود دارد ك,,ه ب,,راي هم,,ه xو yه,,ا f(x)=f(y) ،اگ,,ر و تنه,,ا اگ,,ر yمتعل,,ق ب,,ه مجموع,,ه { }…,x,x±a,x±2aباشد .هدف يافتن aاست. مرتبه زماني يافتن عاملهاي اول يك عدد به روش كالسيك exp(n1/3) ،وبه روش كوانتومي )n2log(n مي باشد. ‏David McMahon – Quantum Computing Edplained, (2008) John Wiley & Sons 20 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي محاسبات كوانتومي /پيچيدگي محاسباتي الگوريتمهاي كالسيك در برابر الگوريتمهاي كوانتومي... كوانتومي كالسيك الگوريتمها 1 2 ‏Deutsch 1 2n-1+1 ‏Deutsch-Josza ‏n 2n-1+1 ‏Simon 2n/2 2n ‏Grover ‏n2logn )exp(n1/3 ‏Shor --- 21 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي قابليتهاي محاسبات كوانتومي سبب شده است كه در تكنيكهاي حل مسائل بهين,,ه س,,ازي ،نظ,,ير موارد زير از آنها استفاده شود. ‏Quantum Genetic Algorithms  ‏Quantum Ant Colony  ‏Quantum Particle Swarm  ‏Quantum Annealing  ... آنچه قصد بررسي و انجام آن داريم ،بكارگيري محاسبات كوانتومي براي حل يكي از مسائل بهينه سازي نظير TSPيا ، 3SATبه منظور يافتن راه حلي با مرتبه زماني بهتر براي مساله مورد نظر مي باشد .صحت راه حل ارائه شده ،با شبيه سازيهاي انجام شده مورد بررسي قرار خواهد گرفت. 22 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي.. ‏SA : Simulated Annealing -كاهش انرژي ← تغيير پذيرفته مي شود. تغيير در پيكربندي سبب -افزايش انرژي به ميزان ΔE ← تغيير با احتمال -(T) ΔE exp/پذيرفته مي شود. اين فرايند به دفعات تكرار مي شود تا زمانيكه تعادل ترموديناميك حاصل شود. مزيت ، SAقابليت انعطاف آن با توجه به تكامل مساله و سادگي پياده سازي ايراد ، SAباال بودن زمان انجام محاسبات (پياده سازي موازي پيشنهاد مي گردد) 23 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي.. در حل مساله TSPبه روش كوانتومي ،بايد روي دو موضوع كار شود: -1نحوه نمايش تورها بصورت حالتهاي يك سيستم كوانتومي - 2تعيين عملگر مناسب ،بطوريكه با اعمال اين عملگر روي تورها ،تور بهينه بدست آيد. 24 كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي برخي از ابزارهاي شبيه سازي محاسبات كوانتومي  C/C++ EQCS (library for quantum computer simulation) http://home.snafu.de/pbelkner/eqcs/ QGAME (Quantum Gate And Measurement Emulator) http://hampshire.edu/lspector/qgame.html Shor's Algorithm Simulation (simulator of quantum Shor's algorithm) http://alumni.imsa.edu/~matth/quant/  JAVA JaQUZZI (interactive quantum computer simulator) http://www.eng.buffalo.edu/~phygons/jaQuzzi/ Squankum (interactive quantum computation applet) http://www.pha.jhu.edu/~jeffwass/squankum/ 25 http://www.quantiki.org كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي ... برخي از ابزارهاي شبيه سازي محاسبات كوانتومي  Mathematica Quantum Turing Machine Simulator (toolkit to construct, run, and research quantum Turing machines) http://library.wolfram.com/infocenter/Articles/3893/ QuCalc (Mathematica package for doing quantum computation) http://crypto.cs.mcgill.ca/QuCalc/  Matlab QCTools (toolbox to simulate ion trap quantum computers) http://physics.berkeley.edu/research/haeffner/teaching/exp-quant-info QLib (a MATLAB library for Quantum Information calculations) http://www.tau.ac.il/~ quantum/qlib/qlib.html QFC (Quantum Computing Functions for Matlab) http://www.robots.ox.ac.uk/~charles/ 26 http://www.quantiki.org كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي با تشكر از توجه شما 27