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

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

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

$f\colon \{0,1\}^{n}\rightarrow \{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$ است.^[۱]

جستارهای وابسته[ویرایش]

منابع[ویرایش]

↑ 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.

این یک مقالهٔ خرد ریاضیات است. می‌توانید با گسترش آن به ویکی‌پدیا کمک کنید.

[Hidary_2021_p.-1] 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.

[۱]