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

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

فرض کنیم تابع $f$ با $n$ ورودی داریم و ورودی و خروجی‌های آن مقادیر صفر و یک است. الگو:چپ‌چین $f:\{0,1{\}}^n\to \{0,1\}$ الگو:پایان چپ‌چین که در آن $f(x)$ ضرب داخلی (ضرب نقطه‌ای) بین $x$ و رشته $s$ است به طوری که الگو:چپ‌چین $s\in \{0,1{\}}^n$ modulo 2, $f(x)=x\cdot s=x_1{s}_1\oplus x_2{s}_2\oplus \cdots \oplus x_n{s}_n$>. الگو:پایان چپ‌چین در این مسئله هدف پیدا کردن رشته $s$ است.

جستارهای وابسته

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