الگوریتم برنشتاین-وزیرانی

الگوریتم برنشتاین-وزیرانی  یک الگوریتم کوانتومی است. اومش وزیرانی و دانشجویش ایتان برنشتاین کار دویچ و جوژا در الگوریتم دویچ-جوژا را ادامه دادند و در سال ۱۹۹۳ مقاله ای را منتشر کردند که در آن الگوریتم برنشتاین-وزیرانی را معرفی کردند که الگوریتم‌های کلاسیک و کوانتومی را کاملاً از هم جدا می‌کرد حتی اگر خطاهای کوچک مجاز باشد. این نکته از این جهت مهم است که الگوریتم دویچ-جوژا برتری کوانتومی دترمینیستیک نسبت به الگوریتمهای کلاسیک داشت به این معنا که اگر خطاهای کوچکی در محاسبات وارد می‌شد هم نسخه‌های‌های کلاسیک و هم نسخه‌های کوانتومی به بدترین حالت یعنی O(1) قدم نزدیک می‌شدند و مزیت کوانتومی از بین می‌رفت. در حالی که الگوریتم برنشتاین-وزیرانی حتی با وجود خطاهای جزئی الگوریتم‌های کوانتومی را از الگوریتم‌های کلاسیک متمایز می‌کند. مسئله مطرح شده در الگوریتم برنشتاین-وزیرانی روی کامپیوتر کلاسیک با زمان O(n) روی یک کامپیوتر کوانتومی با زمان O(1) حل می‌شود.

فرض کنیم تابع   با   ورودی داریم و ورودی و خروجی‌های آن مقادیر صفر و یک است.

که در آن   ضرب داخلی (ضرب نقطه‌ای) بین  و رشته  است به طوری که

 modulo 2, >.

در این مسئله هدف پیدا کردن رشته  است.

جستارهای وابسته 
 الگوریتم کوانتومی
 اطلاعات کوانتومی
 نظریه پیچیدگی کوانتومی
 اومش وزیرانی

منابع 

الگوریتم‌های کوانتومی
علوم اطلاعات کوانتومی
نظریه پیچیدگی کوانتومی
نظریه پیچیدگی محاسباتی