حل مسئله 3-SAT با استفاده از یک رویکرد پیاده روی تصادفی کلاسیک جذب کننده شبیه سازی شده کوانتومی
| عنوان | حل مسئله 3-SAT با استفاده از یک رویکرد پیاده روی تصادفی کلاسیک جذب کننده شبیه سازی شده کوانتومی |
|---|---|
| نویسنده | دمیرزن، آلپ |
| تاریخ انتشار: | 2023-01-23 T12:42: خز |
| نوع | سند |
| زبان | انگلیسی |
| دیجیتال | بله |
| نسخه خطی | خیر |
| کتابخانه: | دانشگاه اوزیغین |
| شماره ثبت | 317f44b9-0999-40f8-9fad-f2cc40c6152e |
| محل کتابخانه | گروه علوم کامپیوتر |
| تاریخ | 2023-01-23 T12:42: خز |
| متن نمونه | محاسبات کوانتومی رویکردهای جدیدی برای حل مسائل محاسباتی سخت ارائه می دهد. در این پایان نامه یک الگوریتم کوانتومی مبتنی بر شبیه سازی کوانتومی الگوریتم شونینگ برای حل مسئله 3-SAT ارائه می کنیم. ما ابتدا مفهوم راه رفتن تصادفی جاذب کلاسیک شبیهسازی شده کوانتومی بر روی یک ابر مکعب را معرفی میکنیم و این ایده را با استفاده از زنجیرههای مارکوف نشان میدهیم. سپس الگوریتم کوانتومی که بر اساس مفهوم مذکور برای حل مسئله 3-SAT ساخته شده است را شرح می دهیم. الگوریتم با ایجاد برهم نهی مساوی از همه انتساب ها به متغیرهایی که رئوس یک ابر مکعب را نشان می دهند شروع می شود. حالت بعدی با پرس و جو از اوراکل تعیین می شود که بررسی می کند آیا یک بند راضی است یا خیر. بر این اساس، یکی از متغیرهای یک عبارت ناراضی مانند الگوریتم شونینگ برگردانده می شود. الگوریتم به دست آمده راه حل را با احتمالی که معادل احتمال موفقیت مورد انتظار الگوریتم شونینگ است که در تمام حالت های اولیه ممکن شروع می شود، پیدا می کند. الگوریتم از تعداد خطی کیوبیت ها در تعداد متغیرها استفاده می کند به شرطی که بازنشانی امکان پذیر باشد و عملکرد آن از طریق چندین نمونه 3-SAT نشان داده شود. عملکرد آن با الگوریتم گروور مقایسه می شود و الگوریتم پیشنهادی در بیشتر موارد برای تعداد دروازه ها و عمق، از الگوریتم گروور بهتر عمل می کند. Bu tezde, 3-SAT problemini çözmek için Schöning'in algoritmasının kuantum simülasyonuna dayanan bir kuantum algoritması sunuyoruz. İlk olarak, bir hiperküp üzerinde kuantum simülasyonlu klasik soğurucu rastgele yürüyüş kavramını tanıtıyoruz ve bu fikri Markov zincirlerini kullanarak gösteriyoruz. Daha sonra 3-SAT problemini çözmek için bahsedilen konsept üzerine inşa edilen kuantum algoritmasını açıklıyoruz. الگوریتم، bir hiperküpün köşelerini temsil eden değişkenlere tum atamaların eşit süperpozisyonunu oluşturarak başlar. بیر سونراکی دوروم، بیر تومچنین کارشیلانیپ کارشیلانمادیقینی کنترل ایدن کهین سورگولانارک بیلیرلنیر. بونا گوره، بیر دویومسوز تومسدن گلن دغیشکنلردن بیری، شونینگین الگوریتماسیندا اولدوغو گیبی ترس چویریلیر. Ortaya çıkan algoritma, tüm olası başlangıç durumlarından başlayarak Schöning'in algoritmasının beklenen başarı olasılığına eşdeğer bir olasılıkla çözümü bulur. Algoritma، sıfırlamanın mümkun olması ve performansının birkaç 3-SAT örneği aracılığıyla gösterilmesi koşuluyla، değişken sayısında doğrusal sayıda kübit kullanır. Performansı Grover'ın algoritmasıyla karşılaştırılır ve önerilen algoritma, çoğu durumda kapı sayısı ve derinlik için Grover'ın algoritmasından daha iyi performans gösterir. |
