الگوریتم دویچ

الگوریتم دویچ (به انگلیسی: Deutsch's Algorithm) اولین الگوریتم کوانتومی است که سریعتر از یک الگوریتم کلاسیک کار می‌کند. دیوید دویچ در سال ۱۹۸۵ این الگوریتم را پیشنهاد داد. این الگوریتم کاربردی در دنیای واقعی ندارد ولی اولین مثالی بود که نشان داد الگوریتم‌های کوانتومی وجود دارند که سریعتر از الگوریتم‌های کلاسیک هستند. در این مسئله توابعی با یک متغیر بررسی می‌شوند. ورودی و خروجی می‌توانند مقادیر صفر یا یک باشند؛ بنابراین چهار نوع تابع می‌تواند در این الگوریتم تعریف شود: الگو:چپ‌چین $f:\{0,1\}\to \{0,1\}$

• f(0) = 0 & f(1) = 0
• f(0) = 0 & f(1) = 1
• f(0) = 1 & f(1) = 0
• f(0) = 1 & f(1) = 1

توابع اول و چهارم از لیست بالا یک خروجی برای همه ورودی‌ها دارند و تابع ثابت خوانده می‌شوند. توابع دوم و سوم از لیست بالا تابع متوازن خوانده می‌شوند زیرا خروجی برای نیمی از وردی‌ها صفر و برای نیمی دیگر یک است. سؤالی که در الگوریتم دویچ مطرح می‌شود این است که یک تابع چند بار باید ارزیابی شود تا بفهمیم ثابت است یا متوازن؟

تحلیل کلاسیک به این صورت است که اگر ورودی صفر باشد و خروجی هم صفر باشد نمی‌دانیم تابع به شکل اول یا دوم از لیست بالا است و باید یک ارزیابی دیگر انجام دهیم تا متوجه شویم خروجی برای یک چه عددی است و تابع در نهایت ثابت است یا متوازن. در مورد ورودی یک به همین ترتیب دوبار ارزیابی تابع لازم است. در حالی که در تحلیل کوانتومی با یک بار ارزیابی تابع می‌توانیم تشخیص دهیم که تابع ثابت است یا متوازن. دویچ و جوژا در سال ۱۹۹۲ شکل کلی تری از این الگوریتم را پیشنهاد دادند که به نام الگوریتم دویچ-جوژا شناخته می‌شود.

الگوریتم دویچ-جوژا

الگوریتم دویچ-جوژا (به انگلیسی: Deutsch–Jozsa algorithm) شکل تعمیم یافته الگوریتم دویچ است که در سال ۱۹۹۲ به وسیله دیوید دویچ و ریچارد جوژا پیشنهاد شد. در الگوریتم دویچ یک تابع تک متغیره بررسی می‌شد و هدف این بود که ببینیم این تابع ثابت است یا متوازن. در الگوریتم دویچ-جوژا با توابع n متغیره سروکار داریم که ورودی و خروجی‌های ان مقادیر صفر و یک است. الگو:چپ‌چین $f:\{0,1{\}}^n\to \{0,1\}$ الگو:پایان چپ‌چین در تحلیل کلاسیک برای $n$ متغیر $2^n$ ورودی وجود دارد. در بهترین حالت می‌توان نوع تابع (ثابت یا متوازن) را با دو پرسش به دست آورد (در حالتی که خروجی‌ها برابر نباشند تابع قطعاً ثابت نخواهد بود) و در بدترین حالت نیاز به مطرح کردن $2^{n-1}+1$ سؤال خواهیم داشت یعنی تعداد سؤال‌ها با افزایش ورودی‌ها به صورت نمایی افزایش می‌یابد. در حالی که در تحلیل کوانتومی با یک سؤال می‌توانیم دریابیم که تابع ثابت است یا متوازن.

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

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