الگوریتم سایمون
الگوریتم سایمون (به انگلیسی: Simon's algorithm) یک از الگوریتمهای کوانتومی است که برای حل مسئله سایمون پیشنهاد شد. این الگوریتم در سال ۱۹۹۴ به وسیله دنیل سایمون پیشنهاد شد. سایمون نشان داد که الگوریتم کوانتومی وی میتواند مسئله سایمون را به صورت نمایی سریعتر از الگوریتم کلاسیک حل کند. در واقع الگوریتم سایمون میتواند مسئله سایمون را با استفاده از تعداد خطی پرسش حل کند در حالی که الگوریتم کلاسیک نیاز به پرسشهایی با تعداد نمایی دارد.[۱]
فرض کنید تابعی داریم که ورودی آن رشتههای دودویی به طول و خروجی آن نیز رشتههای دودویی به طول است. این تابع یک ویژگی خاص دارد و ان این است که یک رشته دودویی وجود دارد به طوری که:
اگر و تنها اگر
نماد در این گزاره به معنای یای انحصاری (XOR) است. به طوری که
- 0 XOR 0 = 0
- 1 XOR 0 = 1
- 0 XOR 1 = 1
- 1 XOR 1 = 0
و در آن نمیتواند رشتهای با رقمهای کلا صفر باشد. هدف مسئله سایمون این است که این رشته را پیدا کنیم.
بنابراین
البته ما نه تابع را میدانیم و نه رشته . سؤال این است که تابع چند بار باید ارزیابی شود تا بتوانیم رشته را بیابیم؟ در تحلیل کلاسیک در بدترین حالت نیاز به مطرح کردن سؤال خواهیم داشت. در تحلیل کوانتومی برای محاسبه باید معادلات خطی مستقل را حل کنیم که الگوریتمهای مشخصی برای انجام آن وجود دارد.[۲]
جستارهای وابسته
ویرایشمنابع
ویرایش- ↑ Simon, Daniel R. (1997). "On the Power of Quantum Computation". SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). 26 (5): 1474–1483. doi:10.1137/s0097539796298637. ISSN 0097-5397.
- ↑ Bernhardt, C. (2019). Quantum Computing for Everyone. The MIT Press. MIT Press. p. 157-166. ISBN 978-0-262-03925-3. Retrieved 2023-05-12.