الگوریتم برنشتاین-وزیرانی
الگوریتم برنشتاین-وزیرانی (به انگلیسی: Bernstein-Vazirani Algorithm) یک الگوریتم کوانتومی است. اومش وزیرانی و دانشجویش ایتان برنشتاین کار دویچ و جوژا در الگوریتم دویچ-جوژا را ادامه دادند و در سال ۱۹۹۳ مقاله ای را منتشر کردند که در آن الگوریتم برنشتاین-وزیرانی را معرفی کردند که الگوریتمهای کلاسیک و کوانتومی را کاملاً از هم جدا میکرد حتی اگر خطاهای کوچک مجاز باشد. این نکته از این جهت مهم است که الگوریتم دویچ-جوژا برتری کوانتومی دترمینیستیک نسبت به الگوریتمهای کلاسیک داشت به این معنا که اگر خطاهای کوچکی در محاسبات وارد میشد هم نسخههایهای کلاسیک و هم نسخههای کوانتومی به بدترین حالت یعنی O(1) قدم نزدیک میشدند و مزیت کوانتومی از بین میرفت. در حالی که الگوریتم برنشتاین-وزیرانی حتی با وجود خطاهای جزئی الگوریتمهای کوانتومی را از الگوریتمهای کلاسیک متمایز میکند. مسئله مطرح شده در الگوریتم برنشتاین-وزیرانی روی کامپیوتر کلاسیک با زمان O(n) روی یک کامپیوتر کوانتومی با زمان O(1) حل میشود.
فرض کنیم تابع با ورودی داریم و ورودی و خروجیهای آن مقادیر صفر و یک است.
که در آن ضرب داخلی (ضرب نقطهای) بین و رشته است به طوری که
modulo 2, >.
در این مسئله هدف پیدا کردن رشته است.[۱]
جستارهای وابسته
[ویرایش]منابع
[ویرایش]- ↑ Hidary, Jack D. (2021). Quantum Computing: An Applied Approach. Cham: Springer International Publishing. p. 16-17,110. doi:10.1007/978-3-030-83274-2. ISBN 978-3-030-83273-5.